约瑟夫循环实验报告

实验名称：约瑟夫环问题实验类型：综合性实验班级：20102111学号：2010211102姓名：李晓彬实验日期：2012.04.282.问题描述设有编号为1,2,…,n的n（n＞0）个人围成一个圈，每个人持有一个密码m。从第一个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。3.数据结构设计设计实现约瑟夫环问题的存储结构。由于约瑟夫环问题本身具有循环性质，考虑采用循环链表，为了统一对表中任意结点的操作，循环链表不带头结点。将循环链表的结点定义为如下结构类型：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,intm)完成报数m出圈的功能。for(i=1;i=n;i++){for(j=1;jm;j++){p=p-next;}q=p-next;p-next=q-next;if(k%6==0){k++;printf(\n);}elsek++;printf(%3d:%3dout,i,q-data-1);free(q);}Step4:主函数完成本实验的主体功能即得到出圈次序，并打印。NODE*head=NULL;head=createlink(n);jose(head,n,m);5.抽象数据类型的设计NODE*head，*p，*qintm,n,MAX_NODE_NUM,I,k6.界面设计欢迎使用约瑟夫环问题程序1．请输入人数n（最多1000个）;2．初始密码m:3．结果7.运行、测试与分析（1）运行程序，显示菜单:(2)输入n：(3)输入m：（4）结果：8.实验收获及思考对单链表的知识掌握的更加透彻，而且自己一步一步编写程序有一点点的成就感。编写程序的过程中界面的友好程度是一个很重要的指标，下次要努力编写一个界面友好的程序。附录源代码：#includestdio.h#includestdlib.htypedefstructnode{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;//创建新的节点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;jm;j++){p=p-next;}/*访问到每轮的第m-1个*/q=p-next;/*q是第m个*/p-next=q-next;/*p直接指向第m+1个*/if(k%6==0){k++;printf(\n);}elsek++;/*让出圈的数字一行显示六个*/printf(%3d:%3dout,i,q-data-1);/*输出出圈的次序和要出圈的值*/free(q);/*释放节点*/}printf(\n);p-next=NULL;//一直到下一个为空即要出圈已经出的了}/*约瑟夫环*/intmain(){intm,n,MAX_NODE_NUM=1000;while(1){printf(欢迎使用约瑟夫环问题程序\n);printf(1.请输入人数n（最多%d个）:,MAX_NODE_NUM);scanf(%d,&n);printf(2.初始密码m:);scanf(%d,&m);printf(3.结果);if(nMAX_NODE_NUM){printf(人数太多，请重新输入！\n);continue;}elsebreak;}NODE*head=NULL;head=createlink(n);//得到循环链表的基地址jose(head,n,m);//得到出圈的次序system(pause);}/*运行程序*/