15338

Изучение алгоритма поиска в глубину и реализация его на языке программирования С++

Лабораторная работа

Информатика, кибернетика и программирование

Лабораторная работа №3 по дисциплине Структуры и алгоритмы обработки данных Цель работы: Изучение алгоритма поиска в глубину и реализация его на языке программирования С. Задание на работу Реализовать алгоритм поиска в глубину. Оценить временн...

Русский

2013-06-13

150 KB

4 чел.

Лабораторная работа №3

по дисциплине

«Структуры и алгоритмы обработки данных»

Цель работы:

Изучение алгоритма поиска в глубину и реализация его на языке программирования С++.

Задание на работу

  1.  Реализовать алгоритм поиска в глубину.
    1.  Оценить временную сложность алгоритма.

Реализация программы на C++

#include "stdafx.h"

#include <iostream>//подключения библиотек

#include <fstream>

#include <iomanip>

#include <limits>

#include <assert.h>

#include <time.h>

using namespace std;

template<typename NODETYPE>//предварительное описание класса дерево

class Tree;

template<typename NODETYPE>//описание шаблонного класса узел дерева

class Treenode

{

friend class Tree<NODETYPE>;//дерево - друж. класс

public:

Treenode(const NODETYPE &);

NODETYPE getData() const;

private:

Treenode *leftPtr;

Treenode *rightPtr;

NODETYPE data;

};

//конструктор

template<class NODETYPE>

Treenode<NODETYPE>::Treenode(const NODETYPE& d)

{

data = d;

leftPtr = rightPtr = NULL;

}

//возврат значения из узла

template<typename NODETYPE>

NODETYPE Treenode<NODETYPE>::getData() const

{

return data;

}

template<typename NT>//описание шаблонного класса дерево

class Tree

{

struct helpStructure//вспомогательная структура, нужна в поиске узла дерева

{

 NT *ptr;

};

public :

Tree();//конструктор

~Tree();//деструктор

 void insertNode(const NT &);//вставка в дерево

 void inOrderTraversal() const;//последовательный обход дерева

NT *findNode(const NT &) const;//ищет узел в дереве равный параметру, возвращает указатель на него.

void clean();//удаление всех узлов дерева.

private :

Treenode<NT> *rootPtr;

void insertNodeHelper(Treenode<NT> **, const NT &);//вставка в дерево

void inOrderHelper(Treenode<NT> *) const;//последовательный обход дерева

void findNodeHelper(Treenode<NT> *, const NT &, helpStructure &) const;//ищет узел в дереве равный параметру, возвращает указатель на него.

void cleanHelper(Treenode<NT> *);//удаление всех узлов дерева.

};

template<typename NT>//конструктор

Tree<NT>::Tree()

{

rootPtr = NULL;

}

template<typename NT>//деструктор

Tree<NT>::~Tree()

{

clean();

}

template<typename NT>

void Tree<NT>::clean()//удаление всех узлов дерева.

{

cleanHelper(rootPtr);

delete rootPtr;

rootPtr = NULL;

}

template<typename NT>

void Tree<NT>::cleanHelper(Treenode<NT> *ptr)//удаление всех узлов дерева.

{

if(ptr != NULL)

{

 cleanHelper(ptr->leftPtr);

 cleanHelper(ptr->rightPtr);

 if(ptr->leftPtr)//удаление левого узла

  delete ptr->leftPtr;

 if(ptr->rightPtr)//удаление правого узла

  delete ptr->rightPtr;

}

}

template<typename NT>

NT *Tree<NT>::findNode(const NT &x) const//ищет узел в дереве равный параметру, возвращает указатель на него.

{

helpStructure hs;

hs.ptr = NULL;

findNodeHelper(rootPtr, x, hs);

return hs.ptr;

}

template<typename NT>

void Tree<NT>::findNodeHelper(Treenode<NT> *ptr, const NT &x, helpStructure &hs) const//ищет узел в дереве равный параметру, возвращает указатель на него.

{

if(ptr != NULL && hs.ptr == NULL)//если ещё не найден элемент

 {

 if(x == ptr->data)//если найден искомый узел дерева

  hs.ptr = &(ptr->data);

 findNodeHelper(ptr->leftPtr, x, hs);

 findNodeHelper(ptr->rightPtr, x, hs);

}

}

template<typename NT>

void Tree<NT>::insertNode(const NT &Evalue)//вставка элемента в дерево

{

insertNodeHelper(&rootPtr, Evalue);

}

template<typename NT>//вставка элемента в дерево

void Tree<NT>::insertNodeHelper(Treenode<NT> **ptr, const NT &value)

{

if(*ptr == NULL)//вставляем данные в этот узел

 {

 *ptr = new Treenode<NT>(value);

 assert(*ptr != NULL);

}

else

{

 if(value < (*ptr)->data)//переходим в узел слева

  insertNodeHelper(& ((*ptr)->leftPtr), value);

 else if(value > (*ptr)->data)//переходим в узел справа

  insertNodeHelper(& ((*ptr)->rightPtr), value);

 else

  cout << endl << "Значение " << value << " дублирует уже имеющееся значение!" << endl;//данные дублируются

}

}

template<typename NT>//последовательный обход дерева

void Tree<NT>::inOrderTraversal() const

{

inOrderHelper(rootPtr);

}

template<typename NT>//последовательный обход дерева

void Tree<NT>::inOrderHelper(Treenode<NT> *ptr) const

{

if(ptr != NULL)

{

 inOrderHelper(ptr->leftPtr);

 cout << ptr->data << ' ';

 inOrderHelper(ptr->rightPtr);

}

}

int main()

