数据结构实践报告

数据结构实践报告数据结构实践报告学号:150906112姓名:武锦蓉班级:NET2班指导老师:田喜平时间:2016-12-21数据结构实践报告全文共7页，当前为第1页。数据结构实践报告全文共7页，当前为第1页。项目名称项目构思程序由三个模块组成:(1)输入模块:无提示语句,直接输入总人数n与报数次数m,中间用逗号隔开。(2)处理模块:将元素储存于顺序表中。在主函数中根据报数间隔确定需要删除的元素的位置,在顺序表中设置该位置并删除该位置,同时输出该位置的值。反复设置并删除直到表空。(3)输出模块:分别在DOS下与文件中,按移除元素的顺序依次显示其位置。约瑟夫环问题中的数据就是人所在的位置,而这种数据就是存在“第一元素、最后元素”,并且存在“唯一的前驱与后继的”,符合线性表的特点。由于需要模拟约瑟夫环的出列问题,可以采用顺序表来实现线性表,完成出列顺序的输出。核心算法主要分为两步:1、确定需要删除的位置,2、设置并删除该位置。已知报数间隔m,我们可以把当前位置加上m获得需要删除的位置,如果获得的位置超过顺序表中实际元素的总长度,则可以通过减去数组的实际长度来修正(即模拟环状计数)。然后把顺序表中的当前指向位置设置为该位置,继而删掉该位置。反复进行上述确定位置与删除位置的操作,直到顺序表为空。程序主要功能模块1、输入的形式与输入值的范围:每一次输入的值为两个正整数,中间用逗号隔开。若分别设为n,m,则输入格式为:“n,m”。不对非法输入做处理,即假设输入都就是合法的。2、输出的形式:输出格式1:在字符界面上输出这n个数的输出序列输出格式2:将这n个数的输出序列写入到文件中3、程序所能达到的功能:对于输入的约瑟夫环长度n与间隔m,输出约瑟夫环的出列顺序。4、测试数据:包括正确的输入及其输出结果与含有错误的输入及其输出结果。正确:输入:10,3输出:36927185104数据结构实践报告全文共7页，当前为第2页。输入:41,3数据结构实践报告全文共7页，当前为第2页。输出:3691215182124273033363915101419232832374171320263440817293811252224351631错误:输入:103输出:68713429510程序清单抽象数据类型的定义:为实现上述程序的功能,可以用整数存储用户的输入。并将用户输入的值存储于线性表中。线性表ADT定义如下:ADTlist数据对象:整形数据关系:线性关系,即<ai,ai+1>(0≤a＜n)。基本操作:boolremove(int&elem)//移除一个元素,被移除的元素赋给elem //如果操作成功,返回true,否则返回falseboolisEmpty()//判断数组的元素就是否清空,空返回true,否则返回falseboolsetPos(intplace)//设置当前元素的位置,设置成功返回true,否则返回falseintgetLength()//获取数组的实际长度2、各程序模块之间的层次(调用)关系:主函数会按设计的方法调用顺序表中“获取实际长度”、“设置需要删除元素的位置”、“移除该位置元素”与“判断就是否为空表”四种方法方法,使元素依次出列,并正确结束程序。用整形存储用户输入的整数。用顺序表实现线性表:classAList{private:int*listArray;//指向数组的指针intrealSize;//数组中含有元素的实际长度intfence;//指向当前元素下标数据结构实践报告全文共7页，当前为第3页。数据结构实践报告全文共7页，当前为第3页。public:AList(ints)//构造函数,初始化数组{listArray=newint[s];for(inti=0;i<s;i++)listArray[i]=i+1;//数组值等于数组下标+1realSize=s;fence=0;//指向首元素}boolremove(int&elem)//移除一个元素{if(isEmpty())returnfalse;//如果数组为空返回falseelem=listArray[fence];for(inti=fence;i<realSize-1;i++)//从当前位置开始循环向前赋值{listArray[i]=listArray[i+1];}realSize--;returntrue;}boolisEmpty()//判断数组的元素就是否清空{if(realSize==0)returntrue;elsereturnfalse;}boolsetPos(intplace)//设置当前元素的位置{if(place>=0&&place<=realSize){fence=place;returntrue;}returnfalse;}数据结构实践报告全文共7页，当前为第4页。intgetLength()//获取数组长度数据结构实践报告全文共7页，当前为第4页。{returnrealSize;}};在主函数中调用上述模块的方法:ofstreamfout;//文件流fout、open("C:\\Josephus、txt");//设置文件路径intn,m,elem,point=0;scanf("%d,%d",&n,&m);//获得用户输入AListalist(n);//创建顺序表对象while(!alist、isEmpty())//如果顺序表不为空,继续删除{m=m%alist、getLength();//调整计数的长度if(m==0)m=alist、getLength();if(point+m-1<alist、getLength()){point=point+m-1;}//设置偏移位置else{point=point+m-alist、getLength()-1;}alist、setPos(point);//设置当前需要删除的位置alist、remove(elem);//删除元素cout<<elem<<"";//DOS输出fout<<elem<<"";//文件输出数据结构实践报告全文共7页，当前为第5页。四、测试结果(截图显示)数据结构实践报告全文共7页，当前为第5页。五、遇到的问题及解决方法1、初始化部分为循环赋值,时间复杂度为Θ(n)。2、处理部分,我为了提高效率没有采用循环寻找的方法,直接利用数学关系通过当前位置获得下一位置,因此对于长度为n的约瑟夫环,只做了n次定位,每次定位的复杂度为Θ(1),所以时间复杂度为Θ(n)。但就是用顺序表实现时,每次其移除的方法就是时间复杂度为Θ(k)的(k与实际长度有关),所以处理部分总的结果就是()的,化简后时间复杂度仍然为Θ(n2)。综上,该算法的时间代价为Θ(n2)。(PS:如果就是用循环查找,在n次定位中每次都使用了m次的循环,至少就是Θ(n*m),然后再用顺序表的移除方法,总的复杂度应该就是Θ(m*n2)的。)事实上要用线性表来完成这道题,其复杂度最好也就是Θ(n2)的,毕竟对于n个数据,每个都要进行时间复杂度为Θ(n)的删除工作。欲到达Θ(n)的效率除非不用线性表来实现。六、体会数据结构实践报告全文共7页，当前为第6页。数据结构实践报告全文共7页，当前为第6页。输入人数n,报数间隔m,创建顺序表对象。输入人数n,报数间隔m,创建顺序表对象。确定需要删除的位置