Списки. Упорядоченный список.
Указатели и динамические переменные позволяют создавать сложные динамические структуры данных, такие как списки и деревья.
Список можно изобразить графически (рис. 8.6).
Рис. 8.6. Графическое изображение списка
Каждый элемент списка (узел) представляет собой запись, состоящую из двух частей. Первая часть – информационная. Вторая часть отвечает за связь со следующим и, возможно, с предыдущим элементом списка. Список, в котором обеспечивается связь только со следующим элементом, называется односвязным.
Для того чтобы программа могла использовать список, надо определить тип компонентов списка и переменную-указатель на первый элемент списка. Ниже приведен пример объявления компонента списка студентов:
type TPStudent = ^TStudent; // указатель на переменную типа TStudent // описание типа элемента списка TStudent = record surname: string [20]; // фамилия name: string [20];' // имя group: integer; // номер группы address: string [60]; // домашний адрес next: TPStudent; // указатель на следующий элемент списка end; var head: TPStudent; // указатель на первый элемент списка
Добавлять данные можно в начало, в конец или в нужное место списка. Во всех этих случаях необходимо корректировать указатели. На рис. 8.7 изображен процесс добавления элементов в начало списка.
После добавления второго элемента в список head указывает на этот элемент.
Рис. 8.7. Добавление элементов в список