栈和队列试验报告课案

1、专业名称班级：学生姓名西安邮电大学（计算机学院）课内实验报告实验名称：一栈和队列的应用学号（8位）：指导教师：实验时间:实验目的及实验环境1.实验目的(1)熟练使用栈和队列解决实际问题；(2)了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；(3)初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；(4)提高综合运用所学的理论知识和方法独立分析和解决问题的能力；2.实验环境Dev-C+实验内容设计一个国际象棋的马踏棋盘的演示过程。基本要求：将马随机放在国际象棋的8*8棋盘Board88的某个方格中，马按走棋规则进行移动，要求每个方格只进行一次，走遍整个棋盘

2、的全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1,2,，64依次填入一个8*8的方阵，输出之。测试数据：可自行制定一个马的初始位置(i,j),0=IJv=7o第1步：实现提示一般来说,当马位于位置(ij)时，可以走到下列8个位置之一：(i-2,j+1),(il,j+2)(i+l,j+2),(i+2,j+l)(i+2J-l),(i+1J-2)(i-1,j-2),(i-2zj-1)但是，如果(i,j)靠近棋盘的边缘,上述有些位置可能要超出棋盘位置，成为不允许的位置。8个可能位置可以用一位数组HTrylO刀和HTry20刀来表示：01234567-2-11212212

3、1-1-2-1-2-2-1位于(i,j)的马可以走到新位置是在棋盘范围内的(i+HTrylh,j+HTry2h),其中h=0.7o第2步：需求分析(1)输入的形式和输入值的范围：输入马的初始行坐标X和列坐标丫,乂和丫的范围都是口网。(2)输出形式：以数组下表的形式输入，i为行标J为列标，用空格符号隔开。以棋盘形式输出，每一格打印马走的步数，这种方式比较直观(3)程序所能达到的功能：让马从任意起点出发都能够遍历整个8*8的棋盘。(4)测试数据，包括正确输入及输出结果和含有错误的输入及其输出结果。数据可以任定，只要l=xzyv=8就可以了。正确的输出结果为一个二维数组，每个元素的值表示马行走的第几

4、步，若输并且要求用户重新输入数据，直至输入正确为止。入有错，则程序会显示：输入有误！请重新输入/第3步，算法设计思想:1、输入马所在初始位置的坐标值，考虑到用户的输入习惯，此处l=x,yv=8;2、将输入的初始值进栈；3、设置一个while循环，循环条件为count64;4、取出栈顶元素；5、定义flag标志变量的值；6、按照SetRound函数逆时针顺序优先原则，找栈顶元素周围未被占用的7、新位置。若存在该位置，则令order的值等于该新位置的坐标,并入栈;&否则弹出栈顶元素；9、再次回到第步while循环进行判断；10、输出一个8*8的方阵，所示数字即为相应步骤。四测试数据及运行结果1 .

5、正常测试数据(3组)及运行结果；Pleaseincutinoortoointandl=v=8.)InputK=1yInput=2withbegin2.“board:16118611451326319481535(52)3522370455百33644?2049b936&31224346354457ao27214223275411a425404369382941225263928710度迥财播入法全：2 .非正常测试数据（2组）及运行结果Q-7五.总结1 .实验过程中遇到的问题及解决办法。(例如：记录编译时错误信息，根据实验过程中出现的编译错误信息分析出错原因，并改正错误。)2 .对设计及调试过

6、程的心得体会。马踏棋盘，作为一种经典的栈的应用例子，从大方面将,刚看到这名字就知道用栈来实现，但是，当你面对这个题目，打开编译器之后想写的时候，发现又不是那么容易，很多细节需要认真的分析，比如结构体的定义，棋子因为是二维的，所以对于用来存储棋盘的横纵坐标，需要用到两个变量，定义两整型变量x,yo刚开始只定义了这两个变量，后来发现如果找到下一个位置，而下一个位置有很多个都是符合的，如何选取最优的呢？最有的有可能是最先找到的，可找到后还得继续找下去，万一没有比他更优的，则要退回来，如果没有变量from来记录前一位置最优位置，就无法找到之前的点，所以要多加一个变量；其外就是程序的调试，调试确实需要很

7、大的耐心，有时候只是你的大意而输错了字符或输入输出格式不符合就会出现很多看起来不可思议很难发现的错误，这也说明了编程的时候一定要认真有耐心六.附录：源代码(请把源代码按照实验内容附到其后)#include#defineMAXSIZE100#defineN8/(2)、数据类型定义intboard88;/定义棋盘intHtryl8=L-L-2,22L-L-2;/*存储马各个出口位置相对当前位置行下标的增量数组*/intHtry28=2,-2,l,L-L-22-l;/*存储马各个出口位置相对当前位置列下标的增量数组*/structStack/定义栈类型inti;行坐标intj;/列坐标intdire

8、ctor;/存储方向stackMAXSIZE;/定义一个栈数组inttop=-l;栈指针(3)、函数声明voidInitLocation(intxijntyi);/马儿在棋盘上的起始位置坐标intTryPath(intijntj);/马儿每个方向进行尝试，直到试完整个棋盘voidDisplay();/输出马儿行走的路径int x,y;top + +;stacktop.i=xi;stacktop.j=yi;stacktop.director=-l; / boardxiyi=top +1;x=stacktop.i;y=stacktop.j;回0Display();else printf(无解)；(

9、5)、探寻路径函数模块int TryPath(int ijnt j)/(4)、起始坐标函数模块voidInitLocation(intxijntyi)(定义棋盘的横纵坐标变量栈指针指向第一个栈首将起始位置的横坐标进栈将起始位置的纵坐标进栈将起始位置的尝试方向赋初值标记棋盘将起始位置的横坐标赋给棋盘的横坐标输出马儿的行走路径intfind,director,number,min;定义几个临时变量intiljl,h,k,s;/定义几个临时变量if(TryPath(xzy)调用马儿探寻函数，如果马儿探寻整个棋盘返回1否则返inta8zbl8Lb28Ld8;/定义几个临时数组while(top-l)/

10、栈不空时循环(for(h=0;h=0&iv8&j=0&的8)如果找至!下一位置for(k=0;k=0&il=084&jl8)/$D果找到下一位置number+;/记录条数ah=number;/将条数存入数组a8中)for(h=0;h8;h+)根据可行路径条数小至I大按下表排序放入数组d8中(min=9;for(k=0;kak)=63)/如果走完整个棋盘返回1return(1);find=O;II表示没有找到下一个位置for(h=director+l;h=0&i=0&8(jv8)如果找至！下一位置(find=l;/表示找到下一个位置break;)if(find=l)/如果找到下一个位置进栈(st

11、acktop.director=director;/存储栈结点的方向top+;栈指针前移进栈stacktop.i=i;stacktop.j=j;stacktop.director=-l;/重新初始化下一栈结点的尝试方向boardij=top+l;标记棋盘)else/否则退栈boardstacktop.istacktopj=0;/清除棋盘的标记top-；栈指针前移退栈)return(0);)/(6)输出路径函数模块voidDisplayO(intij;for(i=0;iN;i+)for(j=0;jN;j+)printf(t%d，boardij);输出马儿在棋盘上走过的路径printf(nn);)printf(n);)/(5)主程序模块intmain()intij;intx,y;for(i=0;ivN;i+)初始化棋盘for(j=0;jvN;j+)b