Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ

ТОМСКИЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

Институт дистанционного образования

Кафедра Автоматики и компьютерных систем

Направление «Управление в технических системах»

Пояснительная записка к курсовой работе

по дисциплине «Структуры и алгоритмы обработки данных»

Студент гр. З-8001

Поспелова И.В.

Ассистент каф. АиКС

Савенко И.И.

Томск - 2013



Введение

Целью данной курсовой работой является разработка программного комплекса, позволяющего проиллюстрировать работу с иерархическими структурами данных.

Для выполнения данной задачи был использован один из универсальных языков программирования - язык С++. Выбор данного языка обусловлен тем, что он широко используется для создания программ самого разного назначения: начиная от создания операционных систем и заканчивая созданием видеоигр. Этот язык программирования позволяет программисту сделать практически все. Кроме того, C++ - это "чистый" язык, язык в котором нет "заточенности" на ту или иную библиотеку или стиль программирования. С++, в отличие от многих, не привязан ни к чему. Это дает программисту на С++ поразительное количество возможностей и вариантов запрограммировать даже самое простое действие. Кроме того, С++ поддерживает мультипарадигменное программирование, то есть возможность пользоваться при написании программ многими стилями программирования.

Кроме того, в процессе написания курсовой работы потребуется знание о такой иерархической структуре данных как двоичное дерево, а также способов организации этого типа данных при помощи языка С++.



Задание на курсовую работу

Построить двоичное дерево поиска из целых чисел. Удалить из него элементы, встречающиеся несколько раз. Результат вывести на экран. Определить глубину дерева до и после удаления.

Требования, предъявляемые к программному комплексу:

1) Программный комплекс должен состоять из нескольких функций, каждая из которых призвана решать свою специфическую задачу. Например, функция построения дерева, функция вывода на экран построенного дерева и т.д.

2) После запуска программного комплекса, на экране должно быть выведено задание, для решения которого и разработан программный комплекс.

3) Работа программного комплекса должна быть организована в диалоговом режиме с пользователем. Например, пользователь по запросу вводит количество элементов исходного дерева, после решения задачи на экран выводится результат со всеми необходимыми пояснениями. Должно быть предусмотрено два способа ввода информации в дерево - автоматическая генерация случайных данных, ввод данных самим пользователем с клавиатуры.

4) После работы динамическая структура должна быть удалена.

5) В программном комплексе должны осуществляться все возможные проверки, в частности: на корректность исходных данных.



Предметная область

Прежде чем приступать к решению задачи, необходимо ознакомиться с предметной областью.

Деревом называется одна из наиболее широко распространённых структур данных в информатике, эмулирующая древовидную структуру в виде набора связанных узлов. Прежде всего, дерево является связанным графом, не содержащим циклы.

У любого дерева есть корень. Это узел, расположенный в самом верху дерева (см. Рисунок 1). У дерева может быть только один корень.

К любому узлу дерева можно дойти из корня. Кроме того, существует только один путь связывающий корень и узел. Следует обратить внимание на то, что любой узел дерева сам по себе является деревом и именуется поддеревом.

Расстояние от корня до узла называется уровнем. Корень расположен на нулевом уровне.

Глубина дерева - это максимальный уровень любого его узла. Или глубина дерева - это длина самого длинного пути от корня до узла.

Если между узлами b и a есть дуга, и узел a расположен на более высоком уровне, то a называется - родителем (предком), а b - потомком. Каждый узел дерева является корнем поддерева, которое состоит из данного узла и всех его потомков. У узла дерева может быть любое количество потомков.

Самые нижние узлы дерева называют листьями, и они не имеют потомков.



Рисунок 1 - Дерево

Способы изображения древовидной структуры

В данном разделе будут рассмотрены возможные варианты изображения деревьев. Из всех рассмотренных вариантов будет выбран один для реализации поставленной задачи. Этот способ должен быть достаточно удобен для восприятия, а также для реализации средствами языка программирования C++.

1) Первый способ, и наиболее распространенный - Классическая диаграмма (см. рисунок 2).

Рисунок 2 - Классическая диаграмма

2) Вложенные скобки. Легко реализуется на языках программирования, но неудобен для восприятия (см. Рисунок 3).



