数据结构课程设计敢死队问题

《数据结构课程设计敢死队问题》由会员分享，可在线阅读，更多相关《数据结构课程设计敢死队问题（20页珍藏版）》请在装配图网上搜索。

1、河南城建学院数据结构课程设计说明书题目: 敢死队问题 院 系： 计算机科学与工程系 专业班级： 计算机科学与技术 学 号： 学生姓名： 同 组 人： 指导教师： 2010年 12 月 25 日 目录1需求分析11.1问题分析11.2程序执行的命令11.3数据测试12概要设计12.1 功能设计12.2抽象数据类型定义12.3 算法流程图23详细设计23.1 界面设计23.2 详细代码分析23.3 调试分析23.3.1调试结果23.3.2算法分析34总结3参考文献318线性表数据结构1需求分析1.本程序输入队伍人数n为任意的，最终输出记数的初始位置，首先输入一个报数上限m，当达到报数上限时，那名士

2、兵出列执行任务，从下个人开始记数，再次循环，直到只剩一人，得到其在队伍中的位置，通过数学思想求得题目要求即队长为首的情况下 需要记数初始位置。2.程序执行的命令包括： （1）构造数据结构；（2）数据输入；（3）执行队员出列；（4）输出要求数值 （5）结束。3.数据测试：当 n=10 输出结果为：要求的位置是：92概要设计2.1 功能设计本程序其实质是约瑟夫环问题,本次实验用了线性表数据结构,并运用模块化的程序设计思想,算法的实现是这样的:1. 定义类类型2. 定义变量并初始化3. 线性表初始化4. 当队员数小于等于1时,输出错误2.2 算法流程图开始声明数据类型定义变量并初始化初始化线性表输入

3、敢死队员总数敢死队员人数线性表长度队员报数报数值=偏移值?队员出列即L.elemi清零剩下的队员数1?输出增加存储分配图 1 算法流程图3详细设计3.1 头文件设置#include using namespace std;templateclass SeqList /顺序表类，T指定元素类型private:T *element;/动态数组存储顺序表的数据元素int size; /顺序表的数组容量int len; /顺序表长度public:SeqList(int size=100); /构造指定（默认）容量的空表T get(int i); /返回第i（i=0）个元素int set(int i,T

4、 x); /设置第i个元素为xint remove(int i); /删除第i个元素void insert(T x); /在顺序表最后插入xvoid insert(int i,T x);/-templateSeqList:SeqList(int size) /构造指定容量的空表this-size=sizeelement=new Tthis-size;this-len=0;/-template T SeqList:get(int i) /返回第i（i=0）个元素 /若i指定元素序号无效，则抛出异常if (i=0 & ilen)return elementi;throw 参数i指定元素序号无效;/

5、-templateint SeqList:set(int i,T x) /设置第i个元素为x /操作成功返回true，若i指定序号无效返回falseif(i=0 & ilen)elementi=x;return elementi ;return 0 ;/-templateint SeqList:remove(int i) /删除第i个元素if(len0 & i=0 & ilen)for(int j=i;jlen;j+)elementj=elementj+1; /元素前移，平均移动len/2len-;return 1; ;/-templatevoid SeqList:insert(T x) /在

6、顺序表最后插入x元素，函数重载insert(len,x);/-templatevoid SeqList:insert(int i,T x) /插入x，作为第i个元素if(len=size) /如果数组满，则扩充顺序表容量T*temp=element;element=new Tsize*2; /重新申请一个容量更大的数组for(int i=0;isize;i+)elementi=tempi;size*=2;if(ilen) i=len;for(int j=len-1;j=i;j-) /元素后移，平均移动len/2elementj+1=elementj;elementi=x;len+;3.2 详细

7、代码分析（1）模块一：判断输入是否满足条件int number,Surplus_members,count=0,i;/声明变量coutnumber;while(cin.fail()|number=1|getchar()=.)/判断输入是否合法，若不合法请重新输入cin.clear();/取消cin的fail状态,清除错误标志cin.sync(); / 这个函数是用来清空缓冲区的 cout您的输入有误！请查正后输入。(提示：请输入一个大于1的整数)nn;coutnumber;（2）主模块：实现总体功能SeqList L(number);/生成模板类对象Lfor(i=0;i1)/若剩余队员为，则循

8、环结束for(i=0;inumber;i+)if(L.get(i)!=0)count+;if(count=5) L.set(i,0); /数到5时给这名队员号数置0，以表示被派去执行任务count=0; /重新计数Surplus_members-;/剩余队员减for(i=0;inumber;i+)/用数学的思想找出所求位置，并用循环语句判断，输出所示计数位置if(L.get(i)!=0)if(number-L.get(i)+2)%number=0)cout从第number号战士开始计数才能让排长最后一个留下来而不去执行任务。;elsecout从第(number-L.get(i)+2)%numb

