Каждый узел двунаправленного (двусвязного) циклического списка (ДЦС) содержит два поля указателей - на следующий и на предыдущий узлы. Указатель на предыдущий узел корня списка содержит адрес последнего узла. Указатель на следующий узел последнего узла содержит адрес корня списка.
Узел ДЦС можно представить в виде структуры, аналогичной ДЛС:
{
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);
}
как элемент очереди сделать указателем на кольцо?!!!
Использовать циклический список
Подскажите пожалуйста) Нужно удалить первое звено циклического списка, но ничего не выходит
origin-указатель на первый эл-т списка, lust- указатель на последний эл-т, L — текущий эл-т
2
3
4
5
6
7
8
9
if ((*L)->num == (*origin)->next->num)//Если текущий элемент является первым в списке
{
*L = (*L)->next;
(*L)->prev = del->prev;
(*L)->prev->next = del->next;
(*lust)->next = *L;//меняем адрес на который ссылается последний эл-т списка
}
free(del);
2
3
4
5
6
7
8
9
10
if (L == origin)//Должны совпасть адреса элементов, а не значения
{
*L = (*L)->next;
(*L)->prev = del->prev;
del->prev->next = del->next; // (*L)->prev сейчас указывает на удаляемый элемент, и для него связи переставлять бессмысленно
(*lust)->next = *L;//меняем адрес на который ссылается последний эл-т списка
origin = L; // корень списка нужно переместить
}
free(del);
Возник вопрос по взаимообмену узлов. Не проще ли обменять содержимое узлов (данные) не затрагивая структуру связанного списка?
2
3
4
5
6
7
{
int temp_field;
temp_field = lst1->field;
lst2->field = lst1->field;
lst1->field = temp_field;
}
Проще если поле данных одно
Не могли бы вы дать полностью код, одну целую программу, если быть точнее?
Пока полный код доступен только для ОЛС
К этой статье полезно добавить следующее:
— С некоторой версии ядра Linux (2.6, возможно не самой первой в линии 2.6) все без исключения динамические структуры kernel (списки, деревья, графы … все) были переписаны используя единственную базовую структуру — двусвязный циклический список.
— Для этого в types.h они определили struct list_head, а в list.h — десятка полтора макросов для работы со списком на все случаи жизни (таких как list_entry() или list_for_each()).
В дополнение к предыдущему комментарию:
— Огромный профит циклического списка (двухсвязного в частности) в том, что в нём при ошибочном разыменовании ссылок никогда не получится разименовать NULL. И тем самым завалить сразу ядро операционной системы (с последующими перезагрузками, потерями данных и др.). Это неоднократно оценили и отметили в публикациях все работающие с драйверами Linux.
Зачем нужен двусвязный циклический список (как и все другие виды циклических списков)?
Мне не встречалось случаев, где можно было бы их удачно применить. Профит от одной или двух лишних дуг не очевиден.
Единственное удачное применение (и-то с натяжкой, т.к. там не чисто циклический список), которое я видел — это задача на собеседовании(т.е. число академическое применение) следующего вида:
дан список, содержащий цикл, но не обычный, а например
a-b-c-d-e-f-c.
Т.е. первые элементы могут в цикл не входить. Требуется найти начало цикла (придумать оптимальный алгоритм).
Метод «разделяй и властвуй» с циклическими списками вроде бы и работает, но затруднено, т.е. вы не можете отщепить один элемент, а остальные обработать рекурсивно. Вы должны именно «удалить элемент из списка».
Проблемы вижу (скорее неудобство использования), а профита — нет. Асимптотическая сложность основных операций будет точно такой же как и обычного двусвязного списка.