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

,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,单击此处编辑母版标题样式,1,循 环 链 表,2,循环链表,例：猴子选大王。n只猴子围成一圈，顺时针方向从1到n编号。之后从1号开始沿顺时针方向让猴子从1，2，m依次报数，凡报到m的猴子，都让其出圈，取消候选资格。然后不停地按顺时针方向逐一让报出m者出圈，最后剩下一个就是猴王。,3,起始位置,猴 王,1,2,3,4,5,6,7,8,3,6,1,5,2,8,4,猴子被淘汰的顺序,演示：n=8,m=3,4,说明：,如图1所示有8只猴子围成一圈，m=3。从1#猴的位置开始，顺时针1至3报数，第一个出圈的是3#；第二个出圈的是6#，第3个出圈的是1#；第4个出圈的是5#；第5个是2#，第6个是8#；第7个是4#。最后剩下一个是7#，它就是猴王。,我们用,循环链表,来模拟这个选择过程。,5,1、定义一个名为mon的结构struct monint num;/整数，表示猴子的编号struct mon*next;/指针，指向相邻的下一只猴子,2、将链表的头指针head定义为全局变量。struct mon*head;,3、主函数用键盘输入猴子数n，输入数m，调用函数create建立一个循环链表，模拟众猴围成一圈的情况。该函数的实参为n。调用函数select，模拟1至m报数，让n-1只猴子逐一出列的过程。即在具有n个结点的循环链表按报数m删除结点的过程。该函数的实参为m，最后输出猴王的编号。,6,4、建立循环链表的函数create(int nn)其中nn为形式参数。要从编号1到编号nn。,思路是,（1）先做第1个结点，让其中的数据域p-num赋值为1，让指针域赋值为null。之后让链头指针head指向第1个结点。利用指针q记住这个结点，以便让指针p去生成下面的结点。,（2）利用一个计数循环结构，做出第2个结点到第nn个结点。并将相邻结点一个接一个链接到一起。,（3）最后一个结点要和头结点用下一语句链接到一起,tail=q;tail-next=head;,head,tail,q,7,5、删结点的函数select(int mm)mm为形式参数，从1至m报数，凡报到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);,1,head,2,8,tail,q,p,演示,8,这里free(p)是释放p结点所占用的内存空间的语句。如果mm不是1而是3，程序会在do-while循环中，让x加两次1，q和p一起移动两次，p指向3#所在结点，q指向2#所在结点，之后仍然用上述三条语句删去3#所在的结点。,1,head,2,8,q,p,3,4,q,p,p,q,演示,9,这个do-while循环的退出条件是q=q-next。即当只剩下一个结点时才退出循环。当然猴王非其莫属了。这时，让头指针head指向q，head是全局变量，在主程序最后输出猴王时要用head-num。,参考程序如下：,7,head,q,10,#include/预编译命令,#include/内存空间分配,#define null 0/定义空指针常量,/定义常量，表示结构长度,#define LEN sizeof(struct mon),struct mon/结构声明,int num;/整型数，用于记录猴子号,struct mon*next;/mon结构指针,;,struct mon*head,*tail;/mon结构指针，全局变量,11,void create(int nn)/被调用函数,/函数体开始,int i;/整型变量i，用于计数,struct mon*p,*q;/声明mon结构指针p，q,/为p分配内存空间p=(struct mon*)malloc(LEN);,p-num=1;/初始化p结点num域为1,p-next=null;/初始化p结点next域为空,head=p;/链表头指针head赋值为p,q=p;/q赋值为p,12,for(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表示结点删除间隔,void select(int mm),/函数体开始,int x=0;,/声明整型值x，并初始化为0,struct mon*p,*q;,/声明结构指针p，q,q=tail;,/q赋值为tail，指向循环链表尾部,do,/直到型循环，用于循环删除指定间隔的结点,/循环体开始,p=q-next;,/p赋值为q相邻的下一个结点,x=x+1;,/x加1,if(x%mm=0),/x是否整除mm，,/表示是否跳过指定间隔,/输出被删掉的猴子号,printf(被删掉的猴子号为%d号n,p-num);,q-next=p-next;,/删除此结点,free(p);,/释放空间,else q=p;,/q指向相邻的下一个结点p,while(q!=q-next);,/剩余结点数不为1，则继续循环,head=q;,/head指向结点q，q为链表中剩余一个结点,/函数体结束,14,void main()/主函数开始,/函数体开始,int n,m;/声明整型变量n,m,head=null;/初始化head为空,printf(请输入猴子数n);/提示信息,scanf(%d,/输入待插入结点数据,printf(请输入间隔mn);/提示信息,scanf(%d,/输入间隔,create(n);/调用函数create建立循环链表,select(m);/调用函数select，找出剩下的猴子,printf(猴王是%d号n,head-num);/输出猴王,/函数体结束,