生死者游戏.doc

数据结构
课程设计报告书
班级计算机121班
学号 1208010117
姓名张航
指导老师刘勇
课程设计的名称:生死者游戏问题
1. 问题描述:有n个旅客同乘一条船,因为严重超载,加上风高浪大,危险万分;因此船长告诉乘客,只有将全船一半的旅客投入大海,,大家只得同意这种办法,并议定n个人围坐一圈,从1,2,3…到n进行编号。由第一个人数起,依次报数,数到第m人,将它扔进大海中,然后再从他的下一个人数起,数到第m人,再将他扔进大海,如此循环进行,直到剩下一半人为止,问哪几个人是将被扔进大海的人。
2. 基本要求:
(1)输入总人数n和报数上限m;
(2)建立一个有n个结点不带头结点的单循环链表;
(3)输出死者和生者的编号。
3. 算法思想:
DeleteDeath()函数是实现问题要求的主要函数,其算法思想是:利用已建立的有n个结点不带头结点的单循环链表,根据报数上限m,在链表的“第一个结点”开始从1计数,计到m-1时,将下一个结点从链表中删除,然后再从被删除结点的下一个结点开始从1计数,数到m-1,再将其下一个结点从单循环链表中删除,如此循环直至单循环链表剩下一半结点为止。
4. 模块划分:
(1)不带带头结点的单循环链表抽象数据类型List,其中包括基本操作的函数有:初始化操作函数CreateList()。。
(2)LinkList DeleteDeath(int n,int m,LinkList &L),其功能是根据报数上限m,删除不带头结点的含n个结点的单循环链表L中的相应结点。
(3)void OutputLife(LinkList L),其功能是输出不带头结点的单循环链表L。
(4)void main(),主函数,功能是输入总人数及报数上限,输出死者和生者。
5. 数据结构:
(1)不带头结点单循环链表抽象数据类型List。
(2)不带头结点单循环链表抽象数据类型的结点结构定义如下:
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
6. 源程序:
源程序存放在两个文件中,,。
源代码:
/**/
#include<>
#include<>
#define ElemType int
typedef struct LNode{//单循环链表的结点结构
ElemType data;
struct LNode *next;
}LNode,*LinkList;
/*建立单循环链表函数*/
void CreateList(LinkList &L,int n){
int i;
LinkList p,q;
L = p = (LinkList)malloc(sizeof(LNode));
for(i=1;i<n;i++){
q = (LinkList)malloc(sizeof(LNode));
p->data = i;
p->next = q;