Алгоритмы и структуры данных

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

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

следующая группа отсутствует или элемент не является первым в группе, то этот дополнительный указатель принимает значение nil.

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

Если реализован только один уровень, то это, фактически, обычный список и время поиска пропорционально O(n). Однако если имеется достаточное число уровней, то разделенный список можно считать деревом с корнем на высшем уровне, а для дерева время поиска, как будет показано ниже, пропорционально O(log n).

 

1.3.3. Графы

1.3.3.1. Спецификация

Граф G - это упорядоченная пара (V, E), где V - непустое множество вершин, E - множество пар элементов множества V, называемое множеством ребер.

Упорядоченная пара элементов из V называется дугой. Если все пары в Е упорядочены, то граф называется ориентированным (орграфом).

Если дуга e ведет от вершины v_x к вершине v₂, то говорят, что дуга e инцидентна вершине v₂, а вершина v₂ являются смежной вершине v_x. В случае неориентированного графа ребро e является инцидентной обеим вершинам v_x и v₂, а сами вершины - взаимно смежными.

Путь - это любая последовательность вершин орграфа такая, что в этой последовательности вершина b может следовать за вершиной a, только если существует дуга, следующая из a в b. Аналогично можно определить путь, состоящий из дуг.

Путь, начинающийся и заканчивающийся в одной и той же вершине, называется циклом. Граф, в котором отсутствуют циклы, называется ациклическим.

Петля - дуга, соединяющая некоторую вершину сама с собой.

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

1.3.3.2. Реализация

Выбор структуры данных для хранения графа в памяти имеет принципиальное значение при разработке эффективных алгоритмов. Рассмотрим два матричных и три списочных представления графа (см. рис. 13):

• матрица смежности;
• матрица инцидентности;
• списки смежных вершин;
• список ребер;
• списки вершин и ребер.

При дальнейшем изложении будем предполагать, что вершины графа обозначены символьной строкой и всего их до n, а ребер - до m. Каждое ребро и каждая вершина имеют вес - целое положительное число. Если граф не является помеченным, то считается, что вес равен единице.

Матрица смежности - это двумерный массив размером nXn:

type

TAdjacencyMatrix = array [1..n,  1..n]  of integer; var

Graph: TAdjacencyMatrix; При этом

0, если вершина i не смежна вершине j, Graf[i, j] = < вес ребра (дуги), если вершина i смежна вершине j, вес вершины, если i = j.

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

Пространственная сложность этого способа V(n)-O(n²). Способ очень хорош, когда надо часто проверять смежность или находить вес ребра по двум заданным вершинам.

Матрица инцидентности - это двумерный массив размером nXm:

type

TIncidenceMatrix = array [1..n,  1..m]  of integer;

var

Graph: TIncidenceMatrix; При этом

G  _fr.    = j0, если вершина i не инцидентна ребру j,

