- •А.Н. Горитов
- •Учебное пособие
- •Учебное пособие
- •Введение
- •1 Введение в предмет
- •1.1 Непрерывная и дискретная информация
- •1.2 Данные и эвм
- •1.3 Объекты предметной области
- •1.4 Представление информации об объектах
- •1.5 Абстрактные алфавиты. Кодирование
- •2 Основные типы и структуры данных эвм
- •2.1 Архитектурные особенности эвм, наиболее существенные для представления данных
- •2.2 Основные понятия о типах и структурах данных
- •2.3 Массивы
- •2.4 Строки
- •2.5 Записи
- •2.6 Записи с вариантами
- •2.7 Множества
- •3 Последовательный файл
- •3.1 Основные свойства последовательных файлов
- •3.2 Сортировка последовательных файлов
- •4 Полустатические структуры
- •4.1 Стек, очередь и дек как полустатические структуры
- •4.2 Представление полустатических структур с помощью массивов
- •5 Линейные динамические структуры
- •5.1 Основные свойства динамических структур
- •5.2 Реализация связного списка массивом
- •5.3 Кольцевой связный список
- •5.4 Линейный двусвязный список
- •6 Представление динамических структур с помощью указателей
- •6.1 Указатели
- •6.2 Представление стека
- •6.3 Представление очереди
- •6.4 Ведение динамических списков с помощью указателей
- •6.5 Алгоритм составления кольцевого двусвязного списка
- •7 Древовидные структуры данных
- •7.1 Основные понятия и определения
- •7.2 Представление деревьев в эвм
- •7.3 Основные операции с бинарными деревьями
- •7.4 Сильно ветвящиеся деревья
- •8 Алгоритмы на графах
- •8.1 Машинное представление графов
- •8.2 Поиск в глубину в графе
- •8.3 Поиск в ширину в графе
- •8.4 Стягивающие деревья (каркасы)
- •8.5 Отыскание фундаментального множества циклов в графе
- •8.6 Эйлеровы пути в графе
- •8.7 Алгоритмы с возвратом
- •8.8 Нахождение кратчайших путей в графе
- •8.9 Кратчайшие пути от фиксированной вершины
- •8.10 Алгоритм Дейкстры
- •8.11 Пути в бесконтурном графе
- •Литература
7.2 Представление деревьев в эвм
Рассмотрим проблему представления деревьев. Ясно, что представление таких структур с разветвлениями предполагает использование ссылок. Не имеет смысла описывать переменные с фиксированной древовидной структурой. Вместо этого узлы определяются как переменные с фиксированной структурой, а связи между ними – с помощью динамических указателей. Степень дерева при этом определяет число компонент-указателей каждого узла. Ссылка на пустое поддерево обозначается, естественно, через Nil.
Таким образом наше дерево – арифметическое выражение – можно считать состоящим из компонент типа: TYPE NODE = RECORD
INF : CHAR; LEFT, RIGHT : ^NODE END; и наше дерево может быть представлено следующей структурой (рис. 19).
Nach 1 |
► * |
| ||||||||
|
s I ч |
| ||||||||
|
|
|
|
|
|
| ||||
|
+ < |
|
- |
| ||||||
|
/ 1 ^ |
A 1 * |
| |||||||
У |
г |
\ |
|
|
У \ |
| ||||
a |
|
/ |
|
d |
|
/ |
| |||
Nil Nil |
Г 1 i |
Nil Nil |
|
г I • |
| |||||
|
|
I |
|
1 |
|
|
|
I |
1 |
|
|
b |
|
с |
|
/ |
1 |
e | |||
|
Nil Nil |
Nil Nil |
Nil Ni |
Nil Nil |
Рис. 19 Дерево, представленное как структура данных
Формирование дерева в программе может быть выполнено с помощью рекурсивной функции TREE. Предположим, что нужно построить дерево с n узлами и минимальной высотой (т.е. расположить максимальное число узлов на всех уровнях кроме последнего). При этом значениями узлов будут N чисел, прочитанных из входного файла. Пусть TYPE REF = ^NODE;
NODE = RECORD
KEY: integer; { содержание узла – число } LEFT, RIGHT: REF END; VAR N: INTEGER; { число узлов дерева }
ROOT: REF; Чтобы построить такое дерево, нужно постараться расположить все поступающие узлы поровну слева и справа от каждого узла. Такое дерево называется идеально сбалансированным.
Правила, по которым действует процедура TREE, можно сформулировать следующим образом:
взять один узел в качестве корня;
построить левое поддерево с NL = N DIV 2 узлами;
построить правое поддерево с NR = N - NL - 1 узлами тем же способом. Тогда функция:
FUNCTION TREE(N: INTEGER): REF; VAR NEWNODE : REF;
X, NL, NR : INTEGER; BEGIN
IF N = 0 THEN TREE := Nil ELSE BEGIN
NL := N div 2; NR := N - NL - 1;
READ(x); NEW(NEWNODE);
WITH NEWNODE^ DO BEGIN KEY := X; LEFT := TREE(NL); RIGHT := TREE(NR);
END;
TREE := NEWNODE; END END { TREE }
7.3 Основные операции с бинарными деревьями
Над древовидными структурами выполняются три основные операции:
обход (просмотр) дерева с целью нахождения нужного узла;
добавление узла или поддерева в дерево;
удаление узла из дерева.
Обход двоичного дерева
Если рассматривать задачу обхода дерева как единый последовательный процесс, то отдельные узлы посещаются в определенном порядке и могут считаться расположенными линейно. Для обхода бинарного дерева обычно используется один из трех способов:
обход сверху вниз – А, В, С (посетить корень до поддеревьев);
обход слева направо – В, А, С;
обход снизу вверх – В, С, А (посетить корень после поддеревьев). Каждая из этих трех процедур включает в себя в различном порядке следующие
шаги:
просмотр корня поддерева,
обход левого поддерева,
• обход правого поддерева. Обходя наше дерево и выписывая символы, находящиеся в узлах в том порядке, в котором они встречают ся, получим следующие последовательности:
сверху вниз: * + a / b c - d * e f ; (1)
слева направо: a + b / c * - e * f; (2)
снизу вверх: a b c / + d e f * - *; (3) Получили три формы записи выражений, известные как
– префиксная запись;
– инфиксная запись (привычная для нас форма, хотя и без скобок, необходимых для определения порядка выполнения операций);
– постфиксная запись.
Теперь можно описать эти три способа обхода как процедуры с явным параметром T, обозначающим дерево и неявным P(T), означающим операцию, которую нужно выполнять с каждым узлом.
Введем определения: TYPE REF = ^NODE;
NODE = RECORD
LEFT, RIGHT: REF END; Легко выразить три перечисленных метода обхода как рекурсивные процедуры. Они также являются иллюстрацией того, что действия с рекурсивно определенными структурами данных лучше всего описываются рекурсивными алгоритмами. Сверху вниз:
PROCEDURE PREFIX(T: REF); BEGIN IF T <> Nil THEN BEGIN
P(T); { обработка узла }
PREFIX(T^.LEFT);
PREFIX(T^.RIGHT);
END; END;
Слева направо: PROCEDURE INFIX(T: REF); BEGIN IF T <> Nil THEN BEGIN
INFIX(T^.LEFT);
P(T);
INFIX(T^.RIGHT);
END;
END;
Снизу вверх:
PROCEDURE POSTFIX(T: REF);
BEGIN
IF T <> Nil THEN BEGIN
POSTFIX(T^.LEFT);
POSTFIX(T^.RIGHT);
P(T);
END; END;
Заметим, что в этих процедурах ссылка Т передается как параметр-значение. Т.е. здесь существенна сама ссылка (указание) на рассматриваемое поддерево, а не переменная, значение которой есть эта ссылка и которая могла бы изменить значение, если бы Т передавался как параметр-переменная.
Пример программы обхода дерева – программа печати узлов дерева с соответствующим сдвигом, выделяющим каждый уровень.
PROCEDURE PRINTTREE(T: REF, H: INTEGER); { T - указатель на вершину, H - сдвиг при печати } VAR I: INTEGER;
BEGIN { печать дерева Т со сдвигом Н } IF T <> Nil THEN
WHITH T^ DO BEGIN
PRINTTREE(LEFT, H+1); { обход левой ветви }
FOR I := 1 TO H DO WRITE(‘ ‘); { сдвиг }
WRITELN(KEY); { печать ключа }
PRINTTREE(RIGHT, H+1) { обход правой ветви }
END; END;
Вызывающая программа: BEGIN
ROOT := TREE(N); { УКАЗАТЕЛЬ КОРНЯ }
PRINTTREE(ROOT,0) END.
Задача поиска
Очень часто приходится решать следующую задачу: найти элемент с нужным значением ключа. Эту задачу приходится решать с использованием массивов, списков, деревьев. Эта задача решается по-разному в случае неупорядоченных или упорядоченных по возрастанию ключей элементов. В последнем случае можно не просматривать все элементы, а доходить только до элемента с ключом большим, чем требуемый.
Существует два альтернативных способа поиска: последовательный и двоичный. В последовательном списке может применяться только последовательный поиск в порядке следования указателей. В двоичном дереве естественным является двоичный поиск. В массиве может быть организован как тот, так и другой алгоритм.
Поставим задачу так: найти наименьший индекс (указатель) компоненты списка со значением ключа, равным Х.
Последовательный поиск в массиве
Пусть массив:
VAR A: ARRAY[1..N] OF INTEGER;
X: INTEGER; FUNCTION LOC(X: INTEGER): INTEGER; VAR I: INTEGER; BEGIN
I := 0;
REPEAT
I := I+ 1
UNTIL (A[I] = X) OR (I = N);
IF A[I] <> X THEN LOC := 0
ELSE LOC := I END;
Процедура работает как для неупорядоченных, так и для упорядоченных массивов.
Неудобство функции в том, что проверка условия окончания сложная. Программу можно ускорить, если поставить "барьер", т.е. увеличить массив на один элемент и заслать туда значение искомого ключа.
I := 0; A[N+1] := X; REPEAT
I := I + 1; UNTIL A[ I ] = X;
IF I > N THEN LOC := 0 ELSE LOC := I; Среднее число просмотров m = N / 2.
Двоичный поиск в массиве (бинарный)
Применяется для упорядоченных массивов. При двоичном поиске используется метод деления пополам. Алгоритм: I := 1; J := N; REPEAT
K := (I + J) DIV 2;
IF X > A[K] THEN I := K + 1 ELSE J := K - 1 UNTIL (A[K] = X) OR (I > J) Число просмотров m = log2N. При N = 100: последовательный поиск выполнится за 50 просмотров (m = 50), двоичный за 6,62 (m = 6,62).
Поиск в линейном списке
Как и в файле, поиск ведется строго последовательно. Он заканчивается либо когда элемент найден, либо когда достигнут конец списка. Самое простое решение: WHILE (P <> Nil) AND (P^.KEY <> X) DO
P := P^.NEXT Если элемента в списке нет, то при Р равном Nil нет следующего элемента P^.KEY. Поэтому надо ввести вторую часть проверки WHILE P<> Nil DO
IF P^.KEY = X THEN { выход из цикла } ELSE P := P^.NEXT; Лучше воспользоваться логической переменной (флажком): B := TRUE; WHILE (P <> Nil) AND B DO
IF P^.KEY = X THEN B := FALSE
ELSE P := P^.NEXT; Элемент не найден, если P = Nil и B = TRUE.
Поиск в двоичном дереве
Бинарные деревья часто используются для представления данных, элементы которых ищутся по уникальному, только им присущему ключу.
Если для каждого узла ti дерева все ключи в левом поддереве меньше ключа ti, а все ключи в правом поддереве больше ключа ti, то это дерево упорядочено по ключам и называется деревом поиска. В дереве поиска можно найти место каждого ключа, двигаясь от корня и переходя на левое или правое поддерево каждого узла в зависимости от значения его ключа.
Можно убедиться в том, что из N элементов организуется двоичное дерево с высотой не более log2N. Поэтому для поиска среди N элементов может потребоваться не более log2N сравнений, если дерево идеально сбалансировано.
В этом преимущество дерева перед линейным списком, в котором для поиска может потребоваться N сравнений.
Поиск в упорядоченном двоичном дереве проводится по единственному пути от корня к искомому узлу (т.к. он проходит по единственному пути от корня к искомому узлу) и может быть описан с помощью итерационной функции LOC.
FUNCTION LOC(X: INTEGER; T: REF): REF;
VAR FOUND: BOOLEAN;
BEGIN
FOUND := FALSE;
WHILE (T <> Nil) AND NOT FOUND DO
IF T^.KEY = X THEN FOUND := TRUE ELSE IF T^.KEY > X THEN T := T^.LEFT ELSE T := T^.RIGHT LOC := T END;
Функция LOC(X, T) имеет значение Nil, если в дереве с корнем Т не найдено ключа со значением Х. Условие выхода из цикла можно упростить, если организовать еще один тупиковый узел, на который замкнуть все "листья" дерева (рис. 20).
s
Рис. 20 Дерево поиска с барьером Получили дерево, у которого все листья как бы привязаны к одному якорю или барьеру. Тогда упрощенная процедура поиска запишется так: FUNCTION LOC(X: INTEGER; T: REF): REF; BEGIN
S^.KEY := X;
WHILE T^.KEY <> X DO
IF X < T^.KEY THEN T := T^.LEFT
ELSE T := T^.RIGHT; LOC := T END;
Если в дереве с корнем Т не найдено ключа со значением Х, то в этом случае LOC(X, T) принимает значение S, т.е. ссылки на барьер. Ссылка на S просто принимает на себя роль ссылки Nil.
Включение нового узла в дерево
Хорошим примером, иллюстрирующим операцию включения нового узла в дерево, является построение частотного словаря. В этой задаче дана последовательность слов и нужно установить число появлений каждого слова. Это означает, что начиная с пустого дерева, каждое слово ищется в дереве. Если оно найдено, увеличивается счетчик его появлений, если нет – в дерево вставляется это новое слово (с начальным значением счетчика, равным 1). Можно назвать эту задачу поиском по дереву с включением.
Для простоты предполагаем, что слова уже выделены из исходного текста, закодированы целыми числами и находятся во входном файле.
Пусть типы описаны следующим образом: TYPE REF = ^WORD; WORD = RECORD
KEY: INTEGER; COUNT: INTEGER; LEFT, RIGHT: REF END; Считаем, что есть исходный файл ключей F, а переменная ROOT указывает на корень дерева поиска. Тогда программа поиска с включением: RESET (F);
WHILE NOT EOF(F) DO BEGIN READ (F, X); SEARCH (X, ROOT) END;
Здесь SEARCH (X, ROOT) – процедура поиска. Её описание: PROCEDURE SEARCH (X: INTEGER; VAR P: REF); BEGIN
IF P = Nil THEN BEGIN NEW(P); WITH P^ DO BEGIN
KEY := X; COUNT := 1; LEFT := Nil; RIGHT :=Nil END END ELSE
IF X < PA.KEY THEN SEARCH(X, PA.LEFT) ELSE IF X > PA.KEY THEN SEARCH(X, PA.RIGHT) ELSE PA.COUNT := Рл.COUNT +1 END {SEARCH }
Заметим, что параметр Р передается как параметр-переменная, а не как параметр-значение. Это существенно, т.к. ей присваивается новое значение ссылки.
С учетом этого, а также считая, что ключи слов читаются из файла INPUT, основную программу можно записать: BEGIN
ROOT := Nil;
WHILE NOT EOF DO BEGIN READ (K); SEARCH (K, ROOT); END;
PRINTTREE (ROOT, 0) END.
Переменные ROOT и К должны быть описаны как VAR ROOT: REF; К: INTEGER;
Для сравнения построим версии процедуры SEARCH без использования рекурсии. При этом для того, чтобы производить включение, надо помнить пройденный путь хотя бы на один шаг назад. Чтобы правильно включить (привязать) очередную включаемую компоненту, мы должны иметь ссылку на её предка и знать, в качестве какого поддерева она включается: правого или левого. Для этого вводятся две переменные: Р2 и D: PROCEDURE SEARCH (X: INTEGER; ROOT: REF); VAR PI, P2: REF; D: INTEGER; BEGIN
P2 := ROOT; PI := P2A.RIGHT; D := 1; WHILE (PI <> Nil) AND (D <> 0) DO BEGIN P2 := P1; IF X < P1A.KEY THEN
BEGIN PI := P1A.LEFT; D:= -1 END ELSE IF X > P1A.KEY THEN
BEGIN PI := P1A.RIGHT; D := 1 END ELSE D := 0 END;
IF D = 0 THEN PlA.COUNT := P1A.COUNT + 1 ELSE BEGIN NEW(Pl); WITH P1A DO BEGIN
KEY := X; LEFT := Nil; RUGHT :=Nil; COUNT := 1 END;
IF D < 0 THEN P2A.LEFT := PI ELSE IF D > 0 THEN P2A.RIGHT := PI END END;
Здесь используются две ссылки: PI и Р2, причем в процессе поиска Р2 всегда указывает на предикат Р1Л. Чтобы удовлетворить этому условию в начале поиска, вводится вспомогательный фиктивный элемент, на который указывает root. Начало действительного дерева поиска обозначается ссылкой ROOTA.RIGHT. Поэтому программа должна начинаться операторами
NEW(ROOT); ROOTA.RIGHT := Nil;
(вместо начального присваивания ROOT := Nil)
Удаление из дерева
Удаление - задача, обратная включению. Нужно построить алгоритм для удаления узла с ключом Х из дерева с упорядоченными ключами. Удаление элемента обычно не так просто, как включение.
Оно просто в случае, когда удаляемый элемент является терминальным узлом или имеет одного потомка (рис. 21)
В порождающий элемент У порождающего элемента
вносится ссылка Nil ссылка переносится на
порожденный удаляемым
узлом
Рис. 21 Удаление из дерева в простых случаях
Трудность возникает при удалении элементов с двумя потомками, т.к. мы не можем указывать одной ссылкой на два направления. В этом случае удаляемый элемент надо заменить либо на самый правый элемент его левого поддерева, либо на самый левый элемент его правого поддерева. Ясно, что такие элементы не могут иметь более одного потомка (рис. 22).
б) г)
д) е) Рис. 22 Удаление из дерева
Процесс удаления можно представить рекурсивной процедурой DELETE. Она различает три случая:
компоненты с ключом, равным Х, нет;
компонента с ключом Х имеет не более одного потомка;
компонента с ключом Х имеет двух потомков. PROCEDURE DELETE (X: INTEGER; VAR P: REF); VAR Q: REF;
PROCEDURE DEL(VAR R: REF);
BEGIN
IF RA.RIGHT <> NIL THEN DEL(RA.RIGHT)
ELSE BEGIN QMCEY := RMCEY; QA.COUNT := RA.COUNT;
Q := R; R := RA.LEFT END END { DEL } BEGIN { DELETE }
IF P = NIL THEN WRITELNC нет слова с заданным ключом ') ELSE
IF X < PMCEY THEN DELETE(X, PA.LEFT)
ELSE
IF X > PMCEY THEN DELETE (X, PA.RIGHT)
ELSE BEGIN { удаление по указателю Р } Q := P;
IF QA.RIGHT = NIL THEN P := QA.LEFT ELSE
IF QA.LEFT = NIL THEN P := QA.RIGHT ELSE DEL(QA.LEFT);
DISPOSE(Q) END END { DELETE }
Вспомогательная рекурсивная процедура DEL вызывается только в третьем случае. Она "спускается" вдоль самой правой ветви левого поддерева удаляемого узла QA и затем заменяет существующую информацию (ключ и счетчик) в QA соответствующими значениями самой правой компоненты RA этого левого поддерева, после чего от RA можно освободиться. Это делается с помощью стандартной процедуры DISPOSE(Q). Работу процедуры можно проверить по рис. 22.