Каждый узел однонаправленного (односвязного) циклического списка (ОЦС) содержит одно поле указателя на следующий узел. Поле указателя последнего узла содержит адрес корневого элемента.
Узел ОЦС можно представить в виде структуры, аналогичной односвязному линейному списку
{
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);
}
Здравствуйте, возникли проблемы при выводе отсортированного односвязного кольцевого списка. Пожалуйста укажите на ошибки. (Выводит только половину)
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
{
char name[SIZE];// поле данных
char deals[SIZE];// поле данных
char volume[SIZE];// поле данных
struct list* next; // указатель на следующий элемент
} *head;
…..
void arraysort()
{
struct list* str, * srznach,* test ;
srznach = head;
str = head;
do
{
struct list* p, * pfc;
pfc = head;
p = NULL;
int number_sup = 1;
do {
if ((number_sup < atoi(srznach->deals)) )
{
number_sup = atoi(srznach->deals);
p = srznach;
}
srznach = srznach->next;
} while (srznach != head);
while (pfc->next != p) // просматриваем список начиная с корня
{ // пока не найдем узел, предшествующий lst
pfc = pfc->next;
}
pfc->next = p->next; // удаляю элемент который вывел
if (str != p) // проверка на совпадение проверяемого элемента с самим собой
{
printf("Paper: %s Deals: %s Volume: %s ", p->name, p->deals, p->volume);
printf("\n");
printf("arg1\n");
}
else
{
printf("Paper: %s Deals: %s Volume: %s ", str->name, str->deals, str->volume);
printf("\n");
printf("arg2\n");
}
if (str)
{
str = str->next;
}
} while (str != head);
}
atoi(srznach->deals) — это что за работа с указателями?
в deals записывается количество сделок , и atoi(srznach -> deals) переводит строчное значение в целочисленное для сравнения
Да, но deals — это массив, и atoi(srznach->deals) переводит в число адрес этого массива
Спасибо , сделал сам)
Помогите пожалуйста с сортировкой пузырьком для этой структуры…
https://prog-cpp.ru/sort-bubble/
Я пытаюсь сделать эту сортировку , но она у меня не работает, подскажите пожалуйста, в чем моя ошибка?
2
3
4
5
6
7
8
9
10
11
12
list* p = lst;
list* t = lst->next;
for (int i = 0; i < size; ++i) {
for (int j = i+1; j < size; ++j) {
if (p->data > t->data) { swap(p, t, lst); }
t = t->next;
}
p =p->next;
}
}
i должно меняться до size-1
Если есть ещё ошибки, то, возможно, в другой части кода
У меня, почему-то, если список состоит из 3х элементов, например:11,12,5, в сортировке сравниваются 11 и 5, 11 больше 5, идет в Ваш swap, и этот swap возвращает список : 5,12.
Надо код смотреть
Здравствуйте, скажите пожалуйста, а здесь struct list * swap(struct list *lst1, struct list *lst2, struct list *head) lst 1, lst2 — узлы которые меняем, а head — указатель на начало списка?
Да
Здравствуйте, возможно ли реализовать сортировку списка по возрастанию или алфавиту?
Да, возможно. Необходимо сравнивать элементы списка и менять их местами (функция swap)
а если удалить корень, то как быть?
То надо следующий элемент сделать корнем
а каким образом? просто я уже все перепробовал, но так и не смог сделать
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
{
struct list *temp = head->ptr;
struct list *p = head;
if(head == NULL) // список пуст, удалять нечего
return NULL;
if(p->ptr == head) // остался последний элемент, который и есть корень
{
free(head);
return NULL;
}
while (p->ptr != head)
{ // пока не найдем узел, который указывает на корень
p = p->ptr;
}
p->ptr = temp; // зацикливаем указатель
free(head); // освобождаем память удаляемого узла
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); // условие окончания обхода
}//пишет что идентификатор 'list' не определен
Помогите пожалуйста )
Скорее всего, забыли описать структуру list.
при вызове функции addelem(list *lst, int number)
в скобках вместо int number пишем число.
а вместо list *lst что нужно написать?
*lst — это указатель на элемент, после которого требуется осуществить добавление.