Ссылочные переменные

Описание ссылочного типа выглядит следующим образом: Type Ptr = ^t,

где t – стандартный или заранее описанный тип данных, называемый базовым типом. Сами адреса будут храниться в ссылочных переменных, которые описываются обычным образом, например, Var P: Ptr. Такие переменные для хранения адресов динамической памяти называются ссылками или указателями.

Пример. Type Pint = ^Integer; W = array [1..20] of Real; p = ^W; Var N: Pint; U: p;

В объявлениях ссылочных типов после символа “^” может стоять только простое имя типа. В случае сложных имен используется переопределение типов, как в приведенном примере.

Указатели, связанные с адресами значений конкретных базовых типов, называются типизированными. N и U – типизированные указатели. В Турбо Паскале можно объявлять указатель и не связывать его при этом с каким–либо конкретным типом данных. Такие указатели называются нетипизиро­ванными. Описание нетипизированных указателей осуществляется с помощью служебного слова Pointer, например, Var P: Pointer.

Указатели могут сравниваться с помощью операций отношения = или < > (не равно). Сравнение для указателей – ненадежная операция. Если два указателя содержат один и тот же адрес в памяти, но записанный в них разными способами, то они считаются различными. Зато можно проверить, ссылается ли указатель р на что–нибудь или нет путем сравнения p < > Nil.

Содержимое ячейки доступно через имя указателя. Чтобы обратиться к данным, находящимся по адресу, содержащемуся в указателе, используется символ “^”, который ставится сразу после имени ссылочной переменной. Эта операция называется операцией разыменования. Суть ее состоит в переходе от ссылочной переменной к значению, на которое она указывает.

Процедуры управления кучей

Все операции с кучей выполняются под управлением особой программы, которая называется администратором кучи. Она ведет учет всех свободных фрагментов в куче. При очередном обращении к процедуре New администратор кучи отыскивает наименьший свободный фрагмент, в котором еще может разместиться требуемая переменная. Адрес начала найденного фрагмента возвращается в указателе, а сам фрагмент или его часть нужной длины помечается как занятая часть кучи.

Освободить фрагмент кучи можно при использовании процедур Mark и Release. Процедура Mark (var p: pointer) запоминает состояние динамической памяти в тот момент, когда эта процедура вызывается. В указа­теле р сохраняется адрес первого байта свободной области памяти. Далее можно несколько раз выделить память. Затем процедура Release (var p: pointer) возвращает динамическую память в состояние, которое было запомнено ранее при помощи процедуры Mark.

Иногда нежелательно выделять память тем способом, как это делает New. Может потребоваться выделить больше или меньше памяти, чем это делает New по умолчанию. Параметром процедуры New может быть только типизированный указатель. Для работы с нетипизированными указателями используются процедуры Getmem и Freemem: Getmem (p, Size) – резервирование памяти; Freemem (p, Size) – освобождение памяти, где р – переменная типа указатель; Size – размер в байтах требуемой или освобождаемой части кучи.

Существуют еще две функции, возвращающие важную информацию о динамически распределяемой области памяти: MemAvail и MaxAvail. Функция MemAvail возвращает общее число байт, доступных для распределения в динамической памяти. Функция MaxAvail возвращает размер наибольшего доступного блока непрерывной памяти в динамически распределяемой области.

Списки

Главная возможность, которую предоставляет наличие ссылочных типов и ссылочных переменных в Паскале, – это возможность построения с их помощью объектов со сложной, меняющейся структурой. Примерами таких структур являются списки, стеки, деревья.

Список – это набор записей, каждая из которых имеет поле данных и указатель (ссылку) на следующую запись в списке. Та, в свою очередь, тоже содержит поле данных и ссылку на продолжение списка. Последний элемент списка содержит значение Nil, т.е. уже ни на что не ссылается. Начало списка формирует переменная типа “указатель”, содержащая адрес первого элемента списка (рис. 6). Поле данных еще называют информационной частью списка.

Указатель в списке должен быть типизированным. Базовым типом для него является тот же тип данных, что и тип информационной части списка.

Рассмотрим методы работы со списками, информационная часть которых состоит из одного поля типа Integer. Такие списки естественно называть списками целых чисел. Обозначим тип элемента списка идентификатором Elem, а ссылочный тип на элемент списка – идентификатором Uk.

Стек – линейный список, в котором добавления и исключения элемента производятся с одного конца, называемого вершиной стека. Соблюдается принцип “первым пришел – последним ушел”.

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

Работа со стеком осуществляется через указатель стека. При выполнении загрузки элемента в стек данные записываются на место, определяемое указателем стека, а указатель стека изменяет свое состояние и задает следующую свободную ячейку блока памяти.

Списки могут быть не только линейными, но и кольцевыми. В кольцевом списке для последнего элемента следующим является первый, а если список двунаправленный, то для первого предыдущим является последний. Как и линейный, кольцевой список определяется указателем на свой первый элемент.

Мультисписки представляют собой структуру, каждый элемент которой входит в более чем один список одновременно и имеет соответствующее числу списков количество полей связи. Часто в виде мультисписков представляют матрицы очень большой размерности, в которых большинство элементов равны 0 (такие матрицы называются разреженными). Мультисписки обеспечивают эффективное хранение таких структур в памяти: хранятся только те элементы, которые отличны от 0. Каждый элемент входит в два списка: в список-строку и список-столбец. Вся матрица представлена m + n списками, где m и n – соответственно число строк и число столбцов матрицы, каждый элемент хранит значение элемента матрицы и две ссылки: на следующий элемент в строке и на следующий элемент в столбце, указатели на начала этих списков хранятся в двух массивах.