Связанные списки
Указатели и динамические переменные позволяют создавать сложные динамические структуры данных, такие как связанные списки и деревья. Связанный вписок можно изобразить графически, (рис. 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).
head
указывает на этот элемент
после добавления второго элемента в начало списка head указывает на этот элемент
рис. 14
|
…
список пустой: head ни на что не указывает
после добавления одного элемента head
head
