数据结构常见问题：12单元28 敢死队问题

数据结构课程常见问题 -单元28 敢死队问题1敢死队问题求解解析：问题描述有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 (mdata=1;/* 生成第一个结点并使其data值为1 */ for(i=2;inext=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;inext; 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)程序运行正确了，运行如下：显示输出如图：