资源描述：
《数据结构实验报告-约瑟夫环》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、数据结构与程序设计实验实验报告课程名称数据结构与程序设计实验课程编号0906550实验项目名称约瑟夫环学号年级2014姓名专业计算机科学与技术学生所在学院计算机学院指导教师杨静实验室名称地点21B276精选范本,供参考！哈尔滨工程大学实验报告一实验课名称：数据结构与程序设计实验实验名称：约瑟夫环班级学号姓名时间2016.04.05一、问题描述设有编号为1,2,…,n的n（n＞0）个人围成一个圈，每个人持有一个密码m。从第一个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，……，如此下去，
2、直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。二、数据结构设计每个人按报数顺序有唯一的前驱与后继关系，并且报数顺序循环，所以采用单向循环链表模拟，链表节点存储序号number和m，存储结构定义如下：typedefstructList{intnumber;//序号intm;//密码mstructList*next;//指向下一个人的指针}List;为了方便查询及删除的定位，表按序号有序存储。三、算法设计1.初始化，构建循环链表，依次存储序号1至n的人,链表指针L指向序号为1的人。List*create_list_wi
3、th_one_m(List*L,intn){List*pre;//previousnodeinti=1;for(;i<=n;i++){List*cur=(List*)malloc(sizeof(List));//currentnodecur->number=i;cur->next=NULL;if(i==1){//只在第一次进入,initL,preL=cur;pre=cur;}else{//链接pre与cur,并向后移动prepre->next=cur;pre=cur;}}精选范本,供参考！pre->next=L;returnL;}2.为了获
4、取被删除节点的前一个节点,m=1时重新赋值m为1+循环链表的长度，所以需要一个函数获取循环链表的长度。//返回循环链表L的长度intlength_list(List*L){inti=1;List*p=L->next;while(p!=L){i++;p=p->next;}returni;}3.模拟报数过程，L永远指向下一个第一个报数的人，删除L开始后第m个节点，用结点指针del返回删除结点。List*delete_node(List**L,intm,List*del){if(m==1){//为了获取被删除节点的前一个节点,m=1时重新赋值为1
5、+lengthintl=length_list(*L);m=1+l;}List*pri=*L;//priornodeintj=0;while(jnext;j++;}del=pri->next;//deletenodepri->next=del->next;*L=pri->next;returndel;}4.输入构建好的链表L，人数n，密码m，每次调用delete_node函数删除一人，进行n次。voidjoseph_with_one_m(List*L,intn,intm){inti=
6、1;while(i<=n){//每次del一个nodeList*del;del=delete_node(&L,m,del);printf("第%d个出圈的序号是%d",i,del->number);free(del);i++;}}精选范本,供参考！5.如果密码m不同，则删除节点后，以删除节点的密码m作为新的m。voidjoseph_with_diff_m(List*L,intn){inti=1;intm=L->m;while(i<=n){//每次del一个nodeList*del=delete_node(&L,m,del);printf
7、("第%d个出圈的序号是%d",i,del->number);m=del->m;free(del);i++;}}6.在主函数中获取人数和密码m，构建链表，调用joseph函数。intmain(){intn,m;printf("请输入人数n:");scanf("%d",&n);printf("请输入所有人的m:");scanf("%d",&m);List*L;L=create_list_with_one_m(L,n);joseph_with_one_m(L,n,m);return0;}四、界面设计程序需要获取人数n，密码m（相同的密码m和
8、不同的密码m），输出出圈顺序。所以以提示的形式获取n和m。五、运行测试与分析（1）运行程序，显示输入提示，如图所示。精选范本,供参考！（2）根据提示，输入人数，并输入密码，即可输
