2025: 环形传送器（C语言）

解题思路:

本题使用了数据结构中得不带头结点的循环双向链表

注意事项:

删除结点后需要 free(node)

参考代码:

#include <stdio.h>
#include <stdlib.h>

// 链表结点结构体
typedef struct node {
    int data;               // 数据域
    struct node *next;      // 后继指针
    struct node *prior;     // 前驱指针
} Node;

// 申请堆空间创建新的结点
#define NEW_NODE()((struct node*)malloc(sizeof(struct node)))

// 插入结点
Node *insertNode(Node *L, int x) {
    Node *newNode = NEW_NODE();
    newNode->data = x;
    if (L == NULL) {
        newNode->prior = newNode;
        newNode->next = newNode;
    } else {
        newNode->next = L->next;
        newNode->prior = L;
        L->next->prior = newNode;
        L->next = newNode;
    }
    return newNode;     // 返回插入的结点
}

// 删除结点并返回结点中存放的数据
Node *removeNode(Node *L, int *x) {
    if (L == NULL) {
        return NULL;
    }
    Node *current = L;
    *x = current->data;        // 返回删除结点的数据域部分
    if (L->next == L) {         // 删除链表中的最后一个结点
        free(current);
        return NULL;
    }

    Node *next = L->next == L ? NULL : L->next;
    L->next->prior = L->prior;
    L->prior->next = L->next;
    free(current);         // 释放结点申请的堆空间
    return next;
}

int main() {
    int m;
    scanf("%d", &m);
    Node *L = NULL;          // 不带头结点的循环双向链表
    int op, x;
    for (int i = 0; i < m; i++) {
        scanf("%d", &op);
        switch (op) {
            case 1:         // 插入物品
                scanf("%d", &x);
                L = insertNode(L, x);
                break;
            case 2:         // 移动物品
                if (L) {
                    L = L->next;
                }
                break;
            case 3:         // 取出物品
                L = removeNode(L, &x);
                printf("%d\n", x);
                break;
        }
    }
    // 释放链表申请的堆空间
    while (L) {
        L = removeNode(L, &x);
    }
    return 0;
}