Соглашение о ведущем и завершающем узлах связных списков.

Список циклический (не бывает пустым)

Операция	Реализация
вставка t после i	t -> next = x -> next;
удаление после x	x-> next = t; x -> next = x -> next -> next;
цикл обхода	t = head; do {...t= t -> next;} while(t!= head)
проверка на наличие минимум одного элемента	if (head -> next == head)

 

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

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

 

Фиктивный ведущий узел, 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 после модификаций в начале и конце списка.

 

Хранение целых списков

Целый список - линейный список, элементы которого принадлежат множеству натуральных чисел, причем некоторые элементы могут повторяться. В целых списках m – число элементов, n – размах списка, тогда разреженный список тот, в котором m<<n. Для хранения разреженных списков в компактной форме используются массивы.

Если требуется сохранить упорядоченность целых чисел, то включение и исключение элемента из какой-либо позиции вызывает сдвиг всех элементов, находящихся справа от нее. Причем целые списки могут хранить как связные линейные списки, так и кольцевые списки, посредством массива A длины не меньшей m и соответствующего дополнительного массива Next. Этот тип хранения также является компактным.

Альтернативой может служить метод хранения с использованием одного массива A, длина которого соответствует размаху N. Число, хранимое в каждой позиции A дает одновременно значение элемента списка и адрес следующего элемента, в этом случае Next оказывается излишним. Дополнительный указатель IP задает позицию первого числа в списке. Этот тип хранения называется расширенным