约瑟夫生者死者游戏

课程设计报告约瑟夫生者死者游戏学生姓名：专业：班级：学号:指导教师：2017年3月29日1目录一、实验题目.................................2二、实验目的.................................2三、实验要求.................................2四、实现过程.................................31、总体设计：.......................................32、详细设计：.......................................43、调试分析：.......................................84、运行结果：.......................................95、实验总结：.....................................11五、参考文献...............................112一、实验题目约瑟夫生者死者游戏二、实验目的本次课程设计的主要目的是综合运用所学的数据结构知识解决Jonsepu环问题，侧重对循环链表等相关内容的综合应用，使自己能进一步熟悉掌握数据结构的基础知识，进一步提升自己的解决问题和编程调试能力，为后续专业课程的学习打下良好的基础。三、实验要求设计要求本游戏的数学建模如下：假设n个旅客排成一个环形，依次顺序编号1，2，…，n。从某个指定的第1号开始，沿环计数，每数到第m个人就让其出列，且从下一个人开始重新计数，继续进行下去。这个过程一直进行到剩下k个旅客为止。本游戏的要求用户输入的内容包括：1.旅客的个数，也就是n的值；2.离开旅客的间隔数，也就是m的值；3.所有旅客的序号作为一组数据要求存放在某种数据结构中。本游戏要求输出的内容是包括1.离开旅客的序号；2.剩余旅客的序号；3四、实现过程1、总体设计：1.主流程图：开始输入总人数创建链表打印链表输入报数人的位置输入报的数字调用踢出人的模块Out(head,beg,val,huo)结束42.Out函数流程图2、详细设计：1.结构体开始将p指针指向起始报数的位置剩下的人数大于输入留下的人数q指针指向p的下一个结点删除q指针所指的结点p指针指向q的下一个结点释放q指针所指向结点的空间Flag++结束是P指针移动n-3个位置否5typedefstructJonse/*定义结构体*/{intcode;/*编号（分配位置）*/structJonse*next;}jonse;2.链表的构造函数jonse*Create(intn)/*建立n个节点的单向循环链表函数*/{Jonse*h,*p;inti;h=(Jonse*)malloc(sizeof(Jonse));/*为头结点分配空间*/p=h;for(i=1;i=n;i++)/*建立n个节点的单向链表*/{p-code=i;if(in){p-next=(Jonse*)malloc(sizeof(Jonse));/*创建新节点*/p=p-next;}}6p-next=h;/*返回头结点，完成单向循环链表的建立*/returnh;}3.输出链表的函数voidShowList(Jonse*h)/*打印链表函数*/{Jonse*p;p=h;do{printf(%d\t,p-code);p=p-next;}while(p!=h);}4.实现将人剔除的函数voidOut(Jonse*h,inti,intd,ints)/*出队函数*/{intc;c=s;Jonse*p,*q;intk;p=h;7for(q=h;q-next!=h;q=q-next);/*初始化链表*/for(k=1;ki;k++)/*次循环功能：设置好开始报数的人所在位置*/{q=p;p=p-next;}while(p!=p-next)/*循环删除队列结点*/{for(k=1;kd;k++)/*数数*/{q=p;p=p-next;}printf(%d,p-code);/*输出被踢节点的位置*/q-next=p-next;free(p);/*释放被踢出的结点*/p=NULL;/*让p指针赋值为空指针*/p=q-next;flag++;if(num-flag==c)break;8}printf(\n剩余游客的编号:\n);//free(p);/*释放被踢出的结点*/p=NULL;/*让p指针赋值为空指针*/p=h;do{printf(%d,p-code);p=p-next;}while(p!=h);printf(\n);}3、调试分析：程序的编写和调试基本正常。遇到的问题主要是：链表的指向的边界问题。本实验采用数据抽象与模块化程序设计方法，思路清晰，实验时调试顺利，各模块具有很好的可重用性，得到了一次良好的程序设计训练。本实验算法是使用循环链表的方法，由于这种方法在删除一个节点后对其他节点的位置改动放不大，所以很浪费时间，每次都删除第m个数字，都要用O（m）的时间，一共有n个数字，想要剩下一个，其余都要删除，那么就要用（n-1）*O9（m）的时间，所以算法的时间复杂度为O（mn）。还可以用数组来实现本实验，减少时间的浪费。4、运行结果：1.要求输入参与者的总人数：2.打印出创建好的链表，并提示输入开始报数的位置：3.输入报数人所在的位置，并提示输入报数的最大值：104.输入报数的最大值，并提示输入留下的人数：5.输入留下人数，计算显示结果：结果为删除的人所在的位置和留下的人数：115、实验总结：通过本次课程设计的锻炼，使我对数据结构又有了许多新的深刻认识，更深的理解了数据结构的难点，并且通过这次课程设计，我把以前认为没有实际用途的知识转化为了实际问题来解决，非常有意思，同时也觉得这种学习方法，更好的提高学习的效率，以下就是我做这次课程设计的主要体会：一方面，在程序设计语言中，每一个数据都属于某种数据类型。类型明显或隐含地规定了数据的取值范围、存储方式以及允许进行的运算。另一方面，在程序设计过程中，当需要引入某种新的数据结构时，总是借助编程语言所提供的数据类型来描述数据的存储结构。同时，做好课程设计更能体现出同学的学习态度，对于新知识的渴望与追求，能够反映出同学对自己负责任的态度。五、参考文献[1]严蔚敏，吴伟民，《数据结构》，北京：清华大学出版社，2006年[2]苏小红，《C语言程序设计》（第3版）2015年六、附录#includestdio.h#includestdlib.htypedefstructJonse/*定义结构体*/12{intcode;/*编号（分配位置）*/structJonse*next;}jonse;jonse*Create(intn);voidShowList(Jonse*);voidOut(Jonse*,int,int,int);intflag,num;/*主函数*/main(){Jonse*head;intval,beg,huo;flag=0;printf(\n请输入游客总人数：);scanf(%d,&num);head=Create(num);ShowList(head);printf(\n请输入报数的人所在位置：);scanf(%d,&beg);printf(\n请输入报数最大值：);scanf(%d,&val);13printf(\n请输入留下的人数：);scanf(%d,&huo);printf(\n将被扔下大海的游客的编号：\n);Out(head,beg,val,huo);return0;}jonse*Create(intn)/*建立n个节点的单向循环链表函数*/{Jonse*h,*p;inti;h=(Jonse*)malloc(sizeof(Jonse));/*为头结点分配空间*/p=h;for(i=1;i=n;i++)/*建立n个节点的单向链表*/{p-code=i;if(in){p-next=(Jonse*)malloc(sizeof(Jonse));/*创建新节点*/p=p-next;}}p-next=h;/*返回头结点，完成单向循环链表的建立*/returnh;}voidShowList(Jonse*h)/*打印链表函数*/14{Jonse*p;p=h;do{printf(%d\t,p-code);p=p-next;}while(p!=h);}voidOut(Jonse*h,inti,intd,ints)/*出队函数*/{intc;c=s;Jonse*p,*q;intk;p=h;for(q=h;q-next!=h;q=q-next);/*初始化链表*/for(k=1;ki;k++)/*次循环功能：设置好开始报数的人所在位置*/{q=p;p=p-next;}while(p!=p-next)/*循环删除队列结点*/{for(k=1;kd;k++)/*数数*/{q=p;p=p-next;15}printf(%d,p-code);/*输出被踢节点的位置*/q-next=p-next;free(p);/*释放被踢出的结点*/p=NULL;/*让p指针赋值为空指针*/p=q-next;flag++;if(num-flag==c)break;}printf(\n剩余游客的编号:\n);//free(p);/*释放被踢出的结点*/p=NULL;/*让p指针赋值为空指针*/p=h;do{printf(%d,p-code);p=p-next;}while(p!=h);printf(\n);}