冒泡法排序c++及马踏棋盘实验报告单(含代码)

冒泡排序是非常容易理解和实现，，以从小到大排序举例：设数组长度为N。1．比较相邻的前后二个数据，如果前面数据大于后面的数据，就将二个数据交换。2．这样对数组的第0个数据到N-1个数据进行一次遍历后，最大的一个数据就“沉”到数组第N-1个位置。3．N=N-1，如果N不为0就重复前面二步，否则排序完成。按照定义很容易写出代码：//冒泡排序1voidBubbleSort1(inta[],intn){inti,j;for(i=0;i<n;i++)for(j=1;j<n-i;j++)if(a[j-1]>a[j])Swap(a[j-1],a[j]);}

下面对其进行优化，设置一个标志，如果这一趟发生了交换，则为true，否则为false。明显如果有一趟没有发生交换，说明排序已经完成。//冒泡排序2voidBubbleSort2(inta[],intn){intj,k;boolflag;k=n;flag=true;while(flag){flag=false;for(j=1;j<k;j++)if(a[j-1]>a[j]){Swap(a[j-1],a[j]);flag=true;}k--;}}再做进一步的优化。如果有100个数的数组，仅前面10个无序，后面90个都已排好序且都大于前面10个数字，那么在第一趟遍历后，最后发生交换的位置必定小于10，且这个位置之后的数据必定已经有序了，记录下这位置，第二次只要从数组头部遍历到这个位置就可以了。//冒泡排序3voidBubbleSort3(inta[],intn){ intj,k; intflag; flag=n; while(flag>0) { k=flag; flag=0; for(j=1;j<k;j++) if(a[j-1]>a[j]) { Swap(a[j-1],a[j]); flag=j; } }}冒泡排序毕竟是一种效率低下的排序方法，在数据规模很小时，可以采用。数据规模比较大时，最好用其它排序方法。白话经典算法系列之二直接插入排序的三种实现分类：白话经典算法系列2011-08-0619:2723895人阅读评论(32)\o"收藏"收藏\o"举报"举报算法直接插入排序(InsertionSort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。设数组为a[0…n-1]。1.初始时，a[0]自成1个有序区，无序区为a[1..n-1]。令i=12.将a[i]并入当前的有序区a[0…i-1]中形成a[0…i]的有序区间。3.i++并重复第二步直到i==n-1。排序完成。下面给出严格按照定义书写的代码（由小到大排序）：[cpp]\o"viewplain"viewplain\o"copy"copy\o"print"print\o"?"?voidInsertsort1(inta[],intn){inti,j,k;for(i=1;i<n;i++){//为a[i]在前面的a[0...i-1]有序区间中找一个合适的位置for(j=i-1;j>=0;j--)if(a[j]<a[i])break;//如找到了一个合适的位置if(j!=i-1){//将比a[i]大的数据向后移inttemp=a[i];for(k=i-1;k>j;k--)a[k+1]=a[k];//将a[i]放到正确位置上a[k+1]=temp;}}}这样的代码太长了，不够清晰。现在进行一下改写，将搜索和数据后移这二个步骤合并。即每次a[i]先和前面一个数据a[i-1]比较，如果a[i]>a[i-1]说明a[0…i]也是有序的，无须调整。否则就令j=i-1,temp=a[i]。然后一边将数据a[j]向后移动一边向前搜索，当有数据a[j]<a[i]时停止并将temp放到a[j+1]处。[cpp]\o"viewplain"viewplain\o"copy"copy\o"print"print\o"?"?voidInsertsort2(inta[],intn){inti,j;for(i=1;i<n;i++)if(a[i]<a[i-1]){inttemp=a[i];for(j=i-1;j>=0&&a[j]>temp;j--)a[j+1]=a[j];a[j+1]=temp;}}

