发布时间 : 星期六 文章数据结构课程设计报告—敢死队的问题更新完毕开始阅读
数据结构课程设计
系 别 专 业 班级学号 姓 名 指导教师 成 绩
计
年
月 日
敢死队问题
问题描述
有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(\ scanf (\ }
while (n<=0); do {
printf(\ scanf(\ }
while (m<=0); if (n=1)
printf(\ else {
p=CREAT(n); y=DELETE(p,m); z=n-y+2;
if(z%n==0) /* 排除特殊情况 */
printf (\ else
printf(\ }/* 通过数学思想求得实验要求情况下的数值 */
}
（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
t->next=a->next; free(a);/*释放结点*/ t=t->next;
}/* while循环依次删除被点到的士兵 */ printf(\ return (t->data); }
(三) 调试分析：
1.本程序运行后的结果应是如下提示： Exit please input '0' Or Go on Please input the tatal of the team: 输入队伍总人数