ВУЗ:
Составители:
Рубрика:
20
Здесь действует следующее правило Паскаля: в секции type можно описывать
указатель на еще не определенный тип при условии, что данный тип будет опре-
делен позднее в этой же секции.
Как уже было сказано, элементы типа Node можно завязать в цепочку. Для
этого полю next каждого элемента необходимо присвоить указатель на
следую-
щий, поле next последнего элемента следует присвоить значение nil (конец це-
почки):
data next
dat a next dat a next
Структура, изображённая на рисунке, называется линейным односвязным списком,
а ее элементы часто называются узлами списка. Доступ к элементам такого списка
– последовательный: нельзя обратиться к какому-то элементу, не перебрав пре-
дыдущие.
Если поле next последнего элемента списка указывает на первый элемент,
то такая структура называется кольцевым односвязным списком:
data next
dat a next dat a next
В отличие от линейного списка кольцевой не имеет явного начала и конца.
Если у каждого элемента, помимо указателя на следующий, имеется указа-
тель на предыдущий элемент prev: PNode, то такая структура называется линей-
ным двусвязным списком:
data nextprev dat a nextpr ev dat a nextpr ev
Двусвязные списки используются, если требуется двигаться по списку не только в
прямом, но и в обратном направлении.
Если в двусвязном списке первый и последний элементы указывают друг на
друга, то он называется кольцевым двусвязным списком:
data nextprev
2.2 Односвязные линейные списки
Для удобства определим вспомогательную функцию NewNode, создающую в
динамической памяти узел линейного односвязного списка, заполняющую его по-
ля значениями data и next и возвращающую указатель на него:
Страницы
- « первая
- ‹ предыдущая
- …
- 16
- 17
- 18
- 19
- 20
- …
- следующая ›
- последняя »
