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

Concept (Deleuze) vers. Seyn (Heidegger).

Concept (Deleuze) vers. - "méasure of falsity-truth-content" (Pоpper) - vers. Seyn (Heidegger).

 

,, ©Mark V. Zhelnov. Student's Lectures. 2014-2015

Лекция 4

Повторение:

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

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

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

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

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

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

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

 

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

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

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

Линейный список (пустой);

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 – на уровне 2)

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

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

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

Линейный список (пустой);

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))

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

 

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)))