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

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


Базовыми операциями при обработке списков являются операции (функции): 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.


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

{==== Программный пример 5.12 ====} { Вторичные функции обработки списков } 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 в конец списка l. Рассмотрим ее выполнение на примере вызова: Append(4,(1,2,3)).

Поскольку аргумент-список не пустой, выполняется ветвь 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).


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


  • вся арифметика - целочисленная;
  • программа не проверяет правильность исходной записи;
  • в выражении не допускается унарный минус.


{==== Программный пример 5.13 ====} { Калькулятор. Вычисление арифметических выражений } program Calc; Uses ListWork; type cptr = ^char; iptr = ^ integer; const { цифровые символы } digits : set of char = ['0'..'9']; { знаки операций с высоким приоритетом } prty : set of char = ['*','/']; var s : string; { исходная строка } n : integer; { номер текущего символа в исх. строке } {*** Представление исходной строки в списочной форме } Function Creat_Lst : lpt; var lll : lpt; { указатель на начало текущего списка } s1 : char; { текущий символ строки } st : string; { накопитель строки-операнда } {* Создание атома для Integer } Procedure NewInt; var ip : iptr; cc : integer; begin if Length(st) > 0 then begin { если в st накоплено цифровое представление числа, оно переводится в тип integer, для него создается атом и записывается в конец списка } New(ip); Val(st,ip^,cc); lll:=Append(NewAtom(ip,'I'),lll); st:=''; { накопитель строки сбрасывается } end; end; { Procedure NewInt } Procedure NewChar; { Создание атома для Char } var cp : cptr; begin { выделяется память для 1 символа, в ней сохраняется значение s1, для него создается атом, записывается в конец списка} New(cp); cp^:=s1; lll:=Append(NewAtom(cp,'C'),lll); end; { Procedure NewChar } begin { Function Creat_Lst } { исходный список пустой, накопитель строки - пустой } lll:=nil; st:=''; while n nil do begin { до опустошения исходного списка } { выделение знака операции } op:=car(l); l:=cdr(l); { выделение 2-го операнда } op2:=car(l); l:=cdr(l); { если 2-й операнд - подсписок - обработка подсписка } if not atom(op2) then op2:=FormPrty(op2); if cptr(op^.down)^ in prty then { если знак операции приоритетный, то создается подсписок: 1-й операнд, знак, 2-й операнд, этот подсписок далее является 1-ым операндом } op1:=cons(op1,cons(op,cons(op2,nil))) else begin { если знак неприоритетный, 1-й операнд и знак записываются в выходной список, 2-й операнд далее является 1-ым операндом } l2:=Append(op,Append(op1,l2)); op1:=op2; end; end; FormPrty:=Append(op1,l2); { последний операнд добавляется в выходной список } end; { Function FormPrty } {*** Вычисление выражения } Function Eval(l : lpt) : integer; var op1, op, op2 : lpt; begin { выделение 1-го операнда } op1:=car(l); l:=cdr(l); { если 1-й операнд - подсписок - вычислить его выражение } if not atom(op1) then iptr(op1^.down)^:=Eval(op1); while l <> nil do begin { выделение знака операции } op:=car(l); l:=cdr(l); { выделение 2-го операнда } op2:=car(l); l:=cdr(l); { если 2-й операнд - подсписок - вычислить его выражение } if not atom(op2) then iptr(op2^.down)^:=Eval(op2); { выполнение операции, результат - в op1 } case cptr(op^.down)^ of '+' : iptr(op1^.down)^:=iptr(op1^.down)^+iptr(op2^.down)^; '-' : iptr(op1^.down)^:=iptr(op1^.down)^-iptr(op2^.down)^; '*' : iptr(op1^.down)^:=iptr(op1^.down)^*iptr(op2^.down)^; '/' : iptr(op1^.down)^:=iptr(op1^.down)^ div iptr(op2^.down)^; end; end; Eval:=iptr(op1^.down)^; { возврат последнего результата } end; { Function Eval } {*** Главная программа } var l : lpt; begin write('>'); readln(s); { ввод исходной строки } { формирование списка } n:=1; l:=Creat_Lst; { выделение приоритетных операций } l:=FormPrty(l); { вычисление и печать результата } writeln(s,'=',Eval(l)); END.



Выполнение программы состоит во вводе строки, представляющей исходное выражение и последовательных обращений к трем функциям: Creat_Lst, FormPrty и Eval.

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

5+12/2-6*(11-7)+4

функцией Creat_Lst будет сформирован такой список:

(5,+,12,/,2,-,6,*,(11,-,7),+,4)

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

(5,+,(12,/,2),-,(6,*,(11,-,7)),+,4)

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

12 / 2 = 6; 5 + 6 = 11; 11 - 7 = 4; 6 * 4 = 24; 24 + 4 = 28; 11 - 28 = -17




Содержание раздела