Программа иерархических структур данных
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ
РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное бюджетное
образовательное учреждение
высшего профессионального образования
«НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ
ТОМСКИЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»
Институт дистанционного образования
Кафедра Автоматики и компьютерных
систем
Направление «Управление в технических
системах»
Пояснительная записка к курсовой
работе
по дисциплине «Структуры и алгоритмы
обработки данных»
Студент гр.
З-8001
Поспелова
И.В.
Ассистент
каф. АиКС
Савенко И.И.
Томск - 2013
Введение
Целью данной курсовой работой является разработка программного комплекса,
позволяющего проиллюстрировать работу с иерархическими структурами данных.
Для
выполнения данной задачи был использован один из универсальных языков
программирования - язык С++. Выбор данного языка обусловлен тем, что он широко
используется для создания программ самого разного назначения: начиная от
создания операционных систем и заканчивая созданием видеоигр. Этот язык
программирования позволяет программисту сделать практически все. Кроме того,
C++ - это "чистый" язык, язык в котором нет "заточенности"
на ту или иную библиотеку или стиль программирования. С++, в отличие от многих,
не привязан ни к чему. Это дает программисту на С++ поразительное количество
возможностей и вариантов запрограммировать даже самое простое действие. Кроме
того, С++ поддерживает мультипарадигменное
<#"656294.files/image001.jpg">
Рисунок
1 - Дерево
Способы изображения древовидной структуры
В данном разделе будут рассмотрены возможные варианты изображения
деревьев. Из всех рассмотренных вариантов будет выбран один для реализации
поставленной задачи. Этот способ должен быть достаточно удобен для восприятия,
а также для реализации средствами языка программирования C++.
) Первый способ, и наиболее распространенный - Классическая диаграмма
(см. рисунок 2).
Рисунок
2 - Классическая диаграмма
) Вложенные скобки. Легко реализуется на языках программирования, но
неудобен для восприятия (см. Рисунок 3).
Рисунок 3 - Вложенные скобки
) Вложенные множества. Данный способ наглядный и удобный для восприятия,
но возможны проблемы с его реализацией (см. Рисунок 4).
Рисунок 4 - Вложенные множества
) Ломаная последовательность (см. Рисунок 5).
Рисунок 5 - Ломаная последовательность
Двоичное (бинарное) дерево
Двоиичное
деерево - древовидная <#"656294.files/image005.jpg">
Рисунок 6 - Двоичное дерево
Двоичное дерево поиска
Деревья двоичного поиска широко распространены в программировании.
Значение содержимого каждой вершины дерева двоичного поиска:
) Оба поддерева - левое и правое, являются двоичными деревьями поиска.
) У всех узлов левого поддерева произвольного узла X значения ключей
данных меньше, нежели значение ключа данных узла X.
) У всех узлов правого поддерева произвольного узла X значения ключей
данных больше, нежели значение ключа данных узла X.
Распространенность деревьев двоичного поиска в программировании является
следствием эффективности методов поиска в этих деревьях.
Рисунок 7 - Двоичное дерево поиска
Разработка программного комплекса. Описание алгоритмов,
используемых в программном комплексе
После анализа предметной области было решено использовать следующие
языковые средства C++ для решения
поставленной задачи:
. Для хранения вершин дерева с описанием связей - структуры.
Структуры в С++ используются для логического и физического объединения данных
произвольных типов, так же как массивы служат для группирования данных одного
типа.
. Также нам потребуется возможность обходить все вершины, т.к.
обход дерева придется осуществлять несколько раз, удобно будет вынести это
действие в отдельную функцию и при необходимости вызывать ее в теле основной
программы. По мере увеличения размера и сложности программного комплекса
следует разделить его на небольшие легко управляемые части, называемые
функциями. Каждая функция в вашей программе должна выполнять определенную
задачу. Если программе необходимо выполнить определенную задачу, то она вызывает
соответствующую функцию, обеспечивая эту функцию информацией, которая ей
понадобится в процессе обработки.
. Для обхода всех вершин дерева воспользуемся рекурсивной функцией. В
языке С++ функция может вызывать сама себя. В этом случае такая функция называется
рекурсивной. Рекурсия - это процесс определения чего-либо на основе самого
себя, из-за чего рекурсию еще называют рекурсивным определением. Рекурсия
необходима чтобы пройти по всем вершинам дерева. Так как для хранения дерева
была выбрана структура, тогда для обхода дерева нам потребуется рекурсивная
функция. Если бы реализация была основана на использовании массива, можно было
бы осуществить обход графа через циклы. Но реализация обхода дерева,
хранящегося в структурах будет неоправданно усложнена (а в случае не двоичного
дерева, невозможна).
Осуществить поиск и удаление повторяющихся вершин двоичного дерева поиска
удобно, используя две рекурсивные функции. Функция А будет в своем теле
вызывать на исполнение функцию В, передовая ей значение вершины дерева,
полученного при обходе в функции А. Далее, Функция В будет сначала (начиная с
корня дерева), проверять все вершины дерева, сравнивая их с полученный из
функции А значением. Если будет обнаружено более чем одно повторение значения
вершины в графе, то все последующие повторяющиеся элементы, будут удалены.
Более подробная реализация алгоритма будет представлена в следующих
разделах данной работы.
Описание функций, используемых в программе
В программе используется 7 функций. Каждая из них выполняет свою уникальную,
нигде не дублирующуюся функцию. Именно в этом и заключается смысл использования
функций - использование функций решают проблему избыточности описания
повторяющихся действий. Функции позволяют значительно сократить программный код
и упростить процесс разработки программного продукта.
) Функция построения дерева. В качестве входных параметров служат
переменные str (в данную переменную записывается
значение новой вершины, переданное из главной функции программы) и tt (переменная получает адрес памяти хранящий данные корня
дерева).
Сначала проверяется следующее условие: является ли корень дерева пустым.
При выполнении условия в поле данных корня записывается значение переменной.
Если условие не выполняется, происходит проверка следующего условия: является
ли переменная str меньше данных корня дерева. При
выполнении данного условия проверяется еще одно: является ли левое поддерево
пустым. Если левое поддерево пустое, то оно станет новой вершиной следующего
поддерева и в него запишется значение переменной str. Если левое поддерево непустое, вызываем нашу функцию
рекурсивно, но с параметрами tt->
pleft(указатель на левое поддерево) и str. Таким же образом проверяется и
указатель на правое поддерево.
) Функция удаления элемента дерева.
В качестве параметров в функцию будут входить node - значение узла дерева и parent - узел-родитель.
Удаление элемента из сортированного дерева немного сложнее, чем
добавление. После этой операции программа должна перестроить другие узлы, чтобы
сохранить в дереве соотношение «меньше чем». Следует рассмотреть несколько
существующих вариантов.
Во-первых, если удаляемый узел не имеет потомков, допустимо просто убрать
его из дерева. При этом порядок остальных узлов не изменяется (см. Рисунок 8).
Рисунок 8 Удаление листа дерева
Во-вторых, если удаляемый узел имеет один дочерний узел, можно заменить
его дочерним узлом. При этом порядок потомков данного узла остается тем же, так
как эти узлы также являются и потомками дочернего узла (см. Рисунок 9).
Рисунок 9 - Удаление узла с одним потомком
Если удаляемый узел имеет два дочерних, вовсе не обязательно, что один из
них займет его место. Если потомки узла также имеют по два дочерних, то для
размещения всех дочерних узлов в позиции удаленного узла просто нет места. У
удаленного узла есть один лишний потомок, а дочерний узел, которым вы могли бы
заменить исходный, имеет два дочерних узла, поэтому вы должны объявить три
дочерних записи узла в данной позиции.
Чтобы решить эту проблему, вы должны заменить удаленный узел крайним
правым узлом дерева из левой ветви. Другими словами, двигайтесь вниз от
удаленного узла по левой ветви. Затем двигайтесь вниз по правым ветвям до тех
пор, пока не найдете узел без правой ветви. Это и есть нужный узел (см. Рисунок
10).
Рисунок 10 - Удаление узла с двумя потомками
) Функция поиска повторяющихся элементов дерева. В данной функции
используется булевый массив array
(т.е. элементы данного массива могут принимать только два значения: true и false), который изначально состоит только из элементов,
равных false. Используем цикл с предусловием
(пока array[node->dann] имеет значение true), в котором будем вызывать функцию по удалению узла
дерева. После цикла присвоим array[node->dann] значение true и осуществим проверку двух условий:
является ля левое поддерево пустым (если является,то рекурсивно вызываем
функцию с параметрами node->pleft, node->pleft) и является ли правое
поддерево пустым (если является, то также вызываем рекурсивную функцию, но с
параметрами node->pright, node->pright). Таким образом, в результате
работы функции будут находиться повторяющиеся элементы, которые и будут
удаляться.
) Функция вывода дерева на экран. В качестве начальных параметров
используются указатель на корень дерева и step - сдвиг для печати в виде дерева (начальное значение step =0)
Дерево печатается повернутым набок (вверху - правое поддерево, внизу -
левое).
) Функция обхода дерева. В качестве алгоритма обхода был выбран прямой
обход дерева. Смысл алгоритма заключается в том, что каждый узел посещается до
того, как посещены его потомки.
Для корня дерева рекурсивно вызывается следующая процедура:
а) Посетить узел.
б) Обойти левое поддерево.
) Функция определения глубины дерева. В качестве параметра в функцию
передается только узел дерева. Для нахождения глубины нам потребуется две
переменные: a и b, которые изначально равны нулю. В переменную b будет записываться глубина дерева,
переменная a - вспомогательная. Если узел
непустой, то осуществляется дальнейшая проверка условий: если a>b, то a=b. Если непустое левое поддерево, то а
увеличиваем на единицу и рекурсивно вызываем функцию с параметрами ptr->
pleft. Если левое поддерево непустое, то также увеличиваем переменную a на единицу и рекурсивно вызываем
функцию с параметром ptr->pright.
) Функция заполнения дерева случайными числами от 1 до 10 автоматически с
использованием функции rand.
Описание работы программного комплекса. Инструкция по работе
с программным комплексом
программный алгоритм данные бинарный
После запуска программы на экране пользователя появляется окно (см.
Рисунок 11), в котором будет выведены: номер варианта задания, формулировка
задания и список команды выполняемых программой.
Рисунок 11 -Запуск программы
Каждую команду можно активировать, нажав соответствующую клавишу на
клавиатуре («1» - Для заполнения дерева автоматически, «2» - Для ввода дерева
вручную, «3» - Для выхода из программы).
Если пользователем будет выбрана команда «3», то программа завершит
работу.
Команда «1» позволит пользователю самостоятельно заполнить дерево
элементами в диалоговом режиме. Также произойдёт вывод введённого дерева и
вывод обработанного дерева, а также их обход и глубина. (см. Рисунок 12).
Рисунок 12 - ввод дерева с клавиатуры
Выбрав команду «2», программа автоматически сгенерирует дерево заданной
длины, наполнив его случайными элементами. Произойдёт вывод этого дерева, затем
вывод дерева с удаленными повторяющимися элементами, а также их обходы и
глубина (см. Рисунок 13).
Рисунок
13 - Автоматическое генерирование дерева
Заключение
В ходе выполнения курсовой работы были Проанализированы различные способы
представления и использования двоичных деревьев поиска. Общие принципы
построения деревьев и методы удаления элементов из них.
Задача, поставленная в данной курсовой работе, является достаточно сложной
с точки зрения составления алгоритма. Помимо этого, она довольно сложна в плане
реализации, так как требует детального изучения и понимания предметной
области. Результатом выполнения курсовой работы является полноценное приложение
с отдельными функциями, разработанное в соответствии с современными подходами к
созданию программного обеспечения. Был разработан и реализован пользовательский
интерфейс, а также защита от возникновения ошибки при неправильном вводе. Также
написанное приложение решает поставленную ранее задачу и полностью
соответствует всем установленным для нее требованиям.
Выполнение данной работы позволило закрепить изученный материал, а также
получить новые, принципиально важные знания в области программирования,
проектирования и разработки программных продуктов.
Литература
1. «С++.
Освой на примерах» М. И. Динман - СПб: БХВ-Петербург, 2006. 384с.
. «Структуры
и алгоритмы обработки данных» И. В. Цапко - Томск: Изд-во Томского
политехнического университета, 2007. 184с.
. «/С++
и MS Visual C++ 2008 для начинающих» Б.И. Пахомов - СПб: БХВ-Петербург, 2009.
624с.
Приложения
Приложение А
Листинг программы
#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include <iomanip>
#include <time.h>
#pragma hdrstop//директива связана с особенностью работы препроцессора,
производительность которого
//существенно повышается, если учитывается, что некоторое количество
заголовочных файлов
//общие для всех модулей
#pragma argsused//говорит компилятору, что следует подавить выдачу
предупреждающего сообщения о том,
//что параметры функции main () никак в ней не используются.
//---------------------------------------------------------------------------namespace
std;TREE
{dann;*pleft;*pright;
};*root = NULL;*parent = NULL;i, k, b, n, c, p;tt = 0;array[100];*str =
new char [n];a = 0;cmax, cmin;
//---------------------------------------------------------------------------build(TREE
*tt, char str) // функция построения дерева
{*left;*right;(tt->dann==NULL)
{>dann=str;>pleft=NULL;>pright=NULL;
}
{(str<tt->dann)(tt->pleft == NULL)
{= new TREE;>pleft = left;>dann = str;>pleft = NULL;>pright =
NULL;
}build(tt->pleft, str);(tt->pright == NULL)
{= new TREE;>pright = right;>dann = str;>pleft = NULL;>pright
= NULL;
}build(tt->pright, str);
}
}
//---------------------------------------------------------------------------Delet1(TREE*
node, TREE*& parent) // функция удаления узла дерева
{(!node) return;
(!node->pleft && !node->pright)
{node;(parent) parent = 0;
}if (!node->pleft && node->pright)
{(parent) parent = node->pright;node;
}if (node->pleft && !node->pright)
{(parent) parent = node->pleft;node;
}
{* temp = node->pright;(temp->pleft)= temp->pleft;>pleft =
node->pleft;= node;= node->pright;= node;temp;
}
}
//---------------------------------------------------------------------------Solution(TREE*
node, TREE*& parent)//функция поиска повторяющихся элементов
{(array[node->dann])
{(node, parent);= parent;(!node) return;
}[node->dann] = true;(node->pleft) Solution(node->pleft,
node->pleft);(node->pright) Solution(node->pright, node->pright);
}
//---------------------------------------------------------------------------print
(TREE *first, int step) // функция печати дерева
{(first)
{(first->pright, step+1);(int i = 1; i <= step; i++) cout <<
" ";<< first->dann << endl;(first->pleft, step+1);
}
}
{(ptr)
{(ptr->dann);<< ' ';(ptr->pleft)
obhod(ptr->pleft);(ptr->pright) obhod(ptr->pright);
}
}
//---------------------------------------------------------------------------deep(TREE
*ptr) // функция определения глубины дерева
{(ptr)
{(a > b)
{= a;
}(ptr->pleft)
{
++a;(ptr->pleft);
}(ptr->pright)
{
++a;(ptr->pright);
}
}
}
//---------------------------------------------------------------------------RandomCreate(TREE*&
node, int n) // функция генерации случайных велечин
{(time(0));= new TREE;>dann = rand() % 9+48;>pleft =
node->pright = 0;(int i = 1; i < n; i++)(root, rand() % 9+48);
}
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------main()
// главная функция
{
//смена кодировки в консоли для отображения русских
символов(LC_ALL,"rus_rus.1251");
//Вывод задания на экран:<< "Вариант 1" << endl
<< "Построить двоичное дерево поиска из целых чисел.";<<
"Удалить из него элементы, встречающиеся несколько раз. ";<<
"Результат вывести на экран. Определить глубину дерева до и после
удаления."<<endl;n, count;<< "Выберите пункт:"
<< endl;<< "1 - Ввод с клавиатуры" << endl;<<
"2 - Ввод в автоматическом режиме" << endl;<< "3 -
Выход из программы" << endl;<< "-> ";: ;>>
count;(count)
{1:<< "Введите элементы дерева: ";>> str;=
strlen(str);= new TREE;>dann = str[0];>pleft = NULL;>pright = NULL;(i
= 1; i <n; i++) build(root, *(str+i));(i = 0; i < n; i++)[i] =
false;;2:<< "Введите количество элементов дерева: " <<
endl;>> n;(root, n);(i = 0; i < n; i++)[i] = false;;3:exit;;:<<
"Неверный ввод! Повторите ввод снова" << endl;M;;
}<< endl << "Построенное дерево: " << endl
<< endl;(root, 0);<< "Обход дерева: ";(root);<<
endl;(root);<< endl << "Глубина дерева составляет: "
<< b << endl;<< endl << "Дерево после обработки:
" << endl << endl;(root,root);(root,
0);(root);=b=0;(root);<< endl << "Глубина дерева после
обработки составляет: : " << b << endl;();: ;0;
}
//---------------------------------------------------------------------------