下载掌阅APP，畅读海量书库
立即打开
线性表链式存储结构的另一种表现形式，就是循环链表。
对于单链表而言，最后一个结点的地址域是空，如果表中最后一个结点的指针域指向头结点，整个链表形成一个环，就构成了单循环链表，如图2.19所示。
图2.19 带头结点的单循环链表
循环链表的操作基本上和非循环链表相同，只是将原来判断指针是否为空变为判断是否是头指针，没有其他较大的变化。
访问单链表中某一结点每次只能从头开始顺序向后遍历，而访问单循环链表中某一结点，可以从任何一个结点开始，顺序向后遍历到达要访问的结点。
【例2.6】1200101 班每个学生都有学号，分别是1，2，3，...，n，所有同学按学号顺序围坐一圈，从第1 开始数，每数到第m个，该同学就要离开此圈，这样依次下来，直到圈中只剩下最后一位同学，则该同学就为班长。
算法思想：使用单循环链表数据结构模拟问题，每个结点是一位同学，结点的值域为该同学的学号，总共n个结点。遇到出列的结点则删除该结点。如此循环，直到只剩下最后一个结点为止。最后输出该结点的学号。
从循环链表中选择一个数据元素为班长，其中front为循环链表头指针，rear为循环链表表尾指针，length为链表的长度，rest为圈中剩余同学的个数，M为数到第M个，该同学结点就被删除，则选取流程图如图2.20所示。
图2.20 选取流程图
代码首先定义循环链表的结点，为方便起见，结点中只保存编号：
再实现循环链表，为了方便测试，循环链表中同时实现了增加结点和输出链表各结点编号，具体代码如下：
最后写驱动代码测试循环链表：
