栈的基本应用以及迷宫算法.doc

实验报告题目：栈的基本应用以及数字进制间转换和迷宫实现一、需求分析1 本实验报告包括两个实验，由于运用的数据存储方式不一，为了不被混淆，所以分别在两个工程中加以实现。2 在第一个实验中，主要是对栈的一些基本函数方法和应用的实现以及数字进制间的转换，详细情况会在后面的“概要设计”上加以介绍，这里主要介绍迷宫实现的算法。以二维数组maze1010来表示迷宫，其中数值为1表示障碍，不能通过，数值为0表示通道，可以通过。后面再算法实现中有可能讲数组的数值改为2,3等其他数。其中2表示已经走过的通路，用以区分未走的通道。3，45 是为了便于后面的画图。比如，若数值为0，则输出“空格”,数值为1，则输出*，数值为2则输出，数值为3则输出空格，数值为4则输出I表示入口，数值为5则输出O表示出口。3 迷宫我已经构建好，不需要老师自己输入。4 迷宫的出入口需要老师自己输入，可以在正确的范围内随便定义。5 迷宫的求解结果会有两种表现方式：1）为图形形式 2）为文字输出路径形式 。其中文字形式是图形形式的再次说明，因为在某些情况下图形很混乱（由于探路算法的按部就班，可能路径会在出口处显示一圈的“”符号，可能会无法分清具体路径）。6 测试数据：入口坐标（1,1）出口左边（8,8），结果为：（由于图形形式在WORD上不好画出，所以在此省略，见谅.）结点是： 行：8 列：7结点是： 行：8 列：6结点是： 行：8 列：5结点是： 行：7 列：5结点是： 行：6列：5结点是： 行：6 列：4结点是： 行：6 列：3结点是： 行：5 列：3结点是： 行：5列：2结点是： 行：5 列：1结点是： 行：4 列：1结点是： 行：3 列：1结点是： 行：2 列：1结点是： 行：1 列：1 二、概要设计1设定栈的抽象数据类型定义以及数字不同进制间的转换的类型：ADT Stack数据对象：D=ai | aiElemSet,i=1,2,.n,n=0数据关系：R1=| ai-1, ai D,i=2,n基本操作： Int Stack (&S) 操作结果：构造一个空的栈S。DestroyStack (&S) 初始条件：栈S已经存在 操作结果：销毁栈S。StackLength(S) 初始条件：栈S已经存在 操作结果：返回S的长度。StackEmpty(S)初始条件：栈S 已经存在。操作结果：若S为空，则返回TRUE，否则返回FALSE。GetTop(S,&e)初始条件：栈S已存在操作结果：若栈S不空，则以e返回栈顶元素。Push(&S,e)初始条件：栈S 已经存在。操作结果：在栈S的栈顶插入心的栈顶元素e。StachTraverse(S,visit()初始条件：栈S已存在操作结果：从栈底到栈顶一次对S中的每个元素调用函数visit().Zhuanhuan(int n,int m)初始条件：n,m为正整数操作结果：把十进制的数n转换成m进制的数.ADT Stack 2设定迷宫的抽象类型：ADT maze数据对象：D=ai,j| ai,j 空格,*,I,O,0=i=10,0=j=10数据关系：R=ROW,COL ROW=| ai-1,j , ai,j D,i=1,10,j=1,10 COL=| ai-1,j , ai,j D,i=1,10,j=1,10基本操作:mazePath(maze,direction,x1,y1,x2,y2);初始条件：迷宫maze已经被建立好，二维方向direction已经定义好，x1,x2,y1,y2为自己在cmd界面输入的数值，分别表示出入口的行列值.操作结果：若迷宫存在一条路径，则按照上面所说的显示结果，若不存在则输出“没有找到路径”3 本程序主要包含三个模块 1）主程序模块：int main()初始化；do 接受命令； 处理命令；while(命令！=退出)；2）栈模块实现栈抽象数据类型3）迷宫算法实现模块实现迷宫抽象数据类型各模块的调用关系如下： 主程序模块 迷宫模块 栈模块关于迷宫的代码在打包程序中的hanshushixian.cpp中, 栈的定义代码在Stack.h中,主程序代码在main.cpp中，这里不在详细介绍.4) 数字转换的函数调用关系图：主程序main InitStack Push Get DestroyStack 栈模块（Stack）三、详细设计 关于栈的基本应用以及数字进制转换和迷宫的代码分别在打包程序中的hanshushixian.cpp中, 栈的定义代码在Stack.h中,主程序代码在main.cpp中，这里不在详细介绍.四、调试分析 1 本次作业由于内容较多，且难度不低，所以花费了很多时间。特别是迷宫算法的实现，我在网上看了不下4中解法，通过分析最终把它们糅合在一起，且对代码进行了部分优化（不知道算不算得上）。2 在学习了迷宫的算法后，我觉得最大的收获是学会了把现实的东西抽象为数学上的代数表达形式，例如把迷宫抽象为一个二维数组，把探路的方向也抽象为一个二维数组，这对我的数学建模思想帮助很大。3 至于其他的一些问题，最后都加以解决，并且小有收获，总的来说，花费的时间是完全值得的！五、用户手册 1. 本程序的运行环境为Windows 的C+6.0 2. 第一个小实验主函数采用了While循环，除非输入0，否则不会退出程序。3. 在运行迷宫程序时，由于我已经定义好了迷宫，所以不需要老师再定义，若老师需要测试另外的迷宫，只需要把main函数内的maze修改即可.六、测试结果 迷宫的测试结果在需求分析的测试数据中已经详细写出，这里不再累述。这里主要写出栈的基本实现和数字不同进制间的转换的测试结果:1.输入1 回车 则创建一个空栈 创建成功与否都会给与提示测试结果： 创建成功2. 输入 2 回车 则销毁一个非空栈 销毁成功与否都会给予提示3. 输入3 回车 则清空栈4.输入4 回车 1 回车 则数字1入栈 4 回车 2回车 数字2 入栈