黑龙江科技大学

课程设计说明书

（数据结构课程设计）

班级:   统计12-1     姓名:  包旭     

学号：          2012027159            

设计题目：     敢死队问题               

设计时间:__20##-11-5_____至___20##-11-25____

指导教师:______ __________________

评    语:________________________________

_________________________________________

_________________________________________

_________________________________________

_________________________________________

评阅成绩:＿＿   ＿＿评阅教师:＿＿   ＿＿＿

《数据结构》课程设计实验报告

开课实验室：基础实验室一                             20##  年11 月16 日

 

第二篇：数据结构课程设计报告—敢死队的问题

数据结构课程设计

系 别

专 业

班级学号 姓 名 指导教师 成 绩 计算机科学与技术

年 月 日

敢死队问题

问题描述

有M个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完成为止。

排长是不愿意去的，假设排长为1号，请你设计一程序，求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。

要求：至少采用两种不同的数据结构的方法实现。

一、单循环链表数据结构

(一) 需求分析

1.本程序任务是通过输入任意队伍人数n和报数上限m，输出使排长最后一个执行任务而开始记数的初始位置。首先输入队伍人数n，然后输入报数上限m(m<=n),从1号开始报数，当达到报数上限时，那名士兵出列执行任务，从下个人开始记数，再次循环，直到只剩一人，得到其在队伍中的位置，记下该位置视为排长位置，则1号即可视为最先报数的人，通过数学计算即可获得所求。

2.功能模块和流程：

1）功能模块

该程序功能比较单一，主要是为解决敢死队问题而设计。通过输入队伍人数和报数上限即可获得开始报数的位置。

2）程序流程

（1）构造链表（2）数据输入（3）执行删除（4）输出要求数值（5）结束

3.数据测试：

当 n=10，m=5, 输出结果为：要求的位置是：9。

(二) 详细设计

1.算法设计：

本程序其实质是约瑟夫环问题。从排长位置即1号开始报数，共有n个人，达到报数上限m=5的战士出列，继续进行报数，直到剩余最后一人，记下该位置为k。若将该位置视

为排长位置，则原先的1号位置即位所有的开始报数的位置z。则z=n-k+2。

2.以单循环链表为存储结构，包含三个模块：

（1）主程序模块

（2）构造链表并初始化

（3）删除结点

3.结点类型和指针类型

typedef struct node

{

int data;

struct node *next;

}LNode;/* 定义结点类型 */

LNode *p;

4.每个模块的分析

（1）主程序模块：

main()

{

LNode *p;

int m,n,z,y;

do

{

printf(" Please input the people number:\n");

scanf ("%d",&n);

}

while (n<=0);

do

{

printf(" Please input the excursion:\n");

scanf("%d",&m);

}

while (m<=0);

if (n=1)

printf("the position is: 1");

else

{

p=CREAT(n);

y=DELETE(p,m);

z=n-y+2;

if(z%n==0) /* 排除特殊情况 */

printf ("the position is:\n%d\n",z);

else

printf("the position is:\n%d\n",(n-y+2)%n);

}/* 通过数学思想求得实验要求情况下的数值 */

}

（2）构造单循环链表并初始化模块：

LNode* CREAT(int n) /* 创建循环链表 */

{

LNode *s,*q,*t;

int i;

if(n!=0)

{

t=q=(LNode *)malloc(sizeof(LNode));

q->data=1;/* 生成第一个结点并使其data值为1 */

for(i=2;i<=n;i++)

{

s=(LNode *)malloc(sizeof(LNode));/*自动生成结点*/ q->next=s;

q->next->data=i;/*给第i个结点赋值i*/

q=q->next;

}

q->next=t;

}/* 生成后续结点，并使其data值即为它所在链表（队伍）中的位置 */ return t;

}

（3）删除结点模块：

DELETE (LNode* t,int m)/* 链表的删除 */

{

LNode *a;int i;

while (t->next!=t)

{

for (i=1;i<m-1;i++)/*查找要删除结点的前一结点*/

t=t->next;

a=t->next;

t->next=a->next;

free(a);/*释放结点*/

t=t->next;

}/* while循环依次删除被点到的士兵 */

printf("\n");

return (t->data);

}

