循环链表实例(猴子选大王)

1、1循循 环环 链链 表表2循环链表循环链表例：猴子选大王。例：猴子选大王。n只猴子围成一圈，顺时针方向从只猴子围成一圈，顺时针方向从1到到n编号。编号。之后从之后从1号开始沿顺时针方向让猴子从号开始沿顺时针方向让猴子从1，2，m依次报数，凡报到依次报数，凡报到m的猴子，都让的猴子，都让其出圈，取消候选资格。然后不停地按顺时其出圈，取消候选资格。然后不停地按顺时针方向逐一让报出针方向逐一让报出m者出圈，最后剩下一个者出圈，最后剩下一个就是猴王。就是猴王。3 起始位置起始位置猴猴 王王123456783615284猴子被淘汰的顺序猴子被淘汰的顺序演示：演示：n=8, m=34说明：说明：如图如图1

2、所示有所示有8只猴子围成一圈，只猴子围成一圈，m=3。从。从1#猴的位置开始，顺时针猴的位置开始，顺时针1至至3报数，第一个出报数，第一个出圈的是圈的是3#；第二个出圈的是；第二个出圈的是6#，第，第3个出圈个出圈的是的是1#；第；第4个出圈的是个出圈的是5#；第；第5个是个是2#，第，第6个是个是8#；第；第7个是个是4#。最后剩下一个是。最后剩下一个是7#，它就是猴王。它就是猴王。我们用我们用循环链表循环链表来模拟这个选择过程。来模拟这个选择过程。51 1、定义一个名为、定义一个名为monmon的结构的结构struct monstruct mon intint num; num;/ / 整

3、数，表示猴子的编号整数，表示猴子的编号struct monstruct mon * *next;next;/ / 指针，指向相邻的下一指针，指向相邻的下一只猴子只猴子 2 2、将链表的头指针、将链表的头指针headhead定义为全局变量。定义为全局变量。struct monstruct mon* *head;head;3 3、主函数、主函数用键盘输入猴子数用键盘输入猴子数n n，输入数，输入数m m，调用函数，调用函数createcreate建立一个建立一个循环链表，模拟众猴围成一圈的情况。该函数的实参为循环链表，模拟众猴围成一圈的情况。该函数的实参为n n。调用函数调用函数selectsel

4、ect，模拟，模拟1 1至至m m报数，让报数，让n-1n-1只猴子逐一出列只猴子逐一出列的过程。即在具有的过程。即在具有n n个结点的循环链表按报数个结点的循环链表按报数m m删除结点的删除结点的过程。该函数的实参为过程。该函数的实参为m m，最后输出猴王的编号。，最后输出猴王的编号。64、建立循环链表的函数、建立循环链表的函数create(int nn)其中其中nn为形式参数。要从编号为形式参数。要从编号1到编号到编号nn。思路是思路是（1）先做第）先做第1个结点，让其中的数据域个结点，让其中的数据域p-num赋值为赋值为1，让，让指针域赋值为指针域赋值为null。之后让链头指针。之后让链

5、头指针head指向第指向第1个结点。个结点。利用指针利用指针q记住这个结点，以便让指针记住这个结点，以便让指针p去生成下面的结去生成下面的结点。点。（2）利用一个计数循环结构，做出第）利用一个计数循环结构，做出第2个结点到第个结点到第nn个结点。个结点。并将相邻结点一个接一个链接到一起。并将相邻结点一个接一个链接到一起。（3）最后一个结点要和头结点用下一语句链接到一起）最后一个结点要和头结点用下一语句链接到一起tail = q; tail-next = head;headtailq75、删结点的函数、删结点的函数select(int mm)mm为形式参数，从为形式参数，从1至至m报数，凡报到报

6、数，凡报到mm者删除其者删除其所在的结点。所在的结点。设计两个指针设计两个指针p和和q。一开始让。一开始让q指向链表的尾部指向链表的尾部q=tail。让让p指向指向q的下一个结点。开始时让的下一个结点。开始时让p指向指向1#猴所在的结点。猴所在的结点。用一个累加器用一个累加器x，初始时，初始时x=0，从，从1#猴所在结点开始让猴所在结点开始让x=x+1=1，如果，如果mm是是1的话，的话，1#猴所在的猴所在的p结点就要被删结点就要被删除。有三条语句除。有三条语句printf(“被删掉的猴子号为被删掉的猴子号为%d号号n”,p-num);q-next = p-next;free(p);1head

