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

《数据结构与算法设计》迷宫问题实验报告——实验二专业：物联网工程班级：物联网 1班学号：15180118姓名：刘沛航一、 实验目的本程序是利用非递归的方法求出一条走出迷宫的路径，并将路径输出。 首先由用户输入一组二维数组来组成迷宫， 确认后程序自动运行， 当迷宫有完整路径可以通过时， 以0和1所组成的迷宫形式输出， 标记所走过的路径结束程序； 当迷宫无路径时，提示输入错误结束程序。二、实验内容用一个 m*m长方阵表示迷宫， 0和1分别表示迷宫中的通路和障碍。设计一个程序对于任意设定的迷宫， 求出一条从入口到出口的通路，或得出没有通路的结论。三、程序设计1、概要设计1）设定栈的抽象数据类型定义ADTStack

{数据对象：数据关系：

D={ai|ai 属于 CharSet ，i=1、2⋯ｎ，n>=0}R={<ai-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)初始条件：栈已经存在操作结果：销毁栈 s}ADTStack2）设定迷宫的抽象数据类型定义ADTyanshu

{数据对象：

D={ai,j|ai,j

属于

{‘、’‘、*’‘@’、‘#’},0<=i<=M,0<=j<=N}数据关系：

R={ROW,COL}ROW={<ai-1,j ,ai,j>|ai-1,j,ai,j属于D，i=1,2, ⋯M,j=0,1, ⋯N}COL={<ai,j-1

,ai,j>|ai,j-1

,ai,j

属于

D,i=0,1,

⋯Ｍ，j=1,2,

⋯N}基本操作：InitMaze(MazeType&maze,inta[][COL],introw,intcol){初始条件：二维数组 inta[][COL], 已经存在，其中第m-1 1 n-1碍，值1表示通路。

1至第0操作结果： 构造迷宫的整形数组，

以空白表示通路，

字符‘0表’示障碍在迷宫四周加上一圈障碍MazePath（&maze）{初始条件：迷宫 maze已被赋值操作结果：若迷宫 maze中存在一条通路，则按如下规定改变maze的状态；以字符‘*’表示路径上的位置。字符‘@’表示‘死胡同’；否则迷宫的状态不变}PrintMaze（M）{初始条件：迷宫 M已存在操作结果：以字符形式输出迷宫}}ADTmaze3）本程序包括三个模块a、主程序模块voidmain (){初始化；构造迷宫；迷宫求解；迷宫输出；}b、栈模块 ——实现栈的抽象数据类型c、迷宫模块 ——实现迷宫的抽象数据类型2、详细设计1）坐标位置类型：typedefstruct{introw; //intcol; //......

迷宫中的行的列}PosType;//坐标2）迷宫类型：typedefstruct{intm,n;intarr[RANGE][RANGE];}MazeType; // 迷宫类型void//设置迷宫的初值，包括边缘一圈的值BoolMazePath(MazeType&maze,PosTypestart,PosTypeend)//求解迷宫 maze中，从入口 start 到出口 end的一条路径//若存在，则返回 true，否则返回 falseVoidPrintMaze （MazeTypemaze ）//将迷宫打印出来3）栈类型：typedefstruct{int step; // 当前位置在路径上的 "序号"PosType seat; // 当前的坐标位置DirectiveType di; // 往下一个坐标位置的方向}SElemType;// 栈的元素类型typedefstruct{SElemType*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

），则返回

TRUE

，否则返回

FALSEStatueGetTop

（SqStack&S

，SElemTypee

）//r

若栈

S不空，则以

e待会栈顶元素并返回

TRUE

，否则返回

FALSEStatuePop(SqStack&S

，SElemTypee)//若分配空间成功，则在

S的栈顶插入新的栈顶元素

s并返回

TRUE//否则栈不变，并返回

FALSEStatuePush(SqStack&S

，SElemType&e)//若分配空间程控，则删除栈顶并以 e带回其值，则返回 TRUE//否则返回 FALSEVoidStackTraverse （SqStack&S，Status）（*Visit）（SElemTypee））//从栈顶依次对 S中的每个节点调用函数 Visit求迷宫路径的伪码算法：StatusMazePath(MazeType &maze,PosType start, PosType end){ //求解迷宫 maze中,从入口start到出口 end的一条路径InitStack(s);PosTypecurpos=start;intcurstep=1; // 探索第一部do{if(Pass(maze,curpos)){ // 如果当前位置可以通过 ,即是未曾走到的通道块FootPrint(maze,curpos); // 留下足迹e=CreateSElem(curstep,curpos,1); // 创建元素Push(s,e);if(PosEquare(curpos,end)) returnTRUE;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));returnFALSE;}//MazePath四、程序调试分析首先呢，想自己读入数据的，回来发现那样，很麻烦，所以还是事先定义一个迷宫。2.栈的元素类型 一开始有点迷惑，后来就解决了3.本题中三个主要算法； InitMaze ，MazePath和PrintMaze 的时间复杂度均为 O（m*n）本题的空间复杂度也是 O（m*n）五、用户使用说明1．本程序运行在 windows系列的操作系统下， 执行文件为：Maze_Test.exe。六、程序运行结果建立迷宫：2．通过1功能建立 8*8的迷宫后，通过 2功能继续建立迷宫内部：通过建立自己设定单元数目建立迷宫内墙。3．通过 3功能观察已建立的迷宫结构：4．通过 4功能确立迷宫起点和终点：（此处像我们随机选择 4,4和2,7分别为起点终点）5．执行 5功能，判断是否有路径走出迷宫：这种情况无法走出迷宫。我们再次观察图像设 4,4和1,6分别为起点终点，再运行 5功能。观察到可以成功解开迷宫步数从 1依次开始。七、程序清单#include<stdio.h>#include<stdlib.h>#include<string.h>#include<malloc.h>迷宫坐标位置类型typedefstruct{intx; // 行值inty; // 列值}PosType;#defineMAXLENGTH25// 设迷宫的最大行列为 25typedefintMazeType[MAXLENGTH][MAXLENGTH];// 迷宫数组 [行][列]typedefstruct// 栈的元素类型{intord;// 通道块在路径上的＂序号＂PosTypeseat;// 通道块在迷宫中的＂坐标位置＂intdi;// 从此通道块走向下一通道块的＂方向＂ (0～3表示东～北 )}SElemType;全局变量MazeTypem;// 迷宫数组intcurstep=1;// 当前足迹 ,初值为 1#defineSTACK_INIT_SIZE10 //存储空间初始分配量#defineSTACKINCREMENT2 //存储空间分配增量//栈的顺序存储表示typedefstructSqStack{SElemType*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=STACK_INIT_SIZE;return1;}//若栈 S为空栈（栈顶与栈底相同的）

，则返回

1，否则返回

0。intStackEmpty(SqStackS){if(S.top==S.base)return1;elsereturn0;}// 插入元素 e为新的栈顶元素。intPush(SqStack*S,SElemTypee){if((*S).top-(*S).base>=(*S).stacksize){

//栈满，追加存储空间(*S).base=(SElemType*)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType));if(!(*S).base)exit(0);(*S).top=(*S).base+(*S).stacksize;(*S).stacksize+=STACKINCREMENT;}*((*S).top)++=e;return1;}// 若栈不空，则删除 S的栈顶元素，用 e返回其值，并返回 1；否则返回 0。intPop(SqStack*S,SElemType*e){if((*S).top==(*S).base)return0;*e=*--(*S).top;

//这个等式的

++*

优先级相同，但是它们的运算方式，是自右向左return1;}//定义墙元素值为//当迷宫 m的b

0,可通过路径为 1,不能通过路径为点的序号为 1(可通过路径 )，return1;

-1,通过路径为足迹否则，return0

。intPass(PosTypeb){if(m[b.x][b.y]==1)return1;elsereturn0;}voidFootPrint(PosTypea)

//使迷宫

m的

a点的序号变为足迹

(curstep)

，表示经过{m[a.x][a.y]=curstep;}根据当前位置及移动方向，返回下一位置PosTypeNextPos(PosTypec,intdi){PosTypedirec[4]={{0,1},{1,0},{0,-1},{-1,0}};//{ 行增量,列增量}移动方向,依次为东南西北c.x+=direc[di].x;c.y+=direc[di].y;returnc;}//使迷宫 m的b点的序号变为 -1(不能通过的路径 )voidMarkPrint(PosTypeb){m[b.x][b.y]=-1;}//若迷宫 maze中存在从入口 start 到出口 end的通道，则求得一条存放在栈中(从栈底到栈顶)，并返回1；否则返回0intMazePath(PosTypestart,PosTypeend){SqStackS;PosTypecurpos;SElemTypee;InitStack(&S);curpos=start;do{if(Pass(curpos)){// 当前位置可以通过，即是未曾走到过的通道块FootPrint(curpos);// 留下足迹e.ord=curstep;e.di=0;Push(&S,e);//

入栈当前位置及状态curstep++;//

足迹加

1if(curpos.x==end.x&&curpos.y==end.y)//

到达终点

(出口

)return1;curpos=NextPos(curpos,e.di);}else{// 当前位置不能通过if(!StackEmpty(S)){Pop(&S,&e);// 退栈到前一位置curstep--;while(e.di==3&&!StackEmpty(S))//{

前一位置处于最后一个方向

(北)MarkPrint(e.seat);// 留下不能通过的标记 (-1)Pop(&S,&e);// 退回一步curstep--;}if(e.di<3)// 没到最后一个方向 (北){e.di++;// 换下一个方向探索Push(&S,e);curstep++;// 设定当前位置是该新方向上的相邻块curpos=NextPos(e.seat,e.di);}}}}while(!StackEmpty(S));return0;}输出迷宫的结构voidPrint(intx,inty){inti,j;for(i=0;i<x;i++){for(j=0;j<y;j++)printf("%3d",m[i][j]);printf("\n");}}voidmain(){PosTypebegin,end;inti,j,x,y,x1,y1,n,k;do{system("cls");//清屏函数printf("**************************物联网1班-15180118-刘沛航*************************\n\n\n");printf("1请输入迷宫的行数,列数\n");printf("2请输入迷宫内墙单元数\n");printf("3迷宫结构如下\n");printf("4输入迷宫的起点和终点\n");printf("5输出结果\n");printf("0退出\n");printf("\n\n请选择");scanf("%d",&n);switch(n){case1:{printf(" 请输入迷宫的行数 ,列数(包括外墙 )：(空格隔开 )");scanf("%d%d",&x,&y);for(i=0;i<x;i++)//

定义周边值为

0(同墙

){m[0][i]=0;

//迷宫