Размещено на http://www.allbest.ru/
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
«НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ
ТОМСКИЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»
Институт дистанционного образования
Кафедра Автоматики и компьютерных систем
Направление «Управление в технических системах»
Пояснительная записка к курсовой работе
по дисциплине «Структуры и алгоритмы обработки данных»
Студент гр. З-8001
Поспелова И.В.
Ассистент каф. АиКС
Савенко И.И.
Томск – 2013
Введение
Целью данной курсовой работой является разработка программного комплекса, позволяющего проиллюстрировать работу с иерархическими структурами данных.
Для выполнения данной задачи был использован один из универсальных языков программирования - язык С++. Выбор данного языка обусловлен тем, что он широко используется для создания программ самого разного назначения: начиная от создания операционных систем и заканчивая созданием видеоигр. Этот язык программирования позволяет программисту сделать практически все. Кроме того, C++ - это "чистый" язык, язык в котором нет "заточенности" на ту или иную библиотеку или стиль программирования. С++, в отличие от многих, не привязан ни к чему. Это дает программисту на С++ поразительное количество возможностей и вариантов запрограммировать даже самое простое действие. Кроме того, С++ поддерживает мультипарадигменное программирование, то есть возможность пользоваться при написании программ многими стилями программирования.
Кроме того, в процессе написания курсовой работы потребуется знание о такой иерархической структуре данных как двоичное дерево, а также способов организации этого типа данных при помощи языка С++.
Задание на курсовую работу
Построить двоичное дерево поиска из целых чисел. Удалить из него элементы, встречающиеся несколько раз. Результат вывести на экран. Определить глубину дерева до и после удаления.
Требования, предъявляемые к программному комплексу:
Программный комплекс должен состоять из нескольких функций, каждая из которых призвана решать свою специфическую задачу. Например, функция построения дерева, функция вывода на экран построенного дерева и т.д.
2) После запуска программного комплекса, на экране должно быть выведено задание, для решения которого и разработан программный комплекс.
3) Работа программного комплекса должна быть организована в диалоговом режиме с пользователем. Например, пользователь по запросу вводит количество элементов исходного дерева, после решения задачи на экран выводится результат со всеми необходимыми пояснениями. Должно быть предусмотрено два способа ввода информации в дерево – автоматическая генерация случайных данных, ввод данных самим пользователем с клавиатуры.
4) После работы динамическая структура должна быть удалена.
5) В программном комплексе должны осуществляться все возможные проверки, в частности: на корректность исходных данных.
Предметная область
Прежде чем приступать к решению задачи, необходимо ознакомиться с предметной областью.
Деревом называется одна из наиболее широко распространённых структур данных в информатике, эмулирующая древовидную структуру в виде набора связанных узлов. Прежде всего, дерево является связанным графом, не содержащим циклы.
У любого дерева есть корень. Это узел, расположенный в самом верху дерева (см. Рисунок 1). У дерева может быть только один корень.
К любому узлу дерева можно дойти из корня. Кроме того, существует только один путь связывающий корень и узел. Следует обратить внимание на то, что любой узел дерева сам по себе является деревом и именуется поддеревом.
Расстояние от корня до узла называется уровнем. Корень расположен на нулевом уровне.
Глубина дерева – это максимальный уровень любого его узла. Или глубина дерева – это длина самого длинного пути от корня до узла.
Если между узлами b и a есть дуга, и узел a расположен на более высоком уровне, то a называется – родителем (предком), а b - потомком. Каждый узел дерева является корнем поддерева, которое состоит из данного узла и всех его потомков. У узла дерева может быть любое количество потомков.
Самые нижние узлы дерева называют листьями, и они не имеют потомков.
Рисунок 1 - Дерево