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

2010年双学士软件开发环境约瑟夫生死游戏 -之链表解决（必做）一、 问题背景有30个乘客同乘一艘船，因为严重超载，加上风高浪大，危险万分，因此船长告诉乘客，只有将全船一半乘客投入海中，其余人才能幸免于难。无奈，大家只得同意这种办法，并议定给30个人进行编号，30个人按编号围成一圈，由第i个人数起，依次报数，数到第9人，便把他投入大海中，然后再从他的下一个人数起，数到第9人，再将他扔到大海中，如此循环地进行，直到剩下15个乘客为止。问哪些位置是将被扔下大海的位置。二、 解决方案利用循环链表，每次将一个元素从链表中删除，继续按条件查询剩下的元素。首先定义链表节点。数据域用整数表示人员编号。然后将节点组成为30个节点的单循环链表。删除计数器置0 。从指定位置开始计数，移动计数器置1，移动指针到下一个节点，移动计数器加1 。计数器置8时，将下一节点删除。删除计数器加1 。删除计数器小于人数的一半否？是则从删除节点的下一个节点开始作为起始位置，跳至C。否则结束循环。三、 流程图主函数的流程如下：Out函数的流程图为：四、详细设计1、 结构体typedef struct Jonse /* 定义结构体*/int data;struct Jonse * next; /* 编号(分配位置) */Jonse;2、 链表的构造函数Jonse * Create(int n) /* 建立n个结点的单向循环链表函数 */Jonse *p,*h,*q;int i;h=(Jonse *)malloc(sizeof(Jonse); /* 为头结点分配空间 */p=h;for(i=1;idata=i; /编号if(inext=q;p=q;p-next=h; /* 最后返回头结点 ,完成单向循环链表的建立*/return h;3、 输出链表的函数void ShowList(Jonse *h) /*打印链表函数*/Jonse *p;p=h;doprintf(%4d,p-data);p=p-next;while(p!=h);printf(n);4、 实现将人剔除的函数void Out(Jonse *h,int m,int n) /*出队函数*/ int i,j;Jonse *p,*q;p=h;for(i=1;inext; while(num-flognum/2)for(j=i;jnext;q=p-next; /保留将要删除的顶点p-next=q-next; /删除该顶点p=q-next;printf(%4d,q-data); /打印删除顶点的数据域的信息free(q); /释放删除的顶点i=j+1;flog+;printf(n);五、 运行测试1、要求输入参与者的总人数：2、 打印出创建好的链表，并提出输入开始报数的位置：3、 输入报数人所在的位置，并提示输入报数的最大值4、 输入报数的最大值，计算显示结果：结果为删除的人所在的位置调试分析程序的编写和调试基本正常。遇到的问题主要是：链表的指向的边界问题。本实验采用数据抽象的与模块化程序设计方法。思路清晰，实现时调试顺利，各模块具有很好的可重用性，得到了一次良好的程序设计训练。6 测试结果测试结果，输入输出。完整严格。7 附件（全部源代码）#include#includetypedef struct Jonse /* 定义结构体*/ int code; /* 编号(分配位置) */ struct Jonse *next;Jonse;Jonse * Create(int n);void ShowList(Jonse *);void Out(Jonse *,int,int);int flag,num;/* 集合各个接口的主函数，结构很清晰*/void main() Jonse *head;int val,beg;flag=0;printf(n请输入参与者总人数 :n);scanf_s(%d,&num);head=Create(num);ShowList(head);printf(n请输入报数的人所在位置 :n);scanf_s(%d,&beg);printf(n请输入参与者报数最大值 :n);scanf_s(%d,&val);printf(将被扔下大海的参与者的编号，即其所在位置 :n);Out(head,beg,val);getchar();getchar();Jonse * Create(int n) /* 建立n个结点的单向循环链表函数 */ Jonse *h,*p;int i; h=(Jonse *)malloc(sizeof(Jonse); /* 为头结点分配空间 */ p=h; for(i=1;icode=i; if(inext=(Jonse *)malloc(sizeof(Jonse); /* 创建新的结点 */ p=p-next; p-next=h; /* 最后返回头结点 ,完成单向循环链表的建立*/ return h;void ShowList(Jonse *h) /*打印链表函数*/ Jonse *p; p=h; do printf(%dt,p-code); p=p-next; while(p!=h);void Out(Jonse *h,int i,int d) /*出队函数*/ Jonse *p,*q; int k; p=h; for(q=h;q-next!=h;q=q-next); /* 初始化链表 */ for(k=1;knext; /*循环地删除队列结点*/ while(p!=p-next) for(k=1;knext; printf(%dt,p-code); /* 输出被踢结点的位置 */ q-next=p-next; free(p); /* 释放被踢出的结点 */ p=NULL; /* 让p指针赋值为空指针（即让其失效） */ p=q-next; flag+; /* 标志位每次循环被踢出人数加1 */ if(flag=(nu