Алгоритм на псевдокоде

(на примере пузырьковой сортировки)

B:=(1,2,…,n)

DO (i=1,2,…,n-1)

DO(j=n,n-1,…,i+1)

IF(a[b_j]< a[b_j-1]) b_i↔b_j-1 FI

OD

OD

Отметим ряд положительных свойств индексации.

1. Индексация дает возможность построения нескольких различных индексов, которые можно использовать по мере необходимости.

2. Исключается копирование больших массивов данных (физический массив остаётся на месте, а индексы занимают мало места).

3. Имеется возможность фильтрации данных. Фильтрация означает, что при работе с базами данных используются не все элементы, а только те, которые отвечают определённым условиям. В индекс включаются физические номера тех элементов, которые удовлетворяют условию фильтра.

8.3 Индексация через массив указателей

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

8.4 Варианты заданий

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

1. упорядочить справочник по имени по возрастанию

2. упорядочить справочник по телефонному номеру по возрастанию

3. упорядочить справочник по адресу по убыванию

4. выбрать тех абонентов, которые имеют номер в заданном диапазоне

5. упорядочить справочник по имени и телефонному номеру по возрастанию

6. выбрать тех абонентов, которые имеют имя в заданном диапазоне

7. выбрать абонентов, которые имеют имя и адрес в заданном диапазоне

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

9.1 Основные определения и понятия

Определим двоичное дерево следующим образом :

1. Отдельная вершина V является двоичным деревом.

2. Двоичное дерево – это вершина V, соединенная с (возможно пустыми) левым (Т_L) и правым (Т_R) двоичными деревьями.

Пример двоичного дерева приведен на следующем рисунке. Вершины дерева обозначаются кружочками, связи между вершинами стрелками.

Рисунок 27 Пример двоичного дерева

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

Приведем некоторые свойства двоичных деревьев.

Свойство 1. Максимальное число вершин в двоичном дереве высоты h равно

n_max(h)= 2^h – 1

Свойство 2. Минимально возможная высота двоичного дерева с n вершинами равна h_min(n) = élog(n+1)ù

9.2 Различные обходы двоичных деревьев

При разработке алгоритмов для работы с деревьями будем считать, что каждая вершина содержит некоторые данные и указатели на вершины слева и справа. Поэтому вершина дерева это переменная специального типа. В качестве заголовка для дерева используем переменную Root, указывающую на корень.

type pVertex = ^tVertex;

tVertex =record

Data: integer;

Left: pVertex;

Right: pVertex;

end;

VAR Root: pVertex;

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

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

1. Сверху вниз (↓): корень, левое поддерево, правое поддерево.

2. Слева направо (→): левое поддерево, корень, правое поддерево.

3. Снизу вверх (↑): левое поддерево, правое поддерево, корень.

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

Результат обхода: 4 2 5 1 3 6

Рисунок 28

Обходы легко программируются с помощью рекурсивных процедур.