数据结构学习之路(二)----循环链表与双向循环链表

一、前言

上一章学习中，我们学习了顺序表与单链表，单链表是最基础的形式，但它在某些场景下存在局限性：无法从任意结点访问其前驱，尾结点无法快速回到头部。为了解决这些问题，循环链表和双向链表应运而生。本文将详细介绍循环链表（包括带头结点的单向循环链表）、约瑟夫环问题（经典应用）以及双向循环链表的原理与C语言实现，代码均经过整理与测试。

二、循环链表

2.1 什么是循环链表

循环链表是单链表的一种变形：将最后一个结点的 next 指针从 NULL 改为指向头结点（或第一个结点），使整个链表形成一个环。

结构示意（带头结点）：

┌→ [H] → [A] → [B] → [C] ─┐
└──────────────────────────┘

2.2 核心区别

2.3 C语言实现（带头结点的单向循环链表）

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

typedef int Elemtype;

// 结点结构
typedef struct _node {
Elemtype val;
struct _node* next;
} node_t;

// 链表管理结构（带头结点）
typedef struct {
node_t head; // 头结点（不是指针，直接占用空间）
node_t* rear; // 尾指针，方便尾插
int num; // 结点个数（不含头结点）
} LinkList_t;

// 初始化：头结点的next指向自己，rear指向头结点，计数为0
void creatLoopLink(LinkList_t* link_loop) {
link_loop->num = 0;
link_loop->head.next = &link_loop->head;
link_loop->rear = &link_loop->head;
}

// 头插法：在头结点之后插入新结点
int InsertLoopLinkHead(LinkList_t* link_loop, Elemtype val) {
node_t* new_node = malloc(sizeof(node_t));
if (new_node == NULL) {
return -1; // 内存分配失败
}
new_node->val = val;
new_node->next = link_loop->head.next;
link_loop->head.next = new_node;

// 如果插入前链表为空，则更新rear指向新结点
if (link_loop->rear == &link_loop->head) {
link_loop->rear = new_node;
}
link_loop->num++;
return 0;
}

// 尾插法：在rear之后插入新结点，并更新rear
int GoBackLoopLink(LinkList_t* link_loop, Elemtype val) {
node_t* new_node = malloc(sizeof(node_t));
if (new_node == NULL) {
return -1;
}
new_node->val = val;
// 新结点的next指向头结点（保持循环）
new_node->next = link_loop->rear->next;
link_loop->rear->next = new_node;
link_loop->rear = new_node;

// 如果插入前链表为空，则头结点的next也要指向新结点
if (link_loop->head.next == &link_loop->head) {
link_loop->head.next = new_node;
}
link_loop->num++;
return 0;
}

// 遍历并打印所有结点
void showLoopLink(LinkList_t* link_loop) {
node_t* p = link_loop->head.next;
// 循环结束条件：p回到头结点
while (p != &link_loop->head) {
printf("%d\\t", p->val);
p = p->next;
}
printf("\\n");
}

// 删除第一个值为val的结点
void deleteLoopLink(LinkList_t* link_loop, Elemtype val) {
node_t* p = &link_loop->head;
// 寻找待删除结点的前驱
while (p->next != &link_loop->head && p->next->val != val) {
p = p->next;
}
if (p->next->val == val) {
node_t* tmp = p->next;
p->next = tmp->next;
free(tmp);
link_loop->num–;
} else {
printf("no %d Element\\n", val);
}
}

三、约瑟夫环问题

3.1 问题描述

约瑟夫环（Josephus Problem） 是一个经典的数学应用问题：

n 个人编号 1~n 围成一圈，从第 1 个人开始报数，每数到 m 的人出列，然后从下一个人重新报数，直到所有人出列。求最后的幸存者编号（或出列顺序）。

3.2 循环链表解法

利用循环链表可以完美模拟这个围成一圈的过程：每个结点代表一个人，报数过程相当于遍历链表，删除结点对应人出列。

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

typedef int Elemtype;

// 结点结构
typedef struct _node {
Elemtype val;
struct _node* next;
} node_t;

// 约瑟夫环管理结构
typedef struct {
node_t* head; // 指向第一个结点
node_t* tail; // 指向最后一个结点
} Joseph_t;

// 初始化：创建包含 n 个结点的循环链表（编号1~n）
int initJosephList(Joseph_t* game, int n) {
game->head = game->tail = NULL;
for (int i = 1; i <= n; i++) {
node_t* new_node = malloc(sizeof(node_t));
if (new_node == NULL) return -1;
new_node->val = i;
if (game->head == NULL) {
game->head = new_node;
game->tail = new_node;
} else {
game->tail->next = new_node;
game->tail = new_node;
}
}
// 尾结点指向头结点，形成循环
game->tail->next = game->head;
return 0;
}

// 打印当前环中所有结点
void showJoseph(Joseph_t* game) {
node_t* p = game->head;
do {
printf("%d\\t", p->val);
p = p->next;
} while (p != game->head);
printf("\\n");
}

// 开始游戏：每数到 m 的结点删除，返回最后幸存者的编号
int startJosephGame(Joseph_t* game, int m) {
node_t* pre = NULL; // 前驱结点
node_t* cur = game->head;
// 当环中不止一个结点时继续
while (cur != cur->next) {
// 报数 1 到 m-1，移动 pre 和 cur
for (int i = 1; i < m; i++) {
pre = cur;
cur = cur->next;
}
// 此时 cur 指向待删除结点（报数到 m 的人）
pre->next = cur->next;
free(cur);
cur = pre->next; // 从下一个人继续报数
}
int survivor = cur->val;
free(cur);
return survivor;
}

