约瑟夫循环实验报告.doc

《约瑟夫循环实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验名称：约瑟夫环问题实验类型：综合性实验班级：学号：姓名：李晓彬实验日期：2012.04.282.问题描述设有编号为1,2,…,n的n（n＞0）个人围成一个圈，每个人持有一个密码m。从第一个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。3.数据结构设计设计实现约瑟夫环问题的存储结构。由于约瑟夫环问题本身具有循环性质，考虑采用循环链表，为了统一对表中任意结点的操作，循环链表不带头

2、结点。将循环链表的结点定义为如下结构类型：structNode{intdata;Node*next;};4.算法设计一个主函数，两个功能函数。Step1:定义数据结构类型Step2:建立功能函数NODE*createlink(intn)完成建立循环链表的功能。for(i=2;i<=n;i++){q=(structnode*)malloc(sizeof(structnode));if(q==0)return0;p->next=q;p=q;p->data=i;}Step3:功能函数voidjose(NODE*p,intn,i

3、ntm)完成报数m出圈的功能。for(i=1;i<=n;i++){for(j=1;jnext;}q=p->next;p->next=q->next;if(k%6==0){k++;printf("");}elsek++;printf("%3d:%3dout",i,q->data-1);free(q);}Step4:主函数完成本实验的主体功能即得到出圈次序，并打印。NODE*head=NULL;head=createlink(n);jose(head,n,m);5.抽象数据类型的设计NODE*h

4、ead，*p，*qintm,n,MAX_NODE_NUM,I,k6.界面设计欢迎使用约瑟夫环问题程序1．请输入人数n（最多1000个）;2．初始密码m:3．结果7.运行、测试与分析（1）运行程序，显示菜单 :(2)输入n：(3)输入m：（4）结果：8.实验收获及思考对单链表的知识掌握的更加透彻，而且自己一步一步编写程序有一点点的成就感。编写程序的过程中界面的友好程度是一个很重要的指标，下次要努力编写一个界面友好的程序。附录源代码：#include#includetypedefstru

5、ctnode{intdata;structnode*next;}NODE;/*定义节点*/NODE*createlink(intn){NODE*head=NULL,*p=NULL,*q=NULL;inti=1;head=p=(structnode*)malloc(sizeof(structnode));p->data=i;for(i=2;i<=n;i++){q=(structnode*)malloc(sizeof(structnode));if(q==0)return0;//分配失败p->next=q;p=q;//创建新

6、的节点p->data=i;//为每个人分配序号}p->next=head;//循环returnhead;//返回要用的首地址}/*创建循环链表*/voidjose(NODE*p,intn,intm){inti,j,k=0;NODE*q=NULL;for(i=1;i<=n;i++){for(j=1;jnext;}/*访问到每轮的第m-1个*/q=p->next;/*q是第m个*/p->next=q->next;/*p直接指向第m+1个*/if(k%6==0){k++;printf("");}e

7、lsek++;/*让出圈的数字一行显示六个*/printf("%3d:%3dout",i,q->data-1);/*输出出圈的次序和要出圈的值*/free(q);/*释放节点*/}printf("");p->next=NULL;//一直到下一个为空即要出圈已经出的了}/*约瑟夫环*/intmain(){intm,n,MAX_NODE_NUM=1000;while(1){printf("欢迎使用约瑟夫环问题程序");printf("1.请输入人数n（最多%d个）:",MAX_NODE_NUM);scanf("%d"

8、,&n);printf("2.初始密码m:");scanf("%d",&m);printf("3.结果");if(n>MAX_NODE_NUM){printf("人数太多，请重新输入！");continue;}elsebreak;}NODE*head=NULL;head=createlink(n);//得到循环链