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