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

ментов типа El, и пусть Last( w ) = xn – последний элемент последовательности
w, а Lead( w ) = [ x1, x2, ..., xn-1 ], так что Postfix( Lead( w ), Last( w ) ) = w. Тогда
Op12:       {s0 = s }
            GoEOL( s )
            { Left( s ) = Seq( s0 ) & Right( s ) = Δ }
Op13:       { s0 = s & L = Left( s ) }
            b := BOList( s )
            { s0 = s & b = ( L = Δ ) }
Op14:       {not Null( s ) & not BOList( s ) & L = Left( s ) & R = Right( s ) }
            GoPrev( s )
            {Left( s ) = Lead( L ) & Right( s ) = Prefix( Last( L ) , R ) }


12. GoEOL : L_list → L_list         Встать в конец списка
13. BOList : L_list → Boolean       Начало списка (текущим является первый эле-
                                    мент списка)
14. GoPrev : L_list → L_list        Перейти к предыдущему элементу;
                                    отказ: в состояниях Null иBOList

                 Рис. 1.14. Дополнительные базовые операции Л2–списка

   На Паскале реализация цепного представления Л2–списка в связанной па-
мяти может быть выполнена, например, с использованием следующих типов
данных:
type El = ... ;                       { базовый тип для элементов списка}
     Link = ^ Node;                   { cсылка на звено цепи}
     Node = record                    { звено цепи ( списка ) :         }
            Info : El;                { - содержимое (элемент списка)   }
            Next : Link;              { - ссылка на следующее звено     }
            Prev : Link;              { - ссылка на предшествующее звено}
        end { Node } ;
   По сравнению с Л1–списком это означает добавление поля Prev ссылки на
предшествующее звено в каждое звено цепи. Формуляр списка здесь может
иметь тот же вид, что и при реализации L1–списка. В этом случае в поле Prev
первого элемента списка следует хранить ссылку на последний элемент. В ка-
честве формуляра списка можно использовать также запись вида
type
      RepList = record         {формуляр ("представитель") списка }
                   Head , Cur, Last : Link;
              end { RepList } ;
в поле Last которой будет храниться ссылка на последний элемент списка.
Особые случаи при этом определяются как
Null                ↔ ( Head = nil ) & ( Cur = nil ) & ( Last = nil );
BOList & not Null ↔ ( Head = Cur ≠ nil ) & ( Last ≠ nil );
EOList & not Null ↔ ( Head ≠ nil ) & ( Last ≠ nil ) & ( Cur = nil ).
                                           15