Модели и структуры данных



         

Операции обработки списков


Базовыми операциями при обработке списков являются операции (функции): car, cdr, cons и atom.

Операция car в качестве аргумента получает список (указатель на начало списка). Ее возвращаемым значением является первый элемент этого списка (указатель на первый элемент). Например:

  • если X - список (2,6,4,7), то car(X) - атом 2;
  • если X - список ((1,2),6), то car(X) - список (1,2);
  • если X - атом то car(X) не имеет смысла и в действительности не определено.

Операция cdr в качестве аргумента также получает список. Ее возвращаемым значением является остаток списка - указатель на список после удаления из него первого элемента. Например:

  • если X - (2,6,4), то cdr(X) - (6,4);
  • если X - ((1,2),6,5), то cdr(X) - (6,5);
  • если список X содержит один элемент, то cdr(X) равно nil.

Операция cons имеет два аргумента: указатель на элемент списка и указатель на список. Операция включает аргумент-элемент в начало аргумента-списка и возвращает указатель на получившийся список. Например:

  • если X - 2, а Y - (6,4,7), то cons(X,Y) - (2,6,4,7);
  • если X - (1,2), Y - (6,4,7), то cons(X,Y) - ((1,2),6,4,7).

Операция atom выполняет проверку типа элемента списка. Она должна возвращать логическое значение: true - если ее аргумент является атомом или false - если ее аргумент является подсписком.

В программном примере 5.11 приведена реализация описанных операций как функций языка PASCAL. Структура элемента списка, обрабатываемого функциями этого модуля определена в нем как тип litem и полностью соответствует рис.5.16. Помимо описанных операций в модуле определены также функции выделения памяти для дескриптора данных - NewAtom и для элемента списка - NewNode. Реали- зация операций настолько проста, что не требует дополнительных пояснений.

{==== Программный пример 5.11 ====} { Элементарные операции для работы со списками } Unit ListWork; Interface type lpt = ^litem; { указатель на элемент списка } litem = record typeflg : char; { Char(0) - узел, иначе - код типа } down : pointer; { указатель на данные или на подсписок } next: lpt; { указатель на текущем уровне } end; Function NewAtom(d: pointer; t : char) : lpt; Function NewNode(d: lpt) : lpt; Function Atom(l : lpt) : boolean; Function Cdr(l : lpt) : lpt; Function Car(l : lpt) : lpt; Function Cons(l1, l : lpt) : lpt; Function Append(l1,l : lpt) : lpt; Implementation {*** создание дескриптора для атома } Function NewAtom(d: pointer; t : char) : lpt; var l : lpt; begin New(l); l^.typeflg:=t; { тип данных атома } l^.down:=d; { указатель на данные } l^.next:=nil; NewAtom:=l; end; {*** создание элемента списка для подсписка } Function NewNode(d: lpt) : lpt; var l : lpt; begin New(l); l^.typeflg:=Chr(0); { признак подсписка } l^.down:=d; { указатель на начало подсписка } l^.next:=nil; NewNode:=l; end; {*** проверка элемента списка: true - атом, false - подсписок } Function Atom(l : lpt) : boolean; begin { проверка поля типа } if l^.typeflg=Chr(0) then Atom:=false else Atom:=true; end; Function Car(l : lpt) : lpt; {выборка 1-го элемента из списка } begin Car:=l^.down; { выборка - указатель вниз } end; Function Cdr(l : lpt) : lpt;{исключение 1-го элемента из списка} begin Cdr:=l^.next; { выборка - указатель вправо } end; {*** добавление элемента в начало списка } Function Cons(l1,l : lpt) : lpt; var l2 : lpt; begin l2:=NewNode(l1); { элемент списка для добавляемого } l2^.next:=l; { в начало списка } Cons:=l2; { возвращается новое начало списка } end; {*** добавление элемента в конец списка } Function Append(l1,l : lpt) : lpt; var l2, l3 : lpt; begin l2:=NewNode(l1); { элемент списка для добавляемого } { если список пустой - он будет состоять из одного эл-та } if l=nil then Append:=l2 else begin { выход на последний эл-т списка } l3:=l; while l3^.next <> nil do l3:=l3^.next; l3^.next:=l2; { подключение нового эл-та к последнему } Append:=l; { функция возвращает тот же указатель } end; end; END.




Содержание  Назад  Вперед