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