Рисунок 3 - Вложенные скобки

3) Вложенные множества. Данный способ наглядный и удобный для восприятия, но возможны проблемы с его реализацией (см. Рисунок 4).

Рисунок 4 - Вложенные множества

4) Ломаная последовательность (см. Рисунок 5).

Рисунок 5 - Ломаная последовательность



Двоичное (бинарное) дерево

Двоиичное деерево -- древовидная структура данных, в которой каждый узел имеет не более двух потомков. Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками.

То есть двоичное дерево либо является пустым, либо состоит из данных и двух поддеревьев (каждое из которых может быть пустым). Очевидным, но важным для понимания фактом является то, что каждое поддерево в свою очередь тоже является деревом. Если у некоторого узла оба поддерева пустые, то он называется листовым узлом (листовой вершиной).

Например, согласно этой грамматике, двоичное дерево можно было бы записать так (см. Рисунок 6):

Рисунок 6 - Двоичное дерево

Двоичное дерево поиска

Деревья двоичного поиска широко распространены в программировании. Значение содержимого каждой вершины дерева двоичного поиска:

1) Оба поддерева -- левое и правое, являются двоичными деревьями поиска.

2) У всех узлов левого поддерева произвольного узла X значения ключей данных меньше, нежели значение ключа данных узла X.

3) У всех узлов правого поддерева произвольного узла X значения ключей данных больше, нежели значение ключа данных узла X.

Распространенность деревьев двоичного поиска в программировании является следствием эффективности методов поиска в этих деревьях.

Рисунок 7 - Двоичное дерево поиска

Разработка программного комплекса. Описание алгоритмов, используемых в программном комплексе

После анализа предметной области было решено использовать следующие языковые средства C++ для решения поставленной задачи:

1. Для хранения вершин дерева с описанием связей - структуры. Структуры в С++ используются для логического и физического объединения данных произвольных типов, так же как массивы служат для группирования данных одного типа.

2. Также нам потребуется возможность обходить все вершины, т.к. обход дерева придется осуществлять несколько раз, удобно будет вынести это действие в отдельную функцию и при необходимости вызывать ее в теле основной программы. По мере увеличения размера и сложности программного комплекса следует разделить его на небольшие легко управляемые части, называемые функциями. Каждая функция в вашей программе должна выполнять определенную задачу. Если программе необходимо выполнить определенную задачу, то она вызывает соответствующую функцию, обеспечивая эту функцию информацией, которая ей понадобится в процессе обработки.

3. Для обхода всех вершин дерева воспользуемся рекурсивной функцией. В языке С++ функция может вызывать сама себя. В этом случае такая функция называется рекурсивной. Рекурсия -- это процесс определения чего-либо на основе самого себя, из-за чего рекурсию еще называют рекурсивным определением. Рекурсия необходима чтобы пройти по всем вершинам дерева. Так как для хранения дерева была выбрана структура, тогда для обхода дерева нам потребуется рекурсивная функция. Если бы реализация была основана на использовании массива, можно было бы осуществить обход графа через циклы. Но реализация обхода дерева, хранящегося в структурах будет неоправданно усложнена (а в случае не двоичного дерева, невозможна).

Осуществить поиск и удаление повторяющихся вершин двоичного дерева поиска удобно, используя две рекурсивные функции. Функция А будет в своем теле вызывать на исполнение функцию В, передовая ей значение вершины дерева, полученного при обходе в функции А. Далее, Функция В будет сначала (начиная с корня дерева), проверять все вершины дерева, сравнивая их с полученный из функции А значением. Если будет обнаружено более чем одно повторение значения вершины в графе, то все последующие повторяющиеся элементы, будут удалены.

Более подробная реализация алгоритма будет представлена в следующих разделах данной работы.

Описание функций, используемых в программе

В программе используется 7 функций. Каждая из них выполняет свою уникальную, нигде не дублирующуюся функцию. Именно в этом и заключается смысл использования функций - использование функций решают проблему избыточности описания повторяющихся действий. Функции позволяют значительно сократить программный код и упростить процесс разработки программного продукта.

1) Функция построения дерева. В качестве входных параметров служат переменные str (в данную переменную записывается значение новой вершины, переданное из главной функции программы) и tt (переменная получает адрес памяти хранящий данные корня дерева).

