栈和队列实验报告.doc

西西 安安 邮邮 电电 大大 学学 （计算机学院） 课课内内实实验验报报告告 实验名称实验名称: : 栈和队列的应用栈和队列的应用 专业名称专业名称: : 班班 级级: : 学生姓名学生姓名: : 学号（学号（8 8 位）位）: : 指导教师指导教师: : 实验时间实验时间: : 一一. 实验目的及实验环境实验目的及实验环境 1.实验目的实验目的 （1） 熟练使用栈和队列解决实际问题；熟练使用栈和队列解决实际问题； （2） 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； （3） 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； （4） 提高综合运用所学的理论知识和方法独立分析和解决问题的能力；提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 2.实验环境实验环境 Dev-C+ 二二. 实验内容实验内容 设计一个国际象棋的马踏棋盘的演示过程。 基本要求: 将马随机放在国际象棋的 8*8 棋盘 Board88的某个方格中，马按走棋规 则进行移动，要求每个方格只进行一次，走遍整个棋盘的全部 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 个可能位置可以用一位数组 HTry107和 HTry207来 表示： 0 1 2 3 4 5 6 7 -2-11221-1-2 1221-1-2-2-1 位于（i，j）的马可以走到新位置是在棋盘范围内的（i+HTry1h,j+HTry2h）， 其中 h=07。 第第 2 步：需求分析步：需求分析 （1）输入的形式和输入值的范围：输入马的初始行坐标 X 和列坐标 Y，X 和 Y 的范围都是1,8。 （2）输出形式： 以数组下表的形式输入，i 为行标，j 为列标，用空格符号隔开。 以棋盘形式输出，每一格打印马走的步数，这种方式比较直观 （3）程序所能达到的功能：让马从任意起点出发都能够遍历整个 8*8 的 棋盘。 （4）测试数据，包括正确输入及输出结果和含有错误的输入及其输出结 果。数据可以任定，只要 1=x,y=8 就可以了。 正确的输出结果为一个二维数组，每个元素的值表示马行走的第几 步，若输入有错，则程序会显示：“输入有误！请重新输入” 并且要求用户重新输入数据，直至输入正确为止。 第第 3 步，算法设计思想：步，算法设计思想： 1、输入马所在初始位置的坐标值，考虑到用户的输入习惯，此处 1=x，y=8； 2、将输入的初始值进栈； 3、设置一个 while 循环，循环条件为 count-1) /栈不空时循环栈不空时循环 for(h=0;h=0k=0 /记录条数记录条数 ah=number; /将条数存入数组将条数存入数组 a8中中 for(h=0;h=63) /如果走完整个棋盘返回如果走完整个棋盘返回 1 return (1); find=0; /表示没有找到下一个位置表示没有找到下一个位置 for(h=director+1;h=0 /表示找到下一个位置表示找到下一个位置 break; if(find=1) /如果找到下一个位置进栈如果找到下一个位置进栈 stacktop.director=director; /存储栈结点的方向存储栈结点的方向 top+; /栈指针前移进栈栈指针前移进栈 stacktop.i=i; stacktop.j=j; stacktop.director=-1; /重新初始化下一栈结点的尝试方向重新初始化下一栈结点的尝试方向 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;jN;j+) boardij=0; for(;) printf(Please input importpoint(1=x=8 and 1=y=1