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

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

2、的通路，或得出没有通路的结论。三、程序设计 1、概要设计（1） 设定栈的抽象数据类型定义 ADT Stack数据对象：D=ai|ai属于CharSet，i=1、2n，n>=0数据关系：R=<ai-1,ai>|ai-1,ai属于D，i=2,3,n基本操作：          InitStack(&S)             

3、0;   操作结果：构造一个空栈          Push（&S，e）                 初始条件：栈已经存在              

4、;   操作结果：将e所指向的数据加入到栈s中          Pop（&S,&e）                 初始条件：栈已经存在            

5、     操作结果：若栈不为空，用e返回栈顶元素，并删除栈顶元素          Getpop（&S，&e）                 初始条件：栈已经存在        &#

6、160;        操作结果：若栈不为空，用e返回栈顶元          StackEmpty(&S)                 初始条件：栈已经存在      

7、0;          操作结果：判断栈是否为空。若栈为空，返回1，否则返回0          Destroy(&S)                 初始条件：栈已经存在    

8、             操作结果：销毁栈sADT Stack（2）设定迷宫的抽象数据类型定义ADT yanshu数据对象：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,

9、N          COL=<ai,j-1,ai,j>|ai,j-1,ai,j属于D,i=0,1,M，j=1,2,N基本操作：InitMaze(MazeType &maze, int aCOL, int row, int col)初始条件：二维数组int aCOL,已经存在，其中第1至第m-1行，每行自第1到第n-1列的元素已经值，并以值0表示障碍，值1表示通路。操作结果：构造迷宫的整形数组，以空白表示通路，字符0表示障碍    &#

10、160;           在迷宫四周加上一圈障碍              MazePath（&maze）                初始条件：迷宫maze已被赋值 

11、;               操作结果：若迷宫maze中存在一条通路，则按如下规定改变maze的状态；以字符*表示路径上的位置。字符表示死胡同；否则迷宫的状态不变PrintMaze（M）初始条件：迷宫M已存在操作结果：以字符形式输出迷宫           ADTmaze（3）本程序包括三个模块a、 主程序模块void mai

12、n()初始化；构造迷宫；迷宫求解；迷宫输出；b、 栈模块实现栈的抽象数据类型c、 迷宫模块实现迷宫的抽象数据类型2、详细设计 （1）坐标位置类型： typedef struct         int row;    /迷宫中的行    int col;      /.的列PosType;/坐标    

13、60;                                            （2） 迷宫类型：typedef struct 

14、;   int m,n;    int arrRANGERANGE;MazeType;            /迷宫类型void InitMaze(MazeType &maze, int aCOL, int row, int col)/设置迷宫的初值，包括边缘一圈的值Bool MazePath(MazeType &maze,PosType start, PosType end)/求

15、解迷宫maze中，从入口start到出口end的一条路径/若存在，则返回true，否则返回falseVoid PrintMaze（MazeType maze）/将迷宫打印出来（3）  栈类型：typedef struct    int          step;    /当前位置在路径上的"序号"    PosType 

16、60;    seat;    /当前的坐标位置    DirectiveType   di;        /往下一个坐标位置的方向SElemType;/栈的元素类型 typedef struct    SElemType *base;    SElemType *top;&#

17、160;   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，否则返回FALSEStat

18、ue GetTop（SqStack &S，SElemType e）/r若栈S不空，则以e待会栈顶元素并返回TRUE，否则返回FALSEStatue Pop(SqStack&S，SElemType e)/若分配空间成功，则在S的栈顶插入新的栈顶元素s并返回TRUE/否则栈不变，并返回FALSEStatue Push(SqStack&S，SElemType &e)/若分配空间程控，则删除栈顶并以e带回其值，则返回TRUE/否则返回FALSEVoid StackTraverse（SqStack &S，Status）（*Visit）（SElemType e）/从

19、栈顶依次对S中的每个节点调用函数Visit4求迷宫路径的伪码算法：Status MazePath(MazeType &maze,PosType start, PosType end) /求解迷宫maze中,从入口start到出口end的一条路径    InitStack(s);    PosType curpos = start;    int curstep = 1;        &#

20、160;       /探索第一部    do        if( Pass(maze,curpos) )    /如果当前位置可以通过,即是未曾走到的通道块            FootPrint(maze,curpos); 

21、0;          /留下足迹            e = CreateSElem(curstep,curpos,1);    /创建元素            Push(s,e);  

22、0;         if( PosEquare(curpos,end) )    return TRUE;            curpos =NextPos(curpos,1);            /获得下一节点:当前位

23、置的东邻            curstep+;                            /探索下一步       

