Файл: Лекция 13.doc

Лекция 13. Динамические структуры данных

8.1. Указатели

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

8.1.1. Типизированные и нетипизированные указатели

Указатели могут быть типизированными и нетипизированными. При объявлении типизированного указателя определяется и тип объекта в памяти, адресуемого этим указателем. Так, например:

var

ipt : ^integer;

cpt : ^char;

означает, что переменная ipt представляет собой адрес области памяти, в которой хранится целое число, а cpt — адрес области памяти, в которой хранится символ. Хотя физическая структура адреса не зависит от типа и значения данных, хранящихся по этому адресу, компилятор считает указатели ipt и cpt имеющими разный тип, и оператор:

cpt := ipt;

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

Нетипизированный указатель — тип Pointer — служит для представления адреса, по которому содержатся данные неизвестного типа. Работа с нетипизированными указателями существенно ограничена, они могут использоваться только для сохранения адреса; обращение по адресу, задаваемому нетипизированным указателем, невозможно.

8.1.3. Операции над указателями

Основными операциями, в которых участвуют указатели, являются присваивание, получение адреса, выборка.

Присваивание является двухместной операцией, оба операнда которой — указатели. Как и для других типов, операция присваивания копирует значение одного указателя в другой, в результате оба указателя будут содержать один и тот же адрес памяти. Если оба указателя, участвующие в операции присваивания, типизированные, то оба они должны указывать на объекты одного и того же типа.

Операция получения адреса — одноместная, ее операнд может иметь любой тип, результатом является типизированный (в соответствии с типом операнда) указатель, содержащий адрес объекта-операнда.

Операция выборки — одноместная, ее операндом является типизированный указатель, результат — данные, выбранные из памяти по адресу, заданному операндом. Тип результата определяется типом указателя-операнда.

К указателю можно прибавить целое число или вычесть из него целое число. Поскольку память имеет линейную структуру, прибавление к адресу числа даст нам адрес области памяти, смещенной на это число байт (или других единиц измерения) относительно исходного адреса. Результат операций "указатель + целое", "указатель — целое" имеет тип "указатель". В Pascal – необходимо применять Inc(p,1), Dec(p,1)

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

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

Операции адресной арифметики выполняются только над типизированными указателями. Единицей измерения в адресной арифметике является размер объекта, который указателем адресуется. Так, если переменная ipt определена как указатель на целое число

ipt: ^integer;

int *ipt;

то выражение ipt+1 даст адрес, больший не на 1, а на количество байтов в целом числе. Вычитание указателей также дает в результате не количество байтов, а количество объектов данного типа, помещающихся в памяти между двумя адресами. Это справедливо как для указателей на простые типы, так и для указателей на сложные объекты, размеры которых составляют десятки, сотни и более байт.

Итак: указатели бывают типизированные (^тип), указывающие на данные определенного типа, и нетипизированные (pointer), которые могут указывать на данные любого типа.

8.1.4. Действия с указателями

Пример работы с указателями.

Листинг 8.1. Действия с указателями

1 var

2 X, Y: Integer; // X и Y переменные Integer

3 P: ^Integer; // P указатель на Integer

4 begin

5 X := 17; // присвоить значение X

6 P := @X; // присвоить адрес X в P

7 Y := P^; // разыменовывать P; присвоить Y

end;

После выполнения кода, X и Y имеют одинаковое значение 17.

Оператор @, который использовался для того, чтобы взять адрес переменной, действует для функций и процедур. Оператор @ возвращает адрес переменной, функции, процедуры или метода; т.е. @ создает указатель на свой операнд.

Следующие правила относятся к операции @:

• Если X — переменная, @X возвращает адрес X. Тип @X – Pointer, если выполнена директива компилятора {$T-} (по умолчанию). В состояние {$T+}, @X — тип ^T, где T — тип X.

• Если F — функция или процедура, @F возвращает точку входа в F. Тип @F — всегда Pointer.

При применении операции @ к методу перед идентификатором метода должна идти ссылка на имя класса. Например, @TMyClass.MyShow.

Символ ^ может использоваться в двух случаях. Если ^ появляется перед идентификатором типа — ^typeName — он обозначает типизированный указатель. Если ^ появляется после переменной указателя — p^ — он разыменовывает указатель, т.е. возвращает величину по адресу памяти, содержащему указателем.

Следующий код назначает данные вещественного типа в переменную целого.

Листинг 8.2. Назначение данных вещественного типа в переменную целого

type

PInteger = ^Integer;

var

R: Single;

I: Integer;

P: Pointer;

PInt: PInteger;

begin

P := @R;

PInt := PInteger(P);

I := PInt^;

end;

Конечно, вещественные и целые хранятся в разных форматах. Оператор присваивания I:=PInt^ просто копирует непреобразованные двоичные данные из R в I.

Дополнительно к операции @, можно использовать стандартные процедуры динамического распределения памяти.

Разыменованные указатели могут квалифицироваться и могут действавать как классификаторы, как, например, в выражении P1^.Data^.

Зарезервированное слово nil — специальная константа, которая может присваиваться любому указателю. Если nil присваивается указателю, то он никуда не указывает.

Можно объявить указатель на любой тип, используя синтаксис

type pointerTypeName = ^type

Фундаментальные типы PAnsiChar и PWideChar представляют указатели на величины AnsiChar и WideChar, соответственно. Тип PChar представляет указатель на Char (т.е., в последних реализациях, на AnsiChar). Эти символьные указатели используются, чтобы манипулировать нуль-термированными строками.

Модули System и SysUtils объявляют многие стандартные типы указателя.

8.1.5. Операторы для указателей (pointer)

Операторы отношения <, >, <= и >= могут использовать операнды типа PChar. Следующие операторы также берут указатели как операнды.

Оператор ^ разыменовывает указатель. Операнд может быть указателем на любой тип кроме Pointer, который должен быть сначала приведен к конкретному типу прежде, чем его разыменовывать.

P = Q — True, если P и Q указывают на тот же адрес; в противном случае, P <> Q — True.

Можно использовать операторы + и – для увеличения или уменьшения сдвига указателя на символ. Операция – может быть использована для вычисления разности смещения двух символьных указателей. Для операций + и – выполняются следующие правила.

Если I — целое и P — символьный указатель, то P + I (Inc(P,I)) увеличивает на I адрес, определяемый P, т.е. возвращает указатель на адрес, смещенный на I символов после P. Выражение, которое I + P эквивалентно P + I. Операция P - I (Dec(P,I)) вычитает I от адреса, определяемого P, т.е. возвращает указатель на адрес, на I символов перед P.

Если P и Q — символьные указатели, то P - Q вычисляет число символов между P и Q.

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

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

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

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

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

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

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

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

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

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

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