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;

}

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

Вывод

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


 

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

71156. Предложение мероприятий по совершенствованию ОАО «Сбербанк» 632.5 KB
  Стратегической линией Сбербанка России является кредитование реального сектора экономики. Банк является одним из главных локомотивов регионального экономического роста. Кредитный портфель банка составил более 50 млрд. руб., в том числе объем инвестиционных кредитов...
71157. Коммерческие банки и их деятельность на примере ОАО АКБ «Иронбанк» 420.5 KB
  Банковская система – одна из важнейших и неотъемлемых структур рыночной экономики. Развитие их деятельности - необходимое условие реального создания рыночного механизма. Процесс экономических преобразований начался с реформирования банковской системы.
71158. Произвольная память младших школьников с нарушениями интеллекта в игровой деятельности 373 KB
  Важнейшая особенность психики состоит в том, что отражение высших воздействий используется индивидом в его дальнейшем поведении. Постепенное усложнение поведения осуществляется за счет накопления индивидуального опыта. Формирование опыта было бы невозможно,...
71159. Формирование познавательных универсальных учебных действий у учащихся младших классов на уроках математики с применением средств информационных и коммуникационных технологий 1.66 MB
  Понятие системы универсальных учебных действий учащихся младших классов. Функции универсальных учебных действий. Возрастные особенности формирования познавательных универсальных учебных действий у младших школьников.
71160. Структура и семантика терминологических словосочетаний по экономике в аналитической статье англоязычной прессы 407 KB
  Цель данного исследования выявить наиболее употребительные структурные модели терминологических словосочетаний по экономике в англоязычном газетном тексте установить закономерности их перевода на русский язык а также особенности их функционирования в текстах СМИ.
71162. Разработка предложений по повышению уровня кадрового потенциала и совершенствованию кадровой политики на ТОО «Крендель» 791.5 KB
  В современных экономических условиях для государства важно присутствие у рычагов управления предприятиями опытных руководителей способных использовать свои возможности в нужном направлении умеющих эффективно использовать кадровый потенциал предприятия.
71163. Основные особенности гражданско-правовой ответственности в РФ 127.11 KB
  Из них социальная ответственность обобщающее понятие включающее все виды ответственности в обществе а сама юридическая ответственность разновидность форма социальной ответственности. В праве говоря об ответственности имеют в виду как правило юридическую ответственность...
71164. Отличия учетной политики для целей налогообложения от учетной политики для целей бухгалтерского учета 44.32 KB
  Термин «учетная политика предприятия» вошел в употребление в конце восьмидесятых годов в качестве вольного перевода на русский язык словосочетания «accounting policies», употребляемого в стандартах, издаваемых Комитетом по международным стандартам бухгалтерского учета.