数据结构迷宫问题实验报告

《数据结构与算法设计》 迷宫问实验报告 ——实验二 专业：物联网 班级：物联网1班 学号：15180118 姓名：刘沛航 一、 实验目的 本程序是利用非递归的求出一条走出迷宫的路径，并将路径输出。首先由用户输入一组二维数组来组成迷宫，确认后程序自动运行，当迷宫有完整路径可以通过时，以0和1所组成的迷宫形式输出，标记所走过的路径结束程序；当迷宫无路径时，提示输入错误结束程序。 二、实验内容 用一个m*m长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序对于任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 三、程序设计 1、概要设计 （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、 迷宫模块——实现迷宫的抽象数据类型 2、详细设计 （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 Statue GetTop（SqStack &S，SElemType e） //r若栈S不空，则以e待会栈顶元素并返回TRUE，否则返回FALSE Statue Pop(SqStack&S，SElemType e) //若分配空间成功，则在S的栈顶插入新的栈顶元素s并返回TRUE //否则栈不变，并返回FALSE Statue Push(SqStack&S，SElemType &e) //若分配空间程控，则删除栈顶并以e带回其值，则返回TRUE //否则返回FALSE Void StackTraverse（SqStack &S，Status）（*Visit）（SElemType e）） //从栈顶依次对S中的每个节点调用函数Visit 4求迷宫路径的伪码算法： Status MazePath(MazeType &maze,PosType start, PosType end){ //求解迷宫maze中,从入口start到出口end的一条路径 InitStack(s); PosType curpos = start; int curstep = 1;                //探索第一部 do{ if( Pass(maze,curpos) ){    //如果当前位置可以通过,即是未曾走到的通道块 FootPrint(maze,curpos);            //留下足迹 e = CreateSElem(curstep,curpos,1);    //创建元素 Push(s,e); if( PosEquare(curpos,end) )    return TRUE; curpos =NextPos(curpos,1);            //获得下一节点:当前位置的东邻 curstep++;                            //探索下一步 }else{                        //当前位置不能通过 if(!StackEmpty(s)){ Pop(s,e); while(e.di==4 && !StackEmpty(s) ){ MarkPrint(maze,e.seat); Pop(s,e);   //留下不能通过的标记,并退回步 } if(e.di<4){ e.di++; Push(s,e);            //换一个方向探索 curpos = NextPos(e.seat,e.di);    //设定当前位置是该方向上的相块 }//if }//if }//else }while(!StackEmpty(s)); return FALSE; } //MazePath 四、程序调试分析 1.首先呢，想自己读入数据的，回来发现那样，很麻烦，所以还是事先定义一个迷宫。 2.栈的元素类型 一开始有点迷惑，后来就解决了 3.本题中三个主要算法；InitMaze，MazePath和PrintMaze的时间复杂度均为O（m*n）本题的空间复杂度也是O（m*n）