{

setlocale(LC_CTYPE,("Russian"));

srand(time(NULL));

 Tree<int> t;

cout << "Вставляем 20 случайных значений в дерево \n ";

 for(int x = 0; x < 20; x++)

{

 int i = rand() % 500;

 cout << i << ' ';

 t.insertNode(i);

}

cout << endl;

//cin.ignore(numeric_limits<streamsize>::max(), '\n');

 cout << endl << "Последовательный обход дерева " << endl;

t.inOrderTraversal();

 

cout << endl << endl << "Введите значение для поиска: ";

 int x;

cin >> x;

int *xPtr = t.findNode(x);

 if(xPtr)

 cout << "Значение " << x << " найдено и имеет адрес " << xPtr << '.' << endl;

else

 cout << "Значение " << x << " не найдено." << endl;

t.clean();//удаление всех узлов дерева

 cout << endl << endl;

system("PAUSE");

 return 0;

}

Скриншот с результатами выполнения программы

Вывод

Алгоритм  поиска  в  глубину  был изучен и реализован на языке программирования.


 

А также другие работы, которые могут Вас заинтересовать

41402. Базы данных. Нормализация данных 506.5 KB
  Код товара Наименование Цена Количество Стоимость 223 Мяч футбольный 25 3 75 338 Мяч баскетбольный 33 2 66 767 Мяч гандбольный 12 2 24 655 Мяч теннисный 10 10 100 Итого 265 нормальная форма атомарность Счет Дата № Покупателя Фамилия Имя Телефон Адрес Код товара Наименование Цена Количество Стоимость 222333 26. Свердлова 13 223 Мяч футбольный 25 3 75 222333 26. Свердлова 13 338 Мяч баскетбольный 33 2 66 222333 26. Свердлова 13 767 Мяч гандбольный 12 2 24 222333 26.
41404. Разработка программного обеспечения информационных систем 194.5 KB
  Основные причины успеха и провала проектов В отчете группы Стендиша 1994 указано три наиболее часто встречающихся ключевых фактора создающих проблемы в проектах. Некое свойство программного обеспечения необходимое пользователю для решения проблемы при достижении поставленной цели. Подход к управлению требованиями Область проблемы Как правило мы находимся во владениях пользователячужестранца. Таким образом наша задача состоит в том чтобы понять их проблемы в их предметной области и на их языке и построить системы удовлетворяющие их...
41405. Управление требованиями. Объектно-ориентированный анализ и проектирование 240 KB
  Вторую категорию составляют непрямые пользователи а также те на кого воздействуют только бизнес последствия разработки. Этих заинтересованных лиц можно найти в соответствующей бизнес области или в окрестностях среды конкретного приложения. Ограничения налагаемые на систему ввода заказов на покупку Источник Ограничение Объяснение Эксплуатационный Копия данных заказа на покупку должна оставаться в унаследованной базе данных в течение одного года Риск потери данных слишком высок; нам необходимо работать параллельно в течение года...
41406. МЕТОДЫ ВЫЯВЛЕНИЯ ТРЕБОВАНИЙ 85.5 KB
  Пять этапов анализа проблемы Достижение соглашения об определении проблемы Выделение основных причин проблем стоящих за проблемой Выявление заинтересованных лиц и пользователей Определение границ системырешения Выявление ограничений налагаемых на решение 5. Синдром неоткрытых руин Синдром пользователя и разработчика Функции продукта или системы Потребности заинтересованных лиц и пользователей Функции Управление сложностью путем выбора уровня абстракции Атрибуты функций продукта 9. Предельно недорога ...
41407. Обыгрывание ролей 196.5 KB
  Проблема требований Цель Статистика Основные причины успеха и провала проектов Высокая цена ошибок требований 2. Инженерия систем интенсивно использующих программное обеспечение Задача выявления требований 7. Преграды на пути выявления требований Синдром да но. МЕТОДЫ ВЫЯВЛЕНИЯ ТРЕБОВАНИЙ Совещания посвященные требованиям Мозговой штурм и отбор идей Раскадровка Применение прецедентов 9.
41408. Документ Delta Vision 225 KB
  Он представляет собой достаточно подробное описание на естественном языке поэтому основным участникам проекта легко с ним работать. Разработка документаконцепции и работа с ним являясь центром приложения действий многих участников заказчиков пользователей представителей руководства проекта и маркетинга могут играть заметную роль в успехе или неудаче программного проекта. При создании первой версии документа это не так уж сложно так как практически все пункты в перечне будут новыми для данного проекта или по крайней мере должны...
41409. Промышленные технологии проектирования ИС 152.5 KB
  По степени использования типовых проектных решений различают следующие методы проектирования: оригинального индивидуального проектирования когда проектные решения разрабатываются с нуля в соответствии с требованиями к ЭИС; типового проектирования предполагающего конфигурацию ЭИС из готовых типовых проектных решений программных модулей. Итеративному подходу присуща внутренняя гибкость позволяющая включать в бизнесцели новые требования или тактические изменения. Хотя ни один отдельно взятый процесс не способен удовлетворить...
41410. ТИПОВОЕ ПРОЕКТИРОВАНИЕ ИС 250.5 KB
  В качестве примеров широко распространенных функциональных ППП можно назвать: 1С Предприятие автоматизация бухгалтерского учета расчета заработной платы складского учета Фолио Склад автоматизация складских операций Project Expert бизнеспланирование ИНЭК финансовый анализ и др. Таким образом вместе с программным продуктом пользователи приобретают базу знаний knowhow об эффективных методах организации и управления бизнеспроцессами которые можно адаптировать в соответствии со спецификой конкретного экономического...