Динамические структуры данных. Задание практикума. Язык Паскаль. Вылиток А.А - 21 стр.

      p↑.next := q {присоединили в конец списка новое звено}
    end; {insert2}

Как видим, для списка с заглавным звеном нет нужды рассматривать случай
L = nil отдельно.


       Рекурсивная обработка списков

      Вспомним математическое определение списка: это конечная
последовательность    элементов    (возможно,   пустая).   В     непустой
последовательности можно выделить первый элемент – «голову»
последовательности – и оставшуюся часть – «хвост». Заметим, что «хвост» в
свою очередь также является последовательностью. Таким образом, получаем
рекурсивное определение последовательности:
   <последовательность>::= <голова> <хвост> | <пусто>
    <голова>::=<элемент>
    <хвост>::=<последовательность>

      Опираясь на это определение, можно задать рекурсивную процедуру
(функцию)1 поэлементной обработки последовательности. Пусть, например,
требуется напечатать список символов L (тип элементов – char). Процедуру
печати можно сформулировать так: если список пуст – ничего не делать (так как
нечего печатать), иначе напечатать «голову», а за ней напечатать «хвост». Для
печати «хвоста» используем эту же процедуру (рекурсивное применение). Ниже
приводятся рекурсивные процедуры print1 и print2 для печати списков
соответственно без заглавного звена и с заглавным звеном.

procedure print1 (L: list);
{ печать списка без заглавного звена }
  begin if L <> nil then
    begin write(L↑.elem,'9'); {печать «головы»}
           print1(L↑.next)     {печать «хвоста»}
    end;
  end; {print1}

procedure print2 (L: list);
{ печать списка с заглавным звеном }
  begin if L↑.next <> nil then
    begin write(L↑.next↑.elem,'9');
           print2(L↑.next)
    end;
  end; {print2}



1
 Процедуры (функции), которые во время исполнения могут прямо или косвенно (через другие
процедуры или функции) обратиться сами к себе, называются рекурсивными.

                                         - 21 -