约瑟夫生者死者游戏

《约瑟夫生者死者游戏》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、课程设计报告约瑟夫生者死者游戏学生姓名：专业：班级：学号:指导教师：2017年3月29日15目录一、实验题目2二、实验目的2三、实验要求2四、实现过程31、总体设计：32、详细设计：33、调试分析：34、运行结果：35、实验总结：6五、参考文献615一、实验题目约瑟夫生者死者游戏二、实验目的本次课程设计的主要目的是综合运用所学的数据结构知识解决Jonsepu环问题，侧重对循环链表等相关内容的综合应用，使自己能进一步熟悉掌握数据结构的基础知识，进一步提升自己的解决问题和编程调试能力，为后续专业课程的学习打下良好的基础。三、实验要求设计要求本游戏的数学建模如下：假设n个旅客排成一

2、个环形，依次顺序编号1，2，…，n。从某个指定的第1号开始，沿环计数，每数到第m个人就让其出列，且从下一个人开始重新计数，继续进行下去。这个过程一直进行到剩下k个旅客为止。本游戏的要求用户输入的内容包括：1.旅客的个数，也就是n的值；2.离开旅客的间隔数，也就是m的值；3.所有旅客的序号作为一组数据要求存放在某种数据结构中。本游戏要求输出的内容是包括1.离开旅客的序号；2.剩余旅客的序号；15四、实现过程1、总体设计：1.主流程图：开始输入总人数创建链表打印链表输入报数人的位置输入报的数字调用踢出人的模块Out(head,beg,val,huo)结束151.Out函数流程图开

3、始将p指针指向起始报数的位置剩下的人数大于输入留下的人数否是P指针移动n-3个位置q指针指向p的下一个结点删除q指针所指的结点p指针指向q的下一个结点释放q指针所指向结点的空间Flag++结束2、详细设计：1.结构体15typedefstructJonse/*定义结构体*/{intcode;/*编号（分配位置）*/structJonse*next;}jonse;2.链表的构造函数jonse*Create(intn)/*建立n个节点的单向循环链表函数*/{Jonse*h,*p;inti;h=(Jonse*)malloc(sizeof(Jonse));/*为头结点分配空间*/p=

4、h;for(i=1;i<=n;i++)/*建立n个节点的单向链表*/{p->code=i;if(inext=(Jonse*)malloc(sizeof(Jonse));/*创建新节点*/p=p->next;}}15p->next=h;/*返回头结点，完成单向循环链表的建立*/returnh;}3.输出链表的函数voidShowList(Jonse*h)/*打印链表函数*/{Jonse*p;p=h;do{printf("%dt",p->code);p=p->next;}while(p!=h);}4.实现将人剔除的函数voidOut(Jonse*h,inti,in

5、td,ints)/*出队函数*/{intc;c=s;Jonse*p,*q;intk;p=h;15for(q=h;q->next!=h;q=q->next);/*初始化链表*/for(k=1;knext;}while(p!=p->next)/*循环删除队列结点*/{for(k=1;knext;}printf("%d",p->code);/*输出被踢节点的位置*/q->next=p->next;free(p);/*释放被踢出的结点*/p=NULL;/*让p

6、指针赋值为空指针*/p=q->next;flag++;if(num-flag==c)break;15}printf("剩余游客的编号:");//free(p);/*释放被踢出的结点*/p=NULL;/*让p指针赋值为空指针*/p=h;do{printf("%d",p->code);p=p->next;}while(p!=h);printf("");}3、调试分析：程序的编写和调试基本正常。遇到的问题主要是：链表的指向的边界问题。本实验采用数据抽象与模块化程序设计方法，思路清晰，实验时调试顺利，各模块具有很好的可重用性，得到了一次良好的程序设计训练。15本实验算法是

7、使用循环链表的方法，由于这种方法在删除一个节点后对其他节点的位置改动放不大，所以很浪费时间，每次都删除第m个数字，都要用O（m）的时间，一共有n个数字，想要剩下一个，其余都要删除，那么就要用（n-1）*O（m）的时间，所以算法的时间复杂度为O（mn）。还可以用数组来实现本实验，减少时间的浪费。4、运行结果：1.要求输入参与者的总人数：2.打印出创建好的链表，并提示输入开始报数的位置：3.输入报数人所在的位置，并提示输入报数的最大值：151.输入报数的最大值，并提示输入留下的人数：2.输入留下人数，计算显