Односвязные списки - это явные динамические структуры данных, составленные из ячеек. Каждая ячейка представляет собой динамическую переменную типа record, которая в основном состоит из двух полей: поле данных и поле связей. В поле данных запоминается обрабатываемая информация, связанная с ячейкой. Поле связей содержит указатель адреса ячейки, в которую можно попасть из текущей ячейки. Предполагается, что в любую ячейку можно попасть, начиная с первой ячейки, называемой базой списка.
В качестве примера рассмотрим односвязный список, составленный из четырёх ячеек:
Ячейки на рисунке сверху содержат элементы A, B, C и D.
Данные, необходимые для создания и обработки односвязного списка , определяются с помощью следующих описаний:
type AdresaCelula=^Celula;
Celula=record
Info : string;
Urm : AdresaCelula;
end;
var P : AdresaCelula;
Полезная информация, относящаяся к конкретной ячейке, запоминается в поле Info, а адрес следующей ячейки - в поле Urm. В поле Urm последней ячейки списка содержится значение nil. Адрес первой ячейки (базовый адрес) запоминается в переменную ссылочного типа P. Отметим, что при описании ссылочного типа AdresaCelula базовый тип Celula ещё не известен. Согласно правилам языка ПАСКАЛЬ, это возможно только в случае динамических переменных при условии, что базовый тип определяется ниже в этом же описании. Односвязный список может быть создан путём добавления в вершину списка (последний введённый элемент списка). по одному элементу. Естественно, перед началом работы создаваемый список является пустым, то есть не содержит ни одной ячейки.
Любой односвязный список можно определить рекурсивно следующим образом: а) отдельная ячейка является односвязным списком; б) ячейка, которая содержит указатель на другой односвязный список, также является односвязным списком. Для того, чтобы подчеркнуть этот факт соответствующие описания можно представить в виде:
type Lista=^Celula;
Celula=record
Info : string;
Urm : Lista;
end;
var P : Lista;
Частично свойства односвязных списков можно воспроизвести с помощью одномерного массива, но такое представление является неприемлемым в случае списков с заранее неизвестным числом элементов.
Примеры программ:
Program P122;
{Создание односвязного списка A->B->C->D }
type AdresaCelula=^Celula;
Celula=record
Info : string;
Urm : AdresaCelula;
end;
var P, { базовый адрес }
R, V : AdresaCelula;
begin
{ 1 - сперва список является пустым }
P:=nil;
{ 2 - добавление ячейки A }
new(R); { создание ячейки }
P:=R; { инициализация базового адреса }
R^.Info:='A'; { ввод полезной информации }
R^.Urm:=nil;
{ запись индикатора "конец списка" }
V:=R; { запоминание адреса вершины списка }
{ 3 - добавление ячейки B }
new(R); { создание ячейки }
R^.Info:='B'; { ввод полезной информации }
R^.Urm:=nil;{запись индикатора "конец списка"}
V^.Urm:=R; { создание связи A -> B }
V:=R; { обновление адреса вершины списка }
{ 4 - добавление ячейки C }
new(R); { создание ячейки }
R^.Info:='C'; { ввод полезной информации }
R^.Urm:=nil;
{запись индикатора "конец списка"}
V^.Urm:=R; { создание связи B -> C }
V:=R; { обновление адреса вершины списка }
{ 5 - добавление ячейки D }
new(R); { создание ячейки }
R^.Info:='D'; { ввод полезной информации }
R^.Urm:=nil;
{запись индикатора "конец списка"}
V^.Urm:=R; { создание связи C -> D }
V:=R; { обновление адреса вершины списка }
{ Вывод созданного списка на экран}
R:=P;
while R<>nil do begin
writeln(R^.Info);
R:=R^.Urm
end;
readln;
end.
Program P123; { Создание линейных списков }
type AdresaCelula=^Celula;
Celula=record
Info : strig;
Urm : AdresaCelula;
end;
var p, q, r : AdresaCelula;
s : string;
i : integer;
procedure Creare;
begin
p:=nil;
write('s='); readln(s);
new(r) ; r^.Info:=s; r^.Urm:=nil;
p:=r; q:=r; write('s=');
while not eof do
begin
readln (s) ; write('s=');
new(r) ; r^.Info:=s; r^.Urm:=nil;
q^.Urm:=r; q:=r;
end;
end;{ Создание }
procedure Afisare;
begin
r:=p;
while r<>nil do
begin
writeln(r^.info);
r:=r^.urm;
end;
readln;
end; { Вывод на экран }
begin
Creare;
Afisare;
end.
