Односвязный список

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

 

 

Рисунок 3.6 – Структура списка

Структура элемента списка может быть объявлена в программе, например, следующим образом:

Type

ptrList = ^TList;{ тип указателя связан со структурой элемента списка }

TList = record { структура элемента списка: }

inf : <тип данных>; { информация (данные) }

next: ptrList; { указатель на элемент списка }

end;

Рассмотрим типовые схемы создания, просмотра и удаления списка на примере односвязного списка, структура которого приведена выше.

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

Схема создания списка (шаг 1 и шаг 2) приведена на рисунке 3.7.

Var

p1, p2, pList: ptrList; { p1 – указатель на новый элемент списка }

{ p2 – вспомогательный указатель, в начале = NIL}

{ pList – указатель на начало списка }

Begin

p2 := NIL; { список пуст }

<Цикл добавления элементов в список>

Begin

New(p1); { выделяем память для элемента списка }

p1^.inf := <данные>; { формируем данные элемента списка }

p1^.next := p2; { "связываем" элементы списка }

p2 := p1; { сохраняем адрес элемента списка в p2 }

end;

pList:= p2; { Список создан. pList – адрес начала списка }

End.