C语言循环链表的原理与使用操作

C语言循环链表是一种基于链表数据结构的可循环访问的存储方式。与线性表相比,链表能够优化数据的插入和删除操作的效率，并且支持动态的内存分配。而循环链表则定义了表头尾相接，最后一个节点指向第一个节点的链表。下面将详细讲解循环链表的原理、使用操作及其实现过程，以及两个示例进行说明。

原理

循环链表是由多个节点组成的链式结构，每个节点包含自身的数据和指向下一个节点的指针。其最后一个节点的指针指向第一个节点，形成了一个环形结构。这种结构具有更好的复用性和高效性，可以被广泛地应用于各个领域的数据结构。

实现步骤

1. 定义链表节点结构体

   c
typedef struct node {
int data;
struct node* next;
} Node;

2. 插入节点

   首先需要定义一个指向链表头的指针，开始时为空。

   c
Node* head = NULL;

   要插入一个节点，需要先找到要插入的位置，在循环链表中，插入节点的方式与单链表和双链表相同。

   ```c
   void insert(Node head, int data, int pos) {
   Node new_node = (Node)malloc(sizeof(Node));
   new_node->data = data;
   new_node->next = NULL;

   if (*head == NULL) { // 链表为空，直接插入
       *head = new_node;
       (*head)->next = *head;
       return;
   }
   
   if (pos == 0) { // 插入头部
       new_node->next = (*head)->next;
       (*head)->next = new_node;
       int temp = (*head)->data;
       (*head)->data = new_node->data;
       new_node->data = temp;
       return;
   }
   
   Node* current = (*head);
   for (int i = 1; i < pos; i++) {
       current = current->next;
   }
   
   new_node->next = current->next;
   current->next = new_node;
   

   }
   ```

3. 删除节点

   与插入节点类似，删除节点也需要找到要删除的位置。因为需要删除的是链表节点，而链表的节点是通过指针实现的，因此需要记录上一个节点的指针。

   ```c
   void delete (Node* head, int pos) {
   if (head == NULL) { // 链表为空，什么也不做
   return;
   }

   Node* current = (*head);
   Node* previous = NULL;
   
   if (pos == 0) { // 删除头部节点
       while (current->next != *head) {
           current = current->next;
       }
       Node* node_to_delete = *head;
       current->next = (*head)->next;
       *head = (*head)->next;
       free(node_to_delete);
       return;
   }
   
   for (int i = 1; i <= pos; i++) {
       previous = current;
       current = current->next;
   
       if (current == *head && i != pos) { // 节点不存在
           return;
       }
   }
   
   previous->next = current->next;
   free(current);
   

   }
   ```

4. 遍历链表

   循环链表的遍历有一个特殊之处，因为循环链表的尾部是指向头部的，因此需要对链表头特殊处理。

   ```c
   void display(Node* head) {
   if (head == NULL) { // 链表为空
   printf("List is empty.\n");
   return;
   }

   Node* current = head;
   do {
       printf("%d ", current->data);
       current = current->next;
   } while (current != head);
   printf("\n");
   

   }
   ```

示例1

下面的示例描述了如何创建一个循环链表，并将数据插入到链表中。

int main() {
    Node* head = NULL;
    int choice, data, position;
    printf("Welcome to the circular linked list implementation.\n");
    while (1) {
        printf("Enter 1 to insert a node\n");
        printf("Enter 2 to delete a node\n");
        printf("Enter 3 to display the list\n");
        printf("Enter 4 to exit\n");
        scanf("%d", &choice);
        switch (choice) {
            case 1:
                printf("Enter the data:");
                scanf("%d", &data);
                printf("Enter the position:");
                scanf("%d", &position);
                insert(&head, data, position);
                break;
            case 2:
                printf("Enter the position:");
                scanf("%d", &position);
                delete (&head, position);
                break;
            case 3:
                display(head);
                break;
            case 4:
                printf("Bye!\n");
                return 0;
            default:
                printf("Invalid choice! Please try again.\n");
        }
        printf("\n");
    }
}

示例2

下面是一个示例，使用循环链表实现一个循环队列。

#define MAX_QUEUE_SIZE 10

typedef struct queue {
    int items[MAX_QUEUE_SIZE];
    int front;
    int rear;
} Queue;

Queue* create_queue();
void enqueue(Queue* queue, int item);
int dequeue(Queue* queue);
void display(Queue* queue);

int main() {
    Queue* queue = create_queue();
    int choice, item;
    printf("Welcome to the circular queue implementation.\n");
    while (1) {
        printf("Enter 1 to enqueue an item\n");
        printf("Enter 2 to dequeue an item\n");
        printf("Enter 3 to display the queue\n");
        printf("Enter 4 to exit\n");
        scanf("%d", &choice);
        switch (choice) {
            case 1:
                printf("Enter the item:");
                scanf("%d", &item);
                enqueue(queue, item);
                break;
            case 2:
                item = dequeue(queue);
                if (item != -1) {
                    printf("Dequeued item is %d\n", item);
                }
                break;
            case 3:
                display(queue);
                break;
            case 4:
                printf("Bye!\n");
                return 0;
            default:
                printf("Invalid choice! Please try again.\n");
        }
        printf("\n");
    }
}

Queue* create_queue() {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->front = -1;
    queue->rear = -1;
    return queue;
}

void enqueue(Queue* queue, int item) {
    if ((queue->rear + 1) % MAX_QUEUE_SIZE == queue->front) { // 队列满
        printf("Queue is full.\n");
        return;
    }
    if (queue->front == -1) { // 队列为空
        queue->front = 0;
        queue->rear = 0;
    } else {
        queue->rear = (queue->rear + 1) % MAX_QUEUE_SIZE;
    }
    queue->items[queue->rear] = item;
}

int dequeue(Queue* queue) {
    if (queue->front == -1) { // 队列为空
        printf("Queue is empty.\n");
        return -1;
    }
    int item = queue->items[queue->front];
    if (queue->front == queue->rear) { // 队列中只有一个元素
        queue->front = -1;
        queue->rear = -1;
    } else {
        queue->front = (queue->front + 1) % MAX_QUEUE_SIZE;
    }
    return item;
}

void display(Queue* queue) {
    if (queue->front == -1) { // 队列为空
        printf("Queue is empty.\n");
        return;
    }
    int i;
    for (i = queue->front; i != queue->rear; i = (i + 1) % MAX_QUEUE_SIZE) {
        printf("%d ", queue->items[i]);
    }
    printf("%d ", queue->items[i]);
    printf("\n");
}

以上两个示例详细说明了循环链表的原理、使用操作和实现过程，希望能对读者有所帮助。