Связанные списки

Указатели и динамические переменные позволяют создавать сложные динамические структуры данных, такие как связанные списки и деревья.

Связанный вписок можно изобразить графически, (рис. 13).

 

…

 

рис. 13

 

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

Чтобы программа могла использовать список, надо определить тип компонентов списка и переменную-указатель на первый элемент списка. Вот пример объявления списка студентов:

type

{связь между элементами списка}

p_stud=^student;

{описание типа элемента списка}

student=record

surname: string[20]; {фамилия}

name: string[20]; {имя}

group: integer; {номер группы}

address: string[60]; {домашний адрес}

next: p_stud; {указатель на следующий элемент списка}

end;

var

head: p_stud; {указатель на первый элемент списка}

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

 

NIL

head

 

список пустой: head ни на что не указывает

 

head

после добавления одного элемента head

указывает на этот элемент

 

head

после добавления второго элемента в начало

списка head указывает на этот элемент

 

 

рис. 14