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

2.1. СТРУКТУРЫ ДАННЫХ: СПИСКИ, ОЧЕРЕДИ И СТЕКИ

ИМЯ СЛЕДУЮЩАЯ

Элем 1

Элем 4

Элем 2

Элем 3

Рис. 2.2. Представление списка из четырех элементов.

массиве ИМЯ не совпадает с их порядком в списке. Тем не менее рис. 2.2 дает верное представление списка, изображенного на рис. 2.1, так как массив СЛЕДУЮЩАЯ располагает элементы в том же порядке, в каком они расположены в списке (2.1).

Опишем процедуру, вставляющую новую компоненту в список. В ней предполагается, что СВОБОДНАЯ - номер незанятой ячейки в массивах ИМЯ и СЛЕДУЮЩАЯ, а ПОЗИЦИЯ - индекс той компоненты в списке, после которой надлежит вставить ЭЛЕМЕНТ:

procedure ВСТАВИТЬОЛЕМЕНТ, СВОБОДНАЯ, ПОЗИЦИЯ): begin

ИМЯ[СВОБОДНАЯ] ЭЛЕМЕНТ;

СЛЕДУЮЩАЯ[СВОБОДНАЯ] СЛЕДУЮЩАЯ[П03ИЦИЯ]; СЛЕДУЮЩАЯ [ПОЗИЦИЯ] - СВОБОДНАЯ end

Любой разумный перевод в команды РАМ приведет к тому, что время выполнения процедуры ВСТАВИТЬ не будет зависеть от размера списка.

Пример 2.1. Допустим, что мы хотим вставить в список (2.1) элемент Новэлем после Элем 2 и получить список

Элем 1, Элем 2, Новэлем, Элем 3, Элем 4.

Если пятая ячейка в каждом массиве на рис. 2.2 пуста, можно вставить Новэлем после Элем 2 (позиция 3), вызвав ВСТАВИТЬ(Новэлем, 5, 3). В результате выполнения трех операторов в процедуре ВСТАВИТЬ получим: ИМЯ[5J Новэлем,



ИМЯ СЛЕДУЮЩАЯ

Элем )

Элем 4

Элем 1

Элем Ъ

Нов элем

Рис. 2.3. Список со вставленным элементом Нонэлем.

СЛЕДУЮЩАЯ15]=4 и СЛЕДУЮЩАЯ 13]=5; тем самым создадутся массивы, показанные на рис. 2.3. □

Для ТОГО чтобы удалить компоненту, следующую за компонентой в ячейке /, можно положить СЛЕДУЮЩАЯ(/] = СЛЕДУЮЩАЯ (СЛЕДУЮЩАЯ1/11. При желании индекс удаленной компоненты можно поместить в список незанятых ячеек памяти.

Часто в один и тот же массив вкладываются несколько списков Обычно один из этих списков состоит из незанятых ячеек; мы буде.м называть его свободньш списком. Для добавления элемента к списку А можно так изменить процедуру ВСТАВИТЬ, чтобы незанятая ячейка получалась путем удаления первой ячейки в свободном списке. При удалении элемента из списка А соответствующая ячейка возвращается в свободный список для будущего употребления.

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

Еще две основные операции над списками - конкатенация (сцепление) двух списков, в результате которой образуется единственный список, и обратная к ней операция расцепления списка, стоящего после некоторого элемента, результатом которой будут два списка. Конкатенацию можно выполнить за ограниченное (постоянной величиной) число шагов, включив в представление списка еще один указатель. Этот указатель дает индекс последней компоненты списка и тем самым позволяет обойтись без просмотра всего списка для определения его последнего элемента. Расцепление мож-



2.1. СТРУКТУРЫ ДАННЫХ! СПИСКИ, ОЧЬРЕДИ И С1 ЕКН

ВЕРШИНЯ 2

Элелг 2

Злем 3

Рис. 2.4. Реализация стека.

НО сделать за ограниченное (постоянной величиной) время, если известен индекс компоненты, непосредственно предшествующей месту расцепления.

Списки можно сделать проходимыми в обоих направлениях, если добавить еще один массив, называемый ПРЕДЫДУЩАЯ. Значение ПРЕДЫДУЩАЯ!/] равно ячейке, в которой помещается тот элемент списка, который стоит непосредственно перед элементом из ячейки /. Список такого рода называется дважды связанным. Из дважды связанного списка можно удалить элемент или вставить в него элемент, не зная ячейку, где находится предыдущий элемент.

Со списком часто работают очень ограниченными приемами. Например, элементы добавляются или удаляются только на конце списка. Иными словами, элементы вставляются и удаляются по принципу "последний вошел - первый вышел". В этом случае список называют стеком или магазином.

Часто стек реализуется в виде одного массива. Например, список

Элем 1, Элем 2, Элем 3

можно было бы хранить в массиве ИМЯ, как показано на рис. 2.4. Переменная ВЕРШИНА является указателе.м последнего элемента, добавленного к стеку. Чтобы добавить (ЗАТОЛКНУТЬ) новый элемент в стек, значение ВЕРШИНА увеличивают на 1, а затем помещают новый элемент в ИМЯ1ВЕР111ИНА]. (Поскольку массив ИМЯ имеет конечную длину I, перед попыткой вставить новый элемент следует проверить, что ВЕРШИНА </-1.) Чтобы удалить (ВЫТОЛКНУТЬ) элемент из вершины стека, надо просто уменьшить значение ВЕРШИНА на 1. Заметим, что не обязательно физически стирать элемент, удаляемый из стека. Чтобы узнать, пуст ли стек, достаточно проверить, не имеет ли ВЕРШИНА значение, меньшее нуля. Понятно, что время выполнения операций ЗАТОЛКНУТЬ и





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