Кольцо из двусвязного списка
Кольцо на двусвязном списке.
Если направить указатель последнего элемента двунаправленного списка не на NULL, а не первый элемент, то получим структуру-кольцо. Кольцо – циклическая структура, которая обычно реализует операции вставки и удаления, а также операции next и prev, позволяющие двигаться вперёд и назад по кольцу. Если кольцо собрано из односвязного списка, то операция prev, соответственно, не поддерживается. Наша структура-кольцо будет, подобно двусвязному списку, хранить указатель на узел кольца и его размер.

typedef int T; typedef struct _Node { T data; struct _Node *next; struct _Node *prev; } Node; typedef struct _Ring { size_t size; Node *current; } Ring; Ring* createRing() { Ring *tmp = (Ring*)malloc(sizeof(Ring)); tmp->size = 0; tmp->current = NULL; return tmp; }
Никаких особенностей здесь нет. Всё очень похоже на двусвязный список. Функции добавления и удаления элементов:
void addElement(Ring *ring, T value) { Node *prev = NULL; Node *tmp = (Node*)malloc(sizeof(Node)); tmp->data = value; //Если в кольце нет элементов if (ring->current == NULL) { ring->current = tmp; tmp->next = tmp->prev = tmp; } else { prev = ring->current->next->prev; tmp->next = ring->current->next; tmp->prev = ring->current; prev->prev = tmp; ring->current->next = tmp; ring->current = tmp; } ring->size++; } T removeElement(Ring *ring) { Node *afterTarget = NULL; T retVal; if (ring->current == NULL) { exit(1); } //Если в кольце последний элемент if (ring->current->next == ring->current) { retVal = ring->current->data; free(ring->current); ring->current = NULL; } else { afterTarget = ring->current->next; ring->current->prev->next = afterTarget; afterTarget->prev = ring->current->prev; retVal = ring->current->data; free(ring->current); ring->current = afterTarget; } ring->size--; return retVal; }
Заметьте, что при добавлении нового элемента указатель на элемент кольца сдвигается на вновь добавленный элемент. При удалении указатель current сдвигается на следующий элемент, после удаляемого. Функции prev и next позволяют двигаться по кольцевому списку. next сдвигает указатель current вперёд, prev назад.
Node* next(Ring *ring) { Node* retVal = NULL; if (ring->current) { ring->current = ring->current->next; retVal = ring->current; } return retVal; } Node* prev(Ring *ring) { Node* retVal = NULL; if (ring->current) { ring->current = ring->current->prev; retVal = ring->current; } return retVal; }
Последняя функция – circle. Она получает кольцо и функцию, которую применяет к каждому узлу кольца. Мы обходим кольцо до тех пор, пока не наткнёмся на первый узел. Все узлы имеют разный адрес в памяти благодаря тому, что функция addElement создаёт для каждого элемента новый узел
void circle(const Ring *ring, void (*f)(Node* node)) { Node *anchor = ring->current; if (anchor) { do { f(anchor); anchor = anchor->next; } while (anchor != ring->current); } } void printNode(Node *node) { printf("%d ", node->data); }
