Лекция 4

Повторение: Рекурсивная процедура или функция.

• Обязательно есть нерекурсивная ветка.

• Обязательно «когда-нибудь» на нерекурсивную ветку попадем.

Двойная рекурсия. Косвенная рекурсия.

4.1 Списковые структуры. Линейный список

Линейный список – структура данных, позволяющая учесть «вложенность». Используют линейные списки для описания выражений (арифметических, логических), структуры текста программы на алгоритмическом языке и т. д.

Пусть a,b,c,...,+,-,*,/ - элементы типа Т (атомы), скобки – особые символы, описывающие вложенность.

Определение 1 (рекуррентное) линейного списка:

1. Атом есть линейный список (атомарный);

2. ( ) – линейный список (пустой);

3. если l₁,l₂,...,l_n – линейные списки (n>0), то и (l₁ l₂ ...l_n) – линейный список.

В непустом неатомарном списке (l₁ l₂ ...l_n) l₁- голова списка, (l₂ ...l_n) - хвост списка.

Примеры.

Пример	Описание	Степень вложенности (уровень)
a	атомарный список	0 (элемент а на уровне 0)
(a)	список неатомарный	1 (элемент а на уровне 1)
( )	пустой список	1 (нет элементов на уровне 1)
(())	непустой список	2 (элемент ( ) на уровне 1)
ab	не список	-
a(b)	не список	-
(ab)	список	1 (элементы а и b на уровне 1)
(((ab)c)(de))	список	3 (элементы а и b на уровне 3)
((a+b)/(c+d)*f)	список	2 (элементы а, +, b, с, +, d – на уровне 3)

Определение 2 (рекурсивное) линейного списка

Пусть S – линейный список, S⁺ – неатомарный список, S* – непустой неатомарный список.

1. Атом есть линейный список (атомарный);

2. ( ) – линейный список (пустой);

3. S = (либо пустой, либо атомарный, либо S*);

4. S* = (голова:S, хвост:S+);

5. S+ = (либо пустой, либо S*);

Операции над структурой данных линейный список:

• Создать атомарный список;

• Создать пустой список;

• Создать список из набора имеющихся списков по п.3 определения 1;

• Список пуст?;

• Список атом?;

• Расчленение (выделение головы и хвоста);

• Голова (функция с побочным эффектом);

4.2 Об операции "расчленение"

Операция определена на непустых неатомарных списках S*.

Голова - первый элемент первого уровня. Хвост - список без головы.

Примеры:

Список	Голова	Хвост
(a)	a	( )
(ab)	a	(b)
(( ))	( )	( )
(((ab)c)(de))	((ab)c)	((de))

4.3 Логическое описание линейного списка.

pElem=^Elem;

Elem=record

след:pElem;

case R:0..1 of

0: (уров:pElem);

1: (атом:T)

end;

Поле R - поле тега (переключатель).

Примеры:

1. Пустой список ( )

2. Атом a

3.(ab)

4. (a( )b)

5. ((a+b)*(c-(b/a)))

4.4 Вычисление значения арифметического выражения

Функция «Голова(р)» с побочным эффектом (р указывает на непустой неатомарный линейный список).

Голова:=р^.уров;

p^.уров:=Голова^.след;

Голова^.след:=nil

{Серия картинок, иллюстрирующих работу функции Голова}

"Правильное" арифметическое выражение представлено как "правильный" линейный список. Атомы a,b,c,... – инициализированные переменные или константы, атомы + - * / – бинарные операции.

Функция VAL(p:pElem) возвращает значение арифметического выражения, заданного указателем p.

VAL(p:pElem)

Список пуст?
	Список атом?
	VAL=p^.атом	x=VAL(Голова(p))
		оп=Голова(p)^.атом
		y=VAL(p)
		если оп=+ VAL=x+y
		если оп=- VAL=x-y
		если оп=* VAL=x*y
		если оп=/ VAL=x/y

Разъяснения:

Вот «правильный» линейный список

x=VAL(Голова(p)). Вот результат применения функции Голова:

оп=Голова(p)^.атом. Вот результат второго применения функции Голова:

y=VAL(p). Вот результат третьего применения функции Голова:

Вопросы:

1. В какой последовательности будут выполняться операции одного уровня?

2. Почему рекурсия обязательно завершится?

Задача

Имеется правильное выражение в виде строки. Построить линейный список для этого выражения.

pElem=^Elem;

Elem=record

след:pElem;

case R:0..1 of

0: (уров:pElem);

1: (атом:T)

end;

Выражение вводится с клавиатуры.

procedure LS(var p:pElem);

var c:char;

begin

if not eoln

begin

read(c);

case c of

‘(‘ : begin

new(p); p^.R:=0; LS(p^.уров); LS(p^.след);

end;

‘a’..’z’,’+’,’-‘,’*’,’/’: begin

new(p); p^.R:=1; p^.атом:=с; LS(p^.след);

end;

‘)’ : p:=nil;

end;

end

else p:=nil;

end;

Задачи

1. Написать алгоритм вычисления значения арифметического выражения, используя операцию "расчленение".

2. Имеется линейный список для "правильного" арифметического выражения. Построить линейный список для обратной польской записи этого выражения.

3. Построить алгоритм обхода элементов линейного списка (восстановить строку символов с учетом вложенности).