再对将a[j]插入到前面a[0…j-1]的有序区间所用的方法进行改写，用数据交换代替数据后移。如果a[j]前一个数据a[j-1]>a[j]，就交换a[j]和a[j-1]，再j--直到a[j-1]<=a[j]。这样也可以实现将一个新数据新并入到有序区间。[cpp]\o"viewplain"viewplain\o"copy"copy\o"print"print\o"?"?voidInsertsort3(inta[],intn){inti,j;for(i=1;i<n;i++)for(j=i-1;j>=0&&a[j]>a[j+1];j--)Swap(a[j],a[j+1]);}白话经典算法系列之三希尔排序的实现分类：白话经典算法系列2011-08-0811:4118668人阅读评论(27)\o"收藏"收藏\o"举报"举报算法shell优化c希尔排序的实质就是分组插入排序，该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。以n=10的一个数组49,38,65,97,26,13,27,49,55,4为例第一次gap=10/2=549386597261327495541A1B2A2B3A3B4A4B5A5B1A,1B，2A,2B等为分组标记，数字相同的表示在同一组，大写字母表示是该组的第几个元素，每次对同一组的数据进行直接插入排序。即分成了五组(49,13)(38,27)(65,49)(97,55)(26,4)这样每组排序后就变成了(13,49)(27,38)(49,65)(55,97)(4,26)，下同。第二次gap=5/2=2排序后13274955449386597261A1B1C1D1E2A2B2C2D2E第三次gap=2/2=142613273849495597651A1B1C1D1E1F1G1H1I1J第四次gap=1/2=0排序完成得到数组：4132627384949556597下面给出严格按照定义来写的希尔排序[cpp]\o"viewplain"viewplain\o"copy"copy\o"print"print\o"?"?voidshellsort1(inta[],intn){inti,j,gap;for(gap=n/2;gap>0;gap/=2)//步长for(i=0;i<gap;i++)//直接插入排序{for(j=i+gap;j<n;j+=gap)if(a[j]<a[j-gap]){inttemp=a[j];intk=j-gap;while(k>=0&&a[k]>temp){a[k+gap]=a[k];k-=gap;}a[k+gap]=temp;}}}很明显，上面的shellsort1代码虽然对直观的理解希尔排序有帮助，但代码量太大了，不够简洁清晰。因此进行下改进和优化，以第二次排序为例，原来是每次从1A到1E，从2A到2E，可以改成从1B开始，先和1A比较，然后取2B与2A比较，再取1C与前面自己组内的数据比较…….。这种每次从数组第gap个元素开始，每个元素与自己组内的数据进行直接插入排序显然也是正确的。[cpp]\o"viewplain"viewplain\o"copy"copy\o"print"print\o"?"?voidshellsort2(inta[],intn){intj,gap;for(gap=n/2;gap>0;gap/=2)for(j=gap;j<n;j++)//从数组第gap个元素开始if(a[j]<a[j-gap])//每个元素与自己组内的数据进行直接插入排序{inttemp=a[j];intk=j-gap;while(k>=0&&a[k]>temp){a[k+gap]=a[k];k-=gap;}a[k+gap]=temp;}}

再将直接插入排序部分用\o"白话经典算法系列之二直接插入排序的三种实现"白话经典算法系列之二直接插入排序的三种实现中直接插入排序的第三种方法来改写下：[cpp]\o"viewplain"viewplain\o"copy"copy\o"print"print\o"?"?voidshellsort3(inta[],intn){inti,j,gap;for(gap=n/2;gap>0;gap/=2)for(i=gap;i<n;i++)for(j=i-gap;j>=0&&a[j]>a[j+gap];j-=gap)Swap(a[j],a[j+gap]);}这样代码就变得非常简洁了。附注：上面希尔排序的步长选择都是从n/2开始，每次再减半，直到最后为1。其实也可以有另外的更高效的步长选择，如果读者有兴趣了解，请参阅维基百科上对希尔排序步长的说明：/wiki/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F计算机学院《数据结构》课程设计报告课题名称：马踏棋盘 课题负责人（学号/姓名）：同组成员名单（姓名）：指导教师： 评阅成绩：评阅意见： 提交报告时间：Time\@"yyyy年M月d日"2023年5月4日项目成员序号学号姓名职责任务说明1110520131刘伟小组成员需求分析用户使用说明测试结果2110520121黎贵涛组长概要设计2.详细设计3110520104林建彪小组成员1概要设计2.调试分析一、【问题描述】设计一个国际象棋的马踏棋盘的演示过程。基本要求:将马随机放在国际象棋的8*8棋盘Board[8][8]的某个方格中，马按走棋规则进行移动，要求每个方格只进行一次，走遍整个棋盘的全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8*8的方阵，输出之。测试数据：可自行制定一个马的初始位置（i，j），0<=I,j<=7。二、【实验目的】1、对数据结构基本理论和存储结构及算法设计有更深入的理解；2、了解栈的特性，以便在实际问题背景下灵活运用他们；3、提高在世纪设计操作中系统分析、结构确定、算法选择、数学建模和信息加工的能力。【设计过程】81726354第1步：实现提示一般来说，当马位于位置（i,j）时，可以走到下列8个位置之一：（i-2，j+1），(i-1，j+2)（i+1，j+2），(i+2，j+1)（i+2，j-1），(i+1，j-2)（i-1，j-2），(i-2，j-1)（图-1）但是，如果（i，j）靠近棋盘的边缘，上述有些位置可能要超出棋盘位置，成为不允许的位置。8个可能位置可以用一位数组HTry1[0…7]和HTry2[0…7]来表示：01234567-2-11221-1-21221-1-2-2-1（表-2）位于（i，j）的马可以走到新位置是在棋盘范围内的（i+HTry1[h],j+HTry2[h]），其中h=0…7。第2步：需求分析输入的形式和输入值的范围：输入马的初始行坐标X和列坐标Y，X和Y的范围都是[1,8]。输出形式：以数组下表的形式输入，i为行标，j为列标，用空格符号隔开。以棋盘形式输出，每一格打印马走的步数，这种方式比较直观程序所能达到的功能：让马从任意起点出发都能够遍历整个8*8的棋盘。测试数据，包括正确输入及输出结果和含有错误的输入及其输出结果。数据可以任定，只要1<=x,y<=8就可以了。正确的输出结果为一个二维数组，每个元素的值表示马行走的第几步，若输入有错，则程序会显示：“输入有误！请重新输入……”并且要求用户重新输入数据，直至输入正确为止。第3步，算法设计思想：1、输入马所在初始位置的坐标值，考虑到用户的输入习惯，此处1<=x，y<=8；2、将输入的初始值进栈；3、设置一个while循环，循环条件为count<64；4、取出栈顶元素；5、定义flag标志变量的值；6、按照setpossible函数顺时针顺序优先原则，找栈顶元素周围未被占用的新位置。7、若存在该位置，则令order的值等于该新位置的坐标，并入栈；8、否则弹出栈顶元素；9、再次回到第③步while循环进行判断；10、输出一个8*8的方阵，所示数字即为相应步骤。第4步，算法框图：开始开始输入初始坐标X,Y判断X,Y是否合法？Initstack建立新栈并且将初始位置入栈count<64GetTop取栈顶元素；找出所有可走位置根据for循环及优先原则查找是否存在下一个坐标？调用push函数将其压缩进栈调用DleteTop函数将栈顶元素弹出输出否是否是否是第5步，存储结构设计：（1）、位置的存储表示方式typedefstruct{intx;inty;intfrom;}Point;（2）、栈的存储方式#defineSTACKSIZE70#defineSTACKINCREASE10typedefstructStack{Point*top;Point*base;intstacksize;};第6步，设计功能分析与实现（1）、设定栈的抽象数据类型定义：ADTStack{数据对象：D=｛ai|ai∈ElemSet,i=1,2,…,n,n≥0｝数据关系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,…,n}约定an端为栈顶，ai端为栈顶。基本操作：InitStack(&s)操作结果：构造一个空栈s，DestroyStack(&s)初始条件：栈s已存在。操作结果：栈s被销毁。ClearStack(&s)初始条件：栈s已存在。操作结果：栈s清为空栈。StackEmpty(&s)初始条件：栈s已存在。操作结果：若栈s为空栈，则返回OK，否则返回ERROR。StackLength(s);初始条件：栈s存在。操作结果：返回s的元素个数，即栈的长度。GetTop(s,&e);初始条件：栈s已存在且非空。操作结果：用e返回s的栈顶元素。Push(&s,e)初始条件：栈s已存在。操作结果：插入元素e为新的栈顶元素。DeleteTop(&s,&e)初始条件：栈s存在且非空。操作结果：删除栈顶元素，并用e返回。GetDeep(s)初始条件：栈s存在。操作结果：返回一个int型的整数表示栈深。stackTraverse(s,visit())初始条件：栈s存在且非空。操作结果：从栈底到栈顶依次对s的每个元素调用visit()。一旦visit()失败，则操作失败。}ADTStack（2）、选取对该程序有用的函数。1、InitStack(&s)用于构建空栈实现相应的操作；2、StackEmpty(&s)用于判断空栈情况，已确保循环体能够准确实现；3、GetTop(s,&e)用于取放入栈的栈顶元素，实现把放入的横纵坐标按要求取出；4、Push(&s,e)用于将用户输入的横纵坐标放入栈；5、DeleteTop(&s,&e)用于实现将要求取出的元素取出；6、GetDeep()用于获取栈的深度；7、DestroyStack()用于销毁栈。（3）、主要函数及算法说明。1、函数：voidsetpossible(Pointcur)参数：Pointcur功能：找出当前位置下一步的八个位置，将其赋给g_round[8];算法：接受参数传来的值，按顺时针次序加上g_round[i].x={-2,-1,1,2,2,1,-1,-2};g_round[i].y={1,2,2,1,-1,-2,-2,-1};再根据getpossible函数来判断是否合法；若合法则返回OK,否则返回ERROR.2、函数：Statusgetpossible(inti,Point&pt)参数：inti,Point&pt功能：将所在位置周围八个位置坐标赋予指针变量，并判断其合理性；算法：用以下赋值语句pt.x=g_round[i-1].x;pt.y=g_round[i-1].y;将现在周围8个指定位置赋予指针变量pt，并用if(pt.x<0||pt.y<0||pt.x>7||pt.y>7)条件语句判断其合理性，若合理则返回OK，否则返回ERROR.3、语句：for(inti=cur.from+1;i<=8;i++){if(getpossible(i,next)&&order[next.x][next.y]==0){语句……}}功能：按照顺时针优先规则，选出下一个可用的位置，通过if判断语句来判断所选的下一步是否可用，若可用，则使其进栈，否则运行下面一个语句。4、语句：if(flag==NULL){语句…..while(j<p&&GetDeep(herseVisit)>1){语句…..}}功能：如果当前位置不存在任何新路径，则根据while循环进行退栈，直至退到存在有最佳位置的坐标。但必须保证栈不为空。所以此出栈中设定了intGetDeep的基本操作，就是防止空栈还继续弹东西出来的情况发生。四、【调试程序】（1）、问题：语法错误原因：首次运行语法错误比较多，一般都是由于粗心大意输入有误造成的，还有一些错误属于变量忘记定义之类的，经过认真一个一个调试后这类错误得以解决。下图为第一次运行时的错误（2）、问题：运行后突然停止程序原因：可能是输出不恰当解决：此问题出现后，刚开始不知道为啥，看了很多遍程序就是找不出原由，于是后来请教同学，一起研究后无意中改了输出格式，将printf("%s,%2d",'|',order[i][j]);改成了printf("%d,%f",order[i][j],'|');竟然成功输出了。怀疑是%s使用得不恰当。下图为修改前的运行结果：（3）、问题：将上述问题解决后虽然不会出现程序突然终止的情况，但运行结果如下图，输出结果很乱；原因：输出格式不符解决：将printf("%d,%f",order[i][j],'|');改成printf("|%2d",order[i][j]);(4)、问题：上述问题都搞定后，输入初始坐标后按下Enter键后不会出现棋盘原因：main()函数里flag写成intflage；解决：将intflage改成flag(5)、问题：上述问题都搞定后，输入初始坐标后按下Enter键后会出现棋盘，但是在棋盘上会出现0000的情况，与需要的结果不符。原因：regular.h文件里面获得合理位置的边界位置判定，横坐标和纵坐标的范围少写了ps.x>7||ps.y<0。解决：在regular.h文件里面添加横坐标和纵坐标的范围ps.x>7||ps.y<0（6）、问题：上述问题都搞定后，输入初始坐标后按下Enter键后立即退出了原因：main()函数里有scanf()，当用户输入初始坐标后，将这两个坐标赋予给&begin.x,&begin.y，结果当用户想用Enter键进行确认操作后，Enter本身是一个字符，而这个字符不符合循环要求，所以直接退出解决：多加一个getchar()把Enter键给吸收掉，结果如下图：五、【用户手册】运行程序，程序开始界面，如图所示：输入初始值x,y，如输入（3,7），如图所示：因为（3,7）在（1~8）的范围内，所以程序输出结果如下:按（y/Y）后，程序将跳到输入初始值位置，如图所示：按其他任意键后（如按（n/N）键），将退出程序，如图所示：若输入的初始值没在（1~8）的范围内，如输入（7,9），则将提示错误，并要求重新输入，如图所示：按任意键后，程序将跳回输入初始值的位置，如图所示：六、【实验总结与体会】总结：马踏棋盘，作为一种经典的栈的应用例子，从大方面将，刚看到这名字就知道用栈来实现，但是，当你面对这个题目，打开编译器之后想写的时候，发现又不是那么容易，很多细节需要认真的分析，比如结构体的定义，棋子因为是二维的，所以对于用来存储棋盘的横纵坐标，需要用到两个变量，定义两整型变量x,y。刚开始只定义了这两个变量，后来发现如果找到下一个位置，而下一个位置有很多个都是符合的，如何选取最优的呢？最有的有可能是最先找到的，可找到后还得继续找下去，万一没有比他更优的，则要退回来，如果没有变量from来记录前一位置最优位置，就无法找到之前的点，所以要多加一个变量；其外就是程序的调试，调试确实需要很大的耐心，有时候只是你的大意而输错了字符或输入输出格式不符合就会出现很多看起来不可思议很难发现的错误，这也说明了编程的时候一定要认真有耐心。体会：刚学习栈的时候，觉得并不太难，反正就是先进后出，可是到了实际运用的时候，才发现学到的理论知识要用到实际去还真是个问题，通过这次课程设计的实践，让我对栈有了更深入的理解，也发现一种理论再简单的知识，如果不实际运用一下，对于你的掌握肯定是不够的，因为实际运用中你要适当选取哪些是有用的，哪些不必用到的，而且当你很兴奋的写完代码后，会发现很多错误，当然一般是语法错误，如果你的逻辑没错的话，也有可能是你思想没错，但你的表达不妥当，这也会让你对程序的修改显得很无助；再次，世上没有完美的程序，如今社会上出现的各个软件每到一定的时候就会有升级版也正是这个原因，我承认自己这个程序存在很多漏洞和不足，但一个程序的优化可不是一朝一夕的事，只要求自己能完成基本任务就行了。七、【参考文献】《数据结构（C语言版）》--------严蔚敏、吴伟民编著《C语言设计（第三版）》--------谭浩强著《C语言课程设计（第2版）》-------梁旭、谷晓琳、黄明编著《C语言通用范例金典》-------柳盛，王国全，沈永林编著【程序清单】1.文件horse.h#ifndef__HORSE_H__#define__HORSE_H__#include<stdio.h>#include<malloc.h>#defineOK1#defineERROR0#defineSTACKSIZE70#defineSTACKINCREASE10typedefintStatus;//位置的储存typedefstruct{ intx; inty; intfrom;}Point;//栈的储存typedefstruct{ Point*top; Point*base; intstacksize;}Stack;//建栈StatusInitstack(Stack&s){ s.base=(Point*)malloc(STACKSIZE*sizeof(Point)); if(s.base==NULL)returnERROR; s.top=s.base; s.stacksize=STACKSIZE; returnOK;}//向栈中插入元素eStatusPush(Stack&s,Pointe){ if(s.top-s.base>=s.stacksize) { s.base=(Point*)realloc(s.base, (s.stacksize+STACKINCREASE)*sizeof(Point)); if(s.base==NULL)returnERROR; s.top=s.base+s.stacksize; s.stacksize+=STACKINCREASE; } (*s.top).x=e.x; (*s.top).y=e.y; (*s.top).from=e.from; s.top++; returnOK;}//栈不为空，则删除栈顶元素StatusDeleteTop(Stack&s,Point&e){ if(s.top==s.base)returnERROR; s.top--; e.x=(*s.top).x; e.y=(*s.top).y; e.from=(*s.top).from; returnOK;}//销毁栈StatusDestroyStack(Stack&s){ free(s.base);//free(s); returnOK;}//判断栈是否为空StatusStackEmpty(Stacks){ if(s.base==s.top)returnOK; elsereturnERROR;}//获得栈顶元素StatusGetTop(Stacks,Point&e){ if(s.base==s.top)returnERROR; e.x=(*(s.top-1)).x; e.y=(*(s.top-1)).y; e.from=(*(s.top-1)).from; returnOK;}//获得栈的深度intGetDeep(Stacks){ returns.top-s.base;}#endif文件regular.h#ifndef__REGULAR_H__#define__REGULAR_H__#include"horse.h"Pointh_possible[8]={0,0,0};//查找所有可能的位置，并存入h_possible[8]中voidsetPossible(Pointcon){ Pointround[]= { {con.x-2,con.y+1,0}, {con.x-1,con.y+2,0}, {con.x+1,con.y+2,0}, {con.x+2,con.y+1,0}, {con.x+2,con.y-1,0}, {con.x+1,con.y-2,0}, {con.x-1,con.y-2,0}, {con.x-2,con.y-1,0} }; for(inti=0;i<8;i++) { h_possible[i].x=round[i].x; h_possible[i].y=round[i].y; h_possible[i].from=round[i].from; }}//取得合理的可能位置StatusgetPossible(inti,Point&ps){ ps.x=h_possible[i-1].x; ps.y=h_possible[i-1].y; if(ps.x<0||ps.y>7||ps.x>7||ps.y<0)returnERROR; elsereturnOK;}#endif主函数main.c#include<stdio.h>#include<stdlib.h>#include"horse.h"#include"regular.h"voidmain(){ inti,j,p; ints=1; charyn; StackhorseVisit; Pointcur,next;H1:while(s){ intorder[8][8]={0};//是一个中间变量，用来记录当前位置 intcount=0; Pointbegin; system("color31"); printf("<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<马踏棋盘程序演示>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\n"); printf("请输入马在棋盘上的任意初始位置x，y，根据用户习惯，其中x,y为（~8），例如（7）："); scanf("%d%d",&begin.x,&begin.y); printf("\n================================================================================\n"); begin.from=0; while(begin.x>8||begin.y>8||begin.x<1||begin.y<1) { system("cls"); printf("<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<输入格式不对，请重新输入...>>>>>>>>>>>>>>>>>>>\n"); getchar(); getchar(); system("cls"); gotoH1; } getchar(); begin.x--;//注意用户输入的坐标（~8），而储存是（~7），这里要自减 begin.y--; Initstack(horseVisit);//创建空栈 Push(horseVisit,begin);//入栈，将用户输入的坐标存入栈中 count++;//计数器加 order[begin.x][begin.y]=count; while(count<64) { GetTop(horseVisit,cur);//取栈顶元素存入cur中 se