敢死队问题

《敢死队问题》由会员分享，可在线阅读，更多相关《敢死队问题（13页珍藏版）》请在装配图网上搜索。

1、福 建 工 程 学 院 课 程 设 计 课 程：数据结构课程设计 题 目：敢死队问题 专 业：计算机科学与技术 班 级：计算机1001 学 号：3100301118 姓 名：林国辉 指 导 老 师：蒋建辉 刘建华 林芳 设 计 时 间：2011.12.22-2011.12.28 实验题目：敢死队问题1、 要解决的问题有M 个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮 回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5 时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果

2、此战士没完成任 务，再从下一个战士开始数数，被数到第 5 时，此战士接着去执行 任务。以此类推，直到任务完成为止。排长是不愿意去的，假设排长为 1 号，请你设计一程序，求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。2、 算法基本思想描述 1.链表实现 首先从第一号开始报数，循环到指定的偏移位置,删除该结点，直至剩下一个结点。然后返回该结点元素，通过公式计算出从哪里开始计数。 2.队列实现首先从第一号开始报数，循环到指定的偏移位置删除结点，直至剩下一个结点。然后再比较一下它的号码是不是等于1，如果等于则输出开始计数位置，如果不等，继续循环查找，直到找出符合条件的计数起始位置，输

3、出结果。3、 设计1. 数据结构的设计和说明链表实现typedef struct node /*定义结构体 链表*/ int data; struct node *next;LinkNode; /* 定义结点类型 */队列实现#define MAXSIZE 100 /*假定预分配的队列空间最多为100个元素*/typedef structint dataMAXSIZE;int front;int rear;int count; /*计数器，记录队中元素总数*/SeqQueue;2. 关键算法的设计 链表实现int Delete(LinkNode* t) /* 链表的删除 */ LinkNode