(三) 调试分析：

1.本程序运行后的结果应是如下提示：

Exit please input '0' Or Go on

Please input the tatal of the team:

输入队伍总人数

Please input the excursion:

输入间隔人数

结果显示：The wanted position is

选择的位置

2.在程序调试运行的过程中产生了各种各样的问题，有的是多了空格，有的是拼写错误，还有的是少了括号，类似的问题有很多。解决的办法是一遍遍尝试，不断逐行逐句进行修改。 例如程序调试过程中遇到警告：发现错误为 if(m=1)

后改正为 if(m==1)程序运行正确了，运行如下：

显示输出如图：

3.由程序分析可得：本程序时间复杂度为O（nm）!

4.①在设计生成循环单链表时，考虑到程序结果需要士兵的位序，故将每个结点的data值设置为他们在队列中的位置，方便返回。

②在删除单链表时，如果在报数时直接数到出列士兵则不方便链表的删除，可设置i<m-1找到出列士兵的前一位执行如下：

for (i=1;i<m-1;i++)/*查找要删除结点的前一结点*/

t=t->next;

a=t->next;

t->next=a->next;

free(a);/*释放结点*/

t=t->next;

③．在程序设计前，如果按原题所设，则需设队长为第一位，再分别测试从第几个开始才能符合条件。现在改变思想，通过数学思想：单循环链表本身是一个循环体，可先求出当从第一个出发的话，求出每隔m个出去一个最后是谁未出列，然后再设置它为链头，求出当他为队首时从第几个开始方能使其不出列。(n-y+2)%n 即可实现这功能！

5.经验与体会

通过这次课程设计我又学到了很多东西,如程序的模块化设计思想，同时也加深了对数据结构这门课程的理解和学会了如何在实际中应用数据结构.

这个方法是用单循环链表来做的，实现的方法是这样的：首先从第一号开始报数，循环到指定的偏移位置删除结点，直至剩下一个结点。然后设计输出，令这个位置为队长位置，队首为开始报数的位置，并按此输出即为所求。这种方法大大的降低了时间复杂度，复杂度为O(mn)。

（五）测试结果

（六）附件

typedef struct node

{

int data;

struct node *next;

}LNode;/* 定义结点类型 */

LNode* CREAT(int n) /* 创建循环链表 */

{

LNode *s,*q,*t;

int i;

if(n!=0)

{

t=q=(LNode *)malloc(sizeof(LNode));

q->data=1;/* 生成第一个结点并使其data值为1 */

for(i=2;i<=n;i++)

{

s=(LNode *)malloc(sizeof(LNode));/*自动生成结点*/

q->next=s;

q->next->data=i;/*给第i个结点赋值i*/

q=q->next;

}

q->next=t;

}/* 生成后续结点，并使其data值即为它所在链表（队伍）中的位置 */ return t;

}

DELETE (LNode* t,int m)/* 链表的删除 */

{

LNode *a;int i;

while (t->next!=t)

{

for (i=1;i<m-1;i++)/*查找要删除结点的前一结点*/

t=t->next;

a=t->next;

t->next=a->next;

free(a);/*释放结点*/

t=t->next;

}/* while循环依次删除被点到的士兵 */

printf("\n");

return (t->data);

}

main()

{

LNode *p;

int m,n,z,y;

printf("Exit please input '0' Or Go on...\nPlease input the tatal of the team:"); scanf ("%d",&n); /*输入队员总数*/

while(n!=0) /*当队员总数等于0时退出*/

{

do

{

printf("Please input the excursion:"); /*输入偏移数*/

scanf("%d",&m);

}

while (m<=0);

if(m==1)

printf("The wanted position is 1th.\n");

else

{

p=CREAT(n);

y=DELETE(p,m);

z=n-y+2;

if(z%n==0) /* 排除特殊情况 */

printf ("The wanted position is %dth:\n",z);

else

printf("The wanted position is %dth:\n",(n-y+2)%n);

}/* 通过数学思想求得实验要求情况下的数值 */

printf("Exit please input '0' Or Go on...\nPlease input the tatal of the team:");

scanf("%d",&n); /*输入敢死队员总数*/

}

}

