数据结构试验报告-迷宫问题.doc

实验报告：迷宫问题题目：编写一个求解迷宫通路的程序一、 需求分析：1) 采用二维数组mazeMN来表示迷宫，其中：maze0j和mazeM-1j(0jN-1)及mazei0和mazeiN-1(0iM-1)为添加在迷宫外围的一圈障碍。数据元素值0表示通路，1表示障碍。限定迷宫的大小M8，N10.2) 本次实验直接在主程序中输入表示迷宫的二维数组。另外，迷宫的入口和出口位置都将在主程序中直接设置。3) 实验中求出的迷宫通路用“-”表示，迷宫的障碍用“#”表示，已走过但未能求出通路的路径用“”表示。4) 本程序只求出一条成功的通路。5) 本次实验将直接输出构建迷宫的二维数组、初始化的二维数组和求解后的迷宫数组。二、 概要设计：数据结构及其抽象数据类型的定义。（1）栈的抽象数据类型ADT Stack数据对象：D=ai| aiCharSet,i=1,2n,n=0数据关系：R1=| ai-1, aiD,i=2,n基本操作：InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。操作结果：销毁栈S。ClearStack(&S)初始条件：栈S已存在。操作结果：将S清为空栈。StackLength(S)初始条件：栈S已存在。操作结果：返回栈S的长度。StackEmpty(S)初始条件：栈S已存在。操作结果：若S为空栈，则返回TRUE，否则返回FALSE。GetTop(S，&e)初始条件：栈S已存在。操作结果：若栈S不空，则以e返回栈顶元素。Push(&S， e)初始条件：栈S已存在。操作结果：在栈S的栈顶插入新的栈顶元素e。Pop(&S，&e)初始条件：栈S已存在。操作结果：删除S的栈顶元素，并以e返回其值。StackTraverse（S，visit（）初始条件：栈S已存在。操作结果：从栈底到栈顶依次对S中的每个元素调用函数visit（）。 ADT Stack （2）迷宫的抽象数据类型ADT maze数据对象：D=ai,j| ai,j ,#,*,0=i=m+1,0=j=n+1,m,n=10数据关系：R=ROW,COL基本操作：InitMaze(&M,a,row,col)初始条件：二维数组arow+2col+2已存在，其中自第1行至第row+1行，每行中自第1列至第col+1列的元素已有值，并且以值0表示通路，以值1表示障碍。操作结果：构成迷宫的字符型数组，以空白字符表示通路，以字符#表示障碍，并在迷宫四周加上一圈障碍。MazePath(&M)初始条件：迷宫M已被赋值。操作结果：若迷宫M中存在一条通路，则按以下规定改变迷宫M的状态：以字符*表示路径上的位置，字符表示“死胡同”，否则迷宫的状态不变。PrintMaze（M）初始条件：迷宫M已存在。操作结果：以字符形式输出迷宫。 ADT maze三、 详细设计：1、 程序具体代码为：/ MazePath.cpp : 定义控制台应用程序的入口点。/#include stdafx.h#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2#include #include #include #include typedef int Status;#define RANGE 20/RANGE为实际分配的空间行列数#define M 8/maze数组的行数 #define N 11/ maze数组的列数 typedef struct/表达迷宫元素位置信息的坐标int r,c;PosType;typedef struct/m，n为待处理的迷宫的行列数，RANGE为实际分配的空间行列数int m,n;char arrRANGERANGE;MazeType;typedef int directiveType;/东西南北方向用1，2，3，4整数对应typedef struct/路径拟用栈来存储，此处定义栈元素中数据域的信息int step;/存储到达该点时经历的步数PosType seat;/该点位置directiveType di;/从该点位置走向下一位置的方向ElemType;typedef struct NodeType/路径拟用链栈来存储ElemType data;struct NodeType *next;NodeType,*LinkType;typedef struct/对链栈的头指针和元素个数进行封装LinkType top;int size;Stack;/以上是对存储结构逐层进行定义void InitStack(Stack &S) /构建空链栈，不带头结点S.top=NULL; S.size=0; Status MakeNode(LinkType &p,ElemType e) /创建一个新结点，以便插入，本函数可作为链式存储创建结点的通用函数，可用于链表、链栈、链队的插入操作p=(NodeType *)malloc(sizeof(NodeType); if(!p)return FALSE; p-data=e;p-next=NULL; return TRUE; Status Push(Stack &S,ElemType e) /入栈操作，在这里本质上是栈头（链表头）进行插入LinkType p; if(MakeNode(p,e) p-next=S.top; S.top=p; S.size+; return TRUE; return FALSE; Status StackEmpty(Stack S) /判断是否为空栈，这里是通过top指针为NULL来判断的，本质上也可以通过size是否为0来判断if(S.top=NULL)return TRUE; return FALSE; Status Pop(Stack &S,ElemType &e) /出栈操作，本质上是删除表头元素LinkType p;if(StackEmpty(S) return FALSE; else p=S.top;S.top=S.top-next; e=p-data; S.size-; free(p);return TRUE; Status pass(MazeType maze,PosType curpos) /判断迷宫Maze中，当前位置curpos是否是一个可达位置int m,n; /注意这里的m，n只是表达下标的临时变量，与前面出现的m，n是不一样的m=curpos.r; n=curpos.c; if(maze.arrmn= )return TRUE; return FALSE; Status Same(PosType curpos,PosType end) /判断当前位置curpos是否已达出口if(curpos.r=end.r & curpos.c=end.c)return TRUE; return FALSE; void FootPrint(MazeType &maze,PosType curpos) /在迷宫中标识走过的位置，避免在有路可走时还走回头路出现死循环int m,n; m=curpos.r; n=curpos.c; maze.arrmn=-; PosType NextPos(PosType curpos,int di) /通过di的值，确定下一步的位置，下一步位置实际是当前位置的四个邻居中的一个switch(di)case 1:curpos.c+; /向东走break;case 2:curpos.r+; /向南走break;case 3:curpos.c-; /向西走break;case 4:curpos.r-; /向北走 break;return curpos; void MarkPrint(MazeType &maze,PosType p) /对试探无路可走后回退的位置做特殊标识maze.arrp.rp.c=; void PrintMaze(MazeType ma) /对迷宫输出，实际是对一个二维数组的输出int i,j;printf(n); for(i=0;ima.m;i+) printf(t);for(j=0;jma.n;j+) printf(%c ,ma.arrij); printf(n); printf(n); void InitMaze(MazeType &maze,int aN,int row,int col) /根据二维数组来初始化迷宫，这个二维数组可以设计为由用户从键盘输入，解决不同迷宫的问题，但这里用户接口不是我们考虑的重点/数据结构学习时往往将输入的数据直接嵌入到程序中，以简化输入节约时间/二维数组名a做参数时，需要知道待读的二维数组的列数，因为C语言中二维数组是按行优先顺序存储的/控制每行长度的实际就是定义列的数值，所以要明确参数Nint i,j;maze.m=row;maze.n=col;for(i=0;irow;i+) for(j=0;jcol;j+) if(aij=0)maze.arrij= ; elsemaze.arrij=#; /*int MazePath(MazeType &maze,PosType start,PosType end) /求解迷宫的关键函数，maze作为引用型变量是因为要对相关路径做一些标识/返回值为路径的长度,返回0表示无通路Stack s; int curstep=1; /统计路径长度实际可不用curstep，栈s中的size分量已有相关信息，修改一下程序curstep可以用于统计走过的总步数int found=0; ElemType e; /以栈元素的形式暂存当前位置的相关信息，以便入栈构成路径PosType curpos=start; /置开始位置为当前位置InitStack(s);do /栈不空且未到出口则继续循环if(pass(maze,curpos) /如果curpos位置可达则先入栈 FootPrint(maze,curpos); /如果可通则标记为-，当然后边如发现是死胡同，则会重新标记为另外的符号e.step=curstep; e.seat=curpos; e.di=1; Push(s,e); if(Same(curpos,end)found=s.size;else curpos=NextPos(curpos,1); /到新位置时默认先向东走 curstep+; else if(!StackEmpty(s) Pop(s,e); /如果curpos位置不可达，且栈不空，则把刚入栈的元素弹出做相关判断while(e.di=4) & !StackEmpty(s) MarkPrint(maze,e.seat); /标识此路不通 Pop(s,e); /回到上一个位置curstep-; /不减一的话可以用于统计走过的总步数 if(e.di0)/判断下一位置是否可走return steps+;/返回抵达出口时的步数elseMarkPrint(maze,start);/输出迷宫以及路径return FALSE;elsereturn FALSE;void Print(int mazeN)int i,j;printf(表示迷宫的数组n);for(i=0;iM;i+)printf(t);for(j=0;jN;j+)printf(%d ,mazeij);printf(n);printf(n);void main()int step=0;int mazeMN=1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,0,1,1,1,0,0,1,1,0,0,0,0,0,1,0,0,1,1,1,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,0,1,1,0,1,1,1,1,0,0,1,0,1,1,0,0,1,1,1,1,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1;/在程序中直接输入一个建立迷宫的数组MazeType L;PosType start,end;Print(maze);/调用Print函数输出直接输出已建立的迷宫数组InitMaze(L,maze,M,N);/调用InitMaze函数将二维数组初始化为迷宫start.r=1;start.c=1;/设置迷宫的入口end.r=6;end.c=9;/设置迷宫的出口printf(由数组转化出的迷宫);PrintMaze(L);/输出已转化的迷宫if(step=MazePath(L,start,end)printf(迷宫的路径，用-表示,路径长度为:%d,step);elseprintf(此迷宫没有通路！);PrintMaze(L);2、 程序调用关系为： mainPrint InitMaze PrintMaze MazePathSame FootPrint pass NextPos MarkPrint MazePath四、 调试分析：1) 本次实验采用两种求解迷宫路径的核心算法，一种是直接调用相关问题的函数，另一种是采用递归函数的方法（实验详细设计中采用的是第二种）。相比较第一种方法，采用递归的方法更加简洁明了。另外，本次实验为了方便起见采用了直接在主程序中输入用于构建迷宫的二维数组的方法，其实可以采用文件形式来输入构建迷宫的二维数组。2) 本次实验中的另一个的核心就是如何建立存储迷宫的数据结构，即如何用链栈来存储迷宫路径中的各位置以及下一步将要走的方向。3) 对试探无路可走后回退的位置要做特殊标识，另外还要在迷宫中标识走过的位置，避免在有路可走时还走回头路出现死循环。4) 本题中主要算法：PrintMaze和MazePath的时间复杂度均为O（