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

数据结构迷宫问题实验报告..资料..《数据结构与算法设计》迷宫问题实验报告——实验二专业：物联网工程班级：物联网1班学号：15180118：刘沛航数据结构迷宫问题实验报告全文共16页，当前为第1页。数据结构迷宫问题实验报告全文共16页，当前为第1页。实验目的

本程序是利用非递归的方法求出一条走出迷宫的路径，并将路径输出。首先由用户输入一组二维数组来组成迷宫，确认后程序自动运行，当迷宫有完整路径可以通过时，以0和1所组成的迷宫形式输出，标记所走过的路径结束程序；当迷宫无路径时，提示输入错误结束程序。二、实验内容用一个m*m长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序对于任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。三、程序设计1、概要设计（1）

设定栈的抽象数据类型定义ADTStack{数据对象：D={ai|ai属于CharSet，i=1、2…n，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）

初始条件：栈已经存在数据结构迷宫问题实验报告全文共16页，当前为第2页。

操作结果：若栈不为空，用e返回栈顶元数据结构迷宫问题实验报告全文共16页，当前为第2页。

StackEmpty(&S)

初始条件：栈已经存在

操作结果：判断栈是否为空。若栈为空，返回1，否则返回0

Destroy(&S)

初始条件：栈已经存在

操作结果：销毁栈s}ADTStack（2）设定迷宫的抽象数据类型定义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,…M，j=1,2,…N}基本操作：InitMaze(MazeType&maze,inta[][COL],introw,intcol){初始条件：二维数组inta[][COL],已经存在，其中第1至第m-1行，每行自第1到第n-1列的元素已经值，并以值0表示障碍，值1表示通路。操作结果：构造迷宫的整形数组，以空白表示通路，字符‘0’表示障碍

在迷宫四周加上一圈障碍

MazePath（&maze）{

初始条件：迷宫maze已被赋值

操作结果：若迷宫maze中存在一条通路，则按如下规定改变maze的状态；以字符‘*’表示路径上的位置。字符‘’表示‘死胡同’；否则迷宫的状态不变}PrintMaze（M）{初始条件：迷宫M已存在操作结果：以字符形式输出迷宫}

}ADTmaze数据结构迷宫问题实验报告全文共16页，当前为第3页。（3）本程序包括三个模块数据结构迷宫问题实验报告全文共16页，当前为第3页。a、

主程序模块voidmain(){初始化；构造迷宫；迷宫求解；迷宫输出；}b、

栈模块——实现栈的抽象数据类型c、

迷宫模块——实现迷宫的抽象数据类型2、详细设计（1）坐标位置类型：typedefstruct{

introw;

//迷宫中的行

intcol;

//......的列}PosType;//坐标

（2）

迷宫类型：typedefstruct{

intm,n;

intarr[RANGE][RANGE];}MazeType;

//迷宫类型void

InitMaze(MazeType&maze,inta[][COL],introw,intcol)\//设置迷宫的初值，包括边缘一圈的值BoolMazePath(MazeType&maze,PosTypestart,PosTypeend)//求解迷宫maze中，从入口start到出口end的一条路径//若存在，则返回true，否则返回falseVoidPrintMaze（MazeTypemaze）//将迷宫打印出来（3）

栈类型：typedefstruct{

int

step;

//当前位置在路径上的"序号"

PosType

seat;

//当前的坐标位置

DirectiveType

di;

//往下一个坐标位置的方向}SElemType;//栈的元素类型

typedefstruct{数据结构迷宫问题实验报告全文共16页，当前为第4页。

SElemType*base;数据结构迷宫问题实验报告全文共16页，当前为第4页。

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中的每个节点调用函数Visit4求迷宫路径的伪码算法：StatusMazePath(MazeType&maze,PosTypestart,PosTypeend){//求解迷宫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);

//留下不能通过的标记,并退回步数据结构迷宫问题实验报告全文共16页，当前为第5页。

}数据结构迷宫问题实验报告全文共16页，当前为第5页。

if(e.di<4){

e.di++;Push(s,e);

//换一个方向探索

curpos=NextPos(e.seat,e.di);

//设定当前位置是该方向上的相块

}//if

}//if

}//else

}while(!StackEmpty(s));

