迷宫求解课程设计报告

迷宫求解课程设计报告江西农业大学数据结构实验报告迷宫求解姓名:邹运学号:20132234 目录一、需求分析 (2) 二、概要设计 (2) 三、详细设计 (4) 四、调试分析 (6) 五、用户手册 (6) 六、测试结果 (6) 七、附录 (8) 一、需求分析 1以二维数组a[ROW][COL]表示迷宫。数组中以数字1表示障碍,数字0表示通路 2,用预先定好的迷宫作为原始迷宫文件 3设定的迷宫的路口和出口 4若设定的迷宫存在通路,则以‘#’表示障碍,‘*’表示通路打印出来 5.本程序只求出一条成功的...

江西农业大学数据结构实验报告迷宫求解姓名:邹运学号:20132234 目录一、需求分析 (2) 二、概要设计 (2) 三、详细设计 (4) 四、调试分析 (6) 五、用户手册 (6) 六、测试结果 (6) 七、附录 (8) 一、需求分析 1以二维数组a[ROW][COL] 表示迷宫。数组中以数字1表示障碍,数字0表示通路 2,用预先定好的迷宫作为原始迷宫文件 3设定的迷宫的路口和出口 4若设定的迷宫存在通路,则以‘#’表示障碍,‘*’表示通路打印出来 5.本程序只求出一条成功的通路二、概要设计 1、设定栈的抽象数据类型定义: ADT Stack{ 数据对象:D={ai|ai属于CharSet,i=1、2…n,n>=0} 数据关系:R={|ai-1,ai属于D,i=2,3,…n} 基本操作: InitStack(&S) 操作结果:构造一个空栈 Push(&S,e) 初始条件:栈已经存在操作结果:将e所指向的数据加入到栈s中 Pop(&S,&e) 初始条件:栈已经存在操作结果:若栈不为空,用e返回栈顶元素,并删除栈顶元素 Getpop(&S,&e) 初始条件:栈已经存在操作结果:若栈不为空,用e返回栈顶元 StackEmpty(&S) 初始条件:栈已经存在操作结果:判断栈是否为空。若栈为空,返回1,否则返回0 Destroy(&S) 初始条件:栈已经存在操作结果:销毁栈s }ADT Stack 2、设定迷宫的抽象数据类型定义 ADT yanshu{ 数据对象:D={ai,j|ai,j属于{‘ ’、‘*’、‘@’、‘#’},0<=i<=M,0<=j<=N} 数据关系:R={ROW,COL} ROW={|ai-1,j,ai,j属于D,i=1,2,…M,j=0,1,…N} COL={|ai,j-1,ai,j属于D,i=0,1,…M,j=1,2,…N} 基本操作: InitMaze(MazeType &maze, int a[][COL], int row, int col){ 初始条件:二维数组int a[][COL],已经存在,其中第1至第m-1行,每行自第1到第n-1列的元素已经值,并以值0表示障碍,值1表示通路。操作结果:构造迷宫的整形数组,以空白表示通路,字符‘0’表示障碍在迷宫四周加上一圈障碍 MazePath(&maze){ 初始条件:迷宫maze已被赋值操作结果:若迷宫maze中存在一条通路,则按如下规定改变maze的状态;以字符‘*’表示路径上的位置。字符‘@’表示‘死胡同’;否则迷宫的状态不变 } PrintMaze(M){ 初始条件:迷宫M已存在操作结果:以字符形式输出迷宫 } }ADTmaze 3、本程序包括三个模块 a、主程序模块 void main() { 初始化; 构造迷宫; 迷宫求解; 迷宫输出; } b、栈模块——实现栈的抽象数据类型 c、迷宫模块——实现迷宫的抽象数据类型 4、求解迷宫一条路径的伪码算法设定当前位置的初值为入口位置: do{ 若当前位置可通, 则{将当前位置插入栈顶; 若该位置是出口位置,则结束; 否则切换当前位置的东邻块为新的当前位置; 否则{ 若栈不空且栈顶位置还有其他方向未被探索, 则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块; 若栈不空但栈顶位置的四周均不可通, 则{删去栈顶位置; 若栈不空,则重新测试新的栈顶位置, 直至找到一个可通的相邻块或出栈至栈空;} } }while(栈不空) {栈空说明没有路径存在} 三、详细设计 1坐标位置类型 typedef struct{ int row; //迷宫中的行 int col; //......的列 }PosType;//坐标 2. 迷宫类型 typedef struct{ int m,n; int arr[RANGE][RANGE]; }MazeType; //迷宫类型 void InitMaze(MazeType &maze, int a[][COL], int row, int col)\ //设置迷宫的初值,包括边缘一圈的值 Bool MazePath(MazeType &maze,PosType start, PosType end) //求解迷宫maze中,从入口start到出口end的一条路径 //若存在,则返回true,否则返回false Void PrintMaze(MazeType maze) //将迷宫打印出来 3 栈类型 typedef struct{ int step; //当前位置在路径上的"序号" PosType seat; //当前的坐标位置 DirectiveType di; //往下一个坐标位置的方向 }SElemType;//栈的元素类型 typedef struct{ SElemType *base; SElemType *top; int stacksize; }SqStack; 栈的基本操作设置如下: Void InitStack(SqStack & S) //初始化,设S为空栈(S.top=NUL) Void DestroyStack(Stack &S) //销毁栈S,并释放空间 Void ClearStack(SqStack & S) //将栈S清空 Int StackLength(SqStack &S) //返回栈S的长度 Status StackEmpty(SqStack &S) ?、若S为空栈(S.top==NULL),则返回TRUE,否则返回FALSE

                    本文档为【迷宫求解课程设计报告】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

迷宫求解课程设计报告

你可能还喜欢