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;

}

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

Вывод

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


 

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

13320. ВИЗНАЧЕННЯ ПИТОМОЇ ТЕПЛОТИ ПАРОУТВОРЕННЯ РІДИНИ 236 KB
  Лабораторна робота № 5 ВИЗНАЧЕННЯ ПИТОМОЇ ТЕПЛОТИ ПАРОУТВОРЕННЯ РІДИНИ Мета роботи: а вивчення процесів пароутворення; б експериментальне визначення питомої теплоти пароутворення води при температурі кипіння. Прилади та матеріали: калориметр з мішалкою ки
13321. ВИЗНАЧЕННЯ КОЕФІЦІЄНТА ПОВЕРХНЕВОГО НАТЯГУ РІДИНИ МЕТОДОМ ВІДРИВУ КІЛЬЦЯ 168.5 KB
  Лабораторна робота № 6 ВИЗНАЧЕННЯ КОЕФІЦІЄНТА ПОВЕРХНЕВОГО НАТЯГУ РІДИНИ МЕТОДОМ ВІДРИВУ КІЛЬЦЯ. Мета роботи: а вивчення властивостей рідкого стану речовини; б визначення коефіцієнта поверхневого натягу рідини від типу речовини; в визначення залежності коефі
13322. Визначення коефіцієнта Пуасона методом Клемана і Дезорма 473 KB
  Лабораторна робота №8 Визначення коефіцієнта Пуасона методом Клемана і Дезорма. Мста роботи: аВивчення законів ідеального газу. бЕкспериментальне визначення показника адіабати. Прилади і матеріали: балон з двома кранами рідинний манометр ручний насос. Кор...
13323. Визначення теплоти розчинення солі 460 KB
  Лабораторна робота № 9. Визначення теплоти розчинення солі. Мета роботи: адослідним шляхом визначити теплоту розчинення солі; бустановити залежність теплоти розчинення солі від концентрації розчину. Прилади та матеріали: посудина Дюара термометр мензурка сі...
13324. ВИЗНАЧЕННЯ КОЕФІЦІЄНТА ВНУТРІШНЬОГО ТЕРТЯ ТА СЕРЕДНЬОЇ ДОВЖИНИ ВІЛЬНОГО ПРОБІГУ МОЛЕКУЛ ПОВІТРЯ 400 KB
  Лабораторна робота № 10 ВИЗНАЧЕННЯ КОЕФІЦІЄНТА ВНУТРІШНЬОГО ТЕРТЯ ТА СЕРЕДНЬОЇ ДОВЖИНИ ВІЛЬНОГО ПРОБІГУ МОЛЕКУЛ ПОВІТРЯ Мета роботи: а вивчення основних законів молекулярнокінетичної теорії газів; б експериментальне визначення основних параметрів молекулярн...
13325. ВИЗНАЧЕННЯ КОЕФІЦІЄНТА ЛІНІЙНОГО РОЗШИРЕННЯ ТВЕРДИХ ТІЛ 696 KB
  Лабораторна робота №11 ВИЗНАЧЕННЯ КОЕФІЦІЄНТА ЛІНІЙНОГО РОЗШИРЕННЯ ТВЕРДИХ ТІЛ Мета роботи: авивчення термічного розширення твердих тіл; бекспериментальне визначення коефіцієнта лінійного розширення різних матеріалів. Прилади та матеріали: прилад для в...
13326. Визначення вязкості рідини капілярним віскозиметром 365 KB
  Лабораторна робота № 12 Визначення вязкості рідини капілярним віскозиметром. Мета роботи: авивчення властивостей рідини; бекспериментальне визначення коефіцієнта вязкості рідини. Прилади та матеріали: віскозиметр секундомір спирт дистильована вод
13327. Визначення коефіцієнта поверхневого натягу методом Ребіндера 223 KB
  Лабораторна робота №7 Визначення коефіцієнта поверхневого натягу методом Ребіндера. Мета роботи: аВизначення властивостей рідини: бВивчення методів та експериментальне визначення коефіцієнта поверхневого натягу. Прилади та матеріали: аспіратор установка
13328. Комп’ютерний вибір оптимальних однорідних термоелектричних матеріалів для термоелектрики 29.5 KB
  Звіт до лабораторної роботи № 1 Компютерний вибір оптимальних однорідних термоелектричних матеріалів для термоелектрики Мета роботи Використовуючи експериментальні дані кінетичних коефіцієнтів навчитись проводити раціональний вибір термоелектричного мат