Сначала проверяется следующее условие: является ли корень дерева пустым. При выполнении условия в поле данных корня записывается значение переменной. Если условие не выполняется, происходит проверка следующего условия: является ли переменная str меньше данных корня дерева. При выполнении данного условия проверяется еще одно: является ли левое поддерево пустым. Если левое поддерево пустое, то оно станет новой вершиной следующего поддерева и в него запишется значение переменной str. Если левое поддерево непустое, вызываем нашу функцию рекурсивно, но с параметрами tt-> pleft(указатель на левое поддерево) и str. Таким же образом проверяется и указатель на правое поддерево.

2) Функция удаления элемента дерева.

В качестве параметров в функцию будут входить node - значение узла дерева и parent - узел-родитель.

Удаление элемента из сортированного дерева немного сложнее, чем добавление. После этой операции программа должна перестроить другие узлы, чтобы сохранить в дереве соотношение «меньше чем». Следует рассмотреть несколько существующих вариантов.

Во-первых, если удаляемый узел не имеет потомков, допустимо просто убрать его из дерева. При этом порядок остальных узлов не изменяется (см. Рисунок 8).



Рисунок 8 Удаление листа дерева

Во-вторых, если удаляемый узел имеет один дочерний узел, можно заменить его дочерним узлом. При этом порядок потомков данного узла остается тем же, так как эти узлы также являются и потомками дочернего узла (см. Рисунок 9).

Рисунок 9 - Удаление узла с одним потомком

Если удаляемый узел имеет два дочерних, вовсе не обязательно, что один из них займет его место. Если потомки узла также имеют по два дочерних, то для размещения всех дочерних узлов в позиции удаленного узла просто нет места. У удаленного узла есть один лишний потомок, а дочерний узел, которым вы могли бы заменить исходный, имеет два дочерних узла, поэтому вы должны объявить три дочерних записи узла в данной позиции.

Чтобы решить эту проблему, вы должны заменить удаленный узел крайним

правым узлом дерева из левой ветви. Другими словами, двигайтесь вниз от удаленного узла по левой ветви. Затем двигайтесь вниз по правым ветвям до тех пор, пока не найдете узел без правой ветви. Это и есть нужный узел (см. Рисунок 10).

Рисунок 10 - Удаление узла с двумя потомками

3) Функция поиска повторяющихся элементов дерева. В данной функции используется булевый массив array (т.е. элементы данного массива могут принимать только два значения: true и false), который изначально состоит только из элементов, равных false. Используем цикл с предусловием (пока array[node->dann] имеет значение true), в котором будем вызывать функцию по удалению узла дерева. После цикла присвоим array[node->dann] значение true и осуществим проверку двух условий: является ля левое поддерево пустым (если является,то рекурсивно вызываем функцию с параметрами node->pleft, node->pleft) и является ли правое поддерево пустым (если является, то также вызываем рекурсивную функцию, но с параметрами node->pright, node->pright). Таким образом, в результате работы функции будут находиться повторяющиеся элементы, которые и будут удаляться.

4) Функция вывода дерева на экран. В качестве начальных параметров используются указатель на корень дерева и step - сдвиг для печати в виде дерева (начальное значение step =0)

Дерево печатается повернутым набок (вверху - правое поддерево, внизу - левое).

5) Функция обхода дерева. В качестве алгоритма обхода был выбран прямой обход дерева. Смысл алгоритма заключается в том, что каждый узел посещается до того, как посещены его потомки.

Для корня дерева рекурсивно вызывается следующая процедура:

а) Посетить узел.

б) Обойти левое поддерево.

в) Обойти правое поддерево.

6) Функция определения глубины дерева. В качестве параметра в функцию передается только узел дерева. Для нахождения глубины нам потребуется две переменные: a и b, которые изначально равны нулю. В переменную b будет записываться глубина дерева, переменная a - вспомогательная. Если узел непустой, то осуществляется дальнейшая проверка условий: если a>b, то a=b. Если непустое левое поддерево, то а увеличиваем на единицу и рекурсивно вызываем функцию с параметрами ptr-> pleft. Если левое поддерево непустое, то также увеличиваем переменную a на единицу и рекурсивно вызываем функцию с параметром ptr->pright.

