Указатели и ссылки

Динамические структуры данных

Динамические переменные

Переменные, которые рассматривались до сих пор, являлись статическими. Это означает, что размер выделяемой для них памяти происходит при компиляции программы и остается неизменным во все время работы программы. Адрес (относительный) выделенной ячейки памяти определяется при компиляции и соотносится с именем переменной.

Такая структура данных, как массив, является удобным средством в тех случаях, когда необходим прямой доступ к его элементам. Однако, если необходимо, например, вставить новое значение в массив, то приходится сдвигать остальные элементы массива, как это делается при сортировке вставками. При удалении элемента из массива также приходится сдвигать остальные элементы. Если размерность массива N, и все его элементы определены, то вставка еще одного элемента вообще невозможна: память для статического массива также выделяется при компиляции. Файлы позволяют создавать последовательности элементов любой длины, однако файл – линейная структура, и доступ к дисковой памяти намного сложнее, чем к оперативной.

Динамические структуры данных

Многие задачи требуют более сложных, чем линейная, структур. Даже для линейных структур желательно иметь переменный размер и легкость вставки и удаления любого элемента структуры. Такие структуры изменяются во время выполнения программы, поэтому они называются динамическими.

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

Элементарным, неструктурированным оператором является оператор присваивания. Ему соответствует скалярный тип данных. Оба они являются простейшими строительными блоками для составных операторов и типов данных. Простейшие структуры, получаемые с помощью перечисления, или следования, – это составной оператор и запись. Оба состоят из небольшого количества компонент, которые могут различаться. Если все компоненты одинаковы, их не нужно выписывать отдельно: для того, чтобы описать повторения, число которых известно и конечно, пользуются оператором цикла с параметром (for) и массивом. Выбор из двух или более вариантов выражается операторами if или case и соответственно записью с вариантами. И, наконец, повторение неизвестное количество раз выражается оператором цикла с предусловием (while) или с постусловием (repeat). Соответствующая структура данных – последовательность (файл).

Существует ли структура данных, которая подобным же образом соответствует оператору процедуры? Разумеется, наиболее интересная и новая по сравнению с другими операторами особенность процедур – это возможность рекурсии. Значения типа данных, который можно назвать рекурсивным, должны содержать одну или более компонент того же типа, что и все значение, по аналогии с процедурой, содержащей один или более вызовов самой себя. Как и в процедурах, в таких определениях типов рекурсия может быть прямой или косвенной.

Указатели и ссылки

Характерная особенность рекурсивных структур, которая отличает их от основных структур (массивов, записей, множеств), – их способность изменять размер. Поэтому для рекурсивно определенных структур невозможно установить фиксированный размер памяти, и поэтому компилятор не может приписать такой переменной определенного адреса. Для решения этой проблемы чаще всего применяется метод динамического распределения памяти, то есть выделения памяти для отдельных переменных в тот момент, когда они появляются во время выполнения программы, а не во время компиляции. Во время компиляции выделяется фиксированный объем памяти для хранения адреса динамической переменной, а не самой переменной.

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

Явное использование ссылок позволяет строить более разнообразные структуры, чем те, которые можно задать лишь с помощью рекурсивных определений. Следовательно, нужно ввести типы данных, значениями которых являются указатели(ссылки) на другие данные. Для этого используются такие обозначения:

type TPtr=^TElement.

Здесь имеется ввиду, что значениями типа TPtr являются ссылки на переменные типа TElement. Стрелка ^ читается как «ссылка на». Существенно, что тип элементов, на которые ссылаются значения типа TPtr, задан в его определении. Это означает, что TPtr связан с TElement. Эта связь отличает ссылки в языках высокого уровня от адресов в языке ассемблера и является очень важным средством увеличения надежности программ. Пусть есть описания

type Tp1=^TE1;

Tp2=^TE2;

…

var p1: Tp1;

p2: Tp2

Тогда переменные p1 и p2 – разных типов, так как они ссылаются на переменные разных типов. И это несмотря на то, что и размер памяти, отводимой под p1 и p2, – одинаков, и одинакова сущность их значений: обе эти переменные содержат адреса памяти.

Для работы с динамическими структурами необходимы следующие основные операции:

q создание переменной;

q удаление переменной.

Значения ссылочных типов создаются всякий раз, когда динамически создается соответствующая переменная. Для динамического создания переменной служит стандартная процедура new. Если дана ссылочная переменная p типа TPtr, то оператор new(p) выделяет память для переменой типа TElement, создает ссылку типа TPtr на эту вновь созданную переменную и присваивает значение этой ссылки (адрес новой переменной) p. Поскольку собственно значение адреса программиста, как правило, не интересует, ссылка на переменную обозначается стрелкой.

Рис. 8.1.

Сама ссылкаобозначается как p, значение ее – адрес динамически созданной переменной. Динамически созданная переменная своего имени не имеет, но к ней можно обратиться через ее ссылку, и тогда p^ – динамически созданная переменная.

К множеству значений типа TPtr добавляется еще одно значение – Nil, (от англ. ничего, ноль) которое не ссылается ни на какой элемент. Элемент, содержащий такое значение, является конечным элементом структуры.

Операции, допустимые над ссылочными переменными:

q Присваивание (p:=q). Как и для переменных других типов данных, присваивать одной ссылочной переменной можно значение другой ссылочной переменной только если эти переменные одного и того же типа. Значение Nil можно присваивать любой ссылочной переменной.

q Сравнение (if (p<>Nil) and (p=q) then …). Две переменные ссылочного типа можно сравнивать только на равенство/неравенство. Допустимо сравнение со значением Nil.

q Разыменование (p^). Это унарная операция, ее операнд (p) – указатель, результат – данные по адресу, заданные указателем.

Дата добавления: 2015-12-08