ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 19.04.2024

Просмотров: 86

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

Операция 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 - если ее аргумент является подсписком.

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

{==== Программный пример ====}

{ Элементарные операции для работы со списками }

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.

В данном примере в модуль базовых операций включена функция Append - добавления элемента в конец списка. На самом деле эта операция не является базовой, она может быть реализована с использованием описанных базовых операций, без обращения к внутренней структуре элемента списка, хотя, конечно, такая реализация будет менее быстродействующей. В программном примере приведена реализация нескольких простых функций обработки списков, которые могут быть полезными при решении широкого спектра задач. В функциях этого модуля, однако, не используется внутренняя структура элемента списка.

{==== Программный пример ====}

{ Вторичные функции обработки списков }

Unit ListW1;

Interface

uses listwork;

Function Append(x, l : lpt) : lpt;

Function ListRev(l, q : lpt) : lpt;

Function FlatList(l, q : lpt) : lpt;

Function InsList(x, l : lpt; m : integer) : lpt;

Function DelList(l : lpt; m : integer) : lpt;

Function ExchngList(l : lpt; m : integer) : lpt;

Implementation

{*** добавление в конец списка l нового элемента x }

Function Append(x, l : lpt) : lpt;

begin

{ если список пустой - добавить x в начало пустого списка }

if l=nil then Append:=cons(x,l)

{ если список непустой

- взять тот же список без 1-го эл-та - cdr(l);

- добавить в его конец эл-т x;

- добавить в начало 1-й эл-т списка }

else Append:=cons(car(l),Append(x,cdr(l)));

end; { Function Append }

{*** Реверс списка l; список q - результирующий, при первом

вызове он должен быть пустым }

Function ListRev(l, q : lpt) : lpt;

begin

{ если входной список исчерпан, вернуть выходной список }


if l=nil then ListRev:=q

{ иначе: - добавить 1-й эл-т вх.списка в начало вых.списка,

- реверсировать, имея вх. список без 1-го эл-та, а вых.список

- с добавленным эл-том }

else ListRev:=ListRev(cdr(l),cons(car(l),q));

end; { Function ListRev }

{*** Превращение разветвленного списка l в линейный; список q

- результирующий, при первом вызове он должен быть пустым }

Function FlatList(l, q : lpt) : lpt;

begin

{ если входной список исчерпан, вернуть выходной список }

if l=nil then FlatList:=q

else

{ если 1-й эл-т вх. списка - атом, то

- сделать "плоской" часть вх. списка без 1-го эл-та;

- добавить в ее начало 1-й эл-т }

if atom(car(l)) then

FlatList:=cons(car(l),FlatList(cdr(l),q))

{ если 1-й эл-т вх. списка - подсписок, то

- сделать "плоской" часть вх.списка без 1-го эл-та;

- сделать "плоским" подсписок 1-го эл-та }

else FlatList:=FlatList(car(l),FlatList(cdr(l),q));

end; { Function FlatList }

{*** вставка в список l элемента x на место с номером m

( здесь и далее нумерация эл-тов в списке начинается с 0 ) }

Function InsList(x, l : lpt; m : integer) : lpt;

begin

{ если m=0, эл-т вставляется в начало списка }

if m=0 then InsList:=cons(x,l)

{ если список пустой, он и остается пустым }

else if l=nil then InsList:=nil

{ - вставить эл-т x на место m-1 в список без 1-го эл-та;

- в начало полученного списка вставить 1-й эл-т }

else InsList:=cons(car(l),InsList(x,cdr(l),m-1));

end; { Function InsList }

{*** удаление из списка l на месте с номером m }

Function DelList(l : lpt; m : integer) : lpt;

begin

{ если список пустой, он и остается пустым }

if l=nil then DelList:=nil

{ если m=0, эл-т удаляется из начала списка }

else if m=0 then DelList:=cdr(l)

{ - удалить эл-т x на месте m-1 в список без 1-го эл-та;

- в начало полученного списка вставить 1-й эл-т }

else DelList:=cons(car(l),DelList(cdr(l),m-1));

end; { Function DelList }

{*** перестановка в списке l эл-тов местах с номерами m и m+1 }

Function ExchngList(l : lpt; m : integer) : lpt;

begin { если список пустой, он и остается пустым }

if l=nil then ExchngList:=nil

else if m=0 then

{если m=0, а следующего эл-та нет, список остается без изменений}

if cdr(l)=nil then ExchngList:=l

{ если m=0 ( обмен 0-го и 1-го эл-тов):

- берется список без двух 1-ых эл-тов - cdr(cdr(l));

- в его начало добавляется 0-й эл-т;

- в начало полученного списка добавляется 1-й эл-т - car(cdr(l))}

