资源描述：
《Joseph ring实习报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、约瑟夫环问题模拟一、需求分析1、本演示程序模拟约瑟夫环问题：编号为1，2，……，n得n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。2、演示程序以用户和计算机对话的方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中需要的相关信息及命令。运算结果显示在其后。3、程序需要输入的信息与命令
2、包括：1）初始人数n；2）n个人的密码；3）初始的m值；4、测试数据1）n：7密码：3、1、7、2、4、8、4m：62）n：1密码：4m：33）n：4密码：4、2、3、1m：124）n：3密码：1、2、3m：2二、概要设计为了实现上述程序功能，应以单向循环链表模拟问题过程。每个结点代表一个玩家。1、有序表抽象数据类型定义：ADTlist{数据对象：D={ai
3、ai∈LNode,i=1,2,……,n,n>=0}数据关系：R={
4、ai-1,ai∈D,i=2,……,n}基本操作：Init(&L)操作结果：构造一个空的单
5、向循环链表。Insert(&L,n,s)初始条件：链表L已存在，玩家编号n，玩家密码s。操作结果：插入一个玩家结点。Del(&L,m,e)初始条件：链表L已存在，m值有效。操作结果：删除链表中第m个结点，并有e返回这个结点。}ADTlist2、本程序包含两个模块：a)主程序模块：intmain(){初始化;接受命令;处理命令;退出;return0;}a)循环单向链表单元模块——实现单向循环链表抽象数据类型；模块之间的调用关系如下：主程序模块↓单向循环链表单元模块一、详细设计intmain(){//主函数main的实现intn,m,
6、s,i;Listl;if(Init(l)){//初始化链表，执行成功后接受命令printf("howmanyplayers?:");scanf("%d",&n);for(i=1;i<=n;i++){printf("thepasswordofthenumber%dplayer:",i);scanf("%d",&s);if(!Insert(l,i,s)){printf("ERROR!");exit(1);}}//forprintf("Inputthevalueofm:");scanf("%d",&m);Lnodee;for(i=n;i
7、>=1;i--){//处理命令，模拟人员的退出——结点的删除if(Del(l,m,e)){printf("thenumber%dplayercomeout",e.intNum);m=(m-1+e.intSec)%(i-1);if(m==0)m=i-1;}}//for}//ifelseprintf("ERROR!");return0;}typedefstructLnode{//链表结点类型定义intintNum;intintSec;structLnode*next;}Lnode,*Linklist;typedefstruct{/
8、/循环单向链表类型定义Linklisthead;Linklisttail;}List;boolInit(List&l){//链表初始化l.head=l.tail=NULL;returntrue;}boolInsert(List&l,intN,intS){//在链表末尾插入玩家号为N，玩家密码为S的结点Linklistp=(Linklist)malloc(sizeof(Lnode));if(!p)returnfalse;p->intNum=N;p->intSec=S;if(!l.head){l.head=p;}else{l.tail
9、->next=p;}p->next=l.head;l.tail=p;returntrue;}boolDel(List&l,intm,Lnode&e){//删除链表中第m个结点，并用e返回Linklistp=l.tail;if(!p
10、
11、m<1)returnfalse;intcnt=1;while(cntnext;cnt++;}if(l.head==l.tail){p->next=NULL;e=*p;free(p);returntrue;}Linklistq=p->next;if(q==l.tail)l.tail=p
12、;if(m==1)l.head=q->next;p->next=q->next;q->next=NULL;e=*q;free(q);returntrue;}一、调试分析1、由于程序时模拟约瑟夫环过程的，只是单纯的对问题的抽象解决，在数据范围不是很大
