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;

}

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

Вывод

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


 

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

36167. SSD (Solid State Drive). Преимущества и недостатки 20.06 KB
  SSD логически эмулирует обычный жёсткий диск HDD и теоретически везде может применяться вместо него. SSD использующие динамическую память DRAM а не флэшпамять часто называются RAMdrive и имеют ограниченное применение например в качестве выделенного диска для файла подкачки ОС. Сердцем SSD является микросхема контроллера которая в первую очередь определяет такие ключевые характеристики SSD как внешний интерфейс быстродействие и энергопотребление. Преимущества и недостатки Преимущества SSD над HDD.
36168. Магнитные головки для записи информации на жесткий диск 112 KB
  Вначале это были монолитные головки. Композитные головки выполнены из феррита на подложке из стекла или твердой керамики и имеют меньшие размеры в сравнении с монолитными. Дальнейшим развитием технологии композитных головок стали так называемые головки MIGтипа MIG Metal In Gap.
36169. Технологии записи на магнитные диски 206 KB
  Домены магнитных материалов используемых в продольной записи располагаются параллельно поверхности носителя. Этот эффект и используется при записи цифровых данных магнитным полем головки изменяющимся в соответствии с сигналом информации. Попытки увеличить поверхностную плотность записи путем уменьшения размеров частиц будут увеличивать отношение размера зоны неопределенности к размеру полезной зоны не в пользу последней и в конце концов неизбежно приведут к так называемому суперпарамагнитному эффекту когда частицы перейдут в однодоменное...
36170. ОПТИЧЕСКИЕ ГОЛОВКИ 260 KB
  Задача эта непростая поскольку большинство оптических элементов адаптировано как правило для работы с излучением только одной длины волны. Вопервых необходимо было обеспечить приемлемое рабочее расстояние объектива при любой длине волны излучения. Вовторых обеспечить компенсацию сферических аберраций – также при любой длине волны излучения. Втретьих обеспечить изменение числовой апертуры объектива в зависимости от длины волны проходящего через него света.
36171. SuperAudioCD 87 KB
  Следует заметить что технология одноразрядного квантования используется сейчас и для преобразования звука в других форматах однако там полученный одноразрядный поток в конце концов всетаки приводится к последовательности многоразрядных отсчетов 16 20 24разрядных и в дальнейшем все операции по формированию потока данных перед записью на носитель производятся уже с ними. Этот слой является носителем данных DSD и считывается оптической головкой с числовой апертурой 06 лучом лазера с длиной волны излучения 650 нм. В процессе...
36172. Варианты формата CD 133 KB
  Такая версия компактдиска появилась в 1985 году и получила название CDROM Read Only Memory – память только для чтения. Поскольку диск CDROM предстояло использовать в составе вычислительных комплексов различной сложности то для него был разработан специальный дисковод легко вписывающийся в архитектуру компьютера. Дополнительное кодирование в CDROM производится до того как данные поступают на кодер CIRC точно такой же как в системе защиты от ошибок формата CDAudio. В формате CDROM эти 24 символа являются обезличенными и могут нести...
36173. ИЗГОТОВЛЕНИЕ BD-ДИСКОВ 401 KB
  Мастеринг BDдисков Существует три основные технологии мастеринга BDдисков: метод PTM иммерсионный метод и метод записи пучком электронов. Системы EBR Electron Beam Recorder использующие для записи пучок электронов наиболее дороги но позволяют получить очень высокое разрешение.1 иллюстрирует процесс формирования дорожки записи. Такая длина волны близка к длине волны излучения газовых лазеров которые применяются для записи оптических дисков в форматах CD и DVD.
36174. Структура минидиска 56.5 KB
  Частота сигнала вобуляции равна 2205 кГц. Эту частоту легко получить путем деления пополам частоты дискретизации звукового сигнала fд = 441 кГц. Кодирование данных DIP производится перед изготовлением диска путем частотной модуляции несущей fн = 2205 кГц бифазным кодом. Модуляция осуществляется с помощью тактовой частоты fт = 6300 Гц которая получается путем деления частоты дискретизации 441 кГц на 7 см.
36175. Записываемые диски 215.5 KB
  Длина волны вобуляции в общем случае равна 5 мкм рис. ФОРМАТ КОДИРОВАНИЯ АДРЕСНЫХ ДАННЫХ ВОБУЛЯЦИЕЙ НАПРАВЛЯЮЩЕЙ ДОРОЖКИ Записываемый диск BDR и перезаписываемый диск BDRE имеют один и тот же формат данных которые содержатся в законе вобуляции направляющей дорожки и формируются еще при изготовлении диска. Кроме того модулируя закон вобуляции можно заносить на диск дополнительные данные необходимые как для идентификации фрагментов записываемого материала так и для идентификации самого диска. Поскольку запись данных всегда выполняется...