Реализация прикладной задачи при помощи двунаправленных деревьев

ОГУ 220400.62.5014.143 О

 

 

Руководитель работы

старший преподаватель

______________ И.И Стрекалова

"_____"________________2014 г.

Исполнитель

студент гр.11 УТС(б)УИТС

________________ Д.В. Емельянов

"_____"________________2014 г.

 

 

Оренбург 2014

 

Министерство образования и науки Российской Федерации

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ОРЕНБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

 

Факультет информационных технологий

Кафедра управления и информатики в технических системах

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

Реализация прикладной задачи при помощи двунаправленных деревьев.

 

Исходные данные: литература по структурам и алгоритмам обработки данных,

данные сети Интернет.

 

Перечень подлежащих разработке вопросов:

а) раскрыть содержание двунаправленного дерева;

б) выявить основные задачи по реализации данной темы;

в) обосновать перспективы двунаправленных деревьев.

 

Перечень графического материала:

Рисунки, отображающие работу реализуемой программы.

 

 

Дата выдачи задания “__”____________20__г.

 

Руководитель работы

старший преподаватель И.И Стрекалова

Исполнитель

студент гр.11 УТС(б)УИТС Д.В. Емельянов

Срок защиты работы “__”____________20__г.

 

Содержание

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

Введение. 4

1 Структура данных дерева и основные операции над деревьями. 5

1.1 Основные понятия связанные с деревьями. 5

1.2 Классификация деревьев. 6

1.2.1 Двоичные деревья. 6

1.2.2 Представление двоичных деревьев. 8

1.2.3 Упорядоченное двоичное дерево и его свойства. 8

1.3 Двоичные деревья поиска. 9

1.4 Основные операции над деревьями. 11

2.1 Постановка задачи. 27

2.2 Глобальные и локальные переменные. 27

2.2.1 Глобальные переменные. 27

2.2.2 Локальные переменные. 28

2.3 Процедуры и функции. 28

2.3.1 Процедуры программы.. 28

2.3.2 Функции программы.. 29

2.4 Инструкция пользования. 30

Заключение. 33

Список использованных источников. 34

Приложение А.. 35

Приложение Б. 39

(обязательное) 42

 

Введение

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

В результате работы требуется создать программу – базу данных клиентов банка «Клиенты банка», которая будет работать с такими структурами данных как «двунаправленные деревья», с внешними файлами и иметь понятный интерфейс. Предметом является двунаправленное дерево, а объектом – операции над деревьями.

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

Для достижения поставленной цели нужно решить следующие задачи:

- возможность добавления записей в базу данных;

- возможность считывания данных из файла;

- просмотр базы данных;

- поиск по базе данных.

 

 

Структура данных дерева и основные операции над деревьями

Основные понятия связанные с деревьями

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

Дерево – это совокупность элементов, называемых узлами (один из которых определен как корень), и отношений («родительских»), образующих иерархическую структуру узлов. Вообще говоря, древовидная структура задает для элементов дерева (узлов) отношение «ветвления», которое во многом напоминает строение обычного дерева.

Формально дерево (tree) определяется как конечное множество T одного или более узлов со следующими двумя свойствами. Существует один выделенный узел, а именно – корень (root) данного дерева. Остальные узлы (за исключением корня) распределены среди m?0 непересекающихся множеств T 1, T 2, …. T m, и каждое из этих множеств, в свою очередь, является деревом; деревья T 1, T 2,... T m называются поддеревьями данного корня.

Как видите, это определение является рекурсивным: дерево определено на основе понятия дерево. Рекурсивный характер деревьев можно наблюдать и в природе, например, почки молодых деревьев растут и со временем превращаются в ветви (поддеревья), на которых снова появляются почки, которые также растут и со временем превращаются в ветви (поддеревья) и т.д. Можно привести еще одно формальное определение дерева. Один узел является деревом. Этот же узел также является корнем этого дерева.

Пусть n – это узел, а T 1, T 2,... T m – деревья с корнями n 1, n 2, … n m соответственно. Можно построить новое дерево, сделав n родителем узлов n 1, n 2, … n m. В этом дереве n будет корнем, а T 1, T 2,... T m – поддеревьями этого корня. Узлы n 1, n 2, … n m называются сыновьями узла n.

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

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

 

Узел A является корнем, который имеет два поддерева { B } и { C, D, E, F, G }. Корнем дерева{ C, D, E, F, G } является узел C. Уровень узла C равен 1 по отношению ко всему дереву. Он имеет три поддерева { D }, { E }и { F, G }, поэтому степень узла C равна 3. Концевыми узлами (листьями) являются узлы B, D, E, G.

Путем из узла n 1 в узел n k называется последовательность узлов n 1, n 2, … n k, где для всех i, 1? i? k, узел n i является родителем узла n i +1. Длиной пути называется число, на единицу меньшее числа узлов, составляющего этот путь. Таким образом, путем нулевой длины будет путь из любого узла к самому себе. Например, на рисунке путем длины 2 будет путь от узла A к узлу F или от узла C к узлу G.

Если существует путь из узла a в узел b, то в этом случае узел a называется предком узла b, а узел b – потомком узла a. Отметим, что любой узел одновременно является предком и потомком самого себя. Например, на рисунке предками узла G будут сам узел G и узлы F, C и A. Потомками узла C будут являться сам узел C и узлы D, T, F, G. В дереве только корень не имеет предков, а листья не имеют потомков.

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

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

Лес – это множество (обычно упорядоченное), содержащее несколько непересекающихся деревьев. Узлы дерева при условии исключения корня образуют лес[1].