数据结构(笔记）——单向循环链表

1.单向循环链表的定义

单向链表：每个节点只有一个指针域，指向下一个节点。

循环链表：链表的最后一个节点指针不是 NULL，而是指向头节点。

所以 单向循环链表 就是：
链表中的最后一个节点的 next 指针指向头节点，而不是空指针，从而形成一个 环状结构。

2.特点

3.优缺点

优点

可以从任意一个节点开始遍历，形成一个闭环结构。

在循环处理中比较方便（例如：约瑟夫问题）。

插入、删除操作不需要整体移动元素。

缺点

只能单向遍历，不能反向。

查找效率低，必须从头开始。

代码实现比顺序表复杂。

4.实现函数

申请一个节点

Node* _buynode(ElemType x) { Node* s = (Node*)malloc(sizeof(Node)); assert(s != NULL); s->data = x; s->next = NULL; return s; }

目的：申请一个新节点，存放数据 x。

步骤：

malloc 分配一块 Node 结构体大小的内存。

assert(s != NULL) 保证申请成功。

把传入的数据 x 存到 data 域。

next 指针先置空（后续再连接）。

返回这个新节点指针。

初始化

void InitSCList(List* list) { Node* s = (Node*)malloc(sizeof(Node)); assert(s != NULL); list->first = list->last = s; list->last->next = list->first; list->size = 0; }

目的：初始化一个空的单向循环链表。

步骤：

申请一个头结点 s。

头和尾都指向这个结点，说明链表里还没有有效数据。

尾结点的 next 指向头结点，形成 环。

size=0，表示空表。

尾插

void push_back(List* list, ElemType x) { Node* s = _buynode(x); list->last->next = s; list->last = s; list->last->next = list->first; list->size++; }

目的：尾插法，在链表最后添加一个元素。

步骤：

新建节点 s，存放 x。

旧尾节点 last->next = s，把新节点接在后面。

更新尾指针 last = s。

尾节点 next 指向头节点，保持循环。

长度 size++。

头插

void push_front(List* list, ElemType x) { Node* s = _buynode(x); s->next = list->first->next; list->first->next = s; if (list->first == list->last) { list->last = s; } list->size++; }

目的：头插法，把新元素插到表头（头结点之后）。

步骤：

新建节点 s。

让 s->next 指向原来的第一个有效节点。

让头结点指向 s，完成插入。

如果插入前链表是空的（first==last），那么新节点也要成为尾节点。

长度 size++。

显示元素

void show_list(List* list) { Node* p = list->first->next; while (p != list->first) { printf("%d-->", p->data); p = p->next; } printf("Nul.\n"); }

目的：遍历并打印链表数据。

步骤：

从第一个有效节点开始（first->next）。

一直循环，直到回到头结点 first。

每次输出一个节点数据。

输出结束后打印 "Nul."。

尾删

void pop_back(List* list) { if (list->size == 0) return; Node* p = list->first; while (p->next != list->last) { p = p->next; } free(list->last); list->last = p; list->last->next = list->first; list->size--; }

目的：删除最后一个节点。

步骤：

如果空表，直接返回。

找到尾节点的前一个节点 p。

释放原尾节点内存。

更新 last = p。

last->next = first 保持循环。

长度 --。

头删

void pop_front(List* list) { if (list->size == 0) return; Node* p = list->first->next; list->first->next = p->next; free(p); if (list->size == 1) { list->last = list->first; } list->size--; }

目的：删除第一个有效节点。

步骤：

如果空表，直接返回。

取出第一个有效节点 p = first->next。

头结点绕过 p，指向 p->next。

释放 p。

如果删除后变空表，则 last=first。

长度 --。

插入值

void insert_val(List* list, ElemType x) { Node* p = list->first; while (p->next != list->last && p->next->data < x) { p = p->next; } if (p->next == list->last && p->next->data < x) { push_back(list, x); } else { Node* s = _buynode(x); s->next = p->next; p->next = s; list->size++; } }

目的：按升序插入新元素 x。

步骤：

从头结点开始，找到第一个比 x 大的节点前驱 p。

如果到尾节点还比 x 小 → 直接尾插。

否则，在 p 和 p->next 之间插入新节点。

长度 ++。

查找

Node* find(List* list, ElemType key) { if (list->size == 0) return NULL; Node* p = list->first->next; while (p != list->first && p->data != key) p = p->next; if (p == list->first) return NULL; return p; }

目的：查找值为 key 的节点。

步骤：

空表直接返回 NULL。

从第一个节点开始查找，直到回到头结点或找到 key。

如果回到头结点还没找到 → 返回 NULL。

否则返回找到的节点。

长度

int length(List* list) { return list->size; }

目的：返回链表长度。

步骤：直接返回 size。

删除值

void delete_val(List* list, ElemType key) { if (list->size == 0) return; Node* p = find(list, key); if (p == NULL) { printf("要删除的数据不存在.\n"); return; } if (p == list->last) { pop_back(list); } else { Node* q = p->next; p->data = q->data; p->next = q->next; free(q); list->size--; } }

目的：删除值为 key 的节点。

步骤：

如果空表 → 返回。

调用 find 查找目标节点 p。

如果没找到 → 提示不存在。

如果要删的是尾节点 → 调用 pop_back。

否则：用 复制后继节点数据 的方法删除（O(1)）。

把 q = p->next 的数据拷贝到 p。

删除 q 节点，相当于“跳过了它”。

size--。

排序

void sort(List* list) { if (list->size == 0 || list->size == 1) return; Node* s = list->first->next; Node* q = s->next; list->last->next = NULL; list->last = s; list->last->next = list->first; while (q != NULL) { s = q; q = q->next; Node* p = list->first; while (p->next != list->last && p->next->data < s->data) { p = p->next; } if (p->next == list->last && p->next->data < s->data) { s->next = list->last->next; list->last->next = s; list->last = s; } else { s->next = p->next; p->next = s; } } }

目的：对链表进行升序排序（插入排序）。

步骤：

特殊情况：0 或 1 个节点，不用排。

先把第一个节点 s 当作有序链表，后面节点逐个插入。

遍历剩余节点 q，把每个节点 s 插入到合适位置。

插入方法：找到第一个比 s->data 大的节点之前。

如果都小于 → 插到尾部。

逆序

void resver(List* list) { if (list->size == 0 || list->size == 1) return; Node* p = list->first->next; Node* q = p->next; list->last->next = NULL; list->last = p; list->last->next = list->first; while (q != NULL) { p = q; q = q->next; p->next = list->first->next; list->first->next = p; } }

目的：反转链表（头插法逆置）。

步骤：

空表/一个元素 → 不处理。

p 指第一个节点，q 指第二个节点。

暂时断开循环：last->next=NULL。

把第一个节点设为新尾节点。

从第二个节点开始，把每个节点插到头结点后面（头插法）。

直到所有节点反转完成。

清除

void clear(List* list) { Node* p = list->first->next; while (p != list->first) { list->first->next = p->next; free(p); p = list->first->next; } list->last = list->first; list->last->next = list->first; list->size = 0; }

目的：清空链表，但保留头结点。

步骤：

从第一个有效节点开始，依次删除节点。

头结点指向下一个未删除节点。

最后 last=first，size=0。

销毁

void destroy(List* list) { clear(list); free(list->first); list->first = list->last = NULL; }

目的：销毁整个链表，释放所有内存（包括头结点）。

步骤：

调用 clear 清空所有有效节点。

释放头结点。

把指针 first 和 last 置空，避免野指针。