(完整word版)约瑟夫生死游戏课程设计(含源代码可以运行)(2)(word文档良心出品)

1、湖南商学院数据结构与算法课程设计约瑟夫双向生死游戏学生姓名梁子嫣140920043计算机工程与信息学院专业班级计科1402指导教师蒋伟进教授2016年 6月26日目录第一章需求分析1.1课程设计要求 1.2课程设计目标与总体方案错误！未定义书签。1.3程序执行的命令第二章算法描述2.1算法描述错误！未定义书签。2.2系统图形说明第三章系统的设计3.1创建双向链表3.2约瑟夫算法3.4主函数第四章 程序的运行结果图附录约瑟夫生死游戏章需求分析1.1项目简介约瑟夫双向生死游戏是在约瑟夫生者死者游戏的基础上，正向计数后反向计 数，然后再正向计数。具体描述如下：30个旅客同乘一条船，因为严重超载, 加

2、上风高浪大，危险万分；因此船长告诉乘客，只有将全船一半的旅客投入海中, 其余人才能幸免遇难。无奈，大家只得同意这种办法，并议定30个人围成一圈, 由第一个人开始，顺时针依次报数，数到第 9人，便把他投入大海中，然后从他的下一个人数起，逆时针数到第5人，将他投入大海，然后从他逆时针的下一个人数起，顺时针数到第9人，再将他投入大海，如此循环，直到剩下 15个乘客为止。问哪些位置是将被扔下大海的位置。1.2设计思路本游戏的数学建模如下：假设n个旅客排成一个环形，依次顺序编号1,2,-,n。从某个指定的第1号开始，沿环计数，数到第 m个人就让其出列，然后从第 m+1个人反向计数到m-k+1个人，让其出

3、列，然后从m-k个人开始重新正向沿环计数，再数m个人后让其出列，然后再反向数 k个人后让其出列。这个过程一 直进行到剩下q个旅客为止。本游戏的要求用户输入的内容包括:1. 旅客的个数，也就是n的值;2. 正向离开旅客的间隔数，也就是 m的值;3. 反向离开旅客的间隔数，也就是 k的值;4.所有旅客的序号作为一组数据要求存放在某种数据结构中。本游戏要求输出的内容是包括1. 离开旅客的序号;2. 剩余旅客的序号；所以，根据上面的模型分析及输入输出参数分析，可以定义一种数据结构后进行 算法实现。第二章系统的功能2.1系统文字描述(1)创建含有n个结点的双向循环链表;生着与死者的选择：P指向链表的第一

4、个结点，初始i置为1；while(iv=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系统图形说明第三章系统的设计3.1创建双向循环链表;no de* createList(i nt num)no de* head = (no de*)malloc(sizeof( no de);head->value = 1;no

5、 de* p = head;for(i nt i = 1;i vnu m;i+)no de* p Next = (no de*)malloc(sizeof( no de);p Next->value = i+1;p->n ext = p Next;p Next->left = p;p = p Next;p->n ext = head;head->left = p;retu rn head;3.2生者与死者的选择int deleteList (no de* head, int nu m1,i nt nu m2,i nt tota IPeop le,i nt aliv

6、e Pep ole)/num1 代表顺时针数num2代表逆时针数no de* p = head;int peop leOfNow = tota IPeople;while( peop leOfNow>alive Pepole)/ 找到顺时针要删除节点的前一节点 Pfor(i nt i =1; ivnumi - 1;i+)p = p->n ext;/ 删除顺时针时的节点no de* toBeDeleted = p->n ext;prin tf("deadma n = %dn ",toBeDeleted->value);no de* n extToDel

7、eted = toBeDeleted->n ext;p->n ext = n extToDeleted;n extToDeleted->left = p;free(toBeDeleted);peopi eOfNow-;if(peop leOfNow>alive Pep ole) /防止不需要再删除节点了，所以要先判断/找到逆时针时要删除节点的前一节点no de* s = n extToDeleted;for(i nt i =1; ivnum2 -1;i+)s = s->left;/删除逆时针时的节点no de* tobeDeleted = s->left;p

8、rin tf("deadma n = %dn ",tobeDeleted->value);node* leftToBeDeleted = tobeDeleted->left;s->left = leftToBeDeleted;leftToBeDeleted->n ext = s;free(tobeDeleted);peop leOfNow-;p = leftToBeDeleted;return 0;3.3主函数int main()no de* head = createList(30);deleteList( head, 9,5,30,15);ret

9、urn 0;g514101915242029254301221any key to continue第四章程序运行结果i匚 *GMicrosoft Visual StudioXCommonMSDew9£EinTDebLjgyLifu.FJCEde adman deadman de adman deadnian ds adman deadnian deadman de adman deadnian ds adman deadnian deadman deadman de adman de Sidman Press附录源代码#i nclude "stdio.h" #i

10、 nclude "stdlib.h" struct nodeint value;no de* left;no de* n ext;Node;/创建双向的循环链表 no de* createList(i nt num)no de* head = (no de*)malloc(sizeof( no de);head->value = 1;no de* p = head;for(i nt i = 1;i vnu m;i+)no de* p Next = (no de*)malloc(sizeof( no de);p Next->value = i+1;p->n

11、ext = p Next;p Next->left = p;p = p Next;p->n ext = head;head->left = p;retu rn head;int deleteList (no de* head, int nu m1,i nt nu m2,i nt tota IPeop le,i nt alive Pep ole)/num1 代表顺时针数num2代表逆时针数no de* p = head;int peop leOfNow = tota IPeople;while( peop leOfNow>alive Pepole)/ 找到顺时针要删除节点

12、的前一节点 Pfor(i nt i =1; ivnum1 - 1;i+)p = p->n ext;/ 删除顺时针时的节点no de* toBeDeleted = p->n ext;prin tf("deadma n = %dn ",toBeDeleted->value);no de* n extToDeleted = toBeDeleted->n ext;p->n ext = n extToDeleted;n extToDeleted->left = p;free(toBeDeleted);peopi eOfNow-;if(peop leOfNow>alive Pep ole) /防止不需要再删除节点了，所以要先判断/找到逆时针时要删除节点的前一节点no de* s = n extToDeleted;for(i nt i =1; ivnum2 -1;i+)s = s->left;/删除逆时针时的节点no de* tobeDeleted = s->left;prin tf("deadma n = %dn ",tobeDeleted->value);node* leftToBeDeleted = tobeDeleted->