31. Структуры данных. Древовидная таблица

Дерево – это набор вершин и связей между ними (дуг), которые удовлетворяют следующим правилам:

1. Каждая вершина, кроме корня, имеет только одну предыдущую вершину (родителя).

2. Корень не имеет родителя и является единственным в дереве.

Вершина дерева может иметь несколько или не иметь потомков.

Степень вершин – количество потомков.

Лист – вершина без потомков.

Степень дерева – максимальная степень его вершин.

Вершины дерева располагаются по уровням.

Уровень – расстояние от вершины до корня.

Глубина (уровень) – максимальный уровень вершины.

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

	Ключ	информация	ЛП	ПП
0	5	…	2	1
1	8	…	-1	-1
2	3	…	-1	3
3	4	…	-1	-1
..	…	…	…	…

33. Структуры данных. Двоичные деревья.

Двоичное дерево – дерево со степенью два.

Для построения дерева используется следующий типовой элемент:

код вершины

указатель на левого потомка

указатель на правого потомка

Наиболее широкое распространение получило двоичное упорядоченное дерево, оно имеет упорядоченность вершин.

Для каждой вершины выполняется правило: код текущей вершины больше всех вершин левого поддерева (ЛП) и меньше всех кодов вершин правого поддерева (ПП).

Поиск вершины.

Алгоритм поиска

k – код вершины;

р – указатель на текущую вершину;

х – код текущей вершины;

t – указатель на корень дерева.

1. p присвоить значение t.

2. Если р – пустой указатель, то вершина отсутствует, Конец

3. Значение кода текущей вершины сравнивается с искомым кодом:

а) k = x, вершина найдена, Конец;

б) k < x, указатель на левое поддерево;

в) k > x, указатель на правое поддерево.

п.2

Обход дерева

Результатом операции обхода дерева является список вершин дерева.

Существует три способа обхода бинарных деревьев:

1) в прямом порядке: попасть в корень, пройти левое поддерево, пройти правое поддерево;

2) в обратном порядке: пройти левое подд, попасть в корень, пройти правое подд;

3) в концевом порядке: пройти левое подд, пройти правое подд, попасть в корень.

Операция добавления

Добавление в упорядоченном дереве включает в себя:

1. Поиск.

2. Если заданная вершина отсутствует, то добавление.

Добавление всегда выполняется в лист дерева, т.е. добавляемая вершина всегда является листом. Добавление происходит в ту ветку, где прекращен поиск.

Операция удаления

Выполняется в два действия:

1. Поиск вершины.

2. Если он успешен. то удаление вершины.

Операция удаления вершины имеет три варианта решения, которые зависят от связи вершины с другими.

1. Вершина-лист

В этом случае удаление вершины заключается в удалении самой вершины и обнулении указателя на текущую вершину в родительской вершине.

2. Удаляется вершина с одним потомком.

Удаление вершины заключается в перенаправлении указателя на текущую вершину на вершину-потомок, а затем удаление самой вершины.

3. Удаление вершины с двумя потомками.

Существуют два правила удаления такой вершины:

1. Указатель на текущую вершину перенаправляется на вершину (корень) левого поддерева, а вершина (корень) правого поддерева присоединяется к самой правой вершине левого поддерева.

2. Указатель перенаправляется на корень правого поддерева, а корень левого поддерева присоединяется к самой левой вершине правого поддерева.

36.Структуры данных. Б – деревья.

Структуры данных (абстрактные структуры) – это математические модели, предназначенные для представления информации об объектах и о процессах. Структуры хранения данных – это структуры представления информации в компьютере, с помощью которых представляются структуры данных.

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

Относятся к классу сильно ветвящихся деревьев. Дерево строится на основе следующего типового элемента, который является вершиной дерева:

	k1	k2	…	kn
p0	p1	p2	…	pn

Вершина дерева содержит n ключей и (n+1) указателей.

Указатель p₀ указывает на поддерево, содержащее ключи, меньше k₁, p_n указывает на ключи, большие k_n, p_i указывает на ключи, большие k_i и меньшие k_i+1.

Ключи отсортированы в порядке возрастания:

Свойства В – дерева.

1. В каждой вершине за исключением корня, имеют от n/2 до n-ключей. В корне от одного до n ключей.

2. Ключи расположены в порядке возрастания их значений.

3. Все листья дерева находятся на одном уровне.

Для указанного дерева обычно рассматриваются операции выборки и добавления.

Для выполнения этих операций выполняется поиск ключа в дереве.

Алгоритм поиска:

1. Указатель на текущую вершину получает адрес корня дерева;

2. Если указатель пуст, то искомого значения нет, ошибка, и переход к пункту 5

3. Производится поиск требуемого значения вершин текущей вершины (применяется двоичный поиск). Если значение найдено, то поиск успешный и переходим к пункту 5.

4. Если ключа нет, то указателю на текущую вершину присваивается значение соответствующего указателя по значению ключа. Переход к п.2.

5. Конец

Добавление вершины:

1. Поиск вершины с заданным ключом, если ключ обнаружен, то завершение с ошибкой.

2. Добавление заданного ключа в последнюю обрабатываемую вершину. Если число ключей в вершине равно n, то разбиение общего списка ключей на 2 подмножества и создается новый лист с вынесением среднего ключа в вершину-родитель.

3. Повторяется до нормальной вставки нового значения элемента.

Б-деревья используются в тех случаях, когда невозможно заданное множество ключей расположить в оперативной памяти. Т.е. нет возможности работать со всем деревом сразу. Таким образом, часть дерева будет в оперативной памяти, а часть дерева будет во внешней памяти и вершины дерева будут вызываться в оперативную память по мере надобности. Вершины Б-дерева называются страницами и их размер соответствует минимальной или кратной единицы хранения данных на внешнем носителе. Ссылки на вершину представляют собой указатель на место вершины на внешнем носителе.

37. Документирование программ. Спецификация.

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

Основным элементом спецификации является типизация(строгая фиксация структуры объекта с указанием порядка размещения элементов и перечня возможных значения элемента.) Понятие типизации применимо к переменным и процедурам и функциям. Для выполнения работ по разработке программ составляют спецификации на структуры и процедуры и функции.

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

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

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