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

I河南城建学院数据结构课程设计说明书题目:敢死队问题院系：计算机科学与工程系专业班级：计算机科学与技术学号：学生姓名：同组人：指导教师：2010年12月25日II目录1需求分析...............................................................................11.1问题分析.........................................错误!未定义书签。1.2程序执行的命令.............................错误!未定义书签。1.3数据测试.........................................错误!未定义书签。2概要设计...............................................................................12.1功能设计........................................................................12.2抽象数据类型定义......................错误!未定义书签。2.3算法流程图....................................................................23详细设计...............................................................................33.1界面设计........................................................................33.2详细代码分析................................................................43.3调试分析........................................................................63.3.1调试结果................................................................63.3.2算法分析................................................................64总结........................................................................................6参考文献....................................................................................171线性表数据结构1需求分析1.本程序输入队伍人数n为任意的，最终输出记数的初始位置，首先输入一个报数上限m，当达到报数上限时，那名士兵出列执行任务，从下个人开始记数，再次循环，直到只剩一人，得到其在队伍中的位置，通过数学思想求得题目要求即队长为首的情况下需要记数初始位置。2.程序执行的命令包括：（1）构造数据结构；（2）数据输入；（3）执行队员出列；（4）输出要求数值（5）结束。3.数据测试：当n=10输出结果为：要求的位置是：92概要设计2.1功能设计本程序其实质是约瑟夫环问题,本次实验用了线性表数据结构,并运用模块化的程序设计思想,算法的实现是这样的:1.定义类类型2.定义变量并初始化3.线性表初始化4.当队员数小于等于1时,输出错误22.2算法流程图图1算法流程图开始声明数据类型定义变量并初始化初始化线性表输入敢死队员总数敢死队员人数线性表长度队员报数报数值=偏移值?队员出列即L.elem[i]清零剩下的队员数1?输出增加存储分配33详细设计3.1头文件设置#includeiostreamusingnamespacestd;templateclassTclassSeqList//顺序表类，T指定元素类型{private:T*element;//动态数组存储顺序表的数据元素intsize;//顺序表的数组容量intlen;//顺序表长度public:SeqList(intsize=100);//构造指定（默认）容量的空表Tget(inti);//返回第i（i=0）个元素intset(inti,Tx);//设置第i个元素为xintremove(inti);//删除第i个元素voidinsert(Tx);//在顺序表最后插入xvoidinsert(inti,Tx);};//------------------------------------------------------------------------------------------templateclassTSeqListT::SeqList(intsize)//构造指定容量的空表{this-size=size100?100:size;this-element=newT[this-size];this-len=0;};//------------------------------------------------------------------------------------------templateclassTTSeqListT::get(inti)//返回第i（i=0）个元素{//若i指定元素序号无效，则抛出异常if(i=0&&ilen)returnelement[i];throw参数i指定元素序号无效;};//------------------------------------------------------------------------------------------templateclassTintSeqListT::set(inti,Tx)//设置第i个元素为x{//操作成功返回true，若i指定序号无效返回falseif(i=0&&ilen){element[i]=x;returnelement[i];}4return0;};//------------------------------------------------------------------------------------------templateclassTintSeqListT::remove(inti)//删除第i个元素{if(len0&&i=0&&ilen){for(intj=i;jlen;j++)element[j]=element[j+1];//元素前移，平均移动len/2len--;}return1;};//------------------------------------------------------------------------------------------templateclassTvoidSeqListT::insert(Tx)//在顺序表最后插入x元素，函数重载{insert(len,x);};//------------------------------------------------------------------------------------------templateclassTvoidSeqListT::insert(inti,Tx)//插入x，作为第i个元素{if(len==size)//如果数组满，则扩充顺序表容量{T*temp=element;element=newT[size*2];//重新申请一个容量更大的数组for(inti=0;isize;i++)element[i]=temp[i];size*=2;}if(i0)i=0;//序号容错if(ilen)i=len;for(intj=len-1;j=i;j--)//元素后移，平均移动len/2element[j+1]=element[j];element[i]=x;len++;};3.2详细代码分析（1）模块一：判断输入是否满足条件intnumber,Surplus_members,count=0,i;//声明变量cout请输入队员总数：;5cinnumber;while(cin.fail()||number=1||getchar()=='.')//判断输入是否合法，若不合法请重新输入{cin.clear();//取消cin的fail状态,清除错误标志cin.sync();//这个函数是用来清空缓冲区的cout您的输入有误！请查正后输入。(提示：请输入一个大于1的整数)\n\n;cout请输入队员总数：;cinnumber;}（2）主模块：实现总体功能SeqListintL(number);//生成模板类对象Lfor(i=0;inumber;i++)//给队员排号L.insert(i+1);Surplus_members=number;while(Surplus_members1)//若剩余队员为，则循环结束{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)%number号战士开始计数才能让排长最后一个留下来而不去执行任务。endl;}63.3调试分析3.3.1调试结果(1)系统界面算法分析本次设计问题的核心在于算法，因为这影响到了程序的时间复杂度。输出设计是这样实现的：总是从第一个开始报数，报到5用置0方法表示出列。在每次循环中，只要符合公式：number-L.get(i)+2)%number==0则用number输出，否则用number-L.get(i)+2)%number输出报数位置。假设输入队员总数为n每次比较只需要m次，所以其时间复杂度为O(mn)。4总结通过这次课程设计我又学到了很多东西,如程序面向对象的设计思想，同时也加深了对数据结构这门课程的理解和学会了如何在实际中应用数据结构编程。7我首先是用线性表来做的，开始的想法是想用试验的方法来查找到所要求的位置，即首先从第一号开始报数，然后检查最后剩下的一个是否是队首，然后从第二个开始报数……从第三个开始报数……直到所剩下的最后一个是队首。虽然这种方法可以实现查找，可却是以消耗更多的时间为代价的，于是我又想到了这个方法：总是从第一个开始报数，报到5出列，直到剩下最后一个为止，然后就令这个位置为队长位置，队首为开始报数的位置，并按此设计输出即可。循环单链表数据结构1需求分析1.本程序输入队伍人数n为任意的，最终输出记数的初始位置，首先输入一个报数上限m，当达到报数上限时，那名士兵出列执行任务，从下个人开始记数，再次循环，直到只剩一人，得到其在队伍中的位置，通过数学思想求得题目要求即队长为首的情况下需要记数初始位置。2.程序执行的命令包括：（1）构造链表；（2）数据输入；（3）执行删除；（4）输出要求数值（5）结束。2概要设计2.1功能设计以单循环链