数据结构试验报告1约瑟夫环

1、、上机实验的问题和要求:约瑟夫环问题描述：编号是1,2,n(n>0)的n个人按照顺时针方向围坐一圈，每人持有一正整数密码。开始时任选一个正整数作为报数上限值m从某个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。令n最大值取30。设计一个程序来求出出列顺序，并输出结果。基本要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各人的编号。二、程序设计的基本思想，原理和算法描述：(包括程序的结构，数据结构，输入/输出设计，符号名说明等)(1)算法的基本思想：约瑟夫

2、环问题中的数据是人所在的位置，而这种数据是存在“第一元素、最后元素”，并且存在“唯一的前驱和后继的"，符合线性表的特点。由于需要模拟约瑟夫环的出列问题，可以采用顺序表来实现线性表，完成出列顺序的输出。核心算法主要分为两步：1、确定需要删除的位置，2、设置并删除该位置。已知报数间隔m,我们可以把当前位置加上m获得需要删除的位置，如果获得的位置超过顺序表中实际元素的总长度，则可以通过减去数组的实际长度来修正(即模拟环状计数)。然后把顺序表中的当前指向位置设置为该位置，继而删掉该位置。反复进行上述确定位置和删除位置的操作，直到顺序表为空。(2)主程序的流程：程序由三个模块组成：1、输入模块

3、：无提示语句，直接输入总人数n和报数次数m,中间用逗号隔开02、处理模块：将元素储存于顺序表中。在主函数中根据报数间隔确定需要删除的元素的位置，在顺序表中设置该位置并删除该位置，同时输出该位置的值。反复设置并删除直到表空。3、输出模块：分别在DOS下和文件中，按移除元素的顺序依次显示其位置。(3)各程序模块之间的层次(调用)关系：主函数会按设计的方法调用顺序表中“获取实际长度”、“设置需要删除元素的位置”、“移除该位置元素”和“判断是否为空表”四种方法方法，使元素依次出列，并正确结束程序。三、源程序及注释:#include<stdio.h>#include<malloc.h&

4、gt;#include<stdlib.h>/*宏定义和单链表类型定义*/#defineListSize100typedefintDataType;typedefstructNodeDataTypedata;structNode*next;ListNode,*LinkList;/*函数声明*/LinkListCreateCycList(intn);/*创建一个长度为n的循环单链表的函数声明*/voidJosephus(LinkListhead,intn,intm,intk);/*在长度为n的循环单链表中，报数为编号为m的出列*/voidDisplayCycList(LinkListh

5、ead);/*输出循环单链表*/voidmain()LinkListh;intn,k,m;printf(“输入环中人的个数n=");scanf("%d",&n);printf("输入开始报数的序号m=");scanf("%d",&k);printf("输出结果为：");scanf("%d",&k);h=CreateCycList(n);Josephus(h,n,m,k);voidJosephus(LinkListhead,intn,intm,intk)/*在长度

6、为n的循环单链表中，从第k个人开始报数，数到m的人出列*/ListNode*p,*q;inti;p=head;for(i=1;i<k;i+)/*从第k个人开始报数*/q=p;p=p->next;while(p->next!=p)for(i=1;i<m;i+)/*数到m的人出列*/(q=p;p=p->next;)q->next=p->next;/*将p指向的结点删除，即报数为m的人出列*/printf("%4d",p->data);free(p);p=q->next;/*p指向下一个结点，重新开始报数*/)printf(&

7、quot;%4dn",p->data);)LinkListCreateCycList(intn)/*宏定义和单链表类型定义*/(LinkListhead=NULL;ListNode*s,*r;inti;for(i=1;i<=n;i+)(s=(ListNode*)malloc(sizeof(ListNode);s->data=i;s->next=NULL;if(head=NULL)head=s;elser->next=s;r=s;)r->next=head;returnhead;)voidDisplayCycList(LinkListhead)/*输

8、出循环链表的每一个元素*/(ListNode*p;p=head;if(p=NULL)(printf("该链表是空表");return;)while(p->next!=head)/*如果不是最后一个结点，输出该结点*/(printf("%4d",p->data);p=p->next;)printf("%4dn”,p->data);/*输出最后一个结点*/)四、运行输由结果：输入环中人的个数n=7请输入每个人的密码：3172484输入开始报数的序号m=20输出结果为：6147235五、调试和运行程序过程中产生的问题及采取的措

9、施：调试过程中会出现编译错误，主要是细节方面的问题，要检查语法是否正确，数据类型定义是否恰当，括弧之间的匹配，循环次数的准确性。六、对算法的程序的讨论、分析，改进设想，其它经验教训：1、初始化部分为循环赋值，时间复杂度为G)(n)02、处理部分，我为了提高效率没有采用循环寻找的方法，直接利用数学关系通过当前位置获得下一位置，因此对于长度为n的约瑟夫环，只做了n次定位，每次定位的复杂度为0(1),所以时间复杂度为G)(n)0但是用顺序表实现时，每次其移除的方法是时间复杂度为G)(k)W(k与实际长度有关),所以处理部分总的结果是(子加)的，化简后时间复杂度仍然为(n2)o综上，该算法的时间代价为(n2)o(PS:如果是用循环查找，在n次定位中每次都使用了m次的循环，至少是