^,      [вес ребра (дуги в i), если вершина инцидентна ребру j

Пространственная сложность этого способа V(n, m)-O(nXm). Матрица инцидентности лучше всего подходит для операции «перечисление ребер, инцидентных вершине x».

Списки смежных вершин - это одномерный массив размером n, содержащий для каждой вершины указатели на списки смежных с ней вершин:

type

PNode = ^ANode;

Node = record {смежная вершина}

Name:  string; {имя смежной вершины}

Weight: integer;        {вес ребра}

Next: PNode; {следующая смежная вершина}

end;

TAdjacencyList = array [1..n]  of record 
NodeWeight:  integer;    {вес вершины} 
Name:  string; {имя вершины}

List: PNode; {указатель на список смежных}

end;

var

Graph: TAdjacencyList;

Пространственная сложность этого способа V_max(n)~O(n²). Хранение списков в динамической памяти позволяет сократить объем расходуемой памяти, так как в этом случае не будет резервироваться место под n соседей для каждой вершины. Можно и сам массив представить в виде динамического списка, но это не имеет особого смысла, так как граф обычно является статичной (неизменяемой) структурой.

Этот способ хранения лучше всех других подходит для операции «перечисление всех вершин, смежных с x».

Список ребер - это одномерный массив размером m, содержащий список пар вершин, инцидентных с одним ребром графа:

type

TBranchList = array [1..m]  of record

Node1: string; {1-я вершина, инцидентная ребру}

Node2: string; {2-я вершина, инцидентная ребру}

Weight:  integer;      {вес ребра} end; var

Graph:  TBranchList;

Пространственная сложность этого способа V(m)-O(m). Этот способ хранения графа особенно удобен, если главная операция, которой чаще всего выполняется, это перечисление ребер или нахождение вершин и ребер, находящихся в отношениях инцидентности.

Рис. 13. Граф и его реализации

Граф можно представить также в виде списочной структуры, состоящей из списков двух типов - списки вершин и списков ребер: type

PNode = ATNode;

PBranch = ATBranch;

TNode = record {вершина}

Name:  string; {имя вершины}

Weight: integer;        {вес вершины}

Branch: PBranch;        {выходящее ребро}

Next: PNode; {следующая вершина}

end;

TBranch = record        {ребро}

Node:  PNode; {вершина,  в которую входит}

Weight:  integer;        {вес ребра}

Next: PBranch; {следующее выходящее ребро}

end; var

Graph:  PBranch;

Пространственная сложность этого способа V(n, m)-O(n+m).

 

1.3.4. Деревья

1.3.4.1. Общие понятия

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

1. существует узел, в который не входит ни одной дуги (корень);
2. в каждую вершину, кроме корня, входит одна дуга. Вершины дерева подразделяют на следующие три группы:

- корень - вершина, в которую не входит ни одной дуги;

• узлы - вершины, в которые входит одна дуга и выходит одна или более дуг;
• листья - вершины, в которые входит одна дуга и не выходит ни одной дуги.

Все вершины, в которые входят дуги, исходящей из одной вершины, называются потомками этой вершины, а сама вершина - предком. Корень не имеет предка, а листья не имеют потомков.

Выделяют уровни дерева. На первом уровне дерева может быть только одна вершина - корень, на втором - потомки корня, на третьем - потомки потомков корня и т. д.

Поддеревом называется вершина со всеми ее потомками.

Высотой поддерева будем считать максимальную длину цепиy_x, y_n его вершин такую, что y_i+l - потомок y_i для всех i. Высота пустого дерева равна нулю, высота дерева из одного корня - единице.

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

По величине степени дерева часто различают два типа деревьев:

• двоичные - степень дерева не более двух;
• сильноветвящиеся - степень дерева произвольная.

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

 

TTree = record

Data: TypeElement;  {поле данных}

Childs, Next: PTree;  {указатели на потомков и на следующий} end;

 

1.3.4.2. Обходы деревьев

Существует несколько способов обхода (просмотра) всех вершин дерева. Три наиболее часто используемых способа обхода называются (рис. 15):

• в прямом порядке;
• в обратном порядке;
• в симметричном (внутреннем) порядке.

Все три способа обхода рекурсивно можно определить следующим образом:

1. если дерево Tree является пустым деревом, то в список обхода заносится пустая запись;
2. если дерево Tree состоит из одной вершины, то в список обхода записывается эта вершина;
3. если Tree - дерево с корнем n и поддеревьями Tree j, Tree₂, Tree^ то:

 

• при прохождении в прямом порядке сначала посещается корень n, затем в прямом порядке вершины поддерева Tree j, далее в прямом порядке вершины поддерева Tree₂ и т. д. Последними в прямом порядке посещаются вершины поддерева Tree^
• при прохождении в обратном порядке сначала посещаются в обратном порядке вершины поддерева Tree j, далее последовательно в обратном порядке посещаются вершины поддеревьев Tree₂, Tree^ Последним посещается корень n;

- при прохождении в симметричном порядке сначала посещаются в симметричном порядке вершины поддерева Tree j, далее корень n, затем последовательно в симметричном порядке вершины поддеревьев Tree₂, „.^{, Tree}_k^.

Далее приведены наброски процедур, реализующих указанные способы обходов деревьев. При доработке этих набросков необходимо учитывать конкретную реализацию деревьев:

procedure PreOrder(n:  вершина);

{Обход дерева в прямом порядке} begin

Занести в список обхода вершину n;

for для каждого потомка s вершины n в порядке слева направо do PreOrder(s);

end;

procedure LastOrder(n: вершина);

{Обход дерева в обратном порядке} begin

for для каждого потомка s вершины n в порядке слева направо do

LastOrder(s); Занести в список обхода вершину n; end;

procedure InOrder(n: вершина);

{Обход дерева в симметричном порядке} begin

if n - лист then begin

занести в список обхода узел n; end else begin

InOrder(самый левый потомок вершины n);

Занести в список обхода вершину n;

for для каждого потомка s вершины n, исключая самый левый, в порядке слева направо do InOrder(s);

end; end;

 

1.3.4.3. Спецификация двоичных деревьев

Как уже говорилось выше, двоичные (бинарные) деревья - это деревья со степенью не более двух (рис. 16).

По степени вершин двоичные деревья бывают:

 

• с т р о г и е - вершины дерева имеют степень нуль (у листьев) или два (у узлов);
• н е с т рогие - вершины дерева имеют степень нуль (у листьев), один или два (у узлов).

В общем случае на k-м уровне двоичного дерева может быть до 2^k-j вершин.

Двоичное дерево, содержащее только полностью заполненные уровни (т. е. 2^k-j вершин на каждом k-м уровне), называется п о л н ы м .

1.3.4.4. Реализация

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

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

type

PTree = ATTree; TTree = record

Data: TypeElement;  {поле данных}

Left, Right: PTree; {указатели на левого и правого потомков} end;

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

type

Tree: array[1..N]  of TypeElement; Адрес любой вершины в массиве вычисляется как адрес = 2^k-J+i-1,

где k - номер уровня вершины; i - номер на уровне k в полном двоичном дереве. Адрес корня будет равен единице. Для любой вершины, имеющей индекс j в массиве, можно вычислить адреса левого и правого потомков: