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

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

Организации списков

Описание отдельного элемента списка целых чисел имеет вид:

pascal
type
ListPointer = ^List;
List = record
x : integer;
adr : ListPointer;
end;
var
el : ListPointer;

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

Рассмотрим общую схему формирования списка. Допустим, в программе с использованием приведенного выше типа были объявлены два указателя u1 и u2.

pascal
var
u1, u2 : ListPointer;

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

pascal
New(u1);      {размещение 1-го элемента списка}
Read(u1^.x);  {ввод значения 1-го элемента списка}
u1^.adr:=Nil; {следующий элемент пока отсутствует}
u2:=u1;       {адрес 1-го элемента списка используется для формирования ссылки на 2-й элемент}

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

pascal
New(u2^.adr); {размещение 2-го (следующего) элемента списка и помещение его адреса в адресную часть 1-го (предыдущего) элемента}
u2:=u2^.adr;  {переход ко 2-му (следующему) элементу списка}
Read(u2^.x);  {ввод значения 2-го элемента списка}
u2^.adr:=Nil; {следующий элемент пока отсутствует}

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

Ниже приведена процедура вставки в описанный ранее список нового элемента с информационной частью, равной Inf, после элемента u0.

Пример 24

pascal
PROCEDURE InsertElem(u0:ListPointer; Inf:integer);
var
u : ListPointer;
begin
New(u);
u^.x:=Inf;
u^.adr:=u0^.adr;
u0^.adr:=u;
end;

Процедура удаления элемента, следующего за элементом u0, из списка.

Пример 25

pascal
PROCEDURE DeleteElem(u0:ListPointer);
var
u : ListPointer;
begin
if u0^.adr<>Nil then
begin
u:=u0^.adr;
u0^.adr:=u0^.adr^.adr;
dispose(u);
end;
end;