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

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

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

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

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

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

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

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

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

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

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

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

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

Савенко И.И.

Томск - 2013

Введение

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

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

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

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

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

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

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

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

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

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

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

Деревом называется одна из наиболее широко распространённых структур данных <#"justify">У любого дерева есть корень. Это узел, расположенный в самом верху дерева (см. Рисунок 1). У дерева может быть только один корень.

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

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

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

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

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

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

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

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

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

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