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

Возможность выделения и освобождения области памяти позволяет создавать гибкие структуры, размеры и организация которых динамически изменяются. Простейшим примером такой структуры является линейный однонаправленный список. Он представляет собой набор следующих друг за другом однотипных звеньев. Каждое звено состоит из двух частей, информационной и указательной, и имеет тип запись. Информационная и указательная части являются полями этой записи. Информационная часть - некоторая структура данных, чаще всего тоже запись. Назовем это поле inf. Указательная часть (второе поле записи) - ссылка на следующее звено. Обычно это поле называют next. Последнее звено списка не ссылается ни на что. Указательная часть последнего звена имеет значение Nil:

( - обозначает Nil).

Пусть Т - тип информационного поля звена. Поле next имеет тип указатель на звено. По общим правилам Паскаля тип звено не может быть описан до описания типа указатель на звено, так как указатель на звено - это тип одного из полей записи, и наоборот, тип указатель на звено не может быть описан, пока не описан тип звено. Для разрешения этого противоречия в языке Паскаль делается исключение: при описании типа указатель разрешается использовать имя еще не описанного базового типа указателя:

Type t_ptr_link=^t_link;

t_link=record

inf:T;

next:t_ptr_link

end;

Типовыми задачами при работе со списками являются: создание и уничтожение списка, вставка и удаление звена, поиск звена в списке, просмотр списка и т.п.

Опишем подпрограммы для решения некоторых из этих задач. Для определенности в качестве типа информационной части выберем тип integer. Для единообразия выполнения операций вставки и удаления звена создадим список с заголовочным звеном: информационная часть первого звена не используется.

27. ПРЕОБРАЗОВАНИЕ ТИПОВ

В Паскале преобразование типов выполняется автоматически при условии совместимости типов при выполнении операций или присваивания. Например, при присваивании целого вещественной переменной целое значение преобразуется в вещественное. При сложении длинного целого и целого целый тип преобразуется к длинному целому. В ТР при выполнении конкатенации оба операнда приводятся к типу string.

Одна и та же область памяти может рассматриваться как значение разных типов в следующих случаях:

а) при использовании записей с вариантами;

б) если типизованные указатели с разными базовыми типами содержат один и тот же адрес;

с) при размещении переменных разных типов по одному и тому же абсолютному адресу. Это выполняется при описании переменных с использованием директивы absolute:

absolute (<Абсолютный адрес>½<идентификатор ранее описанной

переменной>).

<Абсолютный адрес>::=< сегмент>:< смещение>

Сегмент и смещение - двухбайтовые целые без знака.

Пример.

Var a : array[1..6] of byte;

b : array[1..3] of word absolute a;

r : real absolute a;

z : longint absolute $A12C: $0000;

Переменные a b r располагаются по одному адресу.

В ТР можно обойти ограничения на совместимость типов и с помощью операции приведения типов:

Эта конструкция имеет тип, указанный слева.

Приведение типов выражений и переменных выполняется по-разному.