课程设计报告书.docx
《课程设计报告书.docx》由会员分享，可在线阅读，更多相关《课程设计报告书.docx（15页珍藏版）》请在冰点文库上搜索。
课程设计报告书
数
据
结
构
课
程
设
计
题目：
敢死队问题
指导老师：
张延红
同组人员：
邹霞
姓名：
朱东昌
学号：
061408155
一、题目：
16、敢死队问题1
二、设计内容：
分别用两种数据结构解决敢死队问题2
1、用数组实现2
2、用链表实现2
三、概要设计2
1、数组实现2
2、链表实现2
四、算法描述3
1、数组实现3
（1）main函数3
（2）result函数5
（3）remain函数6
2、链表实现7
（1）main函数7
（2）result函数9
（3）remain函数10
（4）InitList函数11
五、算法分析13
六、心得体会和参考材料13
一、题目：
16、敢死队问题
有M个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。
如果前一个战士没完成任务，则要再派一个战士上去。
现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。
如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。
以此类推，直到任务完成为止。
排长是不愿意去的，假设排长为1号，请你设计一程序，求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。
要求：
至少采用两种不同的数据结构的方法实现。
如果采用三种以上的方法者，可加分。
二、设计内容：
分别用两种数据结构解决敢死队问题
1、用数组实现
2、用链表实现
三、概要设计
1、数组实现
三大模块
2、链表实现
四大模块
四、算法描述
1、数组实现
（1）main函数
流程图
代码
intmain（）
{
intM=0;
printf（"请输入敢死队员的总数M"）;
Loop:
scanf（"%d",&M）;
if（M<2||M>1000）
{
printf（"输入有误请重新输入:
"）;
gotoLoop;
}
printf（"\n需要从一下队员开始计数\n\n"）;
result（M）;
system（"pause"）;
return0;
}
（2）result函数
流程图
代码
voidresult（intm）
{
intk;
for（inti=1;i<=m;i++）
{
for（inti1=1;i1<=m;i1++）
a[i1]=i1;
k=remain（i,m）;
if（k==1）
printf（"第%d号",i）;
}
printf（"\n\n"）;
}
（3）remain函数
流程图
代码intremain（inti,intm）
{
intcount=0,next=i,del=0;
while（del{
if（a[next]!
=0）
{
count++;
if（count==5）
{
a[next]=0;
count=0;
del++;
}
}
next++;
if（next>m）
next=next-m;
}
for（inti1=1;i1<=m;i1++）
if（a[i1]!
=0）
returni1;
return0;
}
2、链表实现
（1）main函数
流程图
代码
intmain（）
{
intM=0;
printf（"请输入敢死队员的总数M"）;
Loop:
scanf（"%d",&M）;
if（M<2）
{
printf（"输入有误请重新输入:
"）;
gotoLoop;
}
printf（"\n需要从一下队员开始计数\n\n"）;
result（M）;
system（"pause"）;
return0;
}
（2）result函数
流程图
代码
voidresult（intm）
{
intk;
LinkListp;
for（inti=1;i<=m;i++）
{
p=InitList（m）;
k=remain（i,p）;
if（k==1）
printf（"第%d号",i）;
}
printf（"\n\n"）;
}
（3）remain函数
流程图
代码
intremain（inti,LinkListL）
{
LNode*pre=L,*pcurr=L;
for（inti1=1;i1<=i-2;i1++）
pre=pre->next;
pcurr=pre->next;
if（i==1）
{
pcurr=L;
pre=Null;
}
while（pre!
=pcurr）
{
for（inti2=1;i2<=4;i2++）
{
pre=pcurr;
pcurr=pcurr->next;
}
pre->next=pcurr->next;
free（pcurr）;
pcurr=pre->next;
}
intk=pcurr->data;
free（pcurr）;
returnk;
}
（4）InitList函数
流程图
代码
LinkListInitList（intm）
{
LinkListL=Null;
LNode*p=Null;
for（inti=m;i>=1;i--）
{
p=（LinkList）malloc（sizeof（LNode））;
p->data=i;
p->next=L;
L=p;
}
for（inti1=1;i1<=m-1;i1++）
p=p->next;
p->next=L;
returnL;
}
五、算法分析
remain是核心函数它的参数i表示从第i个人开始数起，返回值是最后剩下的敢死队员的号，所以只要有了remain函数用result调用它用一个for循环分别把i从1变到M，如果他的返回值是1，也就是说最后剩下的是排长，那么这个i就是要求的起始队员号。
具体实现remain函数时，用数组实现与用链表实现有些不同，用数组实现时，用一个标记next一个一个向后走，起始next=1当a【next】！
=0时，用count计数，起始count为0，当count为5时count重新别为0，且把a【next】=0，相当于将它删除，当next>M时，将next重新变为1，相当于将这个数组变为循环队列。
它时间复杂度度为
O（n2）。
当用链表实现时，多写了一个IntiList函数，用它来构造一个长度为M的循环链表，同样用remain函数来对这个循环链表操作，一次删除一个队员，直到删除M-1个队员为止，剩下的一个队员作为remain函数的返回值。
同样用result调用remain函数即可求出结果。
时间复杂度O（n2）。
虽然时间复杂度都为O（n2），但是数组实现时做了好多无用的操作，用链表实现更快一些。
六、心得体会和参考材料
通过这次课程设计我感觉自己分析问题解决问题的能力有待提高，特别是把复杂问题逐步细化分成若干小问题的能力，这就是过程编程所需要的重要能力。
今后一定要多联系，多编程，逐步调高自己编程能力，调试能力，分析解决问题的能力。
参考材料：
1、严蔚敏吴伟民编著的《数据结构》清华大学出版社
2、谭浩强编著《c程序设计》（第三版）清华大学出版社
升级会员 