 |
Типизированные указатели
|
|
|
|
Для уничтожения динамической переменной, то есть для освобождения занимаемой ею памяти, предназначена стандартная процедура
dispose(<имя_типизир_указателя>).Процедура dispose() снимает пометку "занято" с определенного количества байтов, начиная с указанного адреса. Эта область памяти в дальнейшем считается свободной (хотя старое значение бывшей переменной в ней может некоторое время еще оставаться). Количество освобождаемых байтов определяется типом указателя p.
В результате освобождения памяти при помощи процедуры dispose() значение указателя, хранившего адрес освобожденной области, становится неопределенным. Во избежание проблем его лучше сразу же "обнулить":
dispose(p);p:= nil;Нетипизированные указатели
Для того чтобы освободить память, на которую указывает нетипизрованный указатель, нужно воспользоваться стандартной процедурой freemem(p: pointer; size: word), которая освободит в памяти столько байтов (начиная с указанного в переменной p адреса), сколько задано в переменной size.
Списочные структуры
Если для каждой динамической переменной описывать и хранить ее "личный" указатель, то никакой выгоды на этапе выполнения программы получить не удастся: часть памяти, как и прежде, будет выделяться статически, а ее общий объем даже увеличится - ведь каждый указатель требует для себя четыре байта.
Следовательно, нужно сделать так, чтобы место под хранение адресов будущих переменных также выделялось динамически. Решением этой проблемы и служат списки - специальные динамические структуры.
Списки применяются, например, в таких ситуациях:
· программист заранее ничего не знает о том, какой именно объем памяти может потребоваться его программе;
|
|
|
· некоторые (особенно "тяжелые") переменные нужны поочередно, и после того как первые "отработали свое", их можно смело удалять из памяти, не дожидаясь конца работы программы, - освобождать место для других "тяжелых" переменных;
· в процессе обработки данных нужно провести большую работу по перестройке всей структуры "на ходу"; и т.д.
Структура списков
Итак, каждый элемент создаваемого списка должен содержать:
1. полезную информацию, которая может иметь любой формат: integer, real, array, record и т.п.;
2. специально выделенное поле (и, может быть, не одно), которое хранит адрес другого элемента этой же структуры.
Приведем примеры различных списочных структур:
a) Односвязный (линейный) список: структура, каждый элемент которой "знает" адрес только следующего за ним элемента. Очень удобно представлять таким списком стек и очередь.
b) Двусвязный линейный список: структура, каждый элемент которой "помнит" адрес не только следующего, но и предыдущего элемента списка. Этот список удобен для работы с деками
c) Бинарное дерево может быть представлено двусвязным нелинейным списком: каждая вершина помнит обоих своих возможных потомков. Если каждой вершине необходимо помнить не только потомков, но и предка, то список становится трехсвязным.
d) Для представления ориентированного графа можно использовать иерархические списки - комбинацию из двух различных линейных списков: вершины задаются структурой, содержащей три поля, а дуги - два; справа показан орграф, представленный приведенной списочной структурой).
Описание списков
Сначала мы рассмотрим только самый простой случай: односвязный список. Напомним, что каждый элемент этого списка должен хранить адрес другого элемента из этого же списка.
Рис. 1. Примеры динамических структур
Логичнее всего было бы дать этой структуре такое описание:
|
|
|
Однако этот вариант невозможен по правилам языка Pascal: рекурсивные описания недопустимы, следовательно, структура не может ссылаться сама на себя. Поэтому приходится использовать более сложный, хотя и совершенно эквивалентный, вариант:
type ukazatel = ^element_spiska; element_spiska = record znachenie: integer; next_element: ukazatel; end;Обратите внимание: это единственный случай, когда компилятор согласится принять использование структуры (element_spiska) до ее описания.
Замечание: Кажется, что гораздо более естественным было бы отнести поле next_element к типу pointer: тогда не пришлось бы вводить дополнительный тип данных ukazatel. Однако неудобства, которые непременно возникнут из-за нетипизированности указателей в процессе написания программы, будут гораздо серьезнее, чем одна лишняя строчка при описании типов.
В качестве примера приведем описания всех четырех структур, представленных на (см. табл. 1):
| Таблица 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; |
|
|
|
