Списки

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

Пусть тип point описан следующим образом:

Type point = ^ item;

item = record

number: integer;

next: point

end;

Каждая переменная типа point состоит из двух компонентов: индентифицирующего номера и указателя на следующий элемент. Из этих переменных, связав их указателями, можно создать линейный список.

Способ построения линейного списка: начиная с пустого списка, последовательно добавлять элементы в его начало.

Процесс формирования списка из n элементов:

First: = nil; {начало с пустого списка}

While n>0 do begin

New (r); r^. Next: = first; r^. Number: = n;

First: = r; n: = n-1 end;

Основные операции со списками

Просмотр списка

Напишем процедуру, которая вывод на экран значение поля number элементов списка.

{просмотр списка}

procedure Print (first: point);

Var r: point

Begin

R: = first;

While r<>nil do begin

Writeln (‘number = ‘, r^. Number);

R:= r^. Next; End;

Поиск в списке

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

{поиск в линейном списке}

Procedure Search (first: point; x: integer; var q: point);

{q – звращает указатель на найденный элемент; q – nil, если элемент с ключем х в списке нет}

var r: point;

ok: boolean;

begin

r: = first; ok: = true;

while (r<>nil) and ok do

if r^. Number = x then

ok: = false;

else r: = r^. Next; q: = r

end;

Включить элемент в список

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

{включить элемент в середину списка перед q^}

Procedure Insert (Var q: point; x: integer):

{х – значение информационного поля включаемого элемента}

Var r: point

Begin

New (r); {размещаем элемент в памяти}

R^. Number: = x;

{меняем ссылку}

r^/ next: = q^. Next; q^. Next: = r

end;

Если требуется включить перед элементом q^, а не после него, то кажется, что однонаправленная цепочка связей создает трудность, поскольку нет “прохода” к элементам, предшествующим данному. Однако эту проблему можно решить, используя простой прием, который состоит в том, что новый элемент вставляется после q^, но затем происходит обмен значениями между новым элементом и q^.

{включить элемент в середину списка перед q^}

Procedure insert Before (Var q: point; x: integer);

Var r: point;

Begin

New (r); {размещаем элемент памяти}

{включаем элемент после q^}

r^. Next: = q^. Next; q^. Next: = r;

{выполняем обмен значениями}

r^. Number: = q^. Nunber;

q^. Number: = x

end;

Удалить элемент из списка

Посмотрим как удаляется элемент из середины списка. Следует иметь в виду, что этот довольно очевидный и простой прием можно применять только в случае, когда y q^ есть последующий элемент, т.е он не является последним в списке.

Предположим, что надо удалить элемент, расположенный после элемента, на который указывает ссылка q

{удаление элемента из середины списка после q^}

Procedure Del (Var q: point);

Var r: point;

Begin

r: = q^. Next;

q^. Next: = q^. Next;

r^. Next: = nil

End;

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

{удаление элемента q^}

Prrocedure Deiet (Var q: point):

Var r: point;

Begin

r: = q^. next;

q^: = r^;

r^. Next: = nil; End;

Обратите внимание на то, что удаляемый из списка элемент остается в памяти и к нему имеется доступ к указателю r, так что в дальнейшем этот элемент можно вставить, например, в другой список. Если требуется освободить занимаемую этим элементом память, то следует выполнить

Dispose (r);

r: = nil