Главная Промышленная автоматика.

задний

ПЕРЕДНИЙ-

Рис. 2.5. Реализация очереди в виде одного массива.

ВЫТОЛКНУТЬ и проверка пустоты не зависят от числа элементов в стеке.

Другой специальный вид списка - очередь, т. е. список, в который элементы всегда добавляются с одного (переднего) конца, а удаляются с другого. Как и стек, очередь можно реализовать одним массивом, как показано на рис. 2.5, где приведена очередь, содержащая список из элементов Р, Q, R, S, Т. Два указателя обозначают ячейки текущего переднего и заднего концов очереди. Чтобы добавить (ВПИСАТЬ) новый элемент к очереди, как и в случае стека, полагают ПЕРЕДНИЙ = ПЕРЕДНИЙ +1 и помещают новый элемент в ИМЯ[ПЕРЕДНИЙ]. Чтобы удалить (ВЫПИСАТЬ) элемент из очереди, заменяют ЗАДНИЙ на ЗАДНИЙ +1. Заметьте, что эта техника с точки зрения доступа к элементам основана на принципе "первый вошел - первый вышел".

Поскольку массив ИМЯ имеет конечную длину, скажем /, указатели ПЕРЕДНИЙ и ЗАДНИЙ рано или поздно доберутся до его конца. Если длина списка, представленного этой очередью, никогда не превосходит /, то можно трактовать ИМЯЮ] как элемент, следующий за элементом ИМЯ1/-П.

Элементы, расположенные в виде списка, сами могут быть сложными структурами. Работая, например, со списком массивов, мы на самом деле не добавляем и не удаляем массивы, ибо каждое добавление или удаление потребовало бы времени, пропорционального раз-



меру массива. Вместо этого мы добавляем или удаляем указатели массивов. Таким образом, сложную структуру можно добавить или удалить за фиксированное время, не зависящее от ее размера.

2.2. ПРЕДСТАВЛЕНИЯ МНОЖЕСТВ

Обычно списки применяются для представления множеств. При этом объем памяти, необходимый для представления множества, пропорционален числу его элементов. Время, требуемое для выполнения операции над множествами, зависит от природы операции. Например, пусть Л и В - два множества. Операция А П В требует времени, по крайней мере пропорционального сумме размеров этих множеств, поскольку как список, представляющий А, так и список, представляющий В, надо просмотреть хотя бы один раз ).

Подобным же образом операция A\jB требует времени, пропорционального сумме размеров множеств, поскольку надо выделить элементы, входящие в оба множества, и вычеркнуть один экземпляр каждого такого элемента. Если же Л и В не пересекаются, можно найти Л иВ за время, не зависящее от размера Л и В. Для этого достаточно сделать конкатенацию списков, представляющих Л и В. Задача объединения двух непересекающихся множеств усложняется, если необходимо быстро определять, входит ли данный элемент в данное множество. Этот вопрос подробно обсуждается в разд. 4.6 и 4.7.

Другой способ представления множества, отличный от представления его в виде списка,- представление в виде двоичного (битового) вектора. Пусть U - универсальное множество (т. е. все рассматриваемые множества являются его подмножествами), состоящее из п элементов. Линейно упорядочим его. Подмножество SsL/ представляется в виде вектора Vj из п битов, такого, что i-й разряд в равен 1 тогда и только тогда, когда i-й элемент множества О принадлежит S. Будем называть Vj характеристическим вектором для S.

Представление в виде двоичного вектора удобнее тем, что можно определять принадлежность i-ro элемента множества U данному множеству за время, не зависящее от размера данного множества. Более того, основные операции над множествами, такие, как объединение и пересечение, можно осуществить как операции V и Л над двоичными векторами.

Если мы не хотим считать операции над двоичными векторами первичными (т. е. выполняемыми за единицу времени), то можно с таким же успехом вместо характеристического вектора определить массив Л, для которого Л[/]=1 тогда и только тогда, когда i-й эле-

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



мент множества U принадлежит S. При таком представлении все еще легко выяснять, принадлежит ли данный элемент данному множеству. Недостаток этого представления заключается в том, что объединение и пересечение занимают время, пропорциональное \\и\\ а не размерам рассматриваемых множеств. Подобно этому память, требуемая для хранения множества S, пропорциональна \\и\\, а не IISII.

2.3. ГРАФЫ

Сейчас мы введем математическое понятие графа и те структуры данных, которые обычно применяются для его представления.

Определение. Граф С=(У, Е) состоит из конечного непустого множества узлов V и множества ребер Е. Если ребра представлены в виде упорядоченных пар (v, w) узлов, то граф называется ориентированным; V называется началом, aw - концом ребра (и, w). Если ребра - неупорядоченные пары (множества) различных вершин, также обозначаемые (и, w), то граф называют неориентированным *).

Если в ориентированном графе С=(У, Е) пара (и, w) принадлежит множеству ребер Е, то узел w называется смежным с узлом v. Говорят, что ребро (v, w) идет usv ew. Число узлов, смежных с узлом V, называется полустепенью его исхода.

Если (и, W) - ребро неориентированного графа G=(V, Е), то мы считаем, что (и, w)={w, v), так что {w, и) - то же самое ребро. Узел W называется смежным с узлом v, если {v, w) (а значит, и {w, v)) принадлежит Е. Степень узла - это число узлов, смежных с ним.

Путем в ориентированном или неориентированном графе называют последовательность ребер вида (Ui, Uj), {v, v), . . . , (fn-iifn)-Говорят, что этот путь идет из Uieu„ и имеет длину п-1. Часто такой путь представляют последовательностью Vi, v, . . . , Vn узлов, лежащих на нем. В вырожденном случае один узел обозначает путь длины О, идущий из этого узла в него же. Путь называется простым, если все ребра и все узлы на нем, кроме, быть может, первого и последнего, различны. Цикл - это простой путь длины не менее 1, который начинается и кончается в одном и том же узле. Заметим, что в неориентированном графе длина цикла должна быть не менее 3.

Известно несколько представлений графа G=(V, Е). Один из мш -матрица смежностей, т.е. матрица А размера УхУ, состоящая из О и 1, в которой A[i, /]=1 тогда и только тогда, когда есть ребро из узла i в узел /. Представление в виде матрицы смеж-

1) обозначает здесь число элементов (размер, или мощность) множества X.

Заметим, что в ориентированном графе может быть ребро (а, а), а в неориентированном - нет.





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 [17] 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.002