Рекурсивное определение списка

Список может быть определён следующим образом: список либо пуст, либо состоит из элемента ссылающегося на список (в его ссылочном поле стоит указатель на другой список). Поскольку в этом определении понятие списка определено через само это понятие, то такое определение является рекурсивным. Таким образом, список можно назвать рекурсивной структурой данных. Проверим, является ли очередь из трёх элементов списком в смысле рекурсивного определения.

Это было бы списком, если бы первый элемент (с информационным полем 5) ссылался на список. То есть нужно проверить, является ли списком следующая структура

Это было бы списком, если бы первый элемент с информационным полем 3 ссылался на список. То есть нужно проверить, является ли списком следующая структура

nil

Но эта структура состоит из элемента, ссылающегося на пустой список (nil), а, следовательно, сама по определению является списком и, возвращаясь к исходной структуре, мы получаем, что созданная нами очередь является списком в смысле рекурсивного определения.

Для обработки рекурсивных структур данных естественно использовать рекурсивные процедуры и функции.

Рекурсивная процедура добавления к очереди нового элемента, значение которого берётся из текстового файла f1:

procedure add(var r : link);

begin

if r = nil then

begin new(r); r.next:=nil; read(f1, r.val) end

else add(r.next)

end;

Рекурсивная процедура выведения информационных полей очереди в текстовый файл f2:

procedure out(r : link);

begin

if r<> nil then begin write(f2, r.val:6); out(r.next) end

end;

Вызов этих рекурсивных процедур для создания и распечатки очереди может быть осуществлён в процедуре Button1Click следующим образом:

procedure TForm1.Button1Click(Sender: TObject);

begin

assignfile(f1, ' file8.txt '); assignfile(f2, ' file9.txt ');

reset(f1);

L:=nil;

while not eof(f1) do add(L);

closefile(f1);

rewrite(f2); out(L); closefile(f2);

end;

Как будет работать процедура out, если поменять местами оператор write(f2, r.val:6); и рекурсивный вызов out(r.next) ?

procedure out(r : link);

begin

if r<> nil then begin out(r.next); write(f2, r.val:6) end

end;

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

Задача 25. Создать очередь из чисел файла file8.txt с помощью рекурсивной процедуры

procedure add(var r : link).

Описать рекурсивную функцию

function memb(r:link; b:integer) : boolean;

проверяющую, входит ли элемент с информационным полем b в список r. Описать рекурсивную процедуру

procedure dele(var r:link; w:integer);

удаляющую из списка r первое вхождение элемента с информационным полем w.

Используя функцию memb, проверить, входит ли число, введённое в поле Edit1, в созданный список. Если да, то удалить из списка первое вхождение этого числа с помощью процедуры dele и вывести преобразованный список в файл file9.txt с помощью процедуры out. В противном случае вывести сообщение: «Такого элемента нет».

Содержимое файла file8.txt: 9 -38 15 4 -21

15 9 -47 15 36

type

TForm1 = class(TForm)

Button1: TButton;

Memo1: TMemo;

Edit1: TEdit;

procedure Button1Click(Sender: TObject);

end;

type link = ^elem;

elem = record

val : integer;

next : link

end;

var Form1: TForm1; L : link; f1, f2 : textfile;

implementation

{$R *.dfm}

procedure add(var r : link);

begin

if r = nil then

begin new(r); r.next:=nil; read(f1, r.val) end

else add(r.next)

end;

procedure out(r : link);

begin

if r<> nil then

begin write(f2, r.val : 6); out(r.next) end

end;

function memb(r : link; b : integer) : boolean;

begin

if r=nil then memb:=false

else

if r.val=b then memb:=true

else memb:=memb(r.next, b)

end;

procedure dele(var r : link; w : integer);

var z : link;

begin

if r<>nil then

if r.val=w then

begin z:=r; r:=r.next; dispose(z) end

else dele(r.next, w)

end;

procedure TForm1.Button1Click(Sender: TObject);

var d : integer;

begin

assignfile(f1, ' file8.txt '); assignfile(f2, ' file9.txt ');

reset(f1);

L:=nil;

while not eof(f1) do add(L);

closefile(f1);

d:=strtoint(edit1.Text);

if memb(L, d) then

begin

dele(L, d);

rewrite(f2); out(L); closefile(f2);

memo1.Lines.LoadFromFile(' file9.txt ');

end

else showmessage(' Такого элемента нет ')

end;

Задачи

Задача 26. Создать очередь с помощью рекурсивной процедуры

procedure add(var r : link).

Описать рекурсивную функцию

function neg(r : link) : boolean;

проверяющую, имеется ли в списке элемент с отрицательным информационным полем. Ответ вывести в поле метки.

Задача 27*. Создать очередь с помощью рекурсивной процедуры

procedure add(var r : link).

Описать рекурсивную функцию

function nmemb(r:link; b:integer):integer;

подсчитывающую количество вхождений элемента с информационным полем b в список r.

С помощью этой функции подсчитать, сколько раз встречается в списке число, введённое в поле Edit1. Результат вывести в поле метки.

Задача 28*. Создать очередь с помощью рекурсивной процедуры

procedure add(var r : link).

Описать рекурсивную функцию

function max(r:link) : integer;

для нахождения максимума в списке r. Результат вывести в поле метки.