约瑟夫生死游戏--链表报告课设

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

1、2010年双学士软件开发环境约瑟夫生死游戏--之链表解决（必做）一、问题背景有30个乘客同乘一艘船，因为严重超载，加上风高浪大，危险万分，因此船长告诉乘客，只有将全船一半乘客投入海中，其余人才能幸免于难。无奈，大家只得同意这种办法，并议定给30个人进行编号，30个人按编号围成一圈，由第i个人数起，依次报数，数到第9人，便把他投入大海中，然后再从他的下一个人数起，数到第9人，再将他扔到大海中，如此循环地进行，直到剩下15个乘客为止。问哪些位置是将被扔下大海的位置。二、解决方案利用循环链表，每次将一个元素从链表中删除，继续按条件查询剩下的元素。首先定义链表节点。数据域

2、用整数表示人员编号。然后将节点组成为30个节点的单循环链表。删除计数器置0。从指定位置开始计数，移动计数器置1，移动指针到下一个节点，移动计数器加1。计数器置8时，将下一节点删除。删除计数器加1。删除计数器小于人数的一半否？是则从删除节点的下一个节点开始作为起始位置，跳至C。否则结束循环。一、流程图主函数的流程如下：Out函数的流程图为：四、详细设计1、结构体typedefstructJonse/*定义结构体*/{intdata;structJonse*next;/*编号(分配位置)*/}Jonse;2、链表的构造函数Jonse*Create(intn)/*建立n

3、个结点的单向循环链表函数*/{Jonse*p,*h,*q;inti;h=(Jonse*)malloc(sizeof(Jonse));/*为头结点分配空间*/p=h;for(i=1;i<=n;i++)/*建立n个结点的单向链表*/{p->data=i;//编号if(inext=q;p=q;}}p->next=h;/*最后返回头结点,完成单向循环链表的建立*/returnh;}3、输出链表的函数voidShowList(Jonse*h)/*打印链表函数*/{Jo

4、nse*p;p=h;do{printf("%4d",p->data);p=p->next;}while(p!=h);printf("");}4、实现将人剔除的函数voidOut(Jonse*h,intm,intn)/*出队函数*/{inti,j;Jonse*p,*q;p=h;for(i=1;inext;}while(num-flog>num/2){for(j=i;jnext;}q=p->next;//保留将要删除的顶点p->next=q->next;//删除该顶点p=q->next;printf("%

5、4d",q->data);//打印删除顶点的数据域的信息free(q);//释放删除的顶点i=j+1;flog++;printf("");}}五、运行测试1、要求输入参与者的总人数：2、打印出创建好的链表，并提出输入开始报数的位置：3、输入报数人所在的位置，并提示输入报数的最大值4、输入报数的最大值，计算显示结果：结果为删除的人所在的位置调试分析程序的编写和调试基本正常。遇到的问题主要是：链表的指向的边界问题。本实验采用数据抽象的与模块化程序设计方法。思路清晰，实现时调试顺利，各模块具有很好的可重用性，得到了一次良好的程序设计训练。六．测试结果测试结果，输入输

6、出。完整严格。七．附件（全部源代码）#include#includetypedefstructJonse/*定义结构体*/{intcode;/*编号(分配位置)*/structJonse*next;}Jonse;Jonse*Create(intn);voidShowList(Jonse*);voidOut(Jonse*,int,int);intflag,num;/*集合各个接口的主函数，结构很清晰*/voidmain(){Jonse*head;intval,beg;flag=0;printf("请输入参与者总人数:")

7、;scanf_s("%d",&num);head=Create(num);ShowList(head);printf("请输入报数的人所在位置:");scanf_s("%d",&beg);printf("请输入参与者报数最大值:");scanf_s("%d",&val);printf("将被扔下大海的参与者的编号，即其所在位置:");Out(head,beg,val);getchar();getchar();}Jonse*Create(intn)/*建立n个结点的单向循环链表函数*/{Jonse*h,*p;inti;h=(Jonse*)mall

8、oc(si