Односвязные списки

При работе с динамическими переменными важно помнить, что любая память, выделенная процедурой new, должна быть освобождена в программе процедурой DISPOSE !

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

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

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

Ниже приведены схемы различных видов списков записей. На них символами "*" отмечены поля ссылок. Стрелками показаны связи между записями. Поля данных заглавных звеньев обычно используются для хранения общей информации о списках.

Пример организации односвязного списка приведен ниже.

Type

Z=Record {комбинированный тип для данных}

a: String; {строковое поле}

b, c: Integer; {поле целых чисел}

d: Real {поле вещественных чисел}

end;

P=^S; {тип указатель записи базового типа S}

S=Record {базовый тип для указателей типа Р}

ls:P; {поле типа Р ссылки на следующую запись}

Dt:Z {поле типа Z записи данных}

end;

В этом примере типы Z и S введены для описания переменных - записей, содержащих в своих полях a, b, c, d данные, соответствующие описанным типам полей. P - тип указатель для динамических переменных базового типа S, т.е. значения переменных типа P будут адресами переменных типа S.

Наличие у комбинированной переменной типа S адресного поля ls типа P позволяет включать в состав записи ссылку на последующую запись и хранить таблицы в памяти машины в виде динамических списков связанных записей.

Var

Dt:Z; {запись данных}

Uz,U:P {указатели заглавного и текущего звеньев списка}