4、 *a;int i; while (t-next!=t) /*while循环依次删除被点到的士兵*/ for (i=1;inext; a=t-next; t-next=a-next; /*执行删除操作，删除数据*/ free(a); /*释放结点*/ t=t-next; printf(n); return (t-data); /*返回t的值*/void main() LinkNode *p; int m,n,z,y; printf(请输入士兵总数:); scanf (%d,&n); /*输入队员总数*/ /*当队员总数等于0时退出*/ p=Creat(n); /*创建链表p*/ y=Delet

5、e(p); /*选出去炸碉堡的人 调用删除函数*/ z=n-y+2; if(z%n=0) /* 排除特殊情况 */ printf (从第%d号开始计数排长最后一个留下来而不去执行任务:n,z); else printf(从第%d号开始计数排长最后一个留下来而不去执行任务:n,(n-y+2)%n); /* 通过数学思想求得实验要求情况下的数值 */队列实现 int begin,count,i,j,num; SeqQueue *s; printf(请输入敢死队的人数：); scanf(%d,&num); for(begin=1;begin=num;begin+)/*begin为测试起点*/ s=I

6、nitial(); for(i=1;i=num;i+) EnQueue(s,i); for(i=1;ibegin;i+) j=DeQueue(s); EnQueue(s,j);/*把对头的元素取出来然后放到对尾去， 经过这个循环以后，要从那个开始的士兵的编号就会在队的 对头位置了*/ count=1;/*删除结点数*/ while(countnum) for(i=1;idatas-front=1)/*此时队只剩一个点，如果是排长就输出*/ break;printf(从第%d号战士开始计数排长最后一个留下来而不去执行任务。n,begin);3. 模块结构图及各模块的功能 主函数 1.链表实现 2

7、.队列实现创建队列创建链表删除查找到的节点元素（报数为5）判断队空或队满入队，报数为5出队 找出从哪里计数找出从哪里计数Dfg发给流程图： 开始链表实现创建循环单链表 并存入士兵号数（升序号数从1开始）从号数为1的士兵开始报数）Y剩下士兵数=1？N返回该士兵号数x 士兵报数（从1开始以5为循环）Z=士兵总数nx+2 NZ%n=0？报数值=5？NYY 删除该士兵Y=(nx+2)%nY=Z输出Y 结束队列实现 开始 i=1创建队列，士兵按升序入队(号数从1开始）从i开始报数i前号数按序出队并入队尾 i+Y剩余士兵数=1？NN剩下士兵号数为1 士兵报数（从1开始以5为循环）士兵出队并入队尾 NY报数

8、值=5？输出iY 结束士兵出列即删除该士兵4、 源程序清单#include#define MAXSIZE 100typedef struct int dataMAXSIZE; int front; int rear; int count; /*计数器,记录队中元素总数*/SeqQueue;typedef struct node /*定义结构体 链表*/ int data; struct node *next;LinkNode; /*定义结点类型*/*链表*/LinkNode* Creat(int n) /*创建链表*/ LinkNode *s,*q,*t; int i; if(n!=0) t=

9、q=(LinkNode *)malloc(sizeof(LinkNode); /*生成第一个结点*/ q-data=1; /*使其data值为1*/ for(i=2;inext=s; /*把q的节点指向s*/ q-next-data=i; /*给第i个结点赋值i*/ q=q-next; /*q指向的结点向后移一位*/ q-next=t; /*生成后续结点，并使其data值即为它所在链表（队伍）中的位置*/ return t; /*返回头结点，形成循环链表*/int Delete(LinkNode* t,int m) /*链表的删除*/ LinkNode *a;int i; while (t-n

10、ext!=t) /*while循环依次删除被点到的士兵*/ for (i=1;inext; a=t-next; t-next=a-next; /*执行删除操作，删除数据*/ free(a); /*释放结点*/ t=t-next; printf(n); return (t-data); /*返回t的值*/*队列*/void Initial(SeqQueue *Q) Q-front=Q-rear=0; Q-count=0; /*计数器置空*/*判队列空*/int Empty(SeqQueue *Q) Q-rear=Q-front;/*判队列满*/int Full(SeqQueue *Q) retu

11、rn (Q-rear+1)%MAXSIZE=Q-front;/*入队列*/void EnQueue(SeqQueue *Q,int x) if (Full(Q) printf(队列上溢); /*上溢,退出运行*/ return 0; else Q-count +; /*队列元素个数加1*/ Q-dataQ-rear=x; /*新元素插入队尾*/ Q-rear=(Q-rear+1)%MAXSIZE; /*新队尾位置*/*出队列*/int DeQueue(SeqQueue *Q) int item; if(Empty(Q) printf(队列为空); /*下溢,退出运行*/ return 0; e

12、lse item=Q-dataQ-front; Q-count-; /*队列元素个数减1*/ Q-front=(Q-front+1)%MAXSIZE; /*新队首位置*/ return item;/*菜单*/void menu() printf(-n); printf( 敢死队问题 n); printf(-n); printf( 1.链表 | 2.队列 n); printf(- n); printf( 3.退出 n); printf(- n); printf(请选择方法:);/*主函数*/void main() printf(计算机1001 林国辉 3100301118n); int x; i

13、nt m,n,z,y; int begin,count,i,j,num; LinkNode *p; SeqQueue s; menu(); while(x!=3) scanf(%d,&x); switch(x) case 1: printf(请输入士兵总数:); scanf (%d,&n); /*输入队员总数*/ p=Creat(n); /*创建链表p*/ y=Delete(p); /*选出去炸碉堡的人 调用删除函数*/ z=n-y+2; if(z%n=0) /*排除特殊情况*/ printf (从第%d号开始计数排长最后一个留下来而不去执行任务。n,z); else printf(从第%d号

14、开始计数排长最后一个留下来而不去执行任务。n,(n-y+2)%n); /* 通过数学思想求得实验要求情况下的数值 */ break; case 2: printf(请输入士兵的人数:); scanf(%d,&num); for(begin=1;begin=num;begin+)/*begin为测试起点*/ Initial(&s); for(i=1;i=num;i+) EnQueue(&s,i); for(i=1;ibegin;i+) j=DeQueue(&s); EnQueue(&s,j);/*把对头的元素取出来然后放到对尾去， 经过这个循环以后，要从那个开始的士兵的编号就会在队的对头位置了*

15、/ count=1;/*删除结点数*/ while(countnum) for(i=1;i5;i+) j=DeQueue(&s); EnQueue(&s,j);/*把对头的元素取出来然后放到对尾*/ /*经过这个循环以后，对头的那个节点的值就是数到5对应的节点*/ j=DeQueue(&s);/*把这个节点出队，但是没有在把它放到对尾，就相当于把它删除了*/ count+; if(s.datas.front=1)/*此时队只剩一个点，如果是排长就输出*/ break; printf(从第%d号战士开始计数排长最后一个留下来而不去执行任务。nn,begin); break; case 3: return 0; default:printf(输入错误，请从新输入n); menu(); 5、 测试数据及测试结果1. 循环链表实现 测试数据：士兵数：2测试结果：2. 循环队列实现测试数据： 士兵数：9测试结果：6、 课程设计总结及心得体会 几天的实习很快就过去了，经过这几天的学习，不仅仅只是完成了学校的教学任务，更是对这学期的所学的一次巩固和提高。 在编程，调试，测试中进一步掌握了链表、队列的知识，而且对程序的模块化设计思想有了进一步的认识。 总之，通过这次实习，让我对数据结构有更大的兴趣，让我对自己的专业更加有信心。