《数据结构迷宫问题实验报告》由会员分享，可在线阅读，更多相关《数据结构迷宫问题实验报告（19页珍藏版）》请在金锄头文库上搜索。
1、数据结构与算法设计迷宫问题实验报告实验二专业：物联网工程班级：物联网1班学号：姓名：、实验目的本程序是利用非递归的方法求出一条走出迷宫的路径，并将路径输出。首先由用户输入一组二维数组来组成迷宫，确认后程序自动运行，当迷宫有完整路径可以通过时，以0和1所组成的迷宫形式输出，标记所走过的路径结束程序；当迷宫无路径时提示输入错误结束程序。二、实验内容用一个m*m长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序对于任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。三、程序设计1、概要设计（1）设定栈的抽象数据类型定义ADTStack数据对象：D=ai|ai属于CharSe
2、t,i=1、2.n,n=0数据关系：R=vai-1,ai|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，否则返回0Destroy(&S)初始条件：栈已经存在操作结果：销毁栈sADTStack2)设定迷宫的抽
3、象数据类型定义ADTyanshu数据对象：D=ai,j|ai,j属于、吶、#,0=iv=M,0|ai-1,j，ai,j属于D,i=1,2,.M,j=0,1,.NC0L=vai,j-1，ai,j|ai,j-1，ai,j属于D,i=0,1,.M,j=1,2,.N基本操作：InitMaze(MazeType&maze,intaCOL,introw,intcol)初始条件：二维数组intaCOL,已经存在，其中第1至第m-1行，每行自第1到第n-1列的元素已经值，并以值0表示障碍,值1表示通路。操作结果：构造迷宫的整形数组，以空白表示通路，字符0表示障碍在迷宫四周加上一圈障碍MazePath(&maz
4、e)初始条件：迷宫maze已被赋值操作结果:若迷宫maze中存在一条通路，则按如下规定改变maze的状态；以字符*表示路径上的位置。字符表示死胡同；否则迷宫的状态不变PrintMaze(M)初始条件：迷宫M已存在操作结果：以字符形式输出迷宫ADTmaze3)本程序包括三个模块a、主程序模块voidmain()初始化；构造迷宫；迷宫求解；迷宫输出；b、栈模块实现栈的抽象数据类型c、迷宫模块实现迷宫的抽象数据类型2、详细设计(1)坐标位置类型：typedefstructintrow;/迷宫中的行intcol;/的列PosType;坐标(2) 迷宫类型：typedefstructintm,n;int
5、arrRANGERANGE;MazeType;/迷宫类型voidInitMaze(MazeType&maze,intaCOL,introw,intcol)/设置迷宫的初值，包括边缘一圈的值BoolMazePath(MazeType&maze,PosTypestart,PosTypeend)求解迷宫maze中，从入口start到出口end的一条路径若存在，则返回true,否则返回falseVoidPrintMaze(MazeTypemaze)/将迷宫打印出来(3) 栈类型：typedefstructintstep;/当前位置在路径上的序号PosTypeseat;/当前的坐标位置Directive
6、Typedi;/往下一个坐标位置的方向SElemType;栈的元素类型typedefstructSElemType*base;SElemType*top;intstacksize;SqStack;栈的基本操作设置如下：VoidInitStack(SqStack&S)初始化，设S为空栈(S.top=NUL)VoidDestroyStack(Stack&S)销毁栈S,并释放空间VoidClearStack(SqStack&S)/将栈S清空IntStackLength(SqStack&S)/返回栈S的长度StatusStackEmpty(SqStack&S)、若S为空栈(S.top=NULL),则返
7、回TRUE，否则返回FALSEStatueGetTop(SqStack&S，SElemTypee)r若栈S不空，则以e待会栈顶元素并返回TRUE，否则返回FALSEStatuePop(SqStack&S，SElemTypee)若分配空间成功，则在S的栈顶插入新的栈顶元素s并返回TRUE/否则栈不变，并返回FALSEStatuePush(SqStack&S，SElemType&e)若分配空间程控，贝9删除栈顶并以e带回其值，则返回TRUE/否则返回FALSEVoidStackTraverse(SqStack&S，Status)(*Visit)(SElemTypee)从栈顶依次对S中的每个节点调用
8、函数Visit4求迷宫路径的伪码算法：StatusMazePath(MazeType&maze,PosTypestart,PosTypeend)/求解迷宫maze中,从入口start到出口end的一条路径InitStack(s);PosTypecurpos=start;intcurstep=1;/探索第一部doif(Pass(maze,curpos)/如果当前位置可以通过,即是未曾走到的通道块FootPrint(maze,curpos);/留下足迹e=CreateSElem(curstep,curpos,1);/创建元素Push(s,e);if(PosEquare(curpos,end)ret
9、urnTRUE;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# includevstdlib.h#includevstring.h#includevmalloc.h/迷宫坐标位置类型typedefstruct/行值/列值intx;inty;PosType;#defineMAXLENGTH25/
10、设迷宫的最大行列为25typedefintMazeTypeMAXLENGTHMAXLENGTH;/迷宫数组行列typedefstruct/栈的元素类型intord;/通道块在路径上的序号PosTypeseat;/通道块在迷宫中的坐标位置intdi;/从此通道块走向下一通道块的方向(03表示东北)SElemType;/全局变量MazeTypem;/迷宫数组intcurstep=1;/当前足迹,初值为1#defineSTACK_INIT_SIZE10/存储空间初始分配量#defineSTACKINCREMENT2/存储空间分配增量/栈的顺序存储表示typedefstructSqStackSEIemType*base;/在栈构造之前和销毁之后，base的值为NULLSElemType*top;/栈顶指针intstacksize;/当前已分配的存储空间，以元素为单位SqStack;/顺序栈/构造一个空栈SintInitStack(SqStack*S)/为栈底分配一个指定大小的存储空间(*S).base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!(*S).base)exit(0);(*S).top=(*S).base;/栈底与栈顶相同表示一个空栈(*S).stacksize
