栈和队列实验报告解读.doc

西 安 邮 电 大 学 （计算机学院） 课内实验报告 实验名称: 栈和队列的应用 专业名称: 班 级: 学生姓名: 学号（8位）: 指导教师: 实验时间:  一. 实验目的及实验环境 1.实验目的 （1）?熟练使用栈和队列解决实际问题；? （2）?了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；? （3）?初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； （4）?提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 2.实验环境 Dev-C++ 二. 实验内容 设计一个国际象棋的马踏棋盘的演示过程。 基本要求: 将马随机放在国际象棋的8*8棋盘Board[8][8]的某个方格中，马按走棋规则进行移动，要求每个方格只进行一次，走遍整个棋盘的全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8*8的方阵，输出之。 测试数据：可自行制定一个马的初始位置（i，j），0=I,j=7。 三．方案设计 第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) 但是，如果（i，j）靠近棋盘的边缘，上述有些位置可能要超出棋盘位置，成为不允许的位置。8个可能位置可以用一位数组HTry1[0…7]和HTry2[0…7]来表示： 0 1 2 3 4 5 6 7 -2 -1 1 2 2 1 -1 -2 1 2 2 1 -1 -2 -2 -1 位于（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循环，循环条件为count64； 4、取出栈顶元素； 5、定义flag标志变量的值； 6、按照SetRound函数逆时针顺序优先原则，找栈顶元素周围未被占用 的7、新位置。若存在该位置，则令order的值等于该新位置的坐标，并入 栈；8、否则弹出栈顶元素； 9、再次回到第③步while循环进行判断； 10、输出一个8*8的方阵，所示数字即为相应步骤。 四．测试数据及运行结果 正常测试数据（3组）及运行结果； 非正常测试数据（2组）及运行结果。 五．总结 实验过程中遇到的问题及解决办法。 （例如：记录编译时错误信息，根据实验过程中出现的编译错误信息分析出错原因，并改正错误。） 对设计及调试过程的心得体会。 马踏棋盘，作为一种经典的栈的应用例子，从大方面将，刚看到这名字就知道用栈来实现，但是，当你面对这个题目，打开编译器之后想写的时候，发现又不是那么容易，很多细节需要认真的分析，比如结构体的定义，棋子因为是二维的，所以对于用来存储棋盘的横纵坐标，需要用到两个变量，定义两整型变量x,y。刚开始只定义了这两个变量，后来发现如果找到下一个位置，而下一个位置有很多个都是符合的，如何选取最优的呢？最有的有可能是最先找到的，可找到后还得继续找下去，万一没有比他更优的，则要退回来，如果没有变量from来记录前一位置最优位置，就无法找到之前的点，所以要多加一个变量；其外就是