栈和队列试验报告

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

2、，马按走棋规 则进行移动，要求每个方格只进行一次，走遍整个棋盘的全部 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 ）靠近棋盘的边缘，上述

3、有些位置可能要超出棋盘位置，成 为不允许的位置。 8 个可能位置可以用一位数组 HTry10 7 和 HTry20 7来 表示：0 1 2 3 4 5 6 7-2-11221-1-21221-1-2-2-1位于（i ，j ）的马可以走到新位置是在棋盘范围内的 （i+HTry1h,j+HTry2h ）， 其中 h=0 7。第 2 步：需求分析（ 1） 输入的形式和输入值的范围：输入马的初始行坐标 X和列坐标 Y，X 和 Y 的范围都是 1,8 。（ 2） 输出形式： 以数组下表的形式输入， i 为行标， j 为列标，用空格符号隔开。 以棋盘形式输出，每一格打印马走的步数，这种方式比较直观（ 3）

4、 程序所能达到的功能：让马从任意起点出发都能够遍历整个 8*8 的 棋盘。（ 4） 测试数据，包括正确输入及输出结果和含有错误的输入及其输出结 果。数据可以任定，只要 1=x,y=8 就可以了。 正确的输出结果为一个二维数组，每个元素的值表示马行走的第几 步，若输入有错，则程序会显示：“输入有误！请重新输入” 并且要求用户重新输入数据，直至输入正确为止。第 3 步，算法设计思想：1、输入马所在初始位置的坐标值， 考虑到用户的输入习惯， 此处 1=x，y=8；2、将输入的初始值进栈；3、设置一个 while 循环，循环条件为 count64 ；4、取出栈顶元素；5、定义 flag 标志变量的值；

5、6、按照 SetRound 函数逆时针顺序优先原则， 找栈顶元素周围未被占用的7、新位置。若存在该位置， 则令 order 的值等于该新位置的坐标， 并入 栈；8、否则弹出栈顶元素；9、再次回到第步 while 循环进行判断；10、输出一个 8*8 的方阵，所示数字即为相应步骤。四测试数据及运行结果1 正常测试数据（ 3 组）及运行结果；2 非正常测试数据（ 2 组）及运行结果五总结1 实验过程中遇到的问题及解决办法。（例如：记录编译时错误信息，根据实验过程中出现的编译错误信息分析出 错原因，并改正错误。）2 对设计及调试过程的心得体会。 马踏棋盘，作为一种经典的栈的应用例子，从大方面将，刚看

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

7、的大意而输错了字符或输入输出格式不符合就 会出现很多看起来不可思议很难发现的错误，这也说明了编程的时候一定要认真有耐心 六附录： 源代码（请把源代码按照实验内容附到其后）#include#define MAXSIZE 100#define N 8/ （ 2）、数据类型定义int board88; /定义棋盘int Htry18=1,-1,-2,2,2,1,-1,-2;/* 存储马各个出口位置相对当前位置行下标的增量数组 */int Htry28=2,-2,1,1,-1,-2,2,-1;/* 存储马各个出口位置相对当前位置列下标的增量数组 */struct Stack/ 定义栈类型int i;

8、/行坐标int j; /列坐标int director; / 存储方向stackMAXSIZE; / 定义一个栈数组int top=-1; /栈指针/ （ 3）、函数声明void InitLocation（int xi,int yi）; /马儿在棋盘上的起始位置坐标int TryPath（int i,int j）; /马儿每个方向进行尝试，直到试完整个棋盘void Display（）; /输出马儿行走的路径/ （ 4）、起始坐标函数模块void InitLocation（int xi,int yi）int x,y; top+; stacktop.i=xi;/ 定义棋盘的横纵坐标变量/ 栈指针指

9、向第一个栈首/ 将起始位置的横坐标进栈将起始位置的纵坐标进栈 将起始位置的尝试方向赋初值 标记棋盘 将起始位置的横坐标赋给棋盘的横坐标 将起始位置的纵坐标赋给棋盘的纵坐标 调用马儿探寻函数，如果马儿探寻整个棋盘返回输出马儿的行走路径1 否则定义几个临时变量stacktop.j=yi;/stacktop.director=-1; / boardxiyi=top+1;/x=stacktop.i;/y=stacktop.j; / if(TryPath(x,y) / 返回 0Display(); /elseprintf( 无解 );/ ( 5)、探寻路径函数模块 int TryPath(int i,i

10、nt j)int find,director,number,min; /int i1,j1,h,k,s; / 定义几个临时变量int a8,b18,b28,d8; /定义几个临时数组while(top-1) /栈不空时循环 for(h=0;h=0&i=0&j8) / 如果找到下一位置 for(k=0;k=0&i1=0&j18)/ 如果找到下 一位置number+; / 记录条数 ah=number; / 将条数存入数组 a8 中 for(h=0;h8;h+) / 根据可行路径条数小到大按下表排序放入数组 d8 中 min=9; for(k=0;kak) min=ak; dh=k; / 将下表存

11、入数组 d8 中 s=k;as=9;director=stacktop.director;if(top=63) / 如果走完整个棋盘返回 1 return (1);find=0; / 表示没有找到下一个位置 for(h=director+1;h=0&i=0&j8) /如果找到下一位置find=1; / 表示找到下一个位置 break; if(find=1) / 如果找到下一个位置进栈 stacktop.director=director; / 存储栈结点的方向 top+; / 栈指针前移进栈 stacktop.i=i;stacktop.j=j;stacktop.director=-1; / 重

12、新初始化下一栈结点的尝试方向 boardij=top+1; /标记棋盘else / 否则退栈 boardstacktop.istacktop.j=0; / 清除棋盘的标记 top-; / 栈指针前移退栈return (0);/ ( 6)输出路径函数模块void Display()int i,j; for(i=0;iN;i+)for(j=0;jN;j+)printf(t%d ,boardij); /输出马儿在棋盘上走过的路径printf(nn); printf(n);/ ( 5)主程序模块int main()int i,j;int x,y; for(i=0;iN;i+) / 初始化棋盘 for(j=0;