Алгоритмический язык Паскаль (стр. 25 из 31)

var X: SS;

begin

¦ N:= 1; X:= Y;

¦ while (X^.elem <> ZNACH) and (X^.next <> nil) do

¦ begin

¦ ¦ X:= X^.next; Z:= X;

¦ ¦ N:= N+1

¦ end;

¦ if X^.next = nil then

¦ begin N:= 0; Z:= nil; end;

end.

ПОЯСНЕНИЕ. С помощью данной процедуры в списке Y ищется звено с элементом ZNACH. Значение переменной N дает номер искомого звена, а переменная Z - ссылку на это звено. Если такого звена нет, то N = 0 и Z = NIL.

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

procedure SORTSPISOK (var X: SS);

{ X - Ссылка на начало списка }

var X1, Y1:SS; P: integer;

begin

¦ X1:= X; { Выбор элемента для сравнения }

¦ while X1^.next <> nil do { Проход по списку до

¦ предпоследнего элемента}

¦ begin

¦ ¦ Y1:=X1^.next;

¦ ¦ while Y1^.next <> nil do { Проход до последнего

¦ ¦ элемента }

¦ ¦ begin

¦ ¦ ¦ { Перестановка местами элементов}

¦ ¦ ¦ if Y1^.elem < X1^.elem then

¦ ¦ ¦ begin

¦ ¦ ¦ ¦ P:= X1^.elem; X1^.elem:= Y1^.elem;

¦ ¦ ¦ ¦ y1^.elem:= P;

¦ ¦ ¦ end;

¦ ¦ ¦ Y1:= Y1^.next; { Сдвигпосписку }

¦ ¦ end;

¦ ¦ X1:= X1^.next; { Сдвиг по списку }

¦ end;

end.

ПОЯСНЕНИЕ. В данной процедуре для сортировки использован метод прямого выбора, т.е. способ поиска минимального элемента и установка его в начало списка.

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

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

SPISOK

NEXT

PRED

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

…	*	*	*	…
…	*	*	*	…
	*	*	*
el	el	el
*	*	*
el	el	el
	*	*	*
…	…	…
Spi-1	SPi	Spi+1

Для реализации этой структуры необходимо задать два типа данных: SS - для обычных списков, SS1 - для дека суперсписка:

type SS = ^ZVENO;

ZVENO = record

el: integer;

next: SS;

end;

SS1 = ^ZVENO1;

ZVENO1 = record

pred1, next1: SS1;

SP: SS;

end.

ЗАМЕЧАНИЕ. В описании 3-го поля второго списка имеется тип SS из первого списка, что позволяет рассматривать каждое звено второго списка как начальное (очередное) звено первого. Для содержания всей этой структуры в рабочем состоянии достаточно хранить в памяти ссылку на один из указателей дека (начало или конец).

Заметим также, что в случае очереди целесообразно построение звена дека из 4-х полей: PRED1, NEXT1, SPL (начало очереди), SPR (конец очереди).

15. ДЕРЕВЬЯ

15.1 Характеристика древовидной структуры данных

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

Существует несколько способов изображения деревьев: вложения множеств, скобок, графы.

При ВЛОЖЕНИИ МНОЖЕСТВ используются хорошо известные в математике диаграммы Венна. Способ изображения дерева в виде ВЛОЖЕНИЯ СКОБОК менее нагляден, например, A(В(D,E)), C(F,G,H)).

Рассмотрим терминологию, присущую представлению дерева в виде графа:

1) элемент дерева - ВЕРШИНА, из которого связи только выходят, называют КОРНЕМ дерева (в нашем случае А);

2) связи между элементами дерева называются РЕБРАМИ;

3) если вершина В находится на графе ниже А, то В называется ПОТОМКОМ, а А - ПРЕДКОМ В;

4) каждая вершина находится на своем УРОВНЕ, причем корню соответствует 0-й уровень;

5) число уровней (или максимальный уровень) называют ВЫСОТОЙ или ГЛУБИНОЙ дерева;

