2.3.4 循环单链表
1.循环单链表的存储
循环单链表（Circular Linked List）是一种首尾相连的单链表。在线性链表中，每个结点的指针都指向它的下一个结点，最后一个结点的指针域为空，不指向任何结点，仅表示链表结束。若把这种结构改变一下，使最后一个结点的指针域指向链表的第一个结点，就构成了循环链表。
与单链表类似，循环单链表也可分为带头结点的结构和不带头结点的结构。循环单链表不为空时，最后一个结点的指针域指向头结点。如图2.22所示。
图2.22 带头结点的循环单链表
循环单链表为空时，头结点的指针域指向头结点本身。如图2.23所示。
图2.23 循环单链表为空时的情况
注意：带头结点的循环单键表为空时，有head->next==head。
有时为了操作上的方便，在循环单链表中只设置尾指针rear而不设置头指针，利用rear指向循环单链表的最后一个结点。如图2.24所示。
图2.24 只设置尾指针的循环单链表示意图
利用尾指针可以使有些操作变得简单，例如，要将如图2.25所示的两个循环单链表（尾指针分别为LA和LB）合并成一个链表，只需要将一个表的表尾和另一个表的表头连接即可。如图2.26所示。
图2.25 设置尾指针的循环单链表LA和LB
图2.26 两个设置尾指针的循环单链表合并后的示意图
合并两个设置尾指针的循环单链表需要三步操作：
①把LA的表尾与LB的第一个结点相连接，即LA->next=LB->next->next。
②释放LB的头结点，即free（LB->next）。
③把LB的表尾与LA的表头相连接，即LB->next=LA->next。
2.循环单链表的应用
【例2.4】 约瑟夫问题。有n个人，编号为1，2，…，n，围成一个圆圈，按照顺时针方向让编号为k的人从1开始报数，报数为m的人出列，从出列的下一个人重新开始报数，报数为m的人出列，一直这样重复下去，直到所有的人都出列。要求编写一个算法，输入n、k和m，依次输出每次出列人的编号。
【分析】解决约瑟夫问题可以分为三个步骤：
（1）建立一个具有n个结点的不带头结点的循环单链表，编号从1到n，代表n个人。
（2）找到第k个结点，即第一个开始报数的人。
（3）编号为k的人从1开始报数，并开始计数，报数为m的人出列即删除该结点。从下一个结点开始继续报数，重复执行步骤（2）和（3），直到最后一个结点被删除。
约瑟夫问题算法描述如下：
测试程序如下：
图2.27 程序运行结果
程序运行结果如图2.27所示。