7) Функция заполнения дерева случайными числами от 1 до 10 автоматически с использованием функции rand.

Описание работы программного комплекса. Инструкция по работе с программным комплексом

программный алгоритм данные бинарный

После запуска программы на экране пользователя появляется окно (см. Рисунок 11), в котором будет выведены: номер варианта задания, формулировка задания и список команды выполняемых программой.

Рисунок 11 -Запуск программы



Каждую команду можно активировать, нажав соответствующую клавишу на клавиатуре («1» - Для заполнения дерева автоматически, «2» - Для ввода дерева вручную, «3» - Для выхода из программы).

Если пользователем будет выбрана команда «3», то программа завершит работу.

Команда «1» позволит пользователю самостоятельно заполнить дерево элементами в диалоговом режиме. Также произойдёт вывод введённого дерева и вывод обработанного дерева, а также их обход и глубина. (см. Рисунок 12).

Рисунок 12 - ввод дерева с клавиатуры

Выбрав команду «2», программа автоматически сгенерирует дерево заданной длины, наполнив его случайными элементами. Произойдёт вывод этого дерева, затем вывод дерева с удаленными повторяющимися элементами, а также их обходы и глубина (см. Рисунок 13).



Рисунок 13 - Автоматическое генерирование дерева



Заключение

В ходе выполнения курсовой работы были Проанализированы различные способы представления и использования двоичных деревьев поиска. Общие принципы построения деревьев и методы удаления элементов из них.

Задача, поставленная в данной курсовой работе, является достаточно сложной с точки зрения составления алгоритма. Помимо этого, она довольно сложна в плане реализации, так как требует детального изучения и понимания предметной области. Результатом выполнения курсовой работы является полноценное приложение с отдельными функциями, разработанное в соответствии с современными подходами к созданию программного обеспечения. Был разработан и реализован пользовательский интерфейс, а также защита от возникновения ошибки при неправильном вводе. Также написанное приложение решает поставленную ранее задачу и полностью соответствует всем установленным для нее требованиям.

Выполнение данной работы позволило закрепить изученный материал, а также получить новые, принципиально важные знания в области программирования, проектирования и разработки программных продуктов.



Литература

1. «С++. Освой на примерах» М. И. Динман - СПб: БХВ-Петербург, 2006. 384с.

2. «Структуры и алгоритмы обработки данных» И. В. Цапко - Томск: Изд-во Томского политехнического университета, 2007. 184с.

3. «/С++ и MS Visual C++ 2008 для начинающих» Б.И. Пахомов - СПб: БХВ-Петербург, 2009. 624с.



Приложения

Приложение А

Листинг программы

#include "stdafx.h"

#include <iostream>

#include <conio.h>

#include <iomanip>

#include <time.h>

#pragma hdrstop//директива связана с особенностью работы препроцессора, производительность которого

//существенно повышается, если учитывается, что некоторое количество заголовочных файлов

//общие для всех модулей

#pragma argsused//говорит компилятору, что следует подавить выдачу предупреждающего сообщения о том,

//что параметры функции main () никак в ней не используются.

//---------------------------------------------------------------------------

using namespace std;

struct TREE

{

char dann;

TREE *pleft;

TREE *pright;

};

TREE *root = NULL;

TREE *parent = NULL;

int i, k, b, n, c, p;

char tt = 0;

bool array[100];

char *str = new char [n];

char a = 0;

char cmax, cmin;

//---------------------------------------------------------------------------

void build(TREE *tt, char str) // функция построения дерева

{

TREE *left;

TREE *right;

if (tt->dann==NULL)

{

tt->dann=str;

tt->pleft=NULL;

tt->pright=NULL;

}

else

{

if (str<tt->dann)

if (tt->pleft == NULL)

{

left = new TREE;

tt->pleft = left;

left->dann = str;

left->pleft = NULL;

left->pright = NULL;

}

else build(tt->pleft, str);

else

if (tt->pright == NULL)

{

right = new TREE;

tt->pright = right;

right->dann = str;

right->pleft = NULL;

right->pright = NULL;

}

else build(tt->pright, str);

}

}

//---------------------------------------------------------------------------

