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

                 1.2. Л1–список как абстрактный тип данных

   Рассмотрим Л1–список как абстрактный тип данных (АТД), определяя
его через класс базовых операций, которые (и только они) выполняются над
Л1–списком. Все остальные действия над Л1–списком реализуются на основе
этих операций.
   Перед тем, как задать функциональную спецификацию Л1–списка, полезно
рассмотреть его неформальную модель. Будем считать, что состояние списка
задается не только перечислением набора элементов, но и дополнительно ука-
занием одного из них в качестве текущего (очередного). Относительно этого
элемента будет определяться семантика базовых операций. Заданием текуще-
го элемента список разделяется на две части: от начала до текущего элемента
(пройденная часть) и от текущего элемента (включая его) до конца списка
(рис. 1.5). К элементам пройденной части можно получить доступ, только на-
чиная просмотр списка сначала. В непройденной части доступны все элемен-
ты поочередно, начиная с текущего элемента.




         Пройденная часть                Текущий
                                         элемент


                               Рис. 1.5. Модель Л1-списка

    Определим Л1-список, задав набор базовых операций с помощью функ-
циональной спецификации, приведенной на рис.1.6. Используем обозначения:
L_list – тип линейного списка, El – тип элементов списка, а знаком × обозна-
чим декартово произведение множеств.
    Пусть w = [ x1, x2, ..., xn ] – последовательность элементов типа El. Для
формального описания семантики базовых операций используем две вспомо-
гательные функции над непустыми последовательностями: First(w) = x1 – пер-
вый элемент последовательности, Rest( w ) = [ x2, x3, ..., xn ] – остаток последо-
вательности.           Операция           Prefix      добавляет   элемент     в    начало
последовательности: Prefix ( x0, w ) = = [ x0, x1, x2, ..., xn ], Prefix( First( w ),
Rest( w ) ) = w, а операция Postfix дописывает элемент в конец последователь-
ности: Postfix( w, x) = [ x1, x2, ..., xn, x ]. Операцию Postfix будем также записы-
вать в инфиксной форме, используя знак * для обозначения этой операции:
[ x1, x2, ..., xn ] * x = [ x1, x2, ..., xn, x ]. Пустую последовательность [ ] обозначим
символом ∆. Тогда Postfix(∆, x)= ∆ * x = Prefix( x, ∆ ) = [ x ], First( [ x ] ) = x,
Rest( [ x ] ) = ∆.


                                           6