15338

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

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

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

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

Русский

2013-06-13

150 KB

3 чел.

Лабораторная работа №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;

}

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

Вывод

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


 

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

66952. Чарівний світ недосяжних романтичних мрій 61 KB
  Мета проекту Дослідити яскраве явище культури романтизм та визначити причини його виникнення. Ідея проекту Представники романтичного стилю XIX ст. Завдання проекту: Досліджувати мистецькі твори романтичного напрямку; Знайти видові романтичні паралелізмі в мистецтві...
66953. «Чашка, повна благодаті» Напої здоров’я. Чай 82 KB
  Мета: розширення кругозору учнів про чай як про напій здоров’я, що є складовою частиною культури харчування, познайомити з цілющими властивостями чаю, географією чаю, секретами заварювання, утвердження здорового способу життя.
66954. Мій рідний край - Донбас 66 KB
  Мета: Формувати в учнів інтерес до навчання; засвоїти слова за темою; вчити розповідати про символи Української держави та їх значення; розвивати прагнення бути свідомим громадянином України, її патріотом. Розвивати пізнавальні інтереси.
66956. Правила дорожного движения 282.5 KB
  Цель: научить детей ориентироваться по дорожным знакам, соблюдать правила дорожного движения. Воспитывать умение быть вежливыми, внимательными друг к другу на дороге. Ход мероприятия: 1 Ведущий. Взошло ласковое теплое солнышко, запели звонкие песни птицы и огласили начало нового дня.
66957. Привитие интереса к учебе, развитие гуманитарных представлений на уроке 162 KB
  Первое направление предусматривает организацию учебно-воспитательного процесса в соответствии с условиями способствующими всестороннему развитию ребенка получению им высокого уровня знаний при сохранении его здоровья на уроках применение здоровьесберегающих технологий привлечение...
66958. ЕКОЛОГІЧНА КАТАСТРОФА В УКРАЇНІ. ДЗВОНИ ЧОРНОБИЛЯ НАМ НАГАДУЮТЬ… 81 KB
  Мета проекту. Розширити знання дітей про трагедію віку – вибух на Чорнобильській АЕС, наголосити про потенційну небезпеку радіації для усього живого, розповісти про ліквідаторів аварії на Чорнобильській АЕС, показати, що чужої біди немає. Вчити застосовувати у повсякденному житті елементарні радіаційно-гігієнічні навички.
66959. Як знайти справжнього друга 66.5 KB
  Розглянути самостійність як найбільшу проблему нашого часу; розкрити причини самотності та необхідності мати друга; формувати вміння спілкуватися та дружити будувати правильні відношення. На одній його половині напишіть ті риси характеру які подобаються вам в інших людях на другій половині...
66960. Чи існує справжня дружба? 50 KB
  Що ж це значить уміти бути другом Давайте з’ясуємо як у тлумачному словнику пояснюється значення слова дружба Учень зачитує. Дружба взаємна симпатія прихильність одне до одного що базується на взаємному довір’ї відданості спільності інтересів ідей мети. У ХХІ столітті Жуковський писав слово Дружба з великої літери.