void Delet1(TREE* node, TREE*& parent) // функция удаления узла дерева

{

if (!node) return;

if (!node->pleft && !node->pright)

{

delete node;

if (parent) parent = 0;

}

else if (!node->pleft && node->pright)

{

if (parent) parent = node->pright;

delete node;

}

else if (node->pleft && !node->pright)

{

if (parent) parent = node->pleft;

delete node;

}

else

{

TREE* temp = node->pright;

while (temp->pleft)

temp = temp->pleft;

temp->pleft = node->pleft;

temp = node;

node = node->pright;

parent = node;

delete temp;

}

}

//---------------------------------------------------------------------------

void Solution(TREE* node, TREE*& parent)//функция поиска повторяющихся элементов

{

while (array[node->dann])

{

Delet1(node, parent);

node = parent;

if (!node) return;

}

array[node->dann] = true;

if (node->pleft) Solution(node->pleft, node->pleft);

if (node->pright) Solution(node->pright, node->pright);

}

//---------------------------------------------------------------------------

void print (TREE *first, int step) // функция печати дерева

{

if (first)

{

print (first->pright, step+1);

for (int i = 1; i <= step; i++) cout << " ";

cout << first->dann << endl;

print (first->pleft, step+1);

}

}

//---------------------------------------------------------------------------

void obhod(TREE *ptr)//функция прямого метода обхода дерева

{

if (ptr)

{

putchar(ptr->dann);

cout << ' ';

if (ptr->pleft) obhod(ptr->pleft);

if (ptr->pright) obhod(ptr->pright);

}

}

//---------------------------------------------------------------------------

void deep(TREE *ptr) // функция определения глубины дерева

{

if (ptr)

{

if (a > b)

{

b = a;

}

if (ptr->pleft)

{

++a;

deep(ptr->pleft);

}

if (ptr->pright)

{

++a;

deep(ptr->pright);

}

}

}

//---------------------------------------------------------------------------

void RandomCreate(TREE*& node, int n) // функция генерации случайных велечин

{

srand(time(0));

node = new TREE;

node->dann = rand() % 9+48;

node->pleft = node->pright = 0;

for(int i = 1; i < n; i++)

build(root, rand() % 9+48);

}

//---------------------------------------------------------------------------

//---------------------------------------------------------------------------

int main() // главная функция

{

//смена кодировки в консоли для отображения русских символов

setlocale(LC_ALL,"rus_rus.1251");

//Вывод задания на экран:

cout << "Вариант 1" << endl << "Построить двоичное дерево поиска из целых чисел.";

cout << "Удалить из него элементы, встречающиеся несколько раз. ";

cout << "Результат вывести на экран. Определить глубину дерева до и после удаления."<<endl;

int n, count;

cout << "Выберите пункт:" << endl;

cout << "1 - Ввод с клавиатуры" << endl;

cout << "2 - Ввод в автоматическом режиме" << endl;

cout << "3 - Выход из программы" << endl;

cout << "-> ";

M: ;

cin >> count;

switch(count)

{

case 1:

cout << "Введите элементы дерева: ";

cin >> str;

n = strlen(str);

root = new TREE;

root->dann = str[0];

root->pleft = NULL;

root->pright = NULL;

for (i = 1; i <n; i++) build(root, *(str+i));

for(i = 0; i < n; i++)

array[i] = false;

break;

case 2:

cout << "Введите количество элементов дерева: " << endl;

cin >> n;

RandomCreate(root, n);

for(i = 0; i < n; i++)

array[i] = false;

break;

case 3:

goto exit;

break;

default:

cout << "Неверный ввод! Повторите ввод снова" << endl;

goto M;

break;

}

cout << endl << "Построенное дерево: " << endl << endl;

print(root, 0);

cout << "Обход дерева: ";

obhod(root);

cout << endl;

deep(root);

cout << endl << "Глубина дерева составляет: " << b << endl;

cout << endl << "Дерево после обработки: " << endl << endl;

Solution(root,root);

print(root, 0);

obhod(root);

a=b=0;

deep(root);

cout << endl << "Глубина дерева после обработки составляет: : " << b << endl;

getch();

exit: ;

return 0;

}

//---------------------------------------------------------------------------

Размещено на Allbest.ru