Динамические структуры данных. Алексеев А.Ю - 12 стр.

Memory [             0           1           2        3       4     5           6       7        8        9     10   11          12 ]
 .Info :                                 a                        b                 d                                c
 .Next :         8           3           5       4        6       11        0       0        9       10       12     7       1

s.Head = 2

                                                                        a



           Head                      2                    Head                  2                    Head                0
   s:      Cur           :                       s:       Cur      :            0           l:       Cur       :         0
                                     2
           PredCur:                  0                    PredCur:              7                    PredCur:            0

               б                         в                           г
      Рис. 1.10. Представление ограниченного Л1–списка при ссылочной реализации
      на базе вектора: а – размещение списка s в массиве Memory; б,в – формуляры
  списка s в состояниях BOList и EOList соответственно; г – формуляр пустого списка l

     На рис. 1.11 изображен макет секции Interface модуля L1ListV, реали-
зующего на Турбо–Паскале типы данных и базовые операции Л1–списка на
базе вектора. Типу L_list функциональной спецификации здесь соответствует
тип L1_listV, а список идентифицируется записью типа RepList. При необхо-
димости можно добиться большего соответствия с предыдущей реализацией,
представляя список указателем на такую запись: type L1_listV = ^ RepList.
     Заметим, что описание массива Memory, предназначенного для хранения
элементов списков, равно как и описание соответствующего типа данных Me-
moryForLists, помещено в секцию Implementation модуля L1ListV
(рис. 1.12). Начальное состояние списка свободной памяти задается в секции
инициализации и устанавливается в процессе загрузки модуля L1ListV, а в мо-
дуле Global (рис.1. 13) теперь задается не только тип El элементов списка, но
и размер MemMaxSize поля памяти, отведенного для размещения списков.
     Обратим внимание на то, что здесь некоторые операции могут быть реа-
лизованы более эффективно, чем в случае с динамической памятью. Напри-
мер, при выполнении операций Empty( s ) и Destroy( s ) необходимо освобо-
дить память, занимаемую списком s. Освобождение динамической памяти,
занятой под каждый элемент списка, производится с помощью вызова предна-
значенной для этого процедуры ( dispose в языке Паскаль). Освобождение же
занятой под список части массива может быть проделано непосредственным
изменением ссылок: последний элемент "опустошаемого" списка s должен те-
перь ссылаться на прежний первый элемент списка свободной памяти, а пер-
                                                                   12