Каждый узел двунаправленного (двусвязного) циклического списка (ДЦС) содержит два поля указателей - на следующий и на предыдущий узлы. Указатель на предыдущий узел корня списка содержит адрес последнего узла. Указатель на следующий узел последнего узла содержит адрес корня списка.
Узел ДЦС можно представить в виде структуры, аналогичной ДЛС:
{
int field; // поле данных
struct list *next; // указатель на следующий элемент
struct list *prev; // указатель на предыдущий элемент
};
Основные действия, производимые над узлами ДЦС:
- Инициализация списка
- Добавление узла в список
- Удаление узла из списка
- Вывод элементов списка
- Вывод элементов списка в обратном порядке
- Взаимообмен двух узлов списка
Инициализация ДЦС
Инициализация списка предназначена для создания корневого узла списка, у которого поля указателей на следующий и предыдущий узлы указывают на сам создаваемый узел.
2
3
4
5
6
7
8
9
10
{
struct list *lst;
// выделение памяти под корень списка
lst = (struct list*)malloc(sizeof(struct list));
lst->field = a;
lst->next = lst; // указатель на следующий узел
lst->prev = lst; // указатель на предыдущий узел
return(lst);
}
Добавление узла в ДЦС
Функция добавления узла в ДЦС аналогична функции для ДЛС и принимает два аргумента:
- Указатель на узел, после которого происходит добавление
- Данные для добавляемого узла.
Процедуру добавления узла можно отобразить следующей схемой:
Добавление узла в ДЦС включает в себя следующие этапы:
- создание узла добавляемого элемента и заполнение его поля данных;
- переустановка указателя "следующий" узла, предшествующего добавляемому, на добавляемый узел;
- переустановка указателя "предыдущий" узла, следующего за добавляемым, на добавляемый узел;
- установка указателя "следующий" добавляемого узла на следующий узел (тот, на который указывал предшествующий узел);
- установка указателя "предыдущий" добавляемого узла на узел, предшествующий добавляемому (узел, переданный в функцию).
Для циклического списка предыдущий узел любого узла существует, поэтому нет необходимости проверки предыдущего элемента на нулевое значение.
Таким образом, функция добавления узла в ДЦС имеет вид:
2
3
4
5
6
7
8
9
10
11
12
{
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);
}
Возвращаемым значением функции является адрес добавленного узла.
Удаление узла ДЦС
В качестве аргументов функции удаления узла ДЦС передается указатель на удаляемый узел. Поскольку узел списка имеет поле указателя на предыдущий узел, нет необходимости передавать указатель на корень списка.
Функция возвращает указатель на узел, следующий за удаляемым.
Удаление узла может быть представлено следующей схемой:
Удаление узла ДЦС включает в себя следующие этапы:
- установка указателя "следующий" предыдущего узла на узел, следующий за удаляемым;
- установка указателя "предыдущий" следующего узла на узел, предшествующий удаляемому;
- освобождение памяти удаляемого узла.
2
3
4
5
6
7
8
9
10
{
struct list *prev, *next;
prev = lst->prev; // узел, предшествующий lst
next = lst->next; // узел, следующий за lst
prev->next = lst->next; // переставляем указатель
next->prev = lst->prev; // переставляем указатель
free(lst); // освобождаем память удаляемого элемента
return(prev);
}
Вывод элементов ДЦС
Функция вывода элементов ДЦС аналогична функции для ОЦС.
В качестве аргумента в функцию вывода элементов передается указатель на корень списка.
Функция осуществляет последовательный обход всех узлов с выводом их значений.
2
3
4
5
6
7
8
9
{
struct list *p;
p = lst;
do {
printf("%d ", p->field); // вывод значения элемента p
p = p->next; // переход к следующему узлу
} while (p != lst); // условие окончания обхода
}
Для ДЦС также можно вызвать функцию вывода элементов списка в обратном порядке.
Вывод элементов ДЦС в обратном порядке
Функция вывода элементов ДЦС в обратном порядке принимает в качестве аргумента указатель на корень списка. Функция перемещает указатель на последний узел списка и осуществляет последовательный обход всех узлов с выводом их значений в обратном порядке. Однако процедура перемещения указателя на последний узел в данном случае намного проще по сравнению с ДЛС, поскольку указатель "предыдущий" корня списка как раз и содержит адрес последнего узла.
2
3
4
5
6
7
8
9
{
struct list *p;
p = lst;
do {
p = p->prev; // переход к предыдущему узлу
printf("%d ", p->field); // вывод значения элемента p
} while (p != lst); // условие окончания обхода
}
Взаимообмен узлов ДЦС
В качестве аргументов функция взаимообмена узлов ДЦС принимает два указателя на обмениваемые узлы, а также указатель на корень списка. Функция возвращает адрес корневого узла списка.
Взаимообмен узлов списка осуществляется путем переустановки указателей. Для этого необходимо определить предшествующий и последующий узлы для каждого заменяемого. При этом возможны две ситуации:
- заменяемые узлы являются соседями;
- заменяемые узлы не являются соседями, то есть между ними имеется хотя бы один узел.
При замене соседних узлов переустановка указателей выглядит следующим образом:
При замене узлов, не являющихся соседними переустановка указателей выглядит следующим образом:
Функция взаимообмена узлов ДЦС выглядит следующим образом:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
{
// Возвращает новый корень списка
struct list *prev1, *prev2, *next1, *next2;
prev1 = lst1->prev; // узел предшествующий lst1
prev2 = lst2->prev; // узел предшествующий lst2
next1 = lst1->next; // узел следующий за lst1
next2 = lst2->next; // узел следующий за 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);
}