二．线性表数据结构

(一)需求分析

1.本程序任务是通过输入任意队伍人数n和报数上限m，输出使排长最后一个执行任务而开始记数的初始位置。首先输入队伍人数n，然后输入报数上限m(m<=n),从1号开始报数，当达到报数上限时，那名士兵出列执行任务，从下个人开始记数，再次循环，直到只剩一人，得到其在队伍中的位置，记下该位置视为排长位置，则1号即可视为最先报数的人，通过数学计算即可获得所求。

2.功能模块和流程：

1）功能模块

该程序功能比较单一，主要是为解决敢死队问题而设计。通过输入队伍人数和报数上限即可获得开始报数的位置。

2）程序流程

如下图。

3.数据测试：

当 n=10 输出结果为：要求的位置是：9

（二）详细设计

1.算法思想: 本程序其实质是约瑟夫环问题,本次实验用了线性表和循环队列两种数据结构,并运用模块化的程序设计思想,算法的实现是这样的:

（1） 定义结构体类型

（2） 定义变量并初始化

（3） 线性表初始化

（4） 队员报数,是5的倍数出列

（5） 当队员数等于1时,输出 流程图

从排长位置即1号开始报数，共有n个人，达到报数上限m=5的战士出列，继续进行报数，直到剩余最后一人，记下该位置为k。若将该位置视为排长位置，则原先的1号位置即位所有的开始报数的位置z。则z=n-k+2。

2.模块设计：

宏定义:

#define LIST_INIT_SIZE 100

#define LISTINCCREMENT 10

数据类型定义:typedef int ElemType;

定义数据结构:

typedef struct KList /*定义数据结构体类型*/

{

ElemType *elem; /*存储空间基址*/

int length; /*当前长度*/

int listsize; /*当前分配的存储容量(以sizeof(ElemType)为单位)*/

}SqList;

模块一:创建线性表函数

SqList InitList_Sq() /*创建线性表函数*/

{

SqList L;

L.elem=(ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));

if(!L.elem) printf("Fail in new creat list"),exit(0); /*存储分配失败*/

else

{

L.length=0; /*空表长度为0*/

L.listsize=LIST_INIT_SIZE; /*初始存储容量*/

}

}

模块二: 线性表再分配函数

SqList ListInsert_Sq(SqList L) /*线性表再分配函数*/

{

/*SqList L;*/

int *newbase;

newbase=(ElemType *)realloc(L.elem,

(L.listsize+LISTINCCREMENT)*sizeof(ElemType));

/*为顺序表增加一个大小为存储LISTINCCREMENT个数据元素的空间*/ if(!newbase) printf("Fail in new add list"),exit(0);/*存储分配失败*/

else

{

L.elem=newbase; /*新基址*/

L.listsize+=LISTINCCREMENT; /*增加存储容量*/

}

}

主模块:实现总体功能

main()

{

SqList L;

int s,i,m,count=0; /*声明变量*/

L=InitList_Sq();

printf("Please input the tatal of the team:");

scanf("%d",&m); /*输入敢死队员总数*/

while(m!=0)/*当输入为0时退出程序*/

{

while(m>L.length) /*当顺序表当前分配的存储空间大小不足时进行再分配*/ L=ListInsert_Sq(L);

for(i=0;i<m;i++) L.elem[i]=i+1; /*为队员赋值*/

s=m;

i=0;

while(s>1) /*当所剩敢死队员总数为1时,总循环结束*/

{

for(i=0;i<m;i++)

if(L.elem[i]!=0)

{

count++;

if(count==5) /*报数循环*/

{

L.elem[i]=0; /*表示队员出列*/

count=0; /*计数器清零*/

s--; /*敢死队员数-1*/

}

}

}

for(i=0;i<m;i++) /*输出*/

if(L.elem[i]!=0)

if((m-L.elem[i]+2)%m==0) /**/

printf("\nThe wanted order is %dth\n",m);

else

printf("\nThe wanted order is %dth\n",(m-L.elem[i]+2)%m);

printf("Exit please input '0' Or Go on...\nPlease input the tatal of the team:"); scanf("%d",&m); /*输入敢死队员总数*/

}

}

（三）调试分析