returnFALSE;}//MazePath四、程序调试分析1.首先呢，想自己读入数据的，回来发现那样，很麻烦，所以还是事先定义一个迷宫。2.栈的元素类型一开始有点迷惑，后来就解决了3.本题中三个主要算法；InitMaze，MazePath和PrintMaze的时间复杂度均为O（m*n）本题的空间复杂度也是O（m*n）五、用户使用说明1．本程序运行在windows系列的操作系统下，执行文件为：Maze_Test.exe。数据结构迷宫问题实验报告全文共16页，当前为第6页。六、程序运行结果数据结构迷宫问题实验报告全文共16页，当前为第6页。1.建立迷宫：2．通过1功能建立8*8的迷宫后，通过2功能继续建立迷宫内部：通过建立自己设定单元数目建立迷宫内墙。数据结构迷宫问题实验报告全文共16页，当前为第7页。3．通过3功能观察已建立的迷宫结构：数据结构迷宫问题实验报告全文共16页，当前为第7页。4．通过4功能确立迷宫起点和终点：（此处像我们随机选择4,4和2,7分别为起点终点）数据结构迷宫问题实验报告全文共16页，当前为第8页。5．执行5功能，判断是否有路径走出迷宫：数据结构迷宫问题实验报告全文共16页，当前为第8页。这种情况无法走出迷宫。我们再次观察图像设4,4和1,6分别为起点终点，再运行5功能。数据结构迷宫问题实验报告全文共16页，当前为第9页。数据结构迷宫问题实验报告全文共16页，当前为第9页。观察到可以成功解开迷宫步数从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;数据结构迷宫问题实验报告全文共16页，当前为第10页。//全局变量数据结构迷宫问题实验报告全文共16页，当前为第10页。MazeTypem;//迷宫数组intcurstep=1;//当前足迹,初值为1#defineSTACK_INIT_SIZE10 //存储空间初始分配量#defineSTACKINCREMENT2 //存储空间分配增量//栈的顺序存储表示typedefstructSqStack{ SElemType*base; //在栈构造之前和销毁之后，base的值为NULL SElemType*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; else return0;}// 插入元素e为新的栈顶元素。intPush(SqStack*S,SElemTypee){ if((*S).top-(*S).base>=(*S).stacksize) //栈满，追加存储空间 {数据结构迷宫问题实验报告全文共16页，当前为第11页。 (*S).base=(SElemType*)realloc((*S).base,数据结构迷宫问题实验报告全文共16页，当前为第11页。 ((*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;}//定义墙元素值为0,可通过路径为1,不能通过路径为-1,通过路径为足迹//当迷宫m的b点的序号为1(可通过路径)，return1;否则，return0。intPass(PosTypeb){ if(m[b.x][b.y]==1) return1; else return0;}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;数据结构迷宫问题实验报告全文共16页，当前为第12页。}数据结构迷宫问题实验报告全文共16页，当前为第12页。//使迷宫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.seat.x=curpos.x; e.seat.y=curpos.y; e.di=0; Push(&S,e);//入栈当前位置及状态 curstep++;//足迹加1 if(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--; }数据结构迷宫问题实验报告全文共16页，当前为第13页。 if(e.di<3)//没到最后一个方向(北)数据结构迷宫问题实验报告全文共16页，当前为第13页。 { 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){数据结构迷宫问题实验报告全文共16页，当前为第14页。case1:{ 数据结构迷宫问题实验报告全文共16页，当前为第14页。 printf("请输入迷宫的行数,列数(包括外墙)：(空格隔开)"); scanf("%d%d",&x,&y); for(i=0;i<x;i++)//定义