// 示例用法
int main() {
Joseph_t game;
int n = 41, m = 3; // 经典约瑟夫问题：41人，数到3出列
initJosephList(&game, n);
printf("初始序列：");
showJoseph(&game);
int survivor = startJosephGame(&game, m);
printf("幸存者编号：%d\\n", survivor);
return 0;
}

四、双向循环链表

4.1 什么是双向循环链表

双向链表的每个结点有两个指针域：prev（前驱）和 next（后继）。将双向链表的头结点的 prev 指向尾结点，尾结点的 next 指向头结点，就构成了双向循环链表。这是实际工程中最常用的链表形态之一（如 Linux 内核链表）。

结构示意：

┌→ [H] ⇄ [A] ⇄ [B] ⇄ [C] ─┐
└──────────────────────────┘
prev 与 next 形成完整闭环

4.2 结点的定义

typedef struct _Dnode {
Elemtype val;
struct _Dnode* next;
struct _Dnode* prev;
} D_nodelist;

4.3 基本操作实现（带头结点的双向循环链表）

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

typedef int Elemtype;

typedef struct _Dnode {
Elemtype val;
struct _Dnode* next;
struct _Dnode* prev;
} D_nodelist;

// 初始化：头结点的 next 和 prev 都指向自身
void initdloopList(D_nodelist* head) {
head->val = 0; // 头结点不存有效数据
head->next = head;
head->prev = head;
}

// 通用添加结点函数：将 new_node 插入到 prev 和 next 之间
void addNode(D_nodelist* new_node, D_nodelist* next, D_nodelist* prev) {
next->prev = new_node;
new_node->next = next;
new_node->prev = prev;
prev->next = new_node;
}

// 头插：在头结点之后插入新结点
int insertHeadDLink(D_nodelist* head, Elemtype val) {
D_nodelist* new_node = malloc(sizeof(D_nodelist));
if (new_node == NULL) return -1;
new_node->val = val;
// 将新结点插入到 head 和 head->next 之间
addNode(new_node, head->next, head);
head->val++; // 头结点的 val 域用来记录结点个数
return 0;
}

// 尾插：在头结点之前（即最后一个结点之后）插入新结点
int GoBackDLink(D_nodelist* head, Elemtype val) {
D_nodelist* new_node = malloc(sizeof(D_nodelist));
if (new_node == NULL) return -1;
new_node->val = val;
// 将新结点插入到 head 和 head->prev 之间
addNode(new_node, head, head->prev);
head->val++;
return 0;
}

// 正向遍历：从头结点的下一个结点开始，直到回到头结点
void showDListV1(D_nodelist* head) {
D_nodelist* pos = head->next;
while (pos != head) {
printf("%d\\t", pos->val);
pos = pos->next;
}
printf("\\n");
}

// 反向遍历：从头结点的前一个结点（即尾结点）开始，直到回到头结点
void showDListV2(D_nodelist* head) {
D_nodelist* pos = head->prev;
while (pos != head) {
printf("%d\\t", pos->val);
pos = pos->prev;
}
printf("\\n");
}

// 通用删除函数：将 next 和 prev 两个结点直接相连
void deDList(D_nodelist* next, D_nodelist* prev) {
next->prev = prev;
prev->next = next;
}

// 删除第一个值为 e 的结点
void deleteDList(D_nodelist* head, Elemtype e) {
D_nodelist* pos = head->next;
// 查找值为 e 的结点
while (pos != head) {
if (pos->val == e) break;
pos = pos->next;
}
if (pos != head) {
// 将 pos 的前驱和后继直接相连
deDList(pos->next, pos->prev);
free(pos);
head->val–;
} else {
printf("NO FIND THIS ELEMENT!\\n");
}
}

// 释放整个链表（所有数据结点）
void release(D_nodelist* head) {
D_nodelist* pos = head->next;
while (pos != head) {
deDList(pos->next, pos->prev);
free(pos);
head->val–;
pos = head->next;
}
}

五、总结对比

5.1 时间复杂度对比

将上一章学习的顺序表与单向链表拿来做对比，我们可以清晰的看见时间复杂度

5.2 空间对比

存储密度 = 数据域大小 / 结点总大小，以 int 数据 + 32位指针为例估算。

5.3 选型指南

场景：需要频繁按下标访问？
└── 是 → 顺序表（数组）

场景：需要频繁在头部插入/删除？
└── 是 → 链表（单/双/循环均可）

场景：需要频繁在尾部操作 + 需要从尾向头遍历？
└── 是 → 双向链表

场景：需要环形遍历（如轮转调度、约瑟夫环）？
└── 是 → 循环链表

场景：需要双向遍历 + 环形结构 + 任意位置O(1)删除？
└── 是 → 双向循环链表（工程首选）

场景：数据量未知或变化剧烈？
└── 是 → 链表
└── 否 → 顺序表

场景：内存紧张，数据量可预估？
└── 是 → 顺序表

5.4 一句话总结

以上就是关于循环链表、约瑟夫环以及双向循环链表的详细讲解与代码实现。