Описание списков

Сначала мы рассмотрим только самый простой случай: односвязный список (см. рис. 10.1 (а)). Напомним, что каждый элемент этого списка должен хранить адрес другого элемента из этого же списка.

Рис. 10.1. Примеры списочных структур

Логичнее всего было бы дать этой структуре такое описание:

type element_spiska = record znachenie: integer; next_element: ^element_spiska; end;

Однако этот вариант невозможен по правилам языка Pascal: рекурсивные описания недопустимы, следовательно, структура не может ссылаться сама на себя. Поэтому приходится использовать более сложный, хотя и совершенно эквивалентный, вариант:

type ukazatel = ^element_spiska; element_spiska = record znachenie: integer; next_element: ukazatel; end;

Обратите внимание: это единственный случай, когда компилятор согласится принять использование структуры (element_spiska) до ее описания.

Замечание: Кажется, что гораздо более естественным было бы отнести поле next_element к типу pointer: тогда не пришлось бы вводить дополнительный тип данных ukazatel. Однако неудобства, которые непременно возникнут из-за нетипизированности указателей в процессе написания программы, будут гораздо серьезнее, чем одна лишняя строчка при описании типов.

В качестве примера приведем описания всех четырех структур, представленных на рис. 10.1 (см. табл. 10.1):

Таблица 10.1. Примеры описаний списочных структур
a)	Односвязный список	type ukazatel = ^elem_spiska; elem_spiska = record znach: integer; sled: ukazatel; end;
b)	Двусвязный линейный список	type point = ^element_spiska; list = record znachenie: integer; sled: point pred: point; end;
с)	Бинарное дерево (иерархический список)	type point = ^tree; tree = record data: integer; left_sibling: point; right_sibling: point; end;
d)	Ориентированный граф (двусвязный нелинейный список)	type uk_versh = ^versh; uk_duga = ^duga; vershina = record nomer: integer; sled_versh: uk_versh; spisok_dug: uk_duga; end; duga = record konec_dugi: uk_versh; sled_duga: uk_duga; end;

Дата добавления: 2014-01-03