Нетипизированные указатели
Для того чтобы освободить память, на которую указывает нетипизированный указатель, нужно воспользоваться стандартной процедурой freemem(p: pointer; size: word), которая освободит в памяти столько байтов (начиная с указанного в переменной p адреса), сколько задано в переменной size.
Списочные структуры
Если для каждой динамической переменной описывать и хранить ее "личный" указатель, то никакой выгоды на этапе выполнения программы получить не удастся: часть памяти, как и прежде, будет выделяться статически, а ее общий объем даже увеличится - ведь каждый указатель требует для себя четыре байта.
Следовательно, нужно сделать так, чтобы место под хранение адресов будущих переменных также выделялось динамически. Решением этой проблемы и служат списки - специальные динамические структуры.
Списки применяются, например, в таких ситуациях:
программист заранее ничего не знает о том, какой именно объем памяти может потребоваться его программе;
некоторые (особенно "тяжелые") переменные нужны поочередно, и после того как первые "отработали свое", их можно смело стирать из памяти, не дожидаясь конца работы программы, - освобождать место для других "тяжелых" переменных;
в процессе обработки данных нужно провести большую работу по перестройке всей структуры "на ходу"; и т.д.
Структура списков
Итак, каждый элемент создаваемого списка должен содержать:
полезную информацию, которая может иметь любой формат: integer, real, array, record и т.п.;
специально выделенное поле (и, может быть, не одно), которое хранит адрес другого элемента этой же структуры.
Приведем примеры различных списочных структур:
а) Односвязный (линейный) список: структура, каждый элемент которой "знает" адрес только следующего за ним элемента (см. рис. 10.1 (a)). Очень удобно представлять таким списком стек и очередь (см. лекцию 9).
b)Двусвязный линейный список: структура, каждый элемент которой "помнит" адрес не только следующего, но и предыдущего элемента списка (см. рис. 10.1 (b)). Этот список удобен для работы с деками (см. лекцию 9)
c) Бинарное дерево (см. лекцию 11) может быть представлено двусвязным нелинейным списком: каждая вершина помнит обоих своих возможных потомков (см. рис. 10.1 (c)). Если каждой вершине необходимо помнить не только потомков, но и предка, то список становится трехсвязным.
d) Для представления ориентированного графа (см. лекцию 11) можно использовать иерархические списки - комбинацию из двух различных линейных списков (см. рис. 10.1 (d): вершины задаются структурой, содержащей три поля, а дуги - два; справа показан орграф, представленный приведенной списочной структурой).
Описание списков
Сначала мы рассмотрим только самый простой случай: односвязный список (см. рис. 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) до ее описания.
Рис. 10.1. Примеры списочных структур
Замечание: Кажется, что гораздо более естественным было бы отнести поле 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;
c)
Бинарное дерево (иерархический список)
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;