9、er号战士开始计数才能让排长最后一个留下来而不去执行任务。1?输出增加存储分配3详细设计3.1结点类型typedef struct node int data; node *next; lnode; /定义结点typedef struct lnode *cl; linklist;3.2模块的分析：主程序模块：void main() int i,number,start,count; linklist l;coutnumber; while(cin.fail()|number=1| getchar()=.)/判断输入是否合法，若不合法请重新输入cin.clear();/取消cin的fail状态,

10、清除错误标志cin.sync(); / 这个函数是用来清空缓冲区的cout您的输入有误！请查正后输入。n;cout number;构造单循环链表并初始化模块：for(start=1;startdata=1; for(i=2;idata=i; p-next=q; p=q; lnode *t=new lnode; /给最后一个结点赋值，并实现链表循环t-data=number; p-next=t; p=t; t-next=l.cl; p=l.cl; for(i=1;inext; count=0; while(count=number-1) for(i=1;inext; t-next=p-next;

11、 count+; p=t-next; if(p-data=1) /如果循环过程中数到排长去执行任务（即号码等于1）则跳出循环。break; cout从第start号战士开始计数才能让排长最后一个留下来而不去执行任务。1?输出增加存储分配3详细设计3.1模块的分析：构造队列模块#define QueueSize 1000 /假定预分配的队列空间最多为1000个元素typedef struct int dataQueueSize; int front;/头指针，若队列不空，指向队列头元素int rear; /尾指针，若队列不空，指向队列尾元素的下一个位置int count; /计数器，记录队中元素

12、总数CirQueue;队列运行模块void Initial(CirQueue *Q) /将顺序队列置空Q-front=Q-rear=0; Q-count=0; /计数器置 / 判队列空int IsEmpty(CirQueue *Q) return Q-front=Q-rear; /判队列满int IsFull(CirQueue *Q) return Q-rear=QueueSize-1+Q-front; /进队列void EnQueue(CirQueue *Q,int x) if (IsFull(Q) printf(队列上溢); /上溢,退出运行exit(1); Q-count +; /队列元

13、素个数加Q-dataQ-rear=x; /新元素插入队尾Q-rear=(Q-rear+1)%QueueSize; /循环意义下将尾指针加 /出队列int DeQueue(CirQueue *Q) int temp; if(IsEmpty(Q) printf(队列为空); /下溢,退出运行exit(1); temp=Q-dataQ-front; Q-count-; /队列元素个数减Q-front=(Q-front+1)%QueueSize; /循环意义下的头指针加1return temp; 主模块，实现总体功能void main() int M,i,start,count,j; CirQueue

14、 s; coutM; while(cin.fail()|M=1| getchar()=.)/判断输入是否合法，若不合法请重新输入cin.clear();/取消cin的fail状态,清除错误标志cin.sync(); / 这个函数是用来清空缓冲区的cout您的输入有误！请查正后输入。n;coutM;for(start=1;start=M;start+)/start为测试起点 Initial(&s); for(i=1;i=M;i+) EnQueue(&s,i); for(i=1;istart;i+) j=DeQueue(&s); EnQueue(&s,j); count=1; while(coun

15、tM) for(i=1;i5;i+) j=DeQueue(&s); EnQueue(&s,j); j=DeQueue(&s); count+; if(s.datas.front=1) break; cout从第start号战士开始计数才能让排长最后一个留下来而不去执行任务。endl; system(pause);3.2调试结果(1)系统界面3.3算法分析本次采用循环队列的数据结构方法实现，但其先进先出的算法结构加大了本程序的时间及空间复杂度。本次设计核心算法是4 总结通过这次课程设计我又学到了很多东西,如程序的模块化设计思想，同时也加深了对数据结构这门课程的理解和学会了如何在实际中应用数据结构这个方法是用队列循环来做的，实现的方法是这样的：首先从第一号开始报数，循环到指定的偏移位置删除结点，直至剩下一个结点。然后再比较一下它的号码是不是等于1，如果等于则输出开始计数位置，如果不等，山东师范大学继续循环查找，直到找出符合条件的计数起始位置，输出结果。参考文献1 朱振元. 数据结构(C+语言描述). 北京: 清华大学出版社,20072 严蔚敏 吴伟民. 数据结构(C语言版). 北京: 清华大学出版社,20093 互联网