Информатика и информационные технологии - А. Цветкова
Шрифт:
Интервал:
Закладка:
Alfa);
begin
sC:= pBegin^.sD;
pBegin:= pBegin^.pNext;
end;
begin
Clrscr;
writeln( ВВЕДИ СТРОКУ );
readln(sC);
CreateQueue(pBegin, pEnd, sC);
repeat
writeln( ВВЕДИ СТРОКУ );
readln(sC);
AddQueue(pEnd, sC);
until sC = 'END';
20. Древовидные структуры данных
Древовидной структурой данных называется конечное множество элементов-узлов, между которыми существуют отношения – связь исходного и порожденного.
Если использовать рекурсивное определение, предложенное Н. Виртом, то древовидная структура данных с базовым типом t – это либо пустая структура, либо узел типа t, с которым связано конечное множество древовидных структур с базовым типом t, называемых поддеревьями.
Далее дадим определения, используемые при оперировании древовидными структурами.
Если узел y находится непосредственно под узлом х, то узел y называется непосредственным потомком узла х, а х – непосредственным предком узла у, т. е., если узел хнаходится на i-ом уровне, то соответственно узел y находится на (i + 1) – ом уровне.
Максимальный уровень узла дерева называется высотой или глубиной дерева. Предка не имеет только один узел дерева – его корень.
Узлы дерева, у которых не имеется потомков, называются терминальными узлами (или листами дерева). Все остальные узлы называются внутренними узлами. Количество непосредственных потомков узла определяет степень этого узла, а максимально возможная степень узла в данном дереве определяет степень дерева.
Предков и потомков нельзя поменять местами, т. е. связь исходного и порожденного действует только в одном направлении.
Если пройти от корня дерева к некоторому конкретному узлу, то количество ветвей дерева, которое при этом будет пройдено, называется длиной пути для этого узла. Если все ветви (узлы) у дерева упорядочены, то дерево называется упорядоченным.
Частным случаем древовидных структур являются бинарные деревья. Это деревья, в которых каждый потомок имеет не более двух потомков, называемых левым и правым поддеревьями. Таким образом, бинарное дерево – это древовидная структура, степень которой равна двум.
Упорядоченность бинарного дерева определяется по следующему правилу: каждому узлу соответствует свое ключевое поле, и для каждого узла значение ключа больше всех ключей в его левом поддереве и меньше всех ключей в его правом поддереве.
Дерево, степень которого больше двух, называется сильноветвящимся.
21. Операции над деревьями
Далее будем рассматривать все операции применительно к бинарным деревьям. I. Построение дерева.
Приведем алгоритм построения упорядоченного дерева.
1. Если дерево пусто, то данные переносятся в корень дерева. Если же дерево не пусто, то осуществляется спуск по одной из его ветвей таким образом, чтобы упорядоченность дерева не нарушалась. В результате новый узел становится очередным листом дерева.
2. Чтобы добавить узел в уже существующее дерево, можно воспользоваться вышеприведенным алгоритмом.
3. При удалении узла из дерева следует быть внимательным. Если удаляемый узел является листом, или же имеет только одного потомка, то операция проста. Если же удаляемый узел имеет двух потомков, то необходимо будет найти узел среди его потомков, который можно будет поставить на его место. Это нужно в силу требования упорядоченности дерева.
Можно поступить таким образом: поменять удаляемый узел местами с узлом, имеющем самое большое значение ключа в левом поддереве, или с узлом, имеющем самое малое значение ключа в правом поддереве, а затем удалить искомый узел как лист.
II. Поиск узла с заданным значением ключевого поля.
При осуществлении этой операции необходимо совершить обход дерева. Необходимо учитывать различные формы записи дерева: префиксную, инфиксную и постфиксную.
Возникает вопрос: каким образом представить узлы дерева, чтобы было наиболее удобно работать с ними? Можно представлять дерево с помощью массива, где каждый узел описывается величиной комбинированного типа, у которой информационное поле символьного типа и два поля ссылочного типа. Но это не совсем удобно, так как деревья имеют большое количество узлов, заранее не определенное. Поэтому лучше всего при описании дерева использовать динамические переменные. Тогда каждый узел представляется величиной одного типа, которая содержит описание заданного количества информационных полей, а количество соответствующих полей должно быть равно степени дерева. Логично отсутствие потомков определять ссылкой nil. Тогда на языке Pascal описание бинарного дерева может выглядеть следующим образом:
TYPE TreeLink = ^Tree;
Tree = record;
Inf: <тип данных>;
Left, Right: TreeLink;
End.
22. Примеры реализации операций
1. Построить дерево из з узлов минимальной высоты, или идеально сбалансированное дерево (количество узлов левого и правого поддеревьев такого дерева должны отличаться не более чем на единицу).
Рекурсивный алгоритм построения:
1) первый узел берется в качестве корня дерева;
2) тем же способом строится левое поддерево из nl узлов;
3) тем же способом строится правое поддерево из nr узлов;
nr = n – nl – 1
В качестве информационного поля будем брать номера узлов, вводимые с клавиатуры. Рекурсивная функция, реализующая данное построение, будет выглядеть следующим образом:
Function Tree(n: Byte): TreeLink;
Var t: TreeLink; nl,nr,x: Byte;
Begin
If n = 0 then Tree:= nil
Else
Begin
nl:= n div 2;
nr = n – nl – 1;
writeln('Введите номер вершины );
readln(x);
new(t);
t^.inf:= x;
t^.left:= Tree(nl);
t^.right:= Tree(nr);
Tree:= t;
End;
{Tree}
End.
2. В бинарном упорядоченном дереве найти узел с заданным значением ключевого поля. Если такого элемента в дереве нет, то добавить его в дерево.
Procedure Search(x: Byte; var t: TreeLink);
Begin
If t = nil then
Begin
New(t);
t^inf:= x;
t^.left:= nil;
t^.right:= nil;
End
Else if x < t^.inf then
Search(x, t^.left)
Else if x > t^.inf then
Search(x, t^.right)
Else
Begin
{обработка найденного элемента}
…
End;
End.
23. Понятие графа. Способы представления графа
Граф – пара G = (V,E), где V – множество объектов произвольной природы, называемых вершинами, а E – семейство пар ei = (vil, vi2), vijOV, называемых ребрами. В общем случае множество V и (или) семейство E могут содержать бесконечное число эле-ментов, но мы будем рассматривать только конечные графы, т. е. графы, у которых как V, так и E конечны. Если порядок элементов, входящих в ei, имеет значение, то граф называется ориентированным, сокращенно – орграф, иначе – неориентированным. Ребра орграфа называются дугами.
Если e = <u,v>, то вершины v и и называются концами ребра. При этом говорят, что ребро e является смежным (инцидентным) каждой из вершин v и и. Вершины v и и также называются смежными (инцидентными). В общем случае допускаются ребра вида e = <v, v>; такие ребра называются петлями.
Степень вершины графа – это число ребер, инцидентных данной вершине, причем петли учитываются дважды.
Вес вершины – число (действительное, целое или рациональное), поставленное в соответствие данной вершине (интерпретируется как стоимость, пропускная способность и т. д.).
Путем в графе (или маршрутом в орграфе) называется чередующаяся последовательность вершин и ребер (или дуг – в орграфе) вида v0, (v0,v1), v1, …, (vn –1,vn), vn. Число n называется длиной пути. Путь без повторяющихся ребер называется цепью, без повторяющихся вершин – простой цепью. Замкнутый путь без повторяющихся ребер называется циклом (или
контуром в орграфе); без повторяющихся вершин (кроме первой и последней) – простым циклом.
Граф называется связным, если существует путь между любыми двумя его вершинами, и несвязным – в противном случае.
Существуют различные способы представления графов.
1. Матрица инцидентности.
Это прямоугольная матрица размерности n ч m, где n – количество вершин, а m – количество ребер.
2. Матрица смежности.
Это квадратная матрица размерности n ч n, где n – количество вершин.
3. Список смежности (инцидентности). Представляет собой структуру данных, которая
для каждой вершины графа хранит список смежных с ней вершин. Список представляет собой массив указателей, i-ый элемент которого содержит указатель на список вершин, смежных с i-ой вершиной.
4. Список списков.
Представляет собой древовидную структуру данных, в которой одна ветвь содержит списки вершин, смежных для каждой.
24. Различные представления графа
Для реализации графа в виде списка инцидентности можно использовать следующий тип:
Type List = ^S;
S = record;
inf: Byte;
next: List;
end;
Тогда граф задается следующим образом:
Var Gr: array[1..n] of List;
Теперь обратимся к процедуре обхода графа. Это вспомогательный алгоритм, который позволяет просмотреть все вершины графа, проанализировать все информационные поля. Если рассматривать обход графа в глубину, то существуют два типа алгоритмов: рекурсивный и нерекурсивный.
На языке Pascal процедура обхода в глубину будет выглядеть следующим образом:
