Файл: Курсач - копия.docx

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знак-операнд". Если один или оба операнда являются подсписками, то сначала вычисляются эти подсписки и заменяются на атомы - результаты вычисления. Если оба операнда - атомы, то над ними выполняется арифметика, задаваемая знаком операции. Поскольку в первую очередь вычисляются подсписки, то подвыражения, обозначенные скобками в исходной строке, и операции умножения и деления выполняются в первую очередь.

Заключение.

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

Список литературы

1. Сайт http://algolist.ru

2. Сайт http://informatics.mccme.ru/

3. «Программирование в среде Turbo Pascal 7.0» Авторы: А. М. Епанешников, В. А. Епанешников Год: 1995. Страниц: 288

4. «Программирование на языке Pascal» Авторы: Рапаков Г. Г., Ржеуцкая С. Ю. Год издания: 2004

5. «Динамическое программирование» Авторы: Беллман Р., Энджел Э.

6. «Алгоритмы и программы» Авторы: Порублев Илья Николаевич, Ставровский Андрей Борисович

7. «Turbo Pascal: Учебник для вузов» Автор: С. Немюгин

8. «Pascal 7.0. Практическое программирование. Решение типовых задач» Автор: Л. Климова

31