Оперирование элементами списка Хранение списка
Для того чтобы сохранить информацию обо всем списке, достаточно только одной переменной - указателя на первый элемент этого списка. Обычно его называют головой списка. Указатель на голову должен быть выделенным: с ним нельзя производить никаких действий, которые могут стать причиной утери всего списка. Для работы со списком обычно заводят вспомогательный указатель.
Например:
var head,p,q: uk_spisok;
Но, вообще говоря, нет никаких специальных правил, которые обязали бы программиста давать выделенным указателям особые имена. Например, на рис. 10.1 выделенные указатели имеют имена head, tail, tree_root и start.
Обращение к элементам списка
Если есть указатель, указывающий на некоторый элемент списка, то содержимое полей этого элемента и даже следующих за ним можно получить так (см. рис. 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.