2.3 单链表和循环单链表
线性表可以采用链式存储结构进行存储，链式存储结构主要有单链表和双链表等，本节主要介绍单链表和循环单链表。
2.3.1 单链表的定义
从2.2节看出，线性表顺序存储结构的空间是整体分配的，逻辑关系上相邻的两个元素在物理上也相邻，因此存取表中任一元素十分简单，但插入和删除运算需要移动大量的元素。而线性表的链式存储结构中每个元素的存储空间作为一个结点单独分配，因此逻辑上相邻的元素对应的结点在物理上不一定是相邻的，通过增加指针域表示逻辑关系，在插入和删除操作时只需要修改相应的指针域，从而克服了顺序表中插入和删除操作需要移动大量的元素的弱点，但同时也失去了顺序表可随机存取的优点。
本节讨论线性表的单链表存储方法，它是一种最基本的链式存储结构。单链表中每个结点存放一个数据元素，并用一个指针表示结点间的逻辑关系，即每个结点的指针域存放后继结点的地址（线性表中每个元素有唯一的后继元素）。因此单链表的一个存储结点包含两个部分，结点的基本形式如下：
其中，data部分称为数据域，用于存储线性表的一个数据元素，也就是说在单链表中一个结点存放一个数据元素；next部分称为指针域或链域，用于指向后继元素对应的结点。
单链表分为带头结点和不带头结点两种类型。在许多情况下，带头结点的单链表能够简化运算的实现过程。因此本章讨论的单链表除特别指出外均指带头结点的单链表。
另外，在单链表中尾结点之后不再有任何结点，那么它的next域设置为什么值呢？有以下两种方式。
（1）将尾结点的next域用一个特殊值NULL（空指针，不指向任何结点，只起标志尾结点的作用）表示，这样的单链表为非循环单链表。通常所说的单链表都是指这种类型的单链表。
（2）将尾结点的next域指向头结点，这样可以通过尾结点移动到头结点，从而构成一个查找环，将这样的单链表称为循环单链表。
仍假设数据元素的类型为ElemType，单链表的结点类型声明如下。
说明：上述SLinkNode类型声明是合法的，实际上是给struct node结构体类型取了一个别名SLinkNode，这样使算法书写更简洁。另外，如果其中next不是指针变量，如改为：
这样就出错了，这里SLinkNode1类型声明是递归的，C/C++中不允许类型递归声明。这是因为类型是用来定义变量的，如果类型声明是递归的，则无法给变量分配空间。对于正确的SLinkNode类型，如果执行SLinkNode∗p=（SLinkNode∗）malloc（sizeof（SLinkNode））语句，其空间分配如图2.12所示，其中，next只分配一个地址大小的空间，如32位机中，每个地址固定占用4B，所以能够正确地为变量p分配所指向的内存空间，其大小为sizeof （ElemType）+4。
图2.12 给变量p分配一个结点空间
如果改为SLinkNode1∗p1=（SLinkNode1∗）malloc（sizeof（SLinkNode1））语句，p1指针变量分配的空间大小应该为sizeof（ElemType）+sizeof（SLinkNode1），而此时sizeof （SLinkNode1）是不能确定的，所以无法为p1分配指向的空间。
需要注意变量p的空间和p所指向的空间的区别，p变量本身仅占用一个地址空间，如4B，而它所指向的空间可能很大。可以这样理解，前面定义指针变量p并分配所指空间的语句中，（SLinkNode∗）malloc（sizeof（SLinkNode））部分由计算机分配一个没有名字的内存空间，通过将其首地址放到变量p中，程序员就可以用变量p间接地操作这块内存空间了，称为p结点
。为了简化，通常不画出p变量的空间，图2.10可以用图2.13的方式来简化表示。
图2.13 简化的指针变量示意图
2.3.2 线性表基本运算在单链表上的实现
在带头结点的单链表中，头结点的data域通常不存储任何信息，头结点的next域指向第一个数据结点，即存放第一个数据结点的地址。通过头结点的指针L（称为头指针）来标识整个单链表。
如图2.14所示是一个带头结点L的单链表，这样的单链表中实际存放的数据元素为n个，即一个头结点，n个数据结点。头结点指针称为头指针，这里是通过头指针标识单链表的。第一个数据结点称为首结点，首结点指针称为首指针（对于不带头结点的单链表，一般是通过首指针标识单链表）。最后一个结点称为尾结点，尾结点指针称为尾指针。
图2.14 带头结点的单链表L
说明：尽管后面算法设计中使用的链表一般是带头结点的，有时根据实际需要也设计成不带头结点的链表，需要读者在掌握带头结点链表算法设计的基础上，领会不带头结点链表算法设计方法。
下面讨论单链表中线性表基本运算算法的实现过程。
图2.15 一个空的单链表L
1．单链表的基本运算算法
1）初始化线性表运算算法
创建一个空的单链表，它只有一个头结点，由L指向它。该结点的next域为空，data域未设定任何值，如图2.15所示。对应的算法如下。
本算法的时间复杂度为O（1）。
说明：
（1）在单链表算法中，大量用到指针运算，读者应充分理解指针运算的含义，如SLinkNode∗p，∗q，∗r语句定义了三个相同类型的指针变量，它们可以指向同一个结点，也可以指向不同的结点（这些结点类型必须相同），但一个指针变量任何时刻只能指向一个结点。
如图2.16所示，p、q指向不同的结点，当执行p—>next=q语句时，计算机先求出赋值符号右边的表达式值（称为右值），这里是结点值为b的结点的地址，存放在指针变量q中，赋值符号左边的值（称为左值，一定是有地址含义的表达式如变量名）p—>next被修改为q的值，也就是说，p所指结点的next域存放值为b的结点的地址。
图2.16 执行p—>next=q的结果
（2）InitList算法中的形参L为引用类型，引用类型的含义在第1章中介绍过，这里再强调一下。任何算法都是用来被调用的（试想象一下，在C/C++程序中，除了main（）函数外，设计一个没有被调用的函数，这个函数显然是不会被执行的），例如以下主函数中调用了单链表中的几个基本运算函数。
其中，h是实参，在执行SLinkNode∗h语句时仅为指针变量h分配了一个地址空间，其值是没有意义的，如果InitList（L）函数中形参L不是引用类型，当执行InitList（h）语句后，形参L的值不会回传给实参h，也就是说h中还是先前没有意义的值，再执行InsElem（h，x，1）语句（功能是在单链表h的第一个位置上插入一个值为x的结点）时一定出错，因为希望初始化的单链表h实际上不存在。只有将InitList（L）函数中L设计为引用类型，执行InitList（h）语句后形参L的值才会回传给实参h，h才真正指向一个单链表的头结点，后面才会正确执行单链表的运算。
2）销毁线性表运算算法
一个单链表L中的所有结点空间都是通过malloc函数分配的（即程序员自己手工分配的），在不再需要L时系统不会自动释放这些结点空间，程序员必须通过调用free函数释放所有结点的空间（即程序员自己手工分配的空间需要程序员自己手工释放）。其实现过程是，先让pre指向头结点，p指向首结点（pre和p是一对相邻结点指针），如图2.17所示，当p不为NULL时循环：释放pre所指结点空间，让pre、p指针沿next域同步后移一个结点。当循环结束，p为NULL，此时再释放pre所指的尾结点。对应的算法如下。
本算法的时间复杂度为O（n），其中，n为单链表L中数据结点的个数。
图2.17 pre、p指针指向两个相邻的结点
3）求线性表的长度运算算法
不同于顺序表，在单链表中没有直接保存长度信息，需要通过扫描方式求长度。设置一个整型变量i作为计数器，i初值为0，p初始时指向首结点。然后沿next域逐个往后查找，每移动一次，i值增1。当p所指结点为空时，结束这个过程，i的值即为表长（数据结点个数，不计头结点）。对应的算法如下。
本算法的时间复杂度为O（n），其中，n为单链表L中数据结点的个数。
4）求线性表中第i个元素运算算法
用p从头开始扫描单链表L中的结点，用计数器j累计扫描过的结点，其初值为0，在扫描中j等于i时，若p不为空，则p所指结点即为要找的结点，查找成功，算法返回1，如图2.18所示；否则算法返回0表示未找到这样的结点。
图2.18 查找第i个结点的过程
对应的算法如下。
本算法的时间复杂度为O（n），其中，n为单链表L中数据结点的个数。
说明：在顺序表中该运算的时间复杂度为O（1），表明顺序表具有随机存取特性。而单链表中该运算的时间复杂度为O（n），表明单链表不具有随机存取特性，这是两种存储结构的重要差别之一。
5）按值查找运算算法
在单链表L中从首结点开始查找第一个值域与e相等的结点，若存在这样的结点，则返回其逻辑序号，如图2.19所示；否则返回0。对应的算法如下。
本算法的时间复杂度为O（n），其中，n为单链表L中数据结点的个数。
图2.19 查找值为e的结点的过程
6）插入元素运算算法
先在单链表L中查找第i—1个结点，若未找到返回0；找到后由p指向该结点，创建一个以x为值的新结点s，将其插入到p结点之后。在p结点之后插入s结点的操作如下。
①将结点s的next域指向结点p的下一个结点（s—>next=p—>next）。
②将结点p的next域改为指向新结点s（p—> next=s）。
插入结点的过程如图2.20所示，从中看到，在单链表中插入一个结点需找到其前驱结点，在插入一个新结点时只需修改前驱结点和新插入结点的next域，不像顺序表那样需要移动大量的元素。
图2.20 在p结点后插入s结点
注意：插入操作的①和②执行顺序不能颠倒，否则若先执行p—>next=s，由于先修改p—>next值使原p结点的后继结点的地址丢失了，会导致插入错误。
对应的算法如下。
本算法的时间复杂度为O（n），其中，n为单链表L中数据结点的个数。
7）删除元素运算算法
先在单链表L中查找第i—1个结点，若未找到返回0，找到后由p指向该结点，然后让q指向后继结点（即要删除的结点），若q所指结点为空则返回0；否则删除q结点并释放其占用的空间。
删除p指结点的后继结点的过程如图2.21所示，其操作如下。
图2.21 删除p结点的后继结点
p—>next=q—>next;
从中看到，在单链表中删除一个结点和插入一个结点一样，需要找到其前驱结点，而且删除结点不像在顺序表中删除一个元素需要移动大量的元素。
对应的算法如下。
本算法的时间复杂度为O（n），其中，n为单链表L中数据结点的个数。
8）输出线性表运算算法
从首结点开始，沿next域逐个往下扫描，输出每个扫描到结点的data域，直到尾结点为止。对应的算法如下。
本算法的时间复杂度为O（n），其中，n为单链表L中数据结点的个数。
提示：将单链表结点类型声明及其基本运算函数存放在SLinkNode.cpp文件中。
当单链表的基本运算设计好后，给出以下主函数调用这些基本运算函数，读者可以对照程序执行结果进行分析，进一步体会单链表各种操作的实现过程。
上述程序的执行结果如图2.9所示。
2．整体创建单链表的算法
可以通过调用基本运算算法来创建单链表，其过程是先初始化一个单链表然后向其中一个一个地插入元素。这里介绍的是快速整体创建单链表的算法也称为整体建表。假设给定一个含有n个元素的数组，由它来整体创建单链表，这种建立单链表的常用方法有如下两种。
1）头插法建表
该方法从一个空单链表（含头结点L，并且置L—>next为NULL）开始，读取数组a（含有n个元素）中的一个元素，创建一个新结点s，将读取的数据元素存放到该结点的数据域中，然后将其插入到当前链表的表头上（操作语句是s—>next= L—>next；L—>next=s；），如图2.22所示。
图2.22 头插法建立单链表
再读取数组a的下一个元素，采用相同的操作建立新结点s并插入到单链表L中，直到数组a中所有元素读完为止。
采用头插法建表的算法如下。
本算法的时间复杂度为O（n）。
若数组a包含4个元素1、2、3和4，则调用CreateListF（L，a，4）建立的单链表如图2.23所示，从中看到，单链表L中数据结点的次序与数组a的元素次序正好相反。
图2.23 一个单链表L
2）尾插法建表
该方法从一个空单链表（含头结点L，L—>next不必置为NULL）开始，读取数组a（含有n个元素）中的一个元素，生成一个新结点s，将读取的数据元素存放到该结点的数据域中，然后将其链接到单链表L的表尾，如图2.24所示。由于尾插法建表每次将新结点链接到表尾，而单链表L中并没有保存尾结点的地址信息，为此增加一个尾指针tc，使其始终指向当前单链表的尾结点，初始时只有一个头结点L，则置tc=L，这样将新结点s链接到表尾的操作是：tc—>next=s，此时结点s变成新的尾结点，所以还需要置tc=s。
图2.24 尾插法建立单链表
再读取数组a的下一个元素，采用相同的操作建立新结点s并插入到单链表L中，直到数组a中所有元素读完为止。与头插法不同，尾插法最后还需要将尾结点的next域置为空，即tc—>next=NULL。
采用尾插法建表的算法如下。
本算法的时间复杂度为O（n）。
若数组a包含4个元素1、2、3和4，则调用CreateListR（L，a，4）建立的单链表如图2.25所示，从中看到，单链表L中数据结点的次序与数组a的元素次序相同。
图2.25 一个单链表L
提示：将单链表的两个整体建表函数也存放在SLinkNode.cpp文件中。
2.3.3 单链表的算法设计示例
1．基于单链表基本操作的算法设计
这类算法设计中包括单链表结点的查找、插入和删除等。
【例2.11】设计一个算法，通过一趟扫描确定单链表L（至少含两个数据结点）中第一个元素值最大的结点。
解：用p扫描单链表，在扫描时用maxp指向data域值最大的结点（maxp的初值为p）。当单链表扫描完毕，最后返回maxp。对应的算法如下。
本算法的时间复杂度为O（n），其中，n为单链表L中数据结点的个数。
【例2.12】设计一个算法，通过一趟扫描求单链表L（至少含两个数据结点）中第一个值最大结点的前驱结点，若存在这样的结点，返回其指针（地址），否则返回NULL。
解：以p扫描单链表，pre指向p结点的前驱结点，在扫描时用maxp指向data域值最大的结点（maxp的初值为p），maxpre指向maxp结点的前驱结点（maxpre的初值为pre）。当单链表扫描完毕，最后返回maxpre。对应的算法如下。
本算法的时间复杂度为O（n），其中，n为单链表L中数据结点的个数。
【例2.13】设计一个算法，删除一个单链表L（至少含两个数据结点）中第一个值最大的结点。
解：在单链表中删除一个结点先要找到它的前驱结点。以p扫描单链表，pre指向p结点的前驱结点，在扫描时用maxp指向data域值最大的结点，maxpre指向maxp结点的前驱结点。当单链表扫描完毕，通过maxpre结点删除其后的结点，即删除了元素值最大的结点。对应的算法如下。
本算法的时间复杂度为O（n）。
2．基于整体建表的算法设计
这类算法设计中需要根据条件产生新的结果单链表，而创建结果单链表的方法有头插法和尾插法。
【例2.14】设计一个算法，将一个单链表L（至少含两个数据结点）中所有结点逆置。并分析算法的时间复杂度。
解：先将单链表L拆分成两部分，一部分是只有头结点L的空表（结果单链表），另一部分是由p指向首结点的单链表。然后扫描p，将p所指结点逐一采用头插法插入到L单链表中，由于头插法的特点是建成的单链表结点次序与插入次序正好相反，从而达到结点逆置的目的。对应的算法如下。
本算法正好扫描了L中所有数据结点一次，所以时间复杂度为O（n），其中，n为单链表L中的数据结点个数。
【例2.15】假设有一个单链表L，其中元素为整数且所有元素值均不相同。设计一个尽可能高效的算法将所有奇数移到所有偶数的前面。
解：先将单链表L拆分成两部分，一部分是只有头结点L的空表（结果单链表），另一部分是由p指向首结点的单链表。然后扫描p，将奇数结点p采用头插法插入到L的开头，将偶数结点p采用尾插法插入到L的末尾。为此设置一个尾结点指针tc，初始时tc指向头结点，每次插入一个偶数结点时会移动tc，但插入一个奇数结点时不会移动tc，这会导致插入一个奇数结点后再插入一个偶数结点出现错误，所以在第一个插入的结点为奇数结点p时，除了头插法插入结点p，还需要置tc=p（若此时后面插入连续若干奇数结点，tc指向的仍然是正确的尾结点）。对应的算法如下。
本算法正好扫描了单链表中每个结点一次，所以时间复杂度为O（n），算法中只定义了固定几个临时变量，所以算法的空间复杂度为O（1）。
3．有序单链表的二路归并算法
有序单链表是有序表的单链表存储结构，同样可以利用有序表元素的有序性提高相关算法的效率。当数据采用单链表存储时，对应的二路归并就是单链表二路归并算法。
【例2.16】设ha和hb分别是两个带头结点的递增有序单链表。设计一个算法，将这两个有序链表的所有数据结点合并成一个递增有序的单链表hc，并分析算法的时间和空间复杂度。要求hc单链表仍使用原来两个链表的存储空间，不另外占用其他的存储空间，ha和hb两个表中允许有重复的数据结点。
解：采用二路归并的思路，用pa扫描ha的数据结点，pb扫描hb的数据结点，将ha头结点用作新单链表hc的头结点，让tc始终指向hc的尾结点（初始时指向hc）。当pa和pb均不为空时循环：比较pa与pb的data值，将较小者链接到单链表hc的末尾。如此重复直到ha或hb为空，再将余下的链表结点链接到单链表hc的末尾。对应的算法如下。
设两个有序单链表中数据结点个数分别为m和n，算法中仅对两个单链表中所有结点扫描一遍，所以算法的时间复杂度为O（m+n）。算法中仅定义固定个数的临时变量，所以算法的空间复杂度为O（1）。
注意：本例是由ha和hb创建hc，而hc没有另外分配存储空间，而是利用ha和hb的所有结点重新链接产生hc的，所以算法的空间复杂度为O（1），但当hc建成后，ha和hb被破坏了，即调用本算法后，ha和hb不再存在。
【例2.17】设ha和hb分别是两个带头结点的递增有序单链表。设计一个算法，由表ha和表hb的所有公共结点（两单链表中data值相同的结点）产生一个递增有序单链表hc，分析算法的时间和空间复杂度。要求不破坏原来两个链表ha和hb的存储空间。
解：本算法仍采用二路归并的思路，用pa、pb分别扫描单链表ha、hb，只不过仅仅将公共的结点复制并链接到单链表hc的末尾，结果单链表hc采用尾插法创建。对应的算法如下。
设两个有序单链表中数据结点个数分别为m和n，算法中最多仅对两个单链表中所有结点扫描一遍，所以算法的时间复杂度为O（m+n）。设ha和hb中公共结点个数为k，算法中新建了k+1结点（含hc的头结点），k最大值为min（m，n），所以算法的空间复杂度为O（min（m，n））。
注意：本例是由ha和hb创建hc，示例要求不破坏ha和hb，这样必须采用结点复制的方法，所以算法的空间复杂度不再为O（1）。
4．单链表的排序算法
在很多情况下，单链表中结点有序时可以提高相应算法的效率。这里通过一个示例讨论单链表的递减排序过程。
【例2.18】设计一个完整的程序，根据用户输入的学生人数n（n≥3）及每个学生姓名和成绩建立一个单链表，并按学生成绩递减排序，然后按名次输出所有学生的姓名和成绩。
解：（1）设计存储结构。
依题意，声明学生单链表结点类型为StudList：
例如，有4个学生记录，其姓名和成绩分别为：（Mary，75），（John，90），（Smith，85），（Harry，95），其构建的带头结点的单链表如图2.26所示。
图2.26 学生单链表
（2）设计基本运算算法。
设计基本运算算法如下。
①void CreateStudent（StudList∗&sl）：采用交互式方式创建学生单链表。
②void DestroyList（StudList∗&L）：销毁学生单链表。
③void DispList（StudList∗L）：输出学生单链表。
④void SortList（StudList∗&L）：将学生单链表按成绩递减排序。
采用尾插法创建学生单链表的算法如下。
销毁学生单链表的算法如下。
输出学生单链表的算法如下。
对学生单链表按成绩递减排序是一个比较复杂的过程，先将该单链表拆分成两部分，如图2.27所示，一部分是只有一个数据结点的有序单链表，另一部分是余下的数据结点，由p所指向。
图2.27 该单链表拆分成两部分
然后将p结点通过比较插入到有序单链表中，在插入时要找插入的前驱结点pre，pre开始时指向头结点，通过pre—>next—>score与p—>score比较，当前者大于后者时，pre向后移一个结点，如此直到pre—>next为NULL或者pre—>next—>score <p—>score成立，最后将p结点插入到pre结点之后，如图2.28所示是插入Smith结点的情况。
图2.28 将p结点插入到有序表中
学生单链表按成绩递减排序的算法如下。
（3）设计主函数。
最后设计如下主函数。
（4）执行结果。
本程序的一次执行结果如下（下画线部分表示用户输入，↙表示Enter键）。
2.3.4 循环单链表
循环单链表是由单链表改造而来的，将单链表中尾结点的next域由原来为NULL改为指向头结点，这样整个链表形成一个环。循环单链表的特点是从任一结点出发都可以找到表中其他结点。
循环单链表的结点类型与单链表的结点类型相同，也采用前面声明的SLinkNode类型。如图2.29所示是一个带头结点的有n个数据结点的循环单链表L。
图2.29 带头结点的循环单链表
从图中看出，在循环单链表L中，p所指结点为尾结点的条件是p—>next==L。
循环单链表的整体建表算法也分为头插法建表和尾插法建表，和单链表的相似，只需在建立后将尾结点next域指向头结点即可，这里不再介绍。
在循环单链表中线性表基本运算算法的实现如下。
1．初始化线性表运算算法
创建一个空的循环单链表，它只有头结点，由L指向它。该结点的next域指向该头结点，data域未设定任何值，如图2.30所示。对应的算法如下。
图2.30 一个空的循环单链表
本算法的时间复杂度为O（1）。
2．销毁线性表运算算法
一个循环单链表L中的所有结点空间都是通过malloc函数分配的，在不再需要时需通过free函数释放所有结点的空间。其实现过程是，先让pre指向头结点，p指向首结点，当p不为头结点时循环：释放pre所指结点空间，让pre、p指针沿next域同步后移一个结点。当循环结束，p指向头结点，此时再释放pre所指的尾结点。对应的算法如下。
本算法的时间复杂度为O（n），其中，n为单链表L中数据结点的个数。
3．求线性表的长度运算算法
设置一个整型变量i作为计数器，i初值为0，p初始时指向第一个结点。然后沿next域逐个往后移动，每移动一次，i值增1。当p所指结点为头结点时这一过程结束，i的值即为表长。对应的算法如下。
本算法的时间复杂度为O（n），其中，n为循环单链表L中数据结点的个数。
4．求线性表中第i个元素运算算法
用p从头开始扫描循环单链表L中的结点（初值指向首结点），用计数器j累计扫描过的结点，其初值为1。当p不为L且j＜i时循环，p后移一个结点，j增1。当循环结束时，若p指向头结点时表示查找失败返回0，否则p所指结点即为要找的结点，查找成功，算法返回1。对应的算法如下。
本算法的时间复杂度为O（n），其中，n为循环单链表L中数据结点的个数。
5．按值查找运算算法
用i累计查找数据结点的个数，从首结点开始，由前往后依次比较单链表中各结点数据域的值，若某结点数据域的值等于给定值x，则返回i；否则继续向后比较。若整个单链表中没有这样的结点，则返回0。对应的算法如下。
本算法的时间复杂度为O（n），其中，n为循环单链表L中数据结点的个数。
6．插入元素运算算法
在循环单链表L中查找第i个结点p及其前驱结点pre，若没有这样的结点p返回0；否则创建一个以x为值的新结点s，将结点s插在pre结点之后，如图2.31所示，返回1。
图2.31 在循环单链表中插入结点s
对应的算法如下。
本算法的时间复杂度为O（n），其中，n为循环单链表中数据结点的个数。
说明：在循环单链表中，用p指针扫描所有结点时，方式有两种：一是以p!=L作为循环条件，当p==L时循环结束，此时p回过来指向头结点，所以p应该初始化指向首结点而不是头结点，否则循环内的语句不会执行。二是扫描指针p的初始化为p=L，循环的条件应该为p—>next!=L，当p—>next==L时循环结束，此时p指向尾结点。上述插入元素运算算法中采用前一种方式查找第i—1个结点，后面删除元素运算算法中采用后一种方式查找第i个结点。
7．删除元素运算算法
在循环单链表L中查找第i—1个结点，若不存在这样的结点返回0；否则让p指向第i—1个结点，q指向后继结点，当q为NULL时返回0，否则将q所指结点删除并释放其空间，返回1。对应的算法如下。
本算法的时间复杂度为O（n），其中，n为循环单链表L中数据结点的个数。
8．输出线性表运算算法
从首结点开始，沿next域逐个往下扫描，输出每个扫描到结点的data域，直到头结点为止。对应的算法如下。
本算法的时间复杂度为O（n），其中，n为循环单链表L中数据结点的个数。
说明：将循环单链表结点类型声明及其基本运算函数存放在CSLinkNode.cpp文件中。
从以上看到，单链表与循环单链表的结点类型完全相同，实现基本运算的算法也很相似。实际上，循环链表和对应的非循环链表的运算基本一致，差别仅在于算法中的循环条件不是判断p或p—>next是否为空，而是判断它们是否等于头结点的指针。
当循环单链表的基本运算设计好后，给出主函数调用这些基本运算函数，读者可以对照程序执行结果进行分析，进一步体会循环单链表各种操作的实现过程。
上述程序的执行结果如图2.9所示。
2.3.5 循环单链表的算法设计示例
【例2.19】设计一个算法求一个循环单链表L中所有值为x的结点个数。
解：用指针p扫描循环单链表L的所有结点，用i（初值为0）累加值为x的结点个数，最后返回i。对应的算法如下。
【例2.20】有一个递增有序的循环单链表L，设计一个算法删除其中所有值为x的结点，并分析算法的时间复杂度。
解：由于循环单链表L是递增有序的，则所有值为x的结点必然是相邻的。先找到第一个值为x的结点p，让pre指向其前驱结点。然后通过pre结点删除p结点及其后面连续值为x的结点。对应的算法如下。
本算法的时间复杂度为O（n），其中，n为循环单链表L中数据结点的个数。
【例2.21】编写一个程序求解约瑟夫（Joseph）问题。有n个小孩围成一圈，给他们从1开始依次编号，从编号为1的小孩开始报数，数到第m个小孩出列，然后从出列的下一个小孩重新开始报数，数到第m个小孩又出列，……，如此反复直到所有的小孩全部出列为止，求整个出列序列。如当n=6，m=5时的出列序列是5，4，6，2，3，1。
解：（1）设计存储结构。
本题采用循环单链表存放小孩圈，其结点类型如下。
依本题操作，小孩圈构成一个循环单链表，例如，n=6时的初始循环单链表如图2.32所示，L指向开始报数的小孩结点。
图2.32 n=6时的初始循环单链表
注意：前面介绍的循环单链表都是带头结点，而这里的循环单链表是不带头结点，因为本题中循环单链表带头结点会导致循环查找数据结点更复杂，为此在算法设计中需要针对不带头结点的情况做相应的修改。
（2）设计基本运算算法。
设计两个基本运算算法。由指定的n采用尾插法创建不带头结点的小孩圈循环单链表L的算法如下。
由指定的n和m输出约瑟夫序列的算法如下。
（3）设计主函数。
设计如下主函数求解n=6，m=5的约瑟夫序列。
void main()
{ int n=6,m=5;
printf(＂n=%d,m=%d的约瑟夫序列：＂,n,m);
Joseph(n,m);printf(＂\n＂);
}
（4）执行结果。
本程序的执行结果如下。
n=6,m=5的约瑟夫序列：5 4 6 2 3 1