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

Рекурсивное определение списка: список м.б. либо пустым, либо состоять из узла, содержащего ссылку на список.

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

Пр. 2 рекурсивные процедуры: 1 для чтения последовательности символов, др. для печати их в исходном порядке.

program CopyList; type link = ^node; node = record data: char; next: link end; var head: link; procedure AddToList (var p: link);

begin if p=nil then begin new(p); p^.next:= nil; read(p^.data); end else AddToList (p^.next); end; procedure PrintList (p: link);

begin if p<>nil then begin write(p^.data); PrintList (p^.next) end; end; BEGIN head:= nil; while not eof do AddToList (head); PrintList (head); END.

Вопрос 21

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

Type link=record Next, Before: link; Data: datatype; End;

Next – ссылка на следующую компоненту списка (ссылка вперед)

Before – ссылка на предыдущую компоненту (ссылка назад)

Для полной симметрии можно связать 1 и последнюю компоненту списка между собой. В результате получится двусвязное кольцо.

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

Деревья.

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

- подструктура связанных с некоторыми узлами не связаны между собой;

- существует узел наз. корнем, из которого просмотром конечного числа ребер может достичь любого узла дерева.

На рисунке узел А – это корень, узла Г,Д,Е,Ж,И,К,Л – терминал узла или листья.

Дерево является рекурсивной структурой. Рекурсивное определение: дерево либо пуста, либо состоит из узла содержащего ссылки на непересекающиеся деревья.

Двоичные деревья.

Каждый узел двоичного дерева имеет не более двух узлов отростков. Эти два отростка наз. левым и правым отросткам. Эти два отростка не являются взаимозаменяемыми.

Для представления двоичного дерева в Паскале удобно пользоваться записями.

type Link=^Node; node=record Data:char; Left,Right:Link; End;

Просмотр двоичного дерева можно производится рекурсивно, для каждого узла нужно выполнить следующие действия:

1. исследовать узел, т.е. выполнить какие то операции;

2. просмотреть левое поддерево;

3. просмотреть правое.

Эти три шага могут выполнять шесть различных последовательности. Благодаря существующим традиционным соглашением о том, что левая поддерево всегда просматривается перед правым кол-во возможных способов снижается до трех. Три оставшихся способа имеют спец. наименования:

1. прямой просмотр – сначала исследуется узел затем левое и правое поддеревья;

2. обратный просмотр – исследуется левое поддерево узел правое;

3. концевой просмотр – узел исследуется после просмотра поддеревьев.

Рекурсивная процедура, выполняющая прямой просмотр дерева:

procedure preorder (tree:Link);

begin if tree<>nil then begin dosomething(tree); {исследуем узел} preorder(tree^.Left); preorder(tree^.Right); end; end;

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

След. последовательность: Д,Б,А,Г,В,Е,З,Ж,И

Обратная последовательность: А,Б,В,Г,Д,Е,Ж,З,И

Концевая: А,В,Г,Б,Ж,И,З,Е,Д

Обратная просмотр приводит к возникновению упорядочности узлов по алфавиту.

Не нашли, что искали? Воспользуйтесь поиском: