栈和队列实验报告.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来记录前一位置最优位置，就无法找到之前的点，所以要多加一个变量；其外就是程序的调试，调试确实需要很大的耐心，有时候只是你的大意而输错了字符或输入输出格式不符合就会出现很多看起来不