6) если вершина не имеет потомков, то она называется ЛИСТОМ (в нашем примере F,G,H,D,E - листы);

7) вершины, лежащие между корнем и листьями, называют ВНУТРЕННИМИ.

Выделяют из всех деревьев так называемые УПОРЯДОЧЕННЫЕ деревья - такие, у которых ребра (т.е. соответствующие им элементы), выходящие из каждой вершины, упорядочены по какому-либо признаку. Для деревьев, элементами (вершинами) которых являются целые числа, упорядоченность устанавливается по возрастанию (убыванию) элементов.

Так, если дерево упорядочено по возрастанию, это означает, что самое левое ребро на графе заполнено наименьшим числом.

НАПРИМЕР:

5

/ &bsol;

3 10

/ &bsol; / &bsol;

2 4 9 12

2 < 3 < 5 < 10 < 12; 2 < 3 < 4;

3 < 10;

2 < 4 < 9 < 12; 9 < 10 < 12.

Особый интерес представляют деревья, у которых из каждой вершины может исходить не более 2-х (т.е. ни одного, одно или два) ребер. Такие деревья называют ДВОИЧНЫМИ или БИНАРНЫМИ, либо деревьями 2-й степени.

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

R

/ &bsol;

O W

/ | &bsol; &bsol;

E Q X H

Бинарное дерево принято также называть ГЕНЕАЛОГИЧЕСКИМ:

X -внук

/ &bsol;

сын - Y Z -дочь

/ &bsol; / &bsol;

A B C D

мать отец мать отец

ОПРЕДЕЛЕНИЕ: дерево называется ПРЕДЕЛЬНО (ИДЕАЛЬНО) СБАЛАНСИРОВАННЫМ, если разница между числом вершин в его левых и правых поддеревьях (на всех уровнях) не более 1.

15.2 Построение идеально сбалансированного дерева

Для построения такого дерева используется рекурсивное правило:

1. Пусть требуется построить дерево из N элементов (вершин).

Выберем один из них в качестве корня.

2. Строим левое поддерево с количеством вершин NL = N div 2.

3. Так же строим правое поддерево с числом вершин NR = N-NL-1.

Например, при построении дерева из 5 элементов:

1) один элемент идет на корень;

2) оставшиеся 4 элемента разбиваются на два поддерева:

NL = 2 и NR = 2;

3) в каждом из поддеревьев один элемент идет на корень, а другой - на лист: NL1= 1, NR1= 0.

Очевидно, что для отображения структуры дерева в память ЭВМ требуется построение динамических объектов.

Здесь K-ELEMENT есть вершина дерева, а LEFT и RIGHT - поля ссылок на левую и правую вершины поддеревьев.

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

У данной процедуры в качестве параметра-аргумента выступает число элементов (вершин) дерева, а значением функции является ссылка - указатель на следующую вершину (левую и правую). Сами элементы запрашиваются с клавиатуры:

function FORMIRTREE (N: integer): SS;

var Z: SS; NL, NR: integer;

begin

¦ if N = 0 then Z:= nil {Пустоедерево}

¦ else

¦ begin

¦ ¦ NL:= N div 2; NR:= N-Nl-1; new(Z);

¦ ¦ write('Ввестивершину'); readln(Z^.k);

¦ ¦ Z^.right:= FORMIRTREE (NR);

¦ end;

¦ FORMIRTREE:= Z; {Запоминание ссылки на корень дерева}

end.

ПОЯСНЕНИЕ. Сначала все N-1 элементов разбиваем на две части - левую и правую. Затем каждую часть соответственно делим на две. Рекурсия прекращается, когда N становится равным нулю - деление закончено, последняя образованная ссылка указывает на корневой элемент:

1
	left	right
2	4
left	left
3	right	5	right

Дерево имеет 2 уровня, на нижнем (втором) уровне располагаются только левые листы (правые отсутствуют из-за нехватки элементов).