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

   Реализация Л2–списка на базе вектора также могла бы быть произведена с
помощью добавления в каждое звено цепи (элемент массива типа Memory-
ForLists ) поля Prev ссылки на предшествующее звено. Однако с целью эко-
номии памяти может быть рекомендована замена пары полей Next и Prev од-
ним полем Diff, предназначенным для хранения разности ссылок на
последующее и предшествующее звенья. Макет модуля L2ListV, содержащий
описание соответствующих типов данных, приведен на рис.1.15. Описанный в
модуле тип данных L2_listV соответствует типу данных L_list расширенной
функциональной спецификации. Для краткости в макет модуля не включены
заголовки и блоки процедур и функций.


 Unit L2ListV; { Реализация ограниченного L2-списка на Турбо-Паскале }
 Interface
 Uses Global; { модуль, в котором описан тип элементов списка El }
                 {Ссылочное представление на базе вектора }
 {const MemMaxSize = максимальный размер "рабочей" памяти, описан в модуле
 Global}
 type Index = 0..MemMaxSize;
 Link = Index; { ссылка на звено цепи                  }
ecord {формуляр ("представитель") списка }
 Head , Cur, PredCur : Link ;
    end { RepList };
    L2_listV = RepList; { Л2–список = формуляр списка }
     ... { Здесь на месте ... размещаются заголовки процедур и функций          }
 Implementation
 const NilLst = 0;         { nil для списков, в том числе для списка свободной памяти
 }
 type DiffLink = - MemMaxSize..MemMaxSize;
 record               {звено цепи ( списка ) :              }
    Info : El;        { - содержимое (элемент списка) }
    Diff : DiffLink; { - разность ссылок                    }
 end { Node } ;
 MemoryForLists = array [ Index ] of Node;
 { "рабочий" массив для размещения списков }
 var Memory : MemoryForLists; i : Index;
    ...       {Здесь на месте “...” размещаются блоки процедур и функций }
 begin
 { инициализация списка свободной памяти в массиве Memory }
 Memory [ 0 ] . Diff := 1;
 for i := 1 to ( MemMaxSize – 1 ) do Memory [ i ] . Diff := 2 ;
 Memory [ MemMaxSize ] . Diff := NilLst - ( MemMaxSize - 1 );
 end { L2ListV }.

                            Рис. 1.15. Макет модуля L2ListV



                                          16