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;

}

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

Вывод

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


 

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

58025. Was feiern wir im Herbst 95.5 KB
  Цілі уроку: Практична: активізувати лексико-граматичний матеріал в усному і писемному мовленні, навчити учнів говорити про осінню природу і свята восени, розвивати навички читання. Освітня: розширити знання учнів про свята в Німеччині і у світі.
58026. Мова програмування HTML. Теги для роботи з фоном. Теги для задання кольору 52 KB
  Мета уроку: Навчальна: закріпити знання учнів про команди мови теги HTMLтехнологію створення HTMLфайлу ознайомити учнів з тегами для роботи з фоном та тегами для задання кольору навчити створювати найпростіші вебсторінки...
58027. Створення форм у HTML-сторінках 794.5 KB
  Навчальна: опанувати технологію і методи створення форм в HTML-документах Розвивальна: розвивати логічне мислення, пізнавальний інтерес до дисципліни та обраної спеціальності; Виховна: виховувати акуратність у веденні електронної документації...
58028. Іменники середнього роду 94 KB
  Мета: Активізувати вивчену лексику. Вчити ознаки іменників середнього роду. Познайомитися зі зменшувальними суфіксами виконувати тренувальні вправи. Розвивати навички письма, граматичні навички.
58029. Завершение формирования мировых колониальных империй. Международные отношения в последней трети XIX века 122 KB
  Цели: Сформировать представление об Индии во второй половине XIX века; ознакомить с принципами колониальной политики Британии в Индии; раскрыть причины ход и результаты восстание сипаев; формировать собственные суждения об идеологии бремени белого человека...
58030. Индия. Культурно — исторические особенности. Экономико-географическая характеристика 118 KB
  Цель: сформировать у учащихся общие представления о культуре и экономических особенностях Индии; совершенствовать навыки учащихся самостоятельно отбирать и анализировать материал; продолжить формирование умений обобщать и делать выводы; воспитывать ответственность...
58031. Давня Індія 78.5 KB
  Слово вчителя: Шановні учні сьогодні ми з вами помандруємо на Схід до цікавої і загадкової Індії. Вивчення нового матеріалу Географічне положення Індії Робота з картою.
58032. Застосування дієприкметника як особливої форми дієслова у захисті проектів «Особливості догляду за шкірою підлітків» 1.94 MB
  МЕТА: виховувати в учнів любов до вивчення української мови; творчу ініціативу та свідоме ставлення до зміцнення й збереження власного здоровя; розвивати мовленнєву компетенцію учнів та навички комунікативно користуватися засобами мови в різних життєвих ситуаціях...
58033. Прості і складені задачі, які включають дії над величинами, вираженими одиницями площі 58.5 KB
  Цілі: освітні: формувати обчислювальні уміння і навички, уміння розв’язувати задачі, аналізувати математичні завдання; розвивальні: розвивати логічне і алгоритмічне мислення, пізнавальні та інтелектуальні можливості, стимулювати розвиток умінь учнів аргументувати свою відповідь...