7、28tailqp演示演示8这里这里free(p)是释放是释放p结点所占用的内存空间的语句。结点所占用的内存空间的语句。如果如果mm不是不是1而是而是3，程序会在，程序会在do-while循环中，循环中，让让x加两次加两次1，q和和p一起移动两次，一起移动两次，p指向指向3#所在结所在结点，点，q指向指向2#所在结点，之后仍然用上述三条语句所在结点，之后仍然用上述三条语句删去删去3#所在的结点。所在的结点。1head28qp34q ppq演示演示9这个这个do-while循环的退出条件是循环的退出条件是q=q-next。即当只。即当只剩下一个结点时才退出循环。当然猴王非其莫属了。剩下一个结点时才

8、退出循环。当然猴王非其莫属了。这时，让头指针这时，让头指针head指向指向q，head是全局变量，在是全局变量，在主程序最后输出猴王时要用主程序最后输出猴王时要用head-num。参考程序如下：参考程序如下：7headq10#include / 预编译命令预编译命令#include / 内存空间分配内存空间分配#define null 0/ 定义空指针常量定义空指针常量/ 定义常量，表示结构长度定义常量，表示结构长度#define LEN sizeof(struct mon)struct mon/ 结构声明结构声明int num;/ 整型数，用于记录猴子号整型数，用于记录猴子号struct m

9、on *next;/ mon结构指针结构指针;struct mon *head, *tail;/ mon结构指针，全局变量结构指针，全局变量11void create(int nn)/ 被调用函数被调用函数/ 函数体开始函数体开始 int i;/ 整型变量整型变量i，用于计数，用于计数struct mon *p,*q;/ 声明声明mon结构指针结构指针p，q/ 为为p分配内存空间分配内存空间p=(struct mon *) malloc(LEN);p-num=1;/ 初始化初始化p结点结点num域为域为1p-next=null;/ 初始化初始化p结点结点next域为空域为空head=p;/ 链

10、表头指针链表头指针head赋值为赋值为pq=p;/ q赋值为赋值为p12for(i=2;inum=i; / 初始化初始化p结点结点num域为域为i，表示猴子号，表示猴子号q-next=p;/ 将将p结点加到链表尾部结点加到链表尾部q=p;/ 让让q指向链表尾部结点指向链表尾部结点p-next=null;/ 链表尾部指向空链表尾部指向空/ 循环体结束循环体结束tail = q;/ 链表尾链表尾tail-next=head;/ 链表尾部指向链表头，链表尾部指向链表头，/ 形成循环链表形成循环链表/ 函数体结束函数体结束13/ 被调用函数被调用函数select，mm表示结点删除间隔表示结点删除间隔v

11、oid select(int mm)/ 函数体开始函数体开始int x=0;/ 声明整型值声明整型值x，并初始化为，并初始化为0struct mon *p,*q;/ 声明结构指针声明结构指针p，qq=tail;/ q赋值为赋值为tail，指向循环链表尾部，指向循环链表尾部 do/ 直到型循环，用于循环删除指定间隔的结点直到型循环，用于循环删除指定间隔的结点/ 循环体开始循环体开始p=q-next;/ p赋值为赋值为q相邻的下一个结点相邻的下一个结点x=x+1;/ x加加1if(x % mm=0)/ x是否整除是否整除mm，/ 表示是否跳过指定间隔表示是否跳过指定间隔/ 输出被删掉的猴子号输出被

12、删掉的猴子号printf(被删掉的猴子号为被删掉的猴子号为%d号号n,p-num);q-next=p-next;/ 删除此结点删除此结点free(p);/ 释放空间释放空间else q=p;/ q指向相邻的下一个结点指向相邻的下一个结点pwhile(q!=q-next);/ 剩余结点数不为剩余结点数不为1，则继续循环，则继续循环head = q;/ head指向结点指向结点q，q为链表中剩余一个结点为链表中剩余一个结点/ 函数体结束函数体结束14void main()/ 主函数开始主函数开始/ 函数体开始函数体开始int n,m;/ 声明整型变量声明整型变量n,mhead = null;/ 初始化初始化head为空为空printf(请输入猴子数请输入猴子数n); / 提示信息提示信息scanf(%d,&n);/ 输入待插入结点数据输入待插入结点数