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

2010年双学士软件开发环境

约瑟夫生死游戏

--之链表解决（必做）

一、 问题背景

有30个乘客同乘一艘船，因为严重超载，加上风高浪大，危险万分，因此船长告诉乘客，只有将全船一半乘客投入海中，其余人才能幸免于难。无奈，大家只得同意这种办法，并议定给30个人进行编号，30个人按编号围成一圈，由第i个人数起，依次报数，数到第9人，便把他投入大海中，然后再从他的下一个人数起，数到第9人，再将他扔到大海中，如此循环地进行，直到剩下15个乘客为止。问哪些位置是将被扔下大海的位置。

二、 解决方案

利用循环链表，每次将一个元素从链表中删除，继续按条件查询剩下的元素。

首先定义链表节点。数据域用整数表示人员编号。然后将节点组成为30个节点的单循环链表。删除计数器置0 。从指定位置开始计数，移动计数器置1，移动指针到下一个节点，移动计数器加1 。计数器置8时，将下一节点删除。删除计数器加1 。删除计数器小于

人数的一半否？是则从删除节点的下一个节点开始作为起始位置，跳至C。否则结束循环。

三、 流程图

主函数的流程如下：

Out函数的流程图为：

开始将p指针指向起始报数的位置剩下的人数大于总人数的一半是p指针移动n-3个位置否q指针指向p的下一个结点删除q指针所指的结点p指针指向q指针的下个结点释放q指针所指向结点的空间i=j+1flag++结束

四、详细设计

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;i<=n;i++) /* 建立n个结点的单向链表*/ {

p->data=i; //编号 if(iq=(Jonse *)malloc(sizeof(Jonse)); //分配空间,创

建新的结点 */

p->next=q; p=q;

*/ }

}

}

p->next=h; /* 最后返回头结点 ,完成单向循环链表的建立

return h;

3、 输出链表的函数

void ShowList(Jonse *h) /*打印链表函数*/ { }

Jonse *p; p=h; do{

printf(\"%4d\p=p->next;

}while(p!=h); printf(\"\\n\");

4、 实现将人剔除的函数

void Out(Jonse *h,int m,int n) /*出队函数*/ { 息

free(q); //释放删除的顶点 int i,j; Jonse *p,*q; p=h;

for(i=1;iwhile(num-flog>num/2) {

for(j=i;jq=p->next; //保留将要删除的顶点 p->next=q->next; //删除该顶点 p=q->next;

printf(\"%4d\ //打印删除顶点的数据域的信p=p->next; p=p->next;

}

}

i=j+1; flog++; printf(\"\\n\");

五、 运行测试

1、要求输入参与者的总人数：

2、 打印出创建好的链表，并提出输入开始报数的位置：

3、 输入报数人所在的位置，并提示输入报数的最大值

4、 输入报数的最大值，计算显示结果：结果为删除的人所在的位置

调试分析

程序的编写和调试基本正常。遇到的问题主要是：链表的指向的边界问题。本实验采用数据抽象的与模块化程序设计方法。思路清晰，实现时调试顺利，各模块具有很好的可重用性，得到了一次良好的程序设计训练。

六．测试结果

测试结果，输入输出。完整严格。

七．附件（全部源代码）

#include #include

typedef 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\head=Create(num); ShowList(head);

printf(\"\\n请输入报数的人所在位置 :\\n\"); scanf_s(\"%d\

printf(\"\\n请输入参与者报数最大值 :\\n\"); scanf_s(\"%d\

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;i<=n;i++) /* 建立n个结点的单向链表*/ {

p->code=i; if(ip->next=(Jonse *)malloc(sizeof(Jonse)); /* 创建新的结点 */

p=p->next; } }

p->next=h; /* 最后返回头结点 ,完成单向循环链表的建立*/ return h; }

void ShowList(Jonse *h) /*打印链表函数*/ {

Jonse *p; p=h; do {

printf(\"%d\\ 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;kq=p;p=p->next; }

/*循环地删除队列结点*/ while(p!=p->next) {

for(k=1;kq=p;p=p->next; }

printf(\"%d\\ /* 输出被踢结点的位置 */ q->next=p->next;

free(p); /* 释放被踢出的结点 */

p=NULL; /* 让p指针赋值为空指针（即让其失效） */ p=q->next;

flag++; /* 标志位每次循环被踢出人数加1 */

if(flag==((num/2)-1))break; /* 当被踢人数达到一半时，跳出外层循环体 */ }

printf(\"%d\\n\ /* 输出被踢结点的位置 */ free(p); /* 释放被踢出的结点 */

p=NULL; /* 让p指针赋值为空指针（即让其失效） */ }