约瑟夫生死游戏课程设计(含源代码可以运行)

湖南商学院数据结构与算法课程设计题目约瑟夫双向生死游戏学生姓名梁子嫣学号140920043学院计算机工程与信息学院专业班级计科1402指导教师蒋伟进职称教授2016年6月26日目录第一章需求分析...................................................31.1课程设计要求..................................................31.2课程设计目标与总体方案........................................31.3程序执行的命令................................错误!未定义书签。第二章算法描述...................................................42.1算法描述......................................错误!未定义书签。2.2系统图形说明..................................................3第三章系统的设计.................................................43.1创建双向链表..................................................43.2约瑟夫算法....................................................43.4主函数........................................................6第四章程序的运行结果图...........................................7附录..............................................................8约瑟夫生死游戏第一章需求分析1.1项目简介约瑟夫双向生死游戏是在约瑟夫生者死者游戏的基础上，正向计数后反向计数，然后再正向计数。具体描述如下：30个旅客同乘一条船，因为严重超载，加上风高浪大，危险万分；因此船长告诉乘客，只有将全船一半的旅客投入海中，其余人才能幸免遇难。无奈，大家只得同意这种办法，并议定30个人围成一圈，由第一个人开始，顺时针依次报数，数到第9人，便把他投入大海中，然后从他的下一个人数起，逆时针数到第5人，将他投入大海，然后从他逆时针的下一个人数起，顺时针数到第9人，再将他投入大海，如此循环，直到剩下15个乘客为止。问哪些位置是将被扔下大海的位置。1.2设计思路本游戏的数学建模如下：假设n个旅客排成一个环形，依次顺序编号1，2，…，n。从某个指定的第1号开始，沿环计数，数到第m个人就让其出列，然后从第m+1个人反向计数到m-k+1个人，让其出列，然后从m-k个人开始重新正向沿环计数，再数m个人后让其出列，然后再反向数k个人后让其出列。这个过程一直进行到剩下q个旅客为止。本游戏的要求用户输入的内容包括：1.旅客的个数，也就是n的值；2.正向离开旅客的间隔数，也就是m的值；3.反向离开旅客的间隔数，也就是k的值；4.所有旅客的序号作为一组数据要求存放在某种数据结构中。本游戏要求输出的内容是包括1.离开旅客的序号；2.剩余旅客的序号；所以，根据上面的模型分析及输入输出参数分析，可以定义一种数据结构后进行算法实现。第二章系统的功能2.1系统文字描述(1)创建含有n个结点的双向循环链表；(2)生着与死者的选择：p指向链表的第一个结点，初始i置为1；while(i=n/2)//删除一半的结点｛从p指向的结点沿链前进m-1步；删除第m个结点（q所指向的结点）；p指向q的下一个结点；输出其位置q-data;i自增1；从p指向的结点沿链后退k-1步；删除第k个结点（q所指向的结点）；p指向q的上一个结点；输出其位置q-data;i自增1；｝(3)输出所有生者的位置。2.2系统图形说明约瑟夫生死游戏确定n值更新链表输入输出构建链表第三章系统的设计3.1创建双向循环链表；node*createList(intnum){node*head=(node*)malloc(sizeof(node));head-value=1;node*p=head;for(inti=1;inum;i++){node*pNext=(node*)malloc(sizeof(node));pNext-value=i+1;p-next=pNext;pNext-left=p;p=pNext;}p-next=head;head-left=p;returnhead;}3.2生者与死者的选择intdeleteList(node*head,intnum1,intnum2,inttotalPeople,intalivePepole)//num1代表顺时针数num2代表逆时针数{node*p=head;intpeopleOfNow=totalPeople;while(peopleOfNowalivePepole){//找到顺时针要删除节点的前一节点pfor(inti=1;inum1-1;i++){p=p-next;}//删除顺时针时的节点node*toBeDeleted=p-next;printf(deadman=%d\n,toBeDeleted-value);node*nextToDeleted=toBeDeleted-next;p-next=nextToDeleted;nextToDeleted-left=p;free(toBeDeleted);peopleOfNow--;if(peopleOfNowalivePepole)//防止不需要再删除节点了，所以要先判断{//找到逆时针时要删除节点的前一节点node*s=nextToDeleted;for(inti=1;inum2-1;i++){s=s-left;}//删除逆时针时的节点node*tobeDeleted=s-left;printf(deadman=%d\n,tobeDeleted-value);node*leftToBeDeleted=tobeDeleted-left;s-left=leftToBeDeleted;leftToBeDeleted-next=s;free(tobeDeleted);peopleOfNow--;p=leftToBeDeleted;}}return0;}3.3主函数intmain(){node*head=createList(30);deleteList(head,9,5,30,15);return0;}第四章程序运行结果附录源代码#includestdio.h#includestdlib.hstructnode{intvalue;node*left;node*next;}Node;//创建双向的循环链表node*createList(intnum){node*head=(node*)malloc(sizeof(node));head-value=1;node*p=head;for(inti=1;inum;i++){node*pNext=(node*)malloc(sizeof(node));pNext-value=i+1;p-next=pNext;pNext-left=p;p=pNext;}p-next=head;head-left=p;returnhead;}intdeleteList(node*head,intnum1,intnum2,inttotalPeople,intalivePepole)//num1代表顺时针数num2代表逆时针数{node*p=head;intpeopleOfNow=totalPeople;while(peopleOfNowalivePepole){//找到顺时针要删除节点的前一节点pfor(inti=1;inum1-1;i++){p=p-next;}//删除顺时针时的节点node*toBeDeleted=p-next;printf(deadman=%d\n,toBeDeleted-value);node*nextToDeleted=toBeDeleted-next;p-next=nextToDeleted;nextToDeleted-left=p;free(toBeDeleted);peopleOfNow--;if(peopleOfNowalivePepole)//防止不需要再删除节点了，所以要先判断{//找到逆时针时要删除节点的前一节点node*s=nextToDeleted;for(inti=1;inum2-1;i++){s=s-left;}//删除逆时针时的节点node*tobeDeleted=s-left;printf(deadman=%d\n,tobeDeleted-value);node*leftToBeDeleted=tobeDeleted-left;s-left=leftToBeDeleted;leftToBeDeleted-next=s;free(tobeDeleted);peopleOfNow--;p=leftToBeDeleted;}}return0;}intmain(){node*head=createList(30);deleteList(head,9,5,30,15);return0;}