Правила форума
Лекция №10.3: Адреса и указатели. Списочные структуры данныхСодержание
Структура списков
Итак, каждый элемент создаваемого списка должен содержать:
- полезную информацию, которая может иметь любой формат: Integer, Real, array, record и т.п.;
- специально выделенное поле (и, может быть, не одно), которое хранит адрес другого элемента этой же структуры.
Приведём примеры различных списочных структур:
- a) Односвязный (линейный) список: структура, каждый элемент которой «знает» адрес только следующего за ним элемента (см. рис. 10.1 (a)). Очень удобно представлять таким списком стек и очередь (см. лекцию 9).
- b) Двусвязный линейный список: структура, каждый элемент которой «помнит» адрес не только следующего, но и предыдущего элемента списка (см. рис. 10.1 (b)). Этот список удобен для работы с деками (см. лекцию 9)
- c) Бинарное дерево (см. лекцию 11) может быть представлено двусвязным нелинейным списком: каждая вершина помнит обоих своих возможных потомков (см. рис. 10.1 (c)). Если каждой вершине необходимо помнить не только потомков, но и предка, то список становится трёхсвязным.
- d) Для представления ориентированного графа (см. лекцию 11) можно использовать иерархические списки — комбинацию из двух различных линейных списков (см. рис. 10.1 (d): вершины задаются структурой, содержащей три поля, а дуги — два; справа показан орграф, представленный приведённой списочной структурой).
Описание списков
Сначала мы рассмотрим только самый простой случай: односвязный список (см. рис. 10.1 (а)). Напомним, что каждый элемент этого списка должен хранить адрес другого элемента из этого же списка.
/10%2D1.gif)
Рис. 10.1. Примеры списочных структур
Логичнее всего было бы дать этой структуре такое описание:
znachenie : Integer;
next_element : ^element_spiska;
end;
Однако этот вариант невозможен по правилам языка Pascal: рекурсивные описания недопустимы, следовательно, структура не может ссылаться сама на себя. Поэтому приходится использовать более сложный, хотя и совершенно эквивалентный, вариант:
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; |
Оперирование элементами списка
Хранение списка
Для того, чтобы сохранить информацию обо всём списке, достаточно только одной переменной — указателя на первый элемент этого списка. Обычно его называют головой списка. Указатель на голову должен быть выделенным: с ним нельзя производить никаких действий, которые могут стать причиной утери всего списка. Для работы со списком обычно заводят вспомогательный указатель.
Например:
Но, вообще говоря, нет никаких специальных правил, которые обязали бы программиста давать выделенным указателям особые имена. Например, на рис. 10.1 выделенные указатели имеют имена head, tail, tree_root и start.
::
::
::
