Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Алгоритмы / Глава 2_Инф._структуры.doc
Скачиваний:
70
Добавлен:
15.02.2015
Размер:
1.28 Mб
Скачать

2.2. Хранение линейных списков

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

Будем обозначать через адрес объектав памяти компьютера. Если элемент списка занимаетадресуемых единиц памяти (ячеек, байтов, слов), то .

Начало списка задаётся базовым адресом таким образом, что

. (16)

Последовательное распределение памяти при работе со стеком. Со стеком связывается переменная , называемаяуказателем стека. В случае пустого стека указателю присваивается нулевое значение: .

Вставка нового элемента реализуется следующими действиями:

.

Удаление элемента из непустого стека (когда ) реализуется в два шага: отправка верхнего элемента на обработку в переменнуюи уменьшение значения указателя на единицу и:

.

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

Вставка нового элемента в конец очереди реализуется следующими действиями:

.

При удалении элемента из начала непустой очереди производится присваивание

.

В результате память, занятая ранее этим элементом, учитывается операционной системой как свободная. Если перед удалением было , то есть единственный элемент очереди был и первым, и последним, то, и список становится пустым.

Если указанным способом производятся сначала вставка элемента в конец очереди, а затем удаление элемента из её начала, то, хотя длина очереди в результате оказывается прежней, все адреса увеличиваются на . При большом числе повторений они могут превзойти допустимый верхний предел (переполнение памяти). Поэтому такая организация вставок/удалений приемлема, только если ожидаемо регулярное опустошение очереди, когда оказывается.

Избежать переполнения памяти при работе с очередью можно путём выделения фиксированного числа , при котором упорядоченность элементов списка зацикливается, и считается, что следует в очереди за . Тогда вставка элемента в конец очереди реализуется присваиваниями:

если , то , в противном случае ;;

если , то, в противном случае ;.

Описанное зацикливание ограничивает длину очереди числом .

Возможно расположение в общем сегменте памяти двух списков-очередей с переменной длиной (динамических), растущих навстречу другу из крайних ячеек (рис. 4). Это, разумеется, окажется эффективным, если имеются основания считать маловероятным быстрый одновременный рост обеих очередей.

Рис. 4.

Расположение бóльшего числа списков в общем сегменте памяти предполагает отказ от фиксации адресов начальных элементов этих списков, что требует переписывания списков в новые участки при их сдвигах внутри общего сегмента. Здесь мы имеем дело с постоянно возникающей в программировании альтернативой <экономия памяти экономия времени>.

Связанное распределение памяти при работе со списками. Последовательное распределение памяти для хранения списков требует выделения сегмента памяти, недоступного для других данных, даже если этот сегмент занят не полностью. Более гибким методом является связанное (иначе — цепное) распределение, при котором наряду с другими полями каждый элемент списка содержит дополнительное адресное поле, в котором хранится адрес следующего элемента, либо признак его отсутствия (рис. 5). При этом программа обслуживания списка должна содержать отдельную переменную (указатель списка), значением которой является адрес начального элемента списка.

Рис. 5.

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

2. Удаление элемента из связанного списка с произвольным доступом сводится лишь к изменению адресной части предыдущего элемента, которая теперь должна принять значение адресной части элемента, следуемого за удаляемым. В то же время при последовательном распределении удаление элемента предполагает сдвиг части списка на новые адреса.

3. Вставка нового элемента междуив связанный список с произвольным доступом сводится к трём действиям:

1) адрес элемента запоминается во вспомогательной переменной;

2) в адресное поле элемента заносится адрес элемента, до этого находившийся в адресном поле элемента;

3) в адресное поле элемента записывается адрес расположения, хранящийся в ячейке.

NB: Здесь существенен порядок действий: при их перестановке адрес элемента будет утрачен после его замены на адрес. Вообще обмен значениями между переменнымиидолжен проводиться с использованием вспомогательной переменной:.

4. Доступ к произвольному элементу списка быстрее реализуется при последовательном распределении памяти: доступ к элементу с номером занимает фиксированное время, затрачиваемое на вычисление адреса по приведённой выше схеме (16). В то же время при связанном распределении нужно пройти по всем предшествующим элементам, чтобы, дойдя до -го элемента, определить адрес -го.

5. Объединение двух списков, как и разбиение списка на два, быстрее реализуются для связанных списков.

6. Схема цепной адресации при последовательном распределении памяти позволяет организовывать более сложные структуры, чем линейные списки. В частности, её можно применить для организации переменного количества списков переменной длины, а также для создания перекрёстных ссылок.

7. Время доступа к элементам связанного списка может резко возрастать при их попадании на разные сегменты внешнего устройства, предназначенного для хранения больших объёмов информации.

8. Связанное распределение памяти предполагает использование процедуры поиска свободной ячейки для размещения нового элемента. Для этого заводится список свободного пространства, реализуемый как стек с цепной адресацией и дисциплиной lifo («последний пришёл – первый ушёл»).