Лекция 11. Данные с динамической структурой. Рекурсивная структура данных.

Данные с динамической структурой

Обычно в задачах данные имеют фиксированный тип (статическую структуру), что позволяет рассчитать требуемую для них память.

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

Существует близкие аналогии между методами построения алгоритмов и методами построения данных.

Соответствие между элементами программ и структурой данных

“Образ конструкции”	Оператор программы	Тип данных
атомарный объект	Присваивание	скалярный тип
перечисление	составной оператор	запись
известное число повторений	оператор цикла с параметром (for)	массив
выбор	условный оператор оператор варианта	объединенный тип (запись с вариантами)
повторение	оператор цикла с пред- и пост- условиями (while)	Последовательность (file)
рекурсия	оператор процедуры, рекурсия	рекурсивный тип
общий граф	оператор перехода	структура, построенная на ссылках

Примеры рекурсивных структур данных

Варианты позволяют ограничить рекурсивную структуру. Они должны присутствовать. Иначе получится бесконечная структура.

Пример 1

Выражение состоит из терма, за которым следует знак операции и затем опять терм (здесь термы являются операндами операции). Терм – либо переменная, либо заключенное в скобки выражение.

1. x+y

2. x-(y*z)

3. (x+y)*(z-w)

4. (x/(y+z))*w

1	+				2	-
	T	x				T	x
	T	y				F	*
							T	y
							T	z
3	*				4	*
	F	+				F	/
		T	x				T	x
		T	y				F	+
	F	-						T	y
		T	z					T	z
		T	w			T	w

Образ расположения в памяти записей с рекурсивной структурой

Описание на языке Модула 2

(на Pascal так определить данные нельзя)

Type expression = RECORD op: operator;

opd1, opd2: term

END

Type term = RECORD

CASE t: BOOLEAN OF

TRUE: id: alfa |

FALSE: subex: expression

END

Пример 2

Генеалогическое дерево : Имя человека + два дерева его родителей.

На каком-то этапе информация о предках отсутствует. Поэтому реально оно конечно.

Type

ped = RECORD

CASE known : boolean of

TRUE : name : alpha; father, mother: ped |

FALSE : (* пусто *)

END

END;

Возможное значение переменной типа ped :

(T,Ted, (T,Fred, (T, Adam, (F), (F)), (F)),

(T, Mary, (F), (T,Eva, (F), (F)))),

	T			Ted
		T		Fred
			T	Adam
				F
				F
				F
		T		Mary
				F
			T	Eva
				F
				F

Рекурсивные структуры данных могут изменять размер. Поэтому для них нельзя выделить память фиксированного размера. Для этого используется динамическое распределение памяти. Память для рекурсивных структур выделяется в процессе выполнения программы, а не во время трансляции. Транслятор же выделяет место для хранения адресов (ссылок) динамически размещаемых компонент. Использование ссылок позволяет строить потенциально бесконечные структуры.

Пример рекурсивных данных

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

М женился на вдове, у которой была взрослая дочь. Отец М женился на падчерице М.

Следовательно, отец М – зять М (зять – муж дочери, сестры), а падчерица М – мать М.

У М родился сын, который стал шурином (шурин – родной брат жены) отца М и одновременно дядей М. У жены отца М, т. е. падчерицы М, тоже родился сын. Таким образом, у М появился брат и одновременно внук. Жена М является бабушкой М, так как она мать матери М. Следовательно, М муж своей жены и одновременно ее внук. Другими словами М – свой собственный дедушка.