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

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

Пусть 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))