else ExchngList:= cons(car(cdr(l)),cons(car(l),cdr(cdr(l))))

else ExchngList:=cons(car(l),ExchngList(cdr(l),m-1));

end; { Function ExchngList }

END.

Функция Append добавляет элемент x в конец списка 1 .

Поскольку аргумент-список не пустой, выполняется ветвь else. Она содержит оператор:

Append:=cons(car(l),Append(x,cdr(l)));

Важно точно представить себе последовательность действий по выполнению этого оператора:


  • car(l) = 1;

  • cdr(l) = (2,3);

  • Append(4,(2,3))) - при этом рекурсивном вызове выполнение вновь пойдет по ветви else, в которой:

    • car(l) = 2;

    • cdr(l) = (3);

    • Append(4,(3))) - выполнение вновь пойдет по ветви else, в которой:

      • car(l) = 3;

      • cdr(l) = nil;

      • Append(4,nil) - в этом вызове список-аргумент пустой, поэтому выполнится Append:=cons(4,nil) и вызов вернет список: (4);

      • cons(car(l),Append(x,cdr(l))) - значения аргументов функции cons - для этого уровня вызовов: cons(3,(4)) = (3,4);

      • на этом уровне Append возвращает список (3,4);

      • cons(car(l),Append(x,cdr(l))) - на этом уровне: cons(2,(3,4)) = (2,3,4);

      • на этом уровне Append возвращает список (2,3,4);

      • cons(car(l),Append(x,cdr(l))) - на этом уровне: cons(1,(2,3,4)) = (1,2,3,4);

      • на этом уровне Append возвращает список (1,2,3,4).

Функция ListRev выполняет инвертирование списка - изменения порядка следования его элементов на противоположный. При обращении к функции ее второй аргумент должен иметь значение nil. Пример: ListRev(1,(2,3),4),nil).

Входной список не пустой, поэтому выполнение идет по ветви else, где:

ListRev:=ListRev(cdr(l),cons(car(l),q));

Последовательность действий:

  • cdr(l) = ((2,3),4);

  • car(l) = 1;

  • cons(car(l),q) = (1) - список q при этом - пустой;

  • рекурсивный вызов ListRev( ((2,3),4), (1)):

    • cdr(l) = (4);

    • car(l) = (2,3);

    • cons(car(l),q) = ((2,3),1) - список q - (1);

    • рекурсивный вызов ListRev((4), ((2,3),1)):

      • cdr(l) = nil;

      • car(l) = 4;

      • cons(car(l),q) = (4,(2,3),1);

      • рекурсивный вызов ListRev(nil, (4,(2,3),1)):

        • поскольку исходный список пустой, вызов возвращает список: (4,(2,3),1);

      • вызов возвращает список: (4,(2,3),1);

    • вызов возвращает список: (4,(2,3),1);

  • вызов возвращает список: (4,(2,3),1).

Функция Creat_Lst преобразует исходную строку в список. В функции поэлементно анализируются символы строки. Различаемые символы: левая круглая скобка, правая скобка, знаки операций и цифры. Цифровые символы накапливаются в промежуточной строке. Когда встречается символ-разделитель - правая скобка или знак операции накопленная строка преобразуется в число, для него создается атом с типом 'I' и включается в конец списка. Для знака операции создается атом с типом 'C' и тоже включается в конец списка. Левая скобка приводит к рекурсивному вызову Creat_Lst. Этот вызов формирует список для подвыражения в скобках, формирование списка заканчивается при появлении правой скобки. Для сформированного таким образом списка создается узел, и он включается в основной список как подсписок.


Функция - FormPrty - выделяет в отдельные подсписки операции умножения и деления, имеющие более высокий приоритет, и их операнды. Функция просматривает список и выделяет в нем последовательные тройки элементов "операнд-знак-операнд". Если один из операндов является подсписком, то он обрабатывается функцией FormPrty. Если знак является одним из приоритетных знаков, то из тройки формируется подсписок, который становится первым операндом для следующей тройки. Если знак не приоритетный, то второй операнд тройки становится первым для следующей тройки.

Функция Eval выполняет вычисления. Она во многом похожа на функцию FormPrty: в ней также выделяются тройки "операнд 1- 0знак-операнд". Если один или оба операнда являются подсписками, то сначала вычисляются эти подсписки и заменяются на атомы - результаты вычисления. Если оба операнда - атомы, то над ними выполняется арифметика, задаваемая знаком операции. Поскольку в первую очередь вычисляются подсписки, то подвыражения, обозначен- ные скобками в исходной строке, и операции умножения и деления выполняются в первую очередь.