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

1、实验报告：迷宫问题题目：编写一个求解迷宫通路的程序一、 需求分析：1) 采用二维数组mazeMN来表示迷宫，其中：maze0j和mazeM-1j(0jN-1)及mazei0和mazeiN-1(0iM-1)为添加在迷宫外围的一圈障碍。数据元素值0表示通路，1表示障碍。限定迷宫的大小M8，N10.2) 本次实验直接在主程序中输入表示迷宫的二维数组。另外，迷宫的入口和出口位置都将在主程序中直接设置。3) 实验中求出的迷宫通路用“-”表示，迷宫的障碍用“#”表示，已走过但未能求出通路的路径用“”表示。4) 本程序只求出一条成功的通路。5) 本次实验将直接输出构建迷宫的二维数组、初始化的二维数组和求解后

2、的迷宫数组。二、 概要设计：数据结构及其抽象数据类型的定义。（1）栈的抽象数据类型ADT Stack数据对象：D=ai| aiCharSet,i=1,2n,n>=0数据关系：R1=<ai-1, ai >| ai-1, aiD,i=2,n基本操作：InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。操作结果：销毁栈S。ClearStack(&S)初始条件：栈S已存在。操作结果：将S清为空栈。StackLength(S)初始条件：栈S已存在。操作结果：返回栈S的长度。StackEmpty(S)初始条件：

3、栈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 

4、9; ','#','','*',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中存在一

5、条通路，则按以下规定改变迷宫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 <stdio.h>

6、#include <stdlib.h>#include <string.h>#include <conio.h>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;ty

7、pedef 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 si

8、ze;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

9、 &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) /出栈操作，本

10、质上是删除表头元素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=' ')retu

11、rn 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 Ne

12、xtPos(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

13、PrintMaze(MazeType ma) /对迷宫输出，实际是对一个二维数组的输出int i,j;printf("n"); for(i=0;i<ma.m;i+) printf("t");for(j=0;j<ma.n;j+) printf("%c ",ma.arrij); printf("n"); printf("n"); void InitMaze(MazeType &maze,int aN,int row,int col) /根据二维数组来初始化迷宫，这个二维数组可以设

14、计为由用户从键盘输入，解决不同迷宫的问题，但这里用户接口不是我们考虑的重点/数据结构学习时往往将输入的数据直接嵌入到程序中，以简化输入节约时间/二维数组名a做参数时，需要知道待读的二维数组的列数，因为C语言中二维数组是按行优先顺序存储的/控制每行长度的实际就是定义列的数值，所以要明确参数Nint i,j;maze.m=row;maze.n=col;for(i=0;i<row;i+) for(j=0;j<col;j+) if(aij=0)maze.arrij=' ' elsemaze.arrij='#' /*int MazePath(MazeType

15、&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(pas

16、s(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位置不可达，且栈不空，则把刚入栈的元素弹出做相关判断whil

17、e(e.di=4) && !StackEmpty(s) MarkPrint(maze,e.seat); /标识此路不通 Pop(s,e); /回到上一个位置curstep-; /不减一的话可以用于统计走过的总步数 if(e.di<4)/如果还有方向未走过，则沿新的方向继续试探 e.di+; Push(s,e); /默认新方向的下一位置可达，将当前位置入栈 curpos=NextPos(e.seat,e.di); /通过当前位置，以及去下一位置的方向得出新的位置，再循环查看新位置是否可达 while(!StackEmpty(s) && !found); re

18、turn found; */int MazePath(MazeType &maze,PosType start,PosType end) /此函数为递归方法求迷宫的算法static int steps=1;if(Same(start,end)FootPrint(maze,start);return steps;else if(pass(maze,start)FootPrint(maze,start);if(MazePath(maze,NextPos(start,1),end)+MazePath(maze,NextPos(start,2),end)+MazePath(maze,NextP

19、os(start,3),end)+MazePath(maze,NextPos(start,4),end)>0)/判断下一位置是否可走return steps+;/返回抵达出口时的步数elseMarkPrint(maze,start);/输出迷宫以及路径return FALSE;elsereturn FALSE;void Print(int mazeN)int i,j;printf("表示迷宫的数组n");for(i=0;i<M;i+)printf("t");for(j=0;j<N;j+)printf("%d ",ma

20、zeij);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 star

21、t,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、 程序调用关系为：