Каждый узел однонаправленного (односвязного) циклического списка (ОЦС) содержит одно поле указателя на следующий узел. Поле указателя последнего узла содержит адрес корневого элемента.
Узел ОЦС можно представить в виде структуры, аналогичной односвязному линейному списку
{
int field; // поле данных
struct list *ptr; // указатель на следующий элемент
};
Основные действия, производимые над элементами ОЦС:
- Инициализация списка
- Добавление узла в список
- Удаление узла из списка
- Вывод элементов списка
- Взаимообмен двух узлов списка
Поскольку список является циклическим, реализация отдельной функции для удаления корня списка не требуется.
Инициализация ОЦС
Инициализация списка предназначена для создания корневого узла списка, у которого поле указателя на следующий элемент содержит адрес самого корневого элемента.
2
3
4
5
6
7
8
9
{
struct list *lst;
// выделение памяти под корень списка
lst = (struct list*)malloc(sizeof(struct list));
lst->field = a;
lst->ptr = lst; // указатель на сам корневой узел
return(lst);
}
Добавление узла в ОЦС
Функция добавления узла в список принимает два аргумента:
- Указатель на элемент, после которого происходит добавление
- Данные для добавляемого элемента.
Процедуру добавления элемента можно отобразить следующей схемой:
Добавление элемента в ОЦС включает в себя следующие этапы:
- создание добавляемого узла и заполнение его поля данных;
- переустановка указателя узла, предшествующего добавляемому, на добавляемый узел;
- установка указателя добавляемого узла на следующий узел (тот, на который указывал предшествующий узел).
Таким образом, функция добавления узла в ОЦС имеет вид, полностью аналогичный функции добавления узла в односвязный линейный список:
2
3
4
5
6
7
8
9
10
{
struct list *temp, *p;
temp = (struct list*)malloc(sizeof(list));
p = lst->ptr; // сохранение указателя на следующий элемент
lst->ptr = temp; // предыдущий узел указывает на создаваемый
temp->field = number; // сохранение поля данных добавляемого узла
temp->ptr = p; // созданный узел указывает на следующий элемент
return(temp);
}
Возвращаемым значением функции является адрес добавленного узла.
Удаление узла ОЦС
В качестве аргументов функции удаления узла ОЦС передается указатель на удаляемый узел. Поскольку список циклический, нет необходимости передавать указатель на корень списка.
Функция возвращает указатель на узел, следующий за удаляемым.
Удаление узла может быть представлено следующей схемой:
Удаление узла ОЦС включает в себя следующие этапы:
- установка указателя предыдущего узла на узел, следующий за удаляемым;
- освобождение памяти удаляемого узла.
2
3
4
5
6
7
8
9
10
11
12
{
struct list *temp;
temp = lst;
while (temp->ptr != lst) // просматриваем список начиная с корня
{ // пока не найдем узел, предшествующий lst
temp = temp->ptr;
}
temp->ptr = lst->ptr; // переставляем указатель
free(lst); // освобождаем память удаляемого узла
return(temp);
}
Вывод элементов ОЦС
Функция вывода элементов ОЦС аналогична функции для ОЛС за исключением условия окончания обхода элементов.
В качестве аргумента в функцию вывода элементов передается указатель на корень списка.
Функция осуществляет последовательный обход всех узлов с выводом их значений.
2
3
4
5
6
7
8
9
{
struct list *p;
p = lst;
do {
printf("%d ", p->field); // вывод значения узла p
p = p->ptr; // переход к следующему узлу
} 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
{
// Возвращает новый корень списка
struct list *prev1, *prev2, *next1, *next2;
prev1 = head;
prev2 = head;
while (prev1->ptr != lst1) // поиск узла предшествующего lst1
prev1 = prev1->ptr;
while (prev2->ptr != lst2) // поиск узла предшествующего lst2
prev2 = prev2->ptr;
next1 = lst1->ptr; // узел следующий за lst1
next2 = lst2->ptr; // узел следующий за lst2
if (lst2 == next1)
{
// обмениваются соседние узлы
lst2->ptr = lst1;
lst1->ptr = next2;
prev1->ptr = lst2;
}
else if (lst1 == next2)
{
// обмениваются соседние узлы
lst1->ptr = lst2;
lst2->ptr = next1;
prev2->ptr = lst2;
}
else
{
// обмениваются отстоящие узлы
prev1->ptr = lst2;
lst2->ptr = next1;
prev2->ptr = lst1;
lst1->ptr = next2;
}
if (lst1 == head)
return(lst2);
if (lst2 == head)
return(lst1);
return(head);
}
