Основные действия, производимые над узлами двусвязного циклического списка (ДЦС)

Над узлами двусвязного циклического списка можно производить следующие действия:

• Инициализация списка
• Добавление узла в список
• Удаление узла из списка
• Вывод элементов списка
• Вывод элементов списка в обратном порядке
• Взаимообмен двух узлов списка

Инициализация ДЦС:

Инициализация списка предназначена для создания корневого узла списка, у которого поля указателей на следующий и предыдущий узлы указывают на сам создаваемый узел.

Рисунок 2 - Инициализация ДЦС

Программная реализация:

struct list * init(int a) { // а- значение первого узла

struct list *lst;

// выделение памяти под корень списка

lst = (struct list*)malloc(sizeof(struct list));

lst->field = a;

lst->next = lst; // указатель на следующий узел

lst->prev = lst; // указатель на предыдущий узел

return(lst);
}

Добавление узла в ДЦС:

Функция добавления узла в ДЦС аналогична функции для ДЛС и принимает два аргумента:

§ Указатель на узел, после которого происходит добавление

§ Данные для добавляемого узла.

Процедуру добавления узла можно отобразить следующей схемой:

Рисунок 3 - Добавление узла в ДЦС

Добавление узла в ДЦС включает в себя следующие этапы:

§ создание узла добавляемого элемента и заполнение его поля данных;

§ переустановка указателя "следующий" узла, предшествующего добавляемому, на добавляемый узел;

§ переустановка указателя "предыдущий" узла, следующего за добавляемым, на добавляемый узел;

§ установка указателя "следующий" добавляемого узла на следующий узел (тот, на который указывал предшествующий узел);

§ установка указателя "предыдущий" добавляемого узла на узел, предшествующий добавляемому (узел, переданный в функцию).

Для циклического списка предыдущий узел любого узла существует, поэтому нет необходимости проверки предыдущего элемента на нулевое значение.

Таким образом, функция добавления узла в ДЦС имеет вид:

struct list * addelem(list *lst, int number) {

struct list *temp, *p;

temp = (struct list*)malloc(sizeof(list));

p = lst->next; // сохранение указателя на следующий узел

lst->next = temp; // предыдущий узел указывает на создаваемый

temp->field = number; // сохранение поля данных добавляемого узла

temp->next = p; // созданный узел указывает на следующий узел

temp->prev = lst; // созданный узел указывает на предыдущий узел

p->prev = temp;

return(temp);
}

Удаление узла ДЦС:

В качестве аргументов функции удаления узла ДЦС передается указатель на удаляемый узел. Поскольку узел списка имеет поле указателя на предыдущий узел, нет необходимости передавать указатель на корень списка.

Функция возвращает указатель на узел, следующий за удаляемым.

Удаление узла может быть представлено следующей схемой:

Рисунок 4 - Удаление узла ДЦС

Удаление узла ДЦС включает в себя следующие этапы:

§ установка указателя "следующий" предыдущего узла на узел, следующий за удаляемым;

§ установка указателя "предыдущий" следующего узла на узел, предшествующий удаляемому;

§ освобождение памяти удаляемого узла.

struct list * deletelem(list *lst) {

struct list *prev, *next;

prev = lst->prev; // узел, предшествующий lst

next = lst->next; // узел, следующий за lst

prev->next = lst->next; // переставляем указатель

next->prev = lst->prev; // переставляем указатель

free(lst); // освобождаем память удаляемого элемента

return(temp);
}

Вывод элементов ДЦС:

Функция вывода элементов ДЦС аналогична функции для ОЦС. В качестве аргумента в функцию вывода элементов передается указатель на корень списка. Функция осуществляет последовательный обход всех узлов с выводом их значений.

void listprint(list *lst) {

struct list *p;

p = lst;

do {

printf("%d ",p->field); // вывод значения элемента p

p = p->next; // переход к следующему узлу

} while(p != lst); // условие окончания обхода
}

Для ДЦС также можно вызвать функцию вывода элементов списка в обратном порядке.

Вывод элементов ДЦС в обратном порядке:

Функция вывода элементов ДЦС в обратном порядке принимает в качестве аргумента указатель на корень списка. Функция перемещает указатель на последний узел списка и осуществляет последовательный обход всех узлов с выводом их значений в обратном порядке. Однако процедура перемещения указателя на последний узел в данном случае намного проще по сравнению с ДЛС, поскольку указатель "предыдущий" корня списка как раз и содержит адрес последнего узла.

void listprintr(list *lst) {

struct list *p;

p = lst;

do {

p = p->prev; // переход к предыдущему узлу

printf("%d ",p->field); // вывод значения элемента p

} while(p != lst); // условие окончания обхода
}

Взаимообмен узлов ДЦС:

В качестве аргументов функция взаимообмена узлов ДЦС принимает два указателя на обмениваемые узлы, а также указатель на корень списка. Функция возвращает адрес корневого узла списка.

Взаимообмен узлов списка осуществляется путем переустановки указателей. Для этого необходимо определить предшествующий и последующий узлы для каждого заменяемого. При этом возможны две ситуации:

§ заменяемые узлы являются соседями;

§ заменяемые узлы не являются соседями, то есть между ними имеется хотя бы один узел.

При замене соседних узлов переустановка указателей выглядит следующим образом:

Рисунок 5 - Взаимообмен узлов ДЦС

Функция взаимообмена узлов ДЦС выглядит следующим образом:

struct list * swap(struct list *lst1, struct list *lst2, struct list *head) {

Возвращает новый корень списка

struct list *prev1, *prev2, *next1, *next2;

prev1 = lst1->prev; // узел предшествующий lst1

prev2 = lst2->prev; // узел предшествующий lst2

next1 = lst1->ptr; // узел следующий за lst1

next2 = lst2->ptr; // узел следующий за lst2

if(lst2 == next1) { // обмениваются соседние узлы

lst2->next = lst1;

lst2->prev = prev1;

lst1->next = next2;

lst1->prev = lst2;

next2->prev = lst1;

prev1->next = lst2;

} else if(lst1 == next2) { // обмениваются соседние узлы

lst1->next = lst2;

lst1->prev = prev2;

lst2->next = next1;

lst2->prev = lst1;

next1->prev = lst2;

prev2->next = lst1;

} else { // обмениваются отстоящие узлы

prev1->next = lst2;

lst2->next = next1;

prev2->next = lst1;

lst1->next = next2;

lst2->prev = prev1;

next2->prev = lst1;

lst1->prev = prev2;

next1->prev = lst2;

}

if(lst1 == head)

return(lst2);

if(lst2 == head)

return(lst1);

return(head);
}