当前位置：首页 > news >正文

算法竞赛阶段二-数据结构（37）数据结构循环链表模拟实现

news 2025/7/28 10:30:25

之前单链表中，数组全初始化为0，末尾最后一个next 存的就是0，指向的就是头节点

循环链表的基本概念

循环链表是一种特殊的链表，其尾节点的指针域指向头节点，形成一个闭环。与普通单链表相比，循环链表的遍历需要额外注意终止条件，避免无限循环。

循环链表的节点结构

循环链表的节点与普通链表节点相同，包含数据域和指针域。以C语言为例：

typedef struct Node {int data;           // 数据域struct Node *next;  // 指针域，指向下一个节点
} Node;

循环链表的初始化

初始化时，头节点的指针域指向自身，形成空循环链表：

Node* initList() {Node *head = (Node*)malloc(sizeof(Node));if (head != NULL) {head->next = head;  // 头节点指向自身}return head;
}

循环链表的插入操作

头插法

新节点插入到头节点之后：

void insertAtHead(Node *head, int data) {Node *newNode = (Node*)malloc(sizeof(Node));newNode->data = data;newNode->next = head->next;head->next = newNode;
}

尾插法

新节点插入到尾节点之后（需先遍历到尾节点）：

void insertAtTail(Node *head, int data) {Node *current = head;while (current->next != head) {current = current->next;}Node *newNode = (Node*)malloc(sizeof(Node));newNode->data = data;newNode->next = head;current->next = newNode;
}

循环链表的删除操作

删除指定值的节点：

void deleteNode(Node *head, int data) {Node *current = head;while (current->next != head) {if (current->next->data == data) {Node *temp = current->next;current->next = temp->next;free(temp);return;}current = current->next;}
}

循环链表的遍历

遍历时需检查是否回到头节点：

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

循环链表的销毁

释放所有节点内存，避免内存泄漏：

void destroyList(Node *head) {Node *current = head->next;while (current != head) {Node *temp = current;current = current->next;free(temp);}free(head);
}