Анимация
JavaScript


Главная  Библионтека 

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 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225

(Внутри компьютера эффективнее было бы оперировать значениями сТ вместо Т в силу соотношения (1). Такие изменения можно вьшолнить достаточно легко, поэтому дальнейшие рассуждения продолжим, полагая, что с = 1.)

Представление очереди или дека организовано несколько сложнее. Очевидным решением могло бы быть применение двух указателей, F и R (для начала и конца очереди), где F = R = О, если очередь пуста. Тогда вставка элемента с конца очереди может быть выполнена с помощью следующих действий:

Rf-R+1; X[R]f-Y. (4)

Удаление же узла в начале очереди (F указывает на ячейку, расположенную перед начальным элементом очереди) может быть выполнено с помощью других действий:

F •(- F + 1; Y <- X [F]; если F = R, то F •(- R •(- 0. (5)

Следует отметить, что, если при такой организации работы очереди R всегда опережает F fi\ е. в очереди всегда имеется хотя бы один узел), элементы таблицы Х[1], X [21, . ., X [1000], ... будут последовательно заниматься вплоть до бесконечности, что приведет к расточительному использованию памяти. Следовательно, простой метод на основе операций (4) и (5) нужно использовать только тогда, когда известно, .то F нпс.тигает R достаточно регулярно, например если все удаления выполняются скачкообразно с полным опустошением очереди.

Чтобы разрешить задачу переполнения памяти при такой организации очереди, можно выде.лить М узлов Х[1],... ,Х[М], неявно образующих замкнутое кольцо, в котором за Х[М] следует Х[1]. Тогда описанные выше действия (4) и (5) будут выглядеть так:

если R = М, то R •«- 1, в противном случае R •«- R --1; X [R] •«- Y; (6) если F = М, то F •«- 1, в противном случае F •«- F -Н 1; Y X [F]. (7)

Фактически циклическая организация очереди уже встречалась ранее, при описании буферов ввода-вывода в разделе 1.4.4.

До сих пор эти рассуждения были далеки от реальности, поскольку неявно предполагалось отсутствие каких-либо нежелательных ситуаций. Например, при удалении узла из стека или очереди допускалось, что в них остается по крайней мере егце один узел. А при вставке узла в стек или очередь допускалось, что для него найдется свободное место в памяти. Но, очевидно, при использовании метода ha основе действий (6) и (7) предполагается, что в очереди может быть не более М узлов, а при использовании (2)-(5) значения Т и R в данной программе не могут превышать определенный максимум. В общем случае, когда такие ограничения не выполняются автоматически, следует предпринять следующие действия:

X < Y (вставка в стек): < если Т > М, то OVERFLOW; (2, а)

I X [Т] •(- Y.

( если Т = О, то UNDERFLOW; Y < X (удаление из стека): < Y •(- Х[Т]; (3, а)

I T-f- Т- 1.



{если R = М, то R <- 1, в противном aiyчае R<-R+l; , . если R = F, то OVERFLOW; >

X[R] <- Y.

(если F = R, то UNDERFLOW; если F = М, то F <- 1, /-т \

„ , (7, а) в противном случае F <- F + 1; YX[F].

Здесь предполагается, что набор узлов Х[1],..., ХСМ] образует общее пространство, доступное для организации списка. А обозначения OVERFLOW (переполнение) и UNDERFLOW (отсутствие) означают избыток или недостаток элементов. Теперь при использовании условий (6, а) и (7, а) начальное условие F = R = О для указателей очереди будет недействительным, поскольку избыток элементов (OVERFLOW) не будет зафиксирован при F = 0. Поэтому в качестве начального условия следует, например, выбрать F = R = 1.

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

В таком случае возникает вопрос: "Что нужно сделать при недостатке (UNDERFLOW) или избытке (OVERFLOW) элементов? Недостаток (UNDERFLOW) возникает при попытке удалить несуществующий элемент. Обычно эта ситуация рассматривается вовсе не как ошибка, а как некое условие с определенным смыслом, которое может быть использовано для управления потоком вьтолнения программы. Например, можно удалять элементы до тех пор, пока не наступит их недостаток (UNDERFLOW). Однако избыток (OVERFLOW) обычно свидетельствует об ошибке. Это значит, что таблица уже полностью заполнена, хотя в нее еще следует ввести некоторую информацию. При возникновении такой ситуации сначала обычно поступает сообщение о том, что программа не может продолжать работу, поскольку исчерпана емкость хранилища, а затем вьшолнение программы прекращается.

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

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

Программа и таблицы

Программа и таблицы Доступное фиксированного

фиксированного размера Список 1 пространство Список 2 размера

Начало Низ Верх Верх Низ Конец

памяти памяти



Здесь список 1 расширяется вправо, а список 2 (хранящийся в обратном порядке) - влево. Избыток (OVERFLOV) не будет происходить до тех пор, пока общий размер обоих списков не будет превышать размер всего доступного пространства в памяти компьютера. Такие списки могут независимо расширяться и сжиматься так, что фактический максимальный размер каждого из них может существенно превышать половину всего доступного им пространства. Такая схема использования памяти часто применяется на практике.

Однако довольно просто можно убедиться в том, что нельзя организовать хранение в памяти компьютера трех и более последовательных списков с изменяемой длиной и соблюсти следующие условия: (а) избыток (OVERFLOW) должен происходить только тогда, когда общий размер всех списков превышает размер доступного для них пространства, (ь) "нижний" элемент каждого списка должен иметь фиксированное место расположения. Проблема эффективного распределения пространства памяти для хранения списков становится очень важной при работе с десятью или более списками с изменяемыми размерами. Причем такие ситуации являются довольно обычными. В подобном случае для удовлетворения условия (а) придется пренебречь условием (ь), т. е. позволить "нижним" элементам изменять их расположение. Это значит, что адрес Lq в уравнении (1) уже не является постоянным, причем теперь нельзя будет делать ссылки на таблицу с помощью абсолютного адреса, поскольку все ссылки должны указьшаться относительно базового адреса Lq. В компьютере MIX код вставки 1-го однословного узла в регистр А, который выглядел как

LD1 I

LD1 I LDA BASE(0:2)

LDA Lo,l теперь будет, например, таким: *+i(0:2)

LDA *,1

где BASE содержит Lq О О О . Подобная относительная адресация, очевидно, вьшолняется дольше, чем адресация по фиксированномз базовому адресу, но не намного, если в компьютере MIX реализована возможность "косвенной адресации" (indirect addressing) (см. упр. 3).

Особенно важным является случай, когда каждый список с изменяемой длиной является стеком. Тогда код может быть таким же эффективным, как и прежде, поскольку в любой момент приходится иметь дело только с верхним элементом каждого стека. Алгоритм вставки и удаления элементов в п стеках будет выглядеть следующим образом (здесь BASE [г] и ТОР [г] - переменные связи г-го стека, а каждый узел составляет одно слово).

Вставка: ТОР [г] <- ТОР [i] -Ы; если ТОР [г] > BASE [г -Н 1], то

OVERFLOW; в противном случае CONTENTS (ТОР [г]) •(- Y. (9)

Удаление: если ТОР [г] = BASE [г], то UNDERFLOW; в противном случае

Y •(- CONTENTS(TOPM), ТОРЮ <- ТОРЮ - 1. (10)

BASE [г-ь 1] является базовым адресом (г + 1)-го стека. Условие ТОР [г] = ВАЗЕЮ означает, что стек г пуст.

В алгоритме (9) условие избытка OVERFLOW уже не является таким критичным, как прежде. Теперь можно "переупаковать память", предоставляя больше свободного пространства для переполняющейся таблицы за счет незанятого пространства



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 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225