AB23-找出链表内最小值并不断输出，并将结点从链表中删除，直到链表为空， 再删除表头结点
代码实现
| C |
|---|
| /**
* 对带头结点的循环单链表执行操作：
* 反复找出链表内最小值并输出，然后删除该结点，
* 直到链表为空，最后删除头结点
* @param L 指向循环链表头结点的指针
*/
void del_min(LinkList L) {
// 边界条件检查：空链表（只有头结点自循环）
if (L == NULL || L->next == L) {
if (L) free(L); // 释放头结点
return;
}
// 循环直到链表为空（只剩头结点自循环）
while (L->next != L) {
// p指向当前结点的前驱（从头结点开始）
LinkList p = L;
// pos指向最小值结点的前驱结点
LinkList pos = L;
// 遍历循环链表查找最小值结点
while (p->next != L) {
// 如果当前结点的值小于已知最小值
if (p->next->data < pos->next->data) {
pos = p; // 更新最小值结点的前驱
}
p = p->next; // 继续向后查找
}
// 找到最小值结点，输出其值
printf("%d ", pos->next->data);
// 准备删除最小值结点
LinkList u = pos->next; // u指向要删除的最小值结点
// 删除操作：绕过最小值结点
pos->next = u->next; // 前驱结点指向最小值结点的后继
// 释放最小值结点的内存
free(u);
}
// 释放头结点
free(L);
}
|
循环链表结构图解
循环链表特点：
| Text Only |
|---|
| 普通链表：L→[ ]→[1]→[2]→[3]→NULL
↑
尾结点指向NULL
循环链表：L→[ ]→[1]→[2]→[3]→ ┐
↑ │
└──────────────────┘
尾结点指向头结点，形成环
|
循环链表遍历终止条件：
| Text Only |
|---|
| while (p != L) { // 当回到头结点时停止
// 处理结点
p = p->next;
}
|
算法执行流程图解
执行过程示例：
| Text Only |
|---|
| 初始循环链表：L→[ ]→[5]→[2]→[8]→[3]→ ┐
↑ │
└─────────────────────┘
第1轮：
查找最小值：2
输出：2
删除后：L→[ ]→[5]→[8]→[3]→ ┐
↑ │
└────────────────┘
第2轮：
查找最小值：3
输出：3
删除后：L→[ ]→[5]→[8]→┐
↑ │
└───────────┘
第3轮：
查找最小值：5
输出：5
删除后：L→[ ]→[8]→┐
↑ │
└───────┘
第4轮：
查找最小值：8
输出：8
删除后：L→[ ]→ ┐ (L->next == L，循环结束)
↑ │
└────┘
最终：释放头结点
|
查找和删除详细图解
查找最小值过程：
| Text Only |
|---|
| 链表：L→[ ]→[5]→[2]→[8]→[3]→--┐
↑ ↑ ↑ ↑ ↑ │
L p1 p2 p3 p4 │
pos │
└───────────────────────┘
查找过程：
p=L: p->next=[5], pos->next=[5]
p=[5]: p->next=[2], 2<5? 是 → pos=[5]
p=[2]: p->next=[8], 8<2? 否
p=[8]: p->next=[3], 3<2? 否
p=[3]: p->next=L, 结束
|
删除操作过程：
| Text Only |
|---|
| 删除前：
L→[ ]→[5]→[2]→[8]→[3]→-┐
↑ ↑ ↑ │
pos u u->next │
└────────────────┘
删除操作：
1. pos->next = u->next → [5]→[8]
2. free(u) → 释放[2]
删除后：
L→[ ]→[5]→[8]→[3]→-┐
↑ ↑ │
pos u->next │
└────────────┘
|
复杂度分析
时间复杂度：O(n²)
- 外层循环：执行n次（每个结点删除一次）
- 内层查找：第i次循环需要查找n-i+1个结点
- 总比较次数：n + (n-1) + (n-2) + ... + 1 = n(n+1)/2
- 总体时间复杂度：O(n²)
空间复杂度：O(1)
- 额外空间：只使用了常数个指针变量：
p、pos、u
- 无辅助空间：没有使用额外的数据结构
- 算法额外空间复杂度：O(1)
优化版本：添加边界检查和更清晰的逻辑
| C |
|---|
| /**
* 优化版本：添加边界检查和更清晰的逻辑
*/
void del_min_Optimized(LinkList L) {
// 边界检查
if (L == NULL) return;
// 检查是否为空循环链表
if (L->next == L) {
free(L);
return;
}
while (L->next != L) {
LinkList current = L;
LinkList min_prev = L;
// 查找最小值结点
while (current->next != L) {
if (current->next->data < min_prev->next->data) {
min_prev = current;
}
current = current->next;
}
// 输出并删除最小值结点
printf("%d ", min_prev->next->data);
LinkList min_node = min_prev->next;
min_prev->next = min_node->next;
free(min_node);
}
free(L);
}
|
优化版本：带计数功能的版本
| C |
|---|
| /**
* 带计数功能的版本
*/
int del_min_with_count(LinkList L) {
if (L == NULL) return 0;
int count = 0;
while (L->next != L) {
LinkList p = L;
LinkList pos = L;
while (p->next != L) {
if (p->next->data < pos->next->data) {
pos = p;
}
p = p->next;
}
printf("%d ", pos->next->data);
LinkList u = pos->next;
pos->next = u->next;
free(u);
count++;
}
free(L);
return count;
}
|
与其他链表类型的对比
| 特性 |
普通单链表 |
循环单链表 |
| 终止条件 |
p->next == NULL |
p->next == L |
| 空表判断 |
L->next == NULL |
L->next == L |
| 遍历复杂度 |
O(n) |
O(n) |
| 实现难度 |
简单 |
中等 |
算法特点
核心思想：
1. 循环查找：不断在循环链表中查找最小值
2. 有序输出：按递增顺序输出所有元素
3. 逐步删除：找到一个删除一个
4. 完全释放：最终释放所有结点内存
关键技巧：
- 循环遍历：使用p->next != L作为终止条件
- 前驱指针：便于删除操作
- 边界处理：正确处理空循环链表的情况
应用场景：
- 需要有序输出并释放内存的场景
- 优先级队列的简单实现
- 一次性处理的临时数据结构
与普通链表版本的区别：
1. 终止条件：从p->next == NULL改为p->next == L
2. 空表判断：从L->next == NULL改为L->next == L
3. 循环特性：利用循环链表的环形结构
这种算法虽然时间复杂度较高，但充分利用了循环链表的特性，是处理循环链表的经典算法之一。