Создание списка из N узлов за счет добавления

     узлов в конец списка

 

Первый узел создается отдельно (т.к. включить узел «за» несуществующим узлом невозможно), а остальные (n-1) узлов создаются и включаются в хвост списка одинаковым образом. При этом удобно использовать вспомогательный указатель на последний добавленный узел. Значение этого указателя изменяется в процессе создания списка, значение указателя на первый узел списка не изменяется после создания первого узла. Порядок следования узлов в списке получается прямым, т.к. первым является тот узел, который был включен в список первым.

 

Procedure Create2(var first: PList;                           n: byte); var p, last: PList; i: byte;		{ first – указатель на первый узел списка,   n – количество узлов в списке }   { last – указатель на последний узел списка }
begin if n=0 then first:=nil else begin		{ создание пустого списка }
new(first);		{ создание первого узла списка }
readln(first^.info);	{ заполнение информационного поля первого узла }
first^.link:=nil;	{ первый узел пока является в списке единственным }
last:=first;	{ установка указателя на последний вставленный узел}
for i:=2 to n do begin		{ создание остальных (n-1) узлов списка }
new(p);		{ создание узла списка }
readln(p^.info);		{ заполнение информационного поля узла }
last^.link:=p;	{ установка связи между списком и вставленным узлом }
last:=p;		{ новое значение указателя на последний узел }
end; end; end;

Исключение узла из начала списка

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

 

Рис. 24. Исключение узла из начала списка

 

Procedure Del_First(var first: PList);			{ first – указатель на первый узел списка }
var p: PList;
begin
if (first <> nil) then begin		{ список не пуст? }
p:=first;	{ установка вспомогательного указателя на первый узел списка }
first:=p^.link;	{ установка указателя first на второй узел списка }
dispose(p);	{ элемент хранения первого узла списка вернуть в кучу }
end;
end;

 

Перестановка указателя

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

 

Рис. 25. Перестановка указателя

 

...
if first<> nil then begin			{ список не пуст? }
p:=first;	{ установка вспомогательного указателя на первый узел списка }
p:=p^.link;	{ перестановка вспомогательного указателя на второй узел списка }
writeln(p^.info);		{ обработка информационного поля второго узла списка }
end;
...