24、; else                        /当前位置不能通过            if(!StackEmpty(s)        

25、;        Pop(s,e);                while(e.di=4 && !StackEmpty(s) )                 

26、0;  MarkPrint(maze,e.seat); Pop(s,e);   /留下不能通过的标记,并退回步                                if(e.di<4)  

27、60;                 e.di+; Push(s,e);            /换一个方向探索                &#

28、160;   curpos = NextPos(e.seat,e.di);    /设定当前位置是该方向上的相块                /if            /if      

29、;  /else    while(!StackEmpty(s);    return FALSE;/MazePath四、程序调试分析 1.首先呢，想自己读入数据的，回来发现那样，很麻烦，所以还是事先定义一个迷宫。2.栈的元素类型 一开始有点迷惑，后来就解决了3.本题中三个主要算法；InitMaze，MazePath和PrintMaze的时间复杂度均为O（m*n）本题的空间复杂度也是O（m*n）五、用户使用说明 1本程序运行在windows系列的操作系统下，执行文件为：Maze_Test.exe

30、。六、程序运行结果1.建立迷宫：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.

31、h>/ 迷宫坐标位置类型typedef struct int x;/ 行值 int y;/ 列值 PosType;#define MAXLENGTH 25 / 设迷宫的最大行列为25 typedef int MazeTypeMAXLENGTHMAXLENGTH; / 迷宫数组行列 typedef struct / 栈的元素类型 int ord; / 通道块在路径上的序号 PosType seat; / 通道块在迷宫中的坐标位置 int di; / 从此通道块走向下一通道块的方向(03表示东北) SElemType;/ 全局变量 MazeType m; / 迷宫数组 int curstep

32、=1; / 当前足迹,初值为1 #define STACK_INIT_SIZE 10/ 存储空间初始分配量 #define STACKINCREMENT 2/ 存储空间分配增量 / 栈的顺序存储表示 typedef struct SqStackSElemType *base;/ 在栈构造之前和销毁之后，base的值为NULL SElemType *top;/ 栈顶指针 int stacksize;/ 当前已分配的存储空间，以元素为单位 SqStack;/ 顺序栈/构造一个空栈Sint InitStack(SqStack *S)/ 为栈底分配一个指定大小的存储空间(*S).base = (SEl

33、emType *)malloc(STACK_INIT_SIZE*sizeof(SElemType);if( !(*S).base )exit(0);(*S).top = (*S).base;/ 栈底与栈顶相同表示一个空栈(*S).stacksize = STACK_INIT_SIZE;return 1;/ 若栈S为空栈（栈顶与栈底相同的），则返回1，否则返回0。int StackEmpty(SqStack S)if(S.top = S.base)return 1;elsereturn 0;/插入元素e为新的栈顶元素。int Push(SqStack *S, SElemType e)if(*S)

34、.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;return 1;/若栈不空，则删除S的栈顶元素，用e返回其值，并返回1；否则返回0。int

35、Pop(SqStack *S,SElemType *e)if(*S).top = (*S).base)return 0;*e = *-(*S).top; / 这个等式的+ * 优先级相同，但是它们的运算方式，是自右向左return 1;/ 定义墙元素值为0,可通过路径为1,不能通过路径为-1,通过路径为足迹/ 当迷宫m的b点的序号为1(可通过路径)，return 1; 否则，return 0。int Pass(PosType b) if(mb.xb.y=1)return 1;elsereturn 0;void FootPrint(PosType a) / 使迷宫m的a点的序号变为足迹(curs

36、tep)，表示经过ma.xa.y=curstep;/ 根据当前位置及移动方向，返回下一位置 PosType NextPos(PosType c,int di)PosType direc4=0,1,1,0,0,-1,-1,0; / 行增量,列增量 / 移动方向,依次为东南西北 c.x+=direcdi.x;c.y+=direcdi.y;return c;/ 使迷宫m的b点的序号变为-1(不能通过的路径)void MarkPrint(PosType b) mb.xb.y=-1;/ 若迷宫maze中存在从入口start到出口end的通道，则求得一条 / 存放在栈中(从栈底到栈顶)，并返回1；否则返回

37、0 int MazePath(PosType start,PosType end) SqStack S;PosType curpos;SElemType e;InitStack(&S);curpos=start;doif(Pass(curpos)/ 当前位置可以通过，即是未曾走到过的通道块 FootPrint(curpos); / 留下足迹 e.ord=curstep;e.seat.x=curpos.x;e.seat.y=curpos.y;e.di=0;Push(&S,e); / 入栈当前位置及状态 curstep+; / 足迹加1 if(curpos.x=end.x&

38、&curpos.y=end.y) / 到达终点(出口) return 1;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+;

39、/ 换下一个方向探索Push(&S,e); curstep+;/ 设定当前位置是该新方向上的相邻块curpos=NextPos(e.seat,e.di);while(!StackEmpty(S);return 0;/ 输出迷宫的结构 void Print(int x,int y) int i,j;for(i=0;i<x;i+)for(j=0;j<y;j+)printf("%3d",mij);printf("n"); void main()PosType begin,end;int i,j,x,y,x1,y1,n,k;dosystem("cls"); /清屏函数printf("*物联网1班-15