Фиктивный ведущий узел, Null – указатель завершающего узла

инициализация	head = new node; head -> next =0;
вставка t после x	t -> next = x -> next; x -> next = t;
удаление после x	t = x -> next; x -> next = t -> next;
цикл обхода	for(t = head ->next; t!0; t = t-> next)
проверка на пустоту	if(head -> next == 0)

 

Фиктивный ведущий и завершающий узлы.

инициализация	head = new node; z = new node; head -> next = z; z -> next -> z;
вставка t после x	t -> next = x -> next; x -> next = t;
удаление после x	x -> next = x -> next -> next;
цикл обхода	for (t = head -> next; t!= x; t=t -> next)
проверка на пустоту	if(head -> next == x)

 

Для связных списков наиболее характерны следующие ошибки:

1) ссылка на неопределенный указатель

2) использование указателя, который изменяется неизвестным образом

Причина этих ошибок – возможное присутствие указателей на один и тот же узел.

 

Линейные связные списки. Двусвязные списки

Линейный связный список - последовательность ячеек, связанных в некотором порядке. Каждая ячейка имеет два поля: в одном из них находится элемент списка, в другом – указатель, сообщающий положение следующей ячейки.

Пример 1

позиция = 1 2 3 4 5 6 7 8 9 [i]

A[i] = x b x d a x c x x

Next[i] = x 7 x 0 2 x 4 x x

IP = 5

признак конца = 0

A[3] <- e

Next[3] <- Next[2]

Next[2] <- 3

Если хотим удалить символ 7, то

Next[2] <- [7]

Двусвязные списки

Двусвязные (двунаправленные) линейные списки - линейные списки, записи которых связаны посредством пары указателей, хранимых в адресных полях записей списка. Логическую структуру двусвязного списка иллюстрирует следующая диаграмма

Рис. 1.

В каждой записи поле prev содержит адрес предыдущей записи, поле - next - адрес последующей записи, а data обозначает информационные поля. Для доступа к списку могут быть использованы адреса начальной (start), конечной (end) и текущей (this) записей списка. Индикатором начальной и конечной записей являются нулевые (NULL) значения адресных полей Start и end, соответственно.

 

Любая функциональная обработка списка строится на основе процедур модификации и просмотра. Процедуры модификации списка должны обеспечивать вставки и исключение записей списка. Частным случаем процедур вставки и исключения являются процедуры добавить и удалить начальную или конечную запись списка. Следующая диаграмма иллюстрирует процедуру вставки новой записи Z после записи Y (или перед записью X)

Рис. 2.

Следующая диаграмма иллюстрирует процедуру исключения текущей записи this.

Рис. 3.

Процедуры просмотра списка должны обеспечивать смещение указателя текущей записи (this) на требуемое число позиций в направлении начала или конца списка, как показано на следующей диаграмме.

Рис. 4.

Частным случаем смещения указателя текущей записи является переход к соседней предыдущей или последующей записи (смещение на 1 позицию), а также нефиксированный переход к начальной или конечной записям списка, который позволяет принудительно инициализировать указатели start и end после модификаций в начале и конце списка.