欢迎来到天天文库
浏览记录
ID:51140828
大小:236.50 KB
页数:14页
时间:2020-03-19
《循环链表实例(猴子选大王).ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、1循环链表2循环链表例:猴子选大王。n只猴子围成一圈,顺时针方向从1到n编号。之后从1号开始沿顺时针方向让猴子从1,2,…,m依次报数,凡报到m的猴子,都让其出圈,取消候选资格。然后不停地按顺时针方向逐一让报出m者出圈,最后剩下一个就是猴王。3起始位置猴王123456783615284猴子被淘汰的顺序演示:n=8,m=34说明:如图1所示有8只猴子围成一圈,m=3。从1#猴的位置开始,顺时针1至3报数,第一个出圈的是3#;第二个出圈的是6#,第3个出圈的是1#;第4个出圈的是5#;第5个是2#,第6个是8#;
2、第7个是4#。最后剩下一个是7#,它就是猴王。我们用循环链表来模拟这个选择过程。51、定义一个名为mon的结构structmon{intnum;//整数,表示猴子的编号structmon*next;//指针,指向相邻的下一只猴子}2、将链表的头指针head定义为全局变量。structmon*head;3、主函数用键盘输入猴子数n,输入数m,调用函数create建立一个循环链表,模拟众猴围成一圈的情况。该函数的实参为n。调用函数select,模拟1至m报数,让n-1只猴子逐一出列的过程。即在具有n个结点的循环
3、链表按报数m删除结点的过程。该函数的实参为m,最后输出猴王的编号。64、建立循环链表的函数create(intnn)其中nn为形式参数。要从编号1到编号nn。思路是(1)先做第1个结点,让其中的数据域p->num赋值为1,让指针域赋值为null。之后让链头指针head指向第1个结点。利用指针q记住这个结点,以便让指针p去生成下面的结点。(2)利用一个计数循环结构,做出第2个结点到第nn个结点。并将相邻结点一个接一个链接到一起。(3)最后一个结点要和头结点用下一语句链接到一起tail=q;tail->next=
4、head;headtailq75、删结点的函数select(intmm)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号”,p->num);q->next=p->next;free(p);1head28tailqp
5、演示8这里free(p)是释放p结点所占用的内存空间的语句。如果mm不是1而是3,程序会在do-while循环中,让x加两次1,q和p一起移动两次,p指向3#所在结点,q指向2#所在结点,之后仍然用上述三条语句删去3#所在的结点。1head28qp34qppq演示9这个do-while循环的退出条件是q==q->next。即当只剩下一个结点时才退出循环。当然猴王非其莫属了。这时,让头指针head指向q,head是全局变量,在主程序最后输出猴王时要用head->num。参考程序如下:7headq10#inclu
6、de//预编译命令#include//内存空间分配#definenull0//定义空指针常量//定义常量,表示结构长度#defineLENsizeof(structmon)structmon//结构声明{intnum;//整型数,用于记录猴子号structmon*next;//mon结构指针};structmon*head,*tail;//mon结构指针,全局变量11voidcreate(intnn)//被调用函数{//函数体开始inti;//整型变量i,用于计数stru
7、ctmon*p,*q;//声明mon结构指针p,q//为p分配内存空间p=(structmon*)malloc(LEN);p->num=1;//初始化p结点num域为1p->next=null;//初始化p结点next域为空head=p;//链表头指针head赋值为pq=p;//q赋值为p12for(i=2;i<=nn;i=i+1)//利用循环结构构造链表{//循环体开始p=(structmon*)malloc(LEN);//为p分配内存空间p->num=i;//初始化p结点num域为i,表示猴子号q->ne
8、xt=p;//将p结点加到链表尾部q=p;//让q指向链表尾部结点p->next=null;//链表尾部指向空}//循环体结束tail=q;//链表尾tail->next=head;//链表尾部指向链表头,//形成循环链表}//函数体结束13//被调用函数select,mm表示结点删除间隔voidselect(intmm){//函数体开始intx=0;//声明整型值x,并初始化为0structmon
此文档下载收益归作者所有