Обращение к элементам списка

Если есть указатель, указывающий на некоторый элемент списка, то содержимое полей этого элемента и даже следующих за ним можно получить так (см. рис. 10.2):

p	- адрес текущего элемента списка;
p^	- запись из нескольких полей, хранящаяся по адресу p;
p^.znachenie	- значение первого поля этой записи;
p^.next_element	- значение второго поля этой записи, являющееся адресом следующего элемента списка;
p^.next_element^.znachenie	- значение, хранящееся в первом поле элемента списка, следующего за тем, на который указывает р.

Рис. 10.2.  Правила обращения к элементам списка

Создание списков

Предположим, что есть некоторый набор значений (например, в файле), которые необходимо записать в создаваемый односвязный список. Тогда у нас есть две возможности создавать этот список: от хвоста к голове или от головы к хвосту.

Мы приведем здесь обе программы, позволив себе для краткости опустить описания типов, воспользовавшись описанием, показанным в табл. 1 (a):

var head,p: ukazatel; f: text; begin ... head:= nil; while not eof(f) do begin new(p); read(f,p^.znach); p^.next:= head; head:= p; end; end.	Рис. 10.3.  Очередной шаг процесса генерации списка "от хвоста к голове"
var head,p,q: ukazatel; f: text; begin ... if eof(f) then head:= nil else begin new(head); {головной элемент создается отдельно} read(f,head^.znach); head^.next:= nil; q:= head; while not eof(f) do begin new(p); read(f,p^.znach); p^.next:= nil; q^.next:= p; q:= q^.next; end; end; end.	Рис. 10.4.  Очередной шаг процесса генерации списка "от головы к хвосту"

Просмотр элементов списка

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

p:= head; {начать просмотр с головы списка}

while p<>nil do

begin

writeln(p^.znach);

p:= p^.next; {переход к следующему элементу списка}

end;

Замечание: Для того чтобы во время работы со списком не произошло выхода за его пределы, любой список обязательно должен оканчиваться "нулевым" указателем nil.

Удаление элементов списка

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

p:= head; {начать с головы списка}

while p^.next^.zhach<>х do p:= p^.next; {поиск}

q:= p^.next; {удаляемый элемент}

p^.next:= q^.next; {связка "через один"}

dispose(q); {освобождение памяти}