Д. Кнут - Искусство программирования том 1 (1119450), страница 67
Текст из файла (страница 67)
Если с > 1, то в некоторых случаях удобнее разбить единый список на с "параллельных" списков таким образом, чтобы?с-е слово узла Х (у) хранилось на фиксированном расстоянии от первого слова Х (2), которое зависит от й. Однако в дальнейшем предположим, что смежные группы по с слов образуют единый узел.) Вообще, 1.ОС (Х (2) ) = 1.о + с?, где 1.о — константа, которая называется базовым адресом (6аэе пай(геээ), т. е. является адресом некоего узла Х(0]. Такой способ представления линейного списка настолько очевиден и хорошо известен, что его более глубокое изучение может показаться вовсе ненужным. Однако, как будет показано в данной главе, существует несколько других, более "изощренных" методов представления списков.
Поэтому, прежде чем рассматривать более сложные случаи, было бы разумно изучить возможности этого простого способа. Очень важно ясно представлять себе как его недостатки, так и преимущества. Последовательное распределение очень удобно при работе со сшеко.н. Для этого достаточно иметь переменную Т, которая называется указателем стека (э(ас6 ро(п1ег). Если стек пуст, то Т = О.
Для ввода нового элемента Т в стек следует выполнить такие действия: (2) Т+-Т+1; ХГТ) +-Т. А если стек не пуст, можем положить У равным верхнему узлу и удалить этот узел, выполнив действия, обратные действиям (2): (3) У+- Х(Т); Т+- Т вЂ” 1. (Внутри компьютера эффективнее было бы оперировать значениями сТ вместо Т в силу соотношений (1). Такие изменения можно выполнить достаточно легко, поэтому дальнейшие оассуждения продолжим, полагая, что с = 1.) Представление очереди или дека организовано несколько сложнее.
Очевидным решением могло бы быть применение двух указателей, г и й (для начала и конца очереди), где Р = й = О, если очередь пуста. Тогда вставка элемента с конца очереди может быть выполнена с помощью следующих действий; (4) й < — й + 1; Х [й] <- Т. Удаление же узла в начале очереди (Р указывает на ячейку, расположенную перед начальным элементом очереди) может быть выполнено с помощью других действий: (5) Г < — г + 1; Т +- Х[Р]; если Р = й, то Р +- й <†О. Следует отметить, что, если при такой организации работы очереди й всегда опережает Р (*.
е. в очереди всегда имеется хотя бы один узел), элементы таблицы Х [13, Х [21,, Х [10003, ... будут последовательно заниматься вплоть до бесконечности, что приведет к расточительному использованию памяти. Следовательно, простой метод на основе опеоаций (4) и ('5) нужно использовать только тогда, когда известно, .то г настигает Я дгстаточно регулярно, например если все удаления выполняются ока ь:ообразно с полным опустошением очереди. Чтобы разрешить задачу переполнения памяти при такой организации очереди, мо кио выделить М узлов Х[1],...,Х[М3, неявно образующих замкнутое кольцо, в котором за Х[М] следует Х[1]. Тогда описанные выше действия (4) и (5) будут выглядеть так: если й=М, той< — 1, в противном случае йс — й+1; Х[й] <-Т; (6) если г =М, то Р < — 1, в противном случае Е < — Р+1; Т < — Х[р].
(7) [т -т+1; Х ~ Т (вставка в стек): ~ если Т > М, то Оуййг1.0М; Х[Т] +- Т. ( если Т = О, то ОИОЕЕИ.ОЫ; Т ~ Х (удаление из стека): ~ Т с — Х [Т3; Т+- Т вЂ” 1. (2, а) (3, а) Фактически циклическая организация очереди уже встречалась ранее, при описании буферов ввода-вывода в разделе 1.4.4. До сих пор эти рассуждения были далеки от реальности, поскольку неявно предполагалось отсутствие каких-либо нежелательных ситуаций. Например, при удалении узла из стека или очереди допускалось, что в них остается по крайней мере еще один узел. А при вставке узла в стек или очередь допускалось, что для него найдется свободное место в памяти.
Но, очевидно, при использовании метода ьэ основе действий (6) и (7) предполагается, что в очереди может быть не более М узлов, а при использовании (2)-(5) значения Т и й в данной программе не могут превышать определенный максимум. В общем случае, когда такие ограничения не выполняются автоматически, следует предпринять следующие действия: если Н гл М, то Н < — 1, в противном случае Н +- Н+ 1; Х ч= У (вставка в очередь): если Н = Р, то ОЧЕНРЬОИ; Х[Н] +- У. (6, а) если Р = Н, то 1ЛО)ЕНРЬОЫ; если Р = М, то Р < — 1, в противном случае Р < — Р+ 1; У+- Х[Р]. У ~ Х (удаление из очереди): Доступное пространство Начало памяти Конец памяти Низ Верх Низ Верх Здесь предполагается, что набор узлов Х[1],...,Х[М] образует общее пространство, доступное для организации списка.
А обозначения ОЧЕНРЬОЫ (переполнение) и ОМОЕНРЬОЧ (отсутствие) означают избыток или недостаток элементов. Теперь при использовании условий (6, а) и (7, а) начальное условие Р = Н = О для указателей очереди будет недействительным, поскольку избыток элементов (ОЧЕНРЬОЫ) не будет зафиксирован при Р = О. Поэтому в качестве начального условия следует, например, выбрать Р = Н = 1. Читателю настоятельно рекомендуется выполнить упр.
1, в котором обсуждается нетривиальный аспект этого простого механизма организации очереди. В таком случае возникает вопрос: "Что нужно сделать при недостатке (ОМОЕНРЬОЫ) или избытке (ОЧЕНРЬОИ) элементов? Недостаток (ОИОЕНРЬОЧ) возникает при попытке удалить несуществующий элемент. Обычно эта ситуация рассматривается вовсе не как ошибка, а как некое условие с определенным смыслом, которое может быть использовано для управления потоком выполнения программы. Например, можно удалять элементы до тех пор, пока не наступит их недостаток (ОМОЕНРЬОЧ). Однако избыток (ОЧЕНРЬОУ) обычно свидетельствует об ошибке.
Это значит, что таблица уже полностью заполнена, хотя в нее еще следует ввести некоторую информацию. При возникновении такой ситуации сначала обычно поступает сообщение о том, что программа не может продолжать работу, поскольку исчерпана емкость хранилища, а затем выполнение программы прекращается.
Конечно, вряд ли стоит прерывать выполнение программы в случае возникновения избытка (ОЧЕНРЬОЧ), когда переполняется только один список, а в других списках той же программы еще остается достаточно свободного места. Выше предполагалось, что в программе имеется всего один список. Тем не менее довольно часто на практике используются программы с несколькими стеками, причем размер каждого из них может динамически изменяться. В таком случае не следует накладывать какое-либо ограничение на максимальный размер каждого стека, поскольку его размер непредсказуем. Даже если дця каждого стека будет определен его максимальный размер, вряд ли возникнет ситуация, когда одновременно переполнятся все стеки. Сосуществование всего двух списков с изменяемой длиной можно довольно просто организовать за счет роста их навстречу друг другу, как показано ниже.
Программа и таблицы Программа и таблицы фиксированного фиксированного размера Список 1 Список 2 РазмеРа Здесь список 1 расширяется вправо, а список 2 (хранящийся в обратном порядке)— влево. Избыток (ОЧЕЕРЬОэ) не будет происходить до тех пор, пока общий размер обоих списков не будет превышать размер всего доступного пространства в памяти компьютера. Такие спискй могут независимо расширяться и сжиматься так, что фактический максимальный размер каждого из них может существенно превышать половину всего доступного им пространства.
Такая схема использования памяти часто применяется на практике. Однако довольно просто можно убедиться в том, что нельзя организовать хранение в памяти компьютера трех и более последовательных списков с изменяемой длиной и соблюсти следующие условия: (а) избыток (ОЧЕВРЬОЧ) должен происходить только тогда, когда общий размер всех списков превышает размер доступного для них пространства, (Ь) "нижний" элемент каждого списка должен иметь фиксированное место расположения, Проблема эффективного распределения пространства памяти для хранения списков становится очень важной прн работе с десятью или более списками с изменяемыми размерами.
Причем такие ситуации являются довольно обычными. В подобном случае для удовлетворения условия (а) придется пренебречь условием (Ь), т. е. позволить "нижним" элементам изменять их расположение. Это значит, что адрес Ьэ в уравнении (1) уже не является постоянным, причем теперь нельзя будет делать ссылки на таблицу с помощью абсолютного адреса, поскольку все ссылки должны указываться относительно базового адреса Ьэ. В компьютере И1Х код вставки 1-го однословного узла в регистр А,который выглядел как 101 1 1.01 1 ЬОА ВАЯЕ(0;2) А ,,1 ' тепеРь будет, напРимеР, таким' яТА *+1(0:2) ' (8) ЬРА эО1 ОООО~О*~~'О О О.ПЩО*ОО вилно, выполняется дольше, чем адресация по фиксированному базовому адресу, но не намного, если в компьютере И1Х реализована возможность "косвенной адресации" (!пб!гес1 а<Ыгеээ!пЕ) (см.
упр. 3). Особенно важным является случай, когда каждый список с изменяемой длиной является стеком. Тогда код может быть таким же эффективным, как и прежде, поскольку в любой момент приходится иметь дело только с верхним элементом каждого стека. Алгоритм вставки и удаления элементов в и стеках будет выглядеть следующим образом (здесь ВАЯЕ[1] и ТОР [П вЂ” переменные связи 1-го стека, а каждый узел составляет одно слово). Вставка: ТОР[1] < — ТОРЫ +1; если ТОР[1] > ВАЯЕ[1+1], то ОЧЕКРЬОМ; в противном случае СОИТЕИТЯ(ТОР [1]) +- 7 (9) Удаление: если ТОРЫ = ВАЯЕ[1], то ОИОЕНРЬОЧ; в противном случае Ч с — СОИТЕИТЯ(ТОРИ), ТОРЫ +- ТОРИ вЂ” 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
