AOP_Tom1 (1021736), страница 73
Текст из файла (страница 73)
7) Такие простые операции, как последовательная обработка элементов списка, на многих компьютерах выполняется немного быстрее. Для компьютера М11 операторы 1МС1 с и Ю1 0,1О.ХМК) отличаются только одним тактом, но на многих компьютерах не реализована возможность загрузки индексного регистра из индексированной ячейки. Если элементы связанного списка принадлежат разным страницам устройства хранения большого объема, то операция доступа к ним может выполняться значительно дольше. Таким образом, технология связанного распределения памяти позволяет обойти ограничения, накладываемые последовательной природой компьютерной памяти.
При выполнении одних операций она способствует достижению гораздо более высокой эффективности, а при выполнении других, наоборот, снижает ее. Обычно совершенно ясно, какая технология лучше всего подходит в конкретной ситуации. Поэтому часто в одной и той же программе используют списки разных типов.
В следующих нескольких примерах предположим для удобства, что узел состоит из одного слова, которое содержит два поля — 1ИРО и ЫИК: (3) 1Иг0 11ИК При использовании связанного распределения памяти обычно подразумевается, что существует некоторый механизм поиска свободного места для нового узла при вставке новых данных в список. Это обычно выполняется с помощью специального списка свободного пространства. Здесь он будет называться списком АЧА11 (или стеком АЧАП., поскольку он обычно обрабатывается, как стек магазинного типа, т. е. по принципу "последним вошел — первым вышел" (1ааМп-бгэс-опФ)).
Набор всех неиспользуемых в данный момент узлов связан в список, который устроен так же, как и все другие списки. Переменная связи АЧА15 ссылается на самый верхний элемент этого списка. Таким образом, если необходимо присвоить переменной связи Х адрес нового узла, а сам узел зарезервировать для дальнейшего использования, то можно выполнить следующие действия: (4) Х +- АЧА11, АЧА11 +- Ь1ИК(АЧА11).
При этом из стека АЧАХЬ будет удален самый верхний элемент, а Х будет указывать на только что удаленный узел. Операция (4) в дальнейшем будет попользоваться настолько часто, что для нее лучше ввести специальное обозначение: Х ~ АЧА15 будет означать, что Х указывает на новый узел. Для удаления ненужного узла операцию (4) можно обратить: (5) 11ИК(Х) < — АЧА11, АЧА11 г — Х.
При этом узел с адресом, указанным с помощью Х, будет возвращен в список свободного пространства, а вся операция (5) будет обозначаться как АЧА1 г= Х. При обсуждении правил работы со стеком АЧА11 были опущены некоторые важные подробности. Например, ничего не было сказано о его создании после запуска программы. Очевидно, что стек может быть создан следующим образом: (а) за счет связывания всех узлов, которые предполагается использовать для организации связанной памяти, (Ъ) путем присвоения адреса первого из этих узлов переменной связи АЧА11 и (с) в результате присвоения значения Л связи последнего узла.
Набор всех выделенных таким образом узлов называется пулом (ггогаде роо1). Однако самой важной особенностью новой структуры является проверка переполнения. В операции (4) не предусмотрена проверка ситуации, когда в памяти исчерпано все свободное пространство. На самом деле для этого операция Х г= АЧА П. должна быть определена иначе: Если АЧА15 = А, то ОЧЕЕЯ.ОИ; в противном случае Х ~- АЧА1Ь, АЧА11г- 11ИК(АЧА11). (6) Возможность переполнения должна быть предусмотрена всегда! В данной ситуации переполнение (ОЧЕКРЕОИ) означает либо прекращение работы программы (к сожалению), либо запуск процедуры "сборки мусора" (ЕагЬабе со11есгюп), которая предпримет попытку поиска свободного пространства. Сборка мусора более подробно описывается в разделе 2.3.5.
Для управления стеком АУА?Ь можно использовать другую технологию, поскольку часто заранее неизйестно, какой объем памяти потребуется для пула. Для этого можно применить последовательную таблицу переменного размера, которая может сосуществовать в памяти вместе со связанными таблицами. В таком случае нужно позаботиться о том, чтобы связанная область памяти не занимала больше места, чем необходимо. Предположим, что связанная область памяти размещается в ячейках с возрастающими адресами, начиная с ?о, и что эта область никогда не выходит за пределы величины ЯЕЦМ?М (которая представляет собой текущую нижнюю границу для последовательной таблицы).
В таком случае в результате применения новой переменной РООЬМАХ происходит следующее. а) Выполняется установка АУА?Ь ~- Л и РООЬМАХ +- Ье. Ь) Операция Х с= АУА? Ь теперь выглядит так: Если АЧАП ~ Л, то Х +- АЧА?Ь, АЧА11. ~ — 01МК(АЧА1) ); иначе Х +- РООЬМАХ и РООЬМАХ +- Х + с, где с †разм узла; ОЧЕЕРЕОМ имеет место, если РООЬМАХ > ЯЕЦМ1М. (7) Р ~ АЧА?Ь, 1МРО(Р) +- У, 01МК(Р) < — Т, Т+- Р. (Я) с) Другие части программы при попытках уменьшить значение ЯЕЦМ1М подают сигнал о переполнении (ОУЕЕРЬОМ), если ЯЕЦМ?М ( РООЬМАХ.
д) Операция АУА10 ч= Х остается неизменной, т. е, такой же, как и в (5). Эта идея на самом деле представляет собой просто вставку специальной процедуры восстановления, используемой при переполнении (ОУЕЕРЬОМ) в условии (6). Суммарный результат заключается в поддержании пула наименьшего размера. Многие склонны использовать эту идею, даже если есе списки находятся в пуле (так что величина ЯЕЦМ?М остается постоянной), поскольку с ее помощью можно избежать очень неэкономной операции исходного связывания всех ячеек и к тому же упростить отладку. Кроме того, последовательный список можно разместить снизу, а пул— сверху, используя РО01М?М и ЯЕЦМАХ вместо РООЬМАХ н ЯЕЦМ?М.
Следовательно, в пуле свободных узлов довольно просто и эффективно можно выполнять поиск и возврат свободных узлов. Описанные методы предоставляют возможность получить материал для использования в связанных таблицах. Эти рассуждения основаны на неявном предположении о том, что все узлы имеют одинаковый размер, с, хотя большое значение имеют также случаи с узлами разных размеров. Их рассмотрение будет продолжено в разделе 2.5. Теперь опишем несколько наиболее общих операций со списками при работе со стеками и очередями.
Простейшим типом связанного списка является стек. На рис. 5 показан типичный стек с указателем Т иа верхний элемент стека. Когда стек пуст, этот указатель имеет значе- Рис. 5. Связанный ние Л. стек. Теперь ясно, какие операции следует выполнить для вставки (" проталкивания" ) нового элемента данных Ч сверху такого стека, используя вспомогательный указатель Р: И наоборот: для "выталкивания " верхнего элемента из стека и передачи его данных узлу У следует выполнить такие операции: Если Т = Л, то ОМОЕЕРЕОЫ; в противном случае Р е- Т, Т +- 1.ХИК(Р), У +- 1МРО(Р), АЧАП.
Ф= Р. (9) Их полезно сравнить с аналогичными механизмами работы последовательно организованных стеков, (2, а) и (3, а) в разделе 2.2.2. Читателю следует тщательно изучить операции (8) и (9), поскольку они обладают исключительной важностью. До изучения очередей найдем наиболее удобное выражение операций со стеками в программах для компьютера М11. Программа вставки элемента, где Р = гП, может выглядеть так. Определение поля 1ИРО. Определение поля ХХИК. Р +- АЧАХ1..
Верно ли АЧАХХ = й? АЧАХ). +- 1.ХИК(Р). Р ~ АУАХ1.. (10) 1ИРО(Р) +- У. ХХИК(Р) +- Т. Т+- Р. Для ее выполнения потребуется 17 тактов, по сравнению с 12 тактами для аналогичной операции в последовательной таблице (хотя для обработки события переполнения (ОЧЕЕРЬОМ) при последовательном распределении памяти в большинстве случаев необходимо гораздо больше времени). В этой программе, как и в других программах данной главы, ОЧЕКРЕОЫ обозначает либо завершение процедуры, либо подпрограмму поиска свободного пространства и возвращения в позицию г,1 — 2. Программа удаления элемента также очень проста. ОО1 Т 312 ОМОЕИРЕОМ Х.ОА 0,1(1.1МК) ЯТА Т 1.ОА 0,1(1МРО) ЯТА У 10А АУА11 ЯТА 0,1(1.1ИК) ЯТ1 АЧА11.
Р е- Т. Верно ли, что Т = й? Т +- ХХИК(Р). У +- 1ИРО(Р). ХХИК(Р) +- АУАП. АЧА11. ~ Р. АЧАХХ. +- Р. ) э Интересно, что для выполнения этих операций необходимо осуществить циклическую перестановку трех ссылок. Допустим, что перед выполнением операции вставки элемента указатель Р равен АЧАХЕ. Если Р ~ Л, то после выполнения этой операции значение АЧА1Е стало равным предыдущему значению Е1МК(Р), значение 11МК(Р) стало равным предыдущему значению Т и значение Т стало равным предыдущему значению АУА11.. 1МРО ЕЦО 11МК ЕЦО 101 312 1ОА ЯТА ЕОА ЯТА ЕОА ЯТА ЯТ1 0:3 Ипб АУА11.
ОЧЕЕРЕОМ 0,1(11МК) АЧА11. у 0,1ПМРО) Т 0,1(1.1МК) Т Таким образом, процесс вставки (за исключением присвоения 1яРО(Р) +- Т) является циклической перестановкой АУА11 У 1 11111УУ Аналогично в случае удаления элемента, если до выполнения этой операции г имеет значение Т и предполагается, что Р ф Л, получим Т < — 1яРО(Р) и У АУА11 1 (УА Факт цикличности этой перестановки на самом деле здесь не так уж и важен, поскольку любая перестановка трех элементов со смещением каждого элемента является циклической. Гораздо важнее то, что в данных операциях изменяются в точности три связи. Хотя алгоритмы вставки и удаления (8) и (9) созданы для стеков, их можно применять и в более широком смысле для вставки и удаления в любом линейном списке.
Допустим, требуется вставить элемент непосредственно перед узлом, на который указывает переменная связи Т. Тогда вставка элемента 2-' в приведенном выше списке (2) может быть выполнена с помощью операции (8), где Т = 11ИК 0.1АУК(РТКЯТ) ). Связанное распределение памяти особенно удобно применять для очередей. Нетрудно заметить, что связи должны быть направлены от начала очереди к ее концу, а при удалении начального узла должен существовать механизм прямого указания нового начального узла. Здесь указатели начального и конечного узлов очереди будут обозначены символами Р и 8 соответственно: За исключением указателя й, эта схема практически идентична схеме на рис. 5 на с.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