1.程序正常运行后应该为：

exit please input ‘0’or go on…

please input the total of the team

输入总共人数

The wanted position is th

输出所求的开始报数位置

2. 在程序调试运行的过程中产生了各种各样的问题，有的是多了空格，有的是拼写错误，还有的是少了括号，类似的问题有很多。解决的办法是一遍遍尝试，不断逐行逐句进行修改。 例如程序调试过程中出现了下面的警告

:

经查询错误为:不可移动的指针（地址常数）赋值

最终发现是下面的定义错误造成的

在变量定义中int *newbase =0;

定义成了 int newbase =0;

经改正程序运行正常了

.

3.经验与体会

通过这次课程设计我又学到了很多东西,如程序的模块化设计思想，同时也加深了对数据结构这门课程的理解和学会了如何在实际中应用数据结构编程。

我首先是用线性表来做的，开始的想法是想用试验的方法来查找到所要求的位置，即首先从第一号开始报数，然后检查最后剩下的一个是否是队首，然后从第二个开始报数……从第三个开始报数……直到所剩下的最后一个是队首。虽然这种方法可以实现查找，可却是以消耗更多的时间为代价的，于是我又想到了这个方法：总是从第一个开始报数，报到5出列，直到剩下最后一个为止，然后就令这个位置为队长位置，队首为开始报数的位置，并按此设

计输出即可。这种方法大大的降低了时间复杂度，复杂度为O(mn)。

（四）测试结果

（五）附件

程序源代码:

#define LIST_INIT_SIZE 100

#define LISTINCCREMENT 10

typedef int ElemType;

typedef struct KList /*定义数据结构体类型*/

{

ElemType *elem; /*存储空间基址*/

int length; /*当前长度*/

int listsize; /*当前分配的存储容量(以sizeof(ElemType)为单位)*/ }SqList;

SqList InitList_Sq() /*创建线性表函数*/

{

SqList L;

L.elem=(ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType)); if(!L.elem) printf("Fail in new creat list"),exit(0); /*存储分配失败*/ else

{

L.length=0; /*空表长度为0*/

L.listsize=LIST_INIT_SIZE; /*初始存储容量*/

}

}

SqList ListInsert_Sq(SqList L) /*线性表再分配函数*/

{

/*SqList L;*/

int *newbase;

newbase=(ElemType *)realloc(L.elem,

(L.listsize+LISTINCCREMENT)*sizeof(ElemType));

/*为顺序表增加一个大小为存储LISTINCCREMENT个数据元素的空间*/ if(!newbase) printf("Fail in new add list"),exit(0);/*存储分配失败*/

else

{

L.elem=newbase; /*新基址*/

L.listsize+=LISTINCCREMENT; /*增加存储容量*/

}

}

main()

{

SqList L;

int s,i,m,count=0; /*声明变量*/

L=InitList_Sq();

printf("Please input the tatal of the team:");

scanf("%d",&m); /*输入敢死队员总数*/

while(m!=0)/*当输入为0时退出程序*/

{

while(m>L.length) /*当顺序表当前分配的存储空间大小不足时进行再分配*/ L=ListInsert_Sq(L);

for(i=0;i<m;i++) L.elem[i]=i+1; /*为队员赋值*/

s=m;

i=0;

while(s>1) /*当所剩敢死队员总数为1时,总循环结束*/

{

for(i=0;i<m;i++)

if(L.elem[i]!=0)

{

count++;

if(count==5) /*报数循环*/

{

L.elem[i]=0; /*表示队员出列*/

count=0; /*计数器清零*/

s--; /*敢死队员数-1*/

}

}

}

for(i=0;i<m;i++) /*输出*/

if(L.elem[i]!=0)

if((m-L.elem[i]+2)%m==0) /**/

printf("\nThe wanted order is %dth\n",m);

else

printf("\nThe wanted order is %dth\n",(m-L.elem[i]+2)%m);

printf("Exit please input '0' Or Go on...\nPlease input the tatal of the team:\n"); scanf("%d",&m); /*输入敢死队员总数*/

}

}

参考文献

1. 谭浩强《c程序设计》

2.李业丽，郑良斌《数据机构（c）实验教程》