Войти на сайт

или
Регистрация

Навигация


Структуры данных: бинарное упорядоченное несбалансированное дерево

13634
знака
1
таблица
1
изображение

Казанский Государственный Технический Университет

им. А. Н. Туполева

Курсовая работа

по программированию

на тему

Структуры данных:

бинарное упорядоченное несбалансированное дерево

Выполнил: Зверев И. М. Проверил: Рахматуллин А. И.

Казань

2003


План работы:

1)    Постановка задачи

2)    Описание программы

3)    Код программы на языках Pascal и С++


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

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


2.          Описание программы

Описание ведётся для кода на Pascalе, отличия для С++ будут указаны ниже.

В программе основным элементом является класс TTree. Его методы – это основные процедуры работы с деревом:

Create – конструктор класса – процедура, создающая дерево,

Add – метод добавления элемента в дерево,

Del – метод удаления элемента из дерева,

View – метод вывода элементов дерева на экран,

Exist – метод проверки существования элемента с некоторым ключом, по сути поиск элемента,

Destroy – деструктор класса – процедура, удаляющая дерево.

Рассмотрим алгоритмы работы процедур.

Create – создание дерева. Присваивает полю Root (корень) значение nil – указателя, который никуда не указывает.

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

Del – удаление элемента из дерева.

Удаление узла довольно просто если он является листом или имеет одного потомка. Например, если требуется удалить узел с ключом М надо просто заменить правую ссылку узла К на указатель на L. Трудность заключается в удалении узла с двумя потомками, поскольку мы не можем указать одним указателем на два направления.

Например, если просто удалить узел с ключом N, то левый указатель узла с ключом Т должен указывать одновременно на К и R что не возможно. В этом случае удаляемый узел нужно заменить на другой узел из дерева. Возникает вопрос, каким же узлом его заменить? Этот узел должен обладать двумя свойствами: во-первых, он должен иметь не более одного потомка; во-вторых, для сохранения упорядоченности ключей, он должен иметь ключ либо не меньший, чем любой ключ левого поддерева удаляемого узла, либо не больший, чем любой ключ правого поддерева удаляемого узла. Таким свойствам обладают два узла, самый правый узел левого поддерева удаляемого узла и самый левый узел его правого поддерева. Любым из этих узлов им можно заменить удаляемый узел. Например, на рисунке это узлы М и Р.

Необходимо различать три случая:

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

Вспомогательная рекурсивная процедура del вызывается только в случае, когда удаляемый узел имеет двух потомков. Она “спускается вдоль” самой правой ветви левого поддерева удаляемого узла q^ (при вызове процедуры ей передается в качестве параметра указатель на левое поддерево) и, затем, заменяет существенную информацию (в нашем случае ключ data) в q^ соответствующим значением самого правого узла r^ этого левого поддерева, после чего от r^ можно освободиться.

View - печать дерева, обходя его справа налево. Чем дальше элемент от корня, тем больше ему будет предшествовать пробелов, т. о. путём несложного алгоритма получается вполне удобно читаемое дерево.

Exist – проверка существования элемента с заданным ключом. Ищем элемент, двигаясь от корня и переходя на левое или правое поддерево каждого узла в зависимости от его ключа.

Destroy – удаление дерева. Обходя дерево слева направо, удаляет элементы. Сначала удаляются потомки узла, затем сам узел.

Различия между описаниями кодов программах на разных языках относятся в основном к конструкторам и деструкторам. В .pas программах они определяются директивами и вызываются явно как методы класса из программы, а в .cpp конструктор вызывается при создании элемента класса и деструктор автоматически при выходе из программы (для чего объект класса размещается в памяти динамически).



Информация о работе «Структуры данных: бинарное упорядоченное несбалансированное дерево»
Раздел: Информатика, программирование
Количество знаков с пробелами: 13634
Количество таблиц: 1
Количество изображений: 1

Похожие работы

Скачать
362757
48
34

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

Скачать
237727
39
0

... , а иногда и невозможным. Недостатки MOLAP-модели: ·           Многомерные СУБД не позволяют работать с большими базами данных. ·           Многомерные СУБД по сравнению с реляционными очень неэффективно используют внешнюю память. В подавляющем большинстве случаев информационный гиперкуб является сильно разреженным, а поскольку данные хранятся в упорядоченном виде, неопределенные значения ...

Скачать
179431
27
82

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

Скачать
232852
0
0

... с приглашением по запросу (в машинной графике)required parameter обязательный параметрrequired space обязательный пробел (в системах подготовки текстов)requirements specification 1. техническое задание 2. описание требований к программному средствуrerun перезапуск, повторный запускreschedule переупорядочивать очередь (о диспетчере операционной системы)reschedule interval период переупорядочения ...

0 комментариев


Наверх