Наибольшее распространение среди динамических структур данных получили списки. Списком называется структура данных, каждый элемен которой содержит ссылку, указывающую на следующий элемент списка. Последний элемент указывает на Nil.
Для организации списков используются записи, состоящие из двух частей: информационной, которая и содержит всю информацию, подлежащую обраюотке, и адресной – указателя на следующий элемент списка.
Описание отдельного элемента списка целых чисел имеет вид:
1 2 3 4 5 6 7 8 9 10 |
type ListPointer = ^List; List = record x : integer; adr : ListPointer; end; var el : ListPointer; |
Обратите внимание на то, что в данном случае допустимо использование типа List до его непосредственного описания. Такое исключение в Турбо-Паскале сделано только для описания динамических структур данных.
Рассмотрим общую схему формирования списка. Допустим, в программе с использованием приведенного выше типа были объявлены два указателя u1 и u2.
1 2 3 4 |
var u1, u2 : ListPointer; |
Размещаем в памяти динамическую переменную u1^ типа запись, являющуюся первым элементом списка.
New(u1); {размещение 1-го элемента списка}
Read(u1^.x); {ввод значения 1-го элемента списка}
u1^.adr:=Nil; {следующий элемент пока отсутствует}
u2:=u1; {адрес 1-го элемента списка используется для формирования ссылки на 2-й элемент}
Размещаем второй элемент списка, все следующие элементы размещаются аналогично второму.
New(u2^.adr); {размещение 2-го (следующего) элемента списка и помещение его адреса в адресную часть 1-го (предыдущего) элемента}
u2:=u2^.adr; {переход ко 2-му (следующему) элементу списка}
Read(u2^.x); {ввод значения 2-го элемента списка}
u2^.adr:=Nil; {следующий элемент пока отсутствует}
Теперь каждый элемент списка содержит ссылку на следующий элемент. Последний элемент не содержит никакой ссылки – на нем список заканчивается.
Ниже приведена процедура вставки в описанный ранее список нового элемента с информационной частью, равной Inf, после элемента u0.
Пример 24
1 2 3 4 5 6 7 8 9 10 11 |
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
1 2 3 4 5 6 7 8 9 10 11 12 13 |
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; |