数据结构-迷宫-实验报告与代码(共14页)

1、一需求分析 本程序是利用非递归的方法求出一条走出迷宫的路径，并将路径输出。首先由用户输入一组二维数组来组成迷宫，确认后程序自动运行，当迷宫有完整路径可以通过时，以0和1所组成的迷宫形式输出，标记所走过的路径结束程序；当迷宫无路径时，提示输入错误结束程序。程序执行的命令：1创建迷宫 ；2求解迷宫；3输出迷宫求解；二算法设计本程序中采用的数据模型，用到的抽象数据类型的定义，程序的主要算法流程及各模块之间的层次调用关系程序基本结构：设定栈的抽象数据类型定义：ADT Stack 数据对象：D=|CharSet，i=1,2,3,.,n,n>=0;数据关系：R=<， >|，D,i=2,n

2、设置迷宫的抽象类型ADT maze数据对象：D=ai|ai ，#，1,i=1,2,n,n>=0数据关系：R=r,cr=<ai-1,ai>|ai-1,aiD, i=1,2,n,c=<ai-1,ai>|ai-1,aiD, i=1,2,n,结构体定义：typedef struct /迷宫中x行y列的位置int x; int y;PosType;typedef struct /栈类型 int ord; /通道块在路径上的“序号” PosType seat; /通道块在迷宫中的“坐标位置” int di; /从此通道块走向下一通道块的“方向”MazeType;typedef

3、 struct MazeType *base; MazeType *top; int stacksize;MazeStack;基本函数：Status InitStack(MazeStack &S)/新建一个栈Status Push(MazeStack &S, MazeType &e)/入栈Status Pop(MazeStack &S, MazeType &e)/出栈Status StackEmpty(MazeStack &S)/判断是否为空Status MazePath(PosType start, PosType end)/迷宫路径求解voi

4、d FootPrint(PosType pos)PosType NextPos(PosType curPos, int &i)void MakePrint(PosType pos)三程序设计根据算法设计中给出的有关数据和算法，选定物理结构，详细设计需求分析中所要求的程序。包括：人机界面设计、主要功能的函数设计、函数之间调用关系描述等。1界面设计1）迷宫界面 2）迷宫路径显示2主要功能1) 入栈操作Status Push(MazeStack &S, MazeType &e) /入栈操作if(S.top - S.base >= S.stacksize)S.base =

5、 (MazeType *)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(MazeType);if(!S.base)exit(OVERFLOW);S.top = S.base + S.stacksize;S.stacksize += STACKINCREMENT;*S.top+ = e;return OK; 2） 出栈操作Status Pop(MazeStack &S, MazeType &e)/出栈if(S.top = S.base)return ERROR;e = *-S.top;return OK;3） 判断

6、栈是否为空Status StackEmpty(MazeStack &S)/判断是否为空if(S.base = S.top)return OK;return ERROR; 4）迷宫路径求解Status MazePath(PosType start, PosType end)/迷宫路径求解PosType curpos;MazeStack S;MazeType e;int curstep;InitStack(S);curpos = start; /设定当前位置为入口位置curstep = 1; /探索第一步cout << "起点: "<< &quo

7、t;(" <<start.y << "," << start.x << ")" << endl;doif(Pass(curpos) /当前位置可以通过，即是未曾走到的通道块FootPrint(curpos); /留下足迹e.ord = curstep;e.seat = curpos;e.di = 1;Push(S, e); /加入路径if(curpos.x = end.x && curpos.y = end.y)cout << "n终点 (&quo

8、t; << e.seat.y << "," << e.seat.x << ")"return TRUE; /到达终点（出口）curpos = NextPos(curpos, e.di); /下一位置是当前位置的东邻+curstep; /探索下一步else /当前位置不能通过if(!StackEmpty(S)Pop(S, e);while(e.di = 4 && !StackEmpty(S)MakePrint(e.seat); /留下不能通过的标记Pop(S, e);cout <<

9、 "倒退到(" << e.seat.y << "," << e.seat.x << ")"if(e.di < 4)+e.di; /换下一个方向探索Push(S, e);curpos = NextPos(e.seat, e.di); /设定当前位置是该新方向上的相邻块while(!StackEmpty(S);return FALSE;5）探索下一个位置PosType NextPos(PosType curPos, int &i)switch(i) /顺时针方向case 1:+

10、curPos.x; /东if(mazeMapcurPos.ycurPos.x != 2)break;-curPos.x;case 2:i = 2;+curPos.y; /南if(mazeMapcurPos.ycurPos.x != 2)break;-curPos.y;case 3:i = 3;-curPos.x; /西if(mazeMapcurPos.ycurPos.x != 2)break;+curPos.x;case 4:i = 4;-curPos.y; /北if(mazeMapcurPos.ycurPos.x = 2)+curPos.y;mazeMapcurPos.ycurPos.x =

11、 0;break;return curPos;6） 标记走过的路径void FootPrint(PosType pos)mazeMappos.ypos.x = 2; /将走过的路径设为27） 标记作废路径void MakePrint(PosType pos)cout << "n(" << pos.y << "," << pos.x << ")走不通，作废"mazeMappos.ypos.x = 0; /将走不通的块替换为墙壁3函数调用 int main()PosType ma

12、zeStart, mazeEnd;mazeStart.x = 1;/开始与结束点mazeStart.y = 1;mazeEnd.x = 8;mazeEnd.y = 8;cout << "迷宫: " << endl;for(int i = 0; i < 10; +i)for(int j = 0; j < 10; +j)cout << mazeMapij;cout << endl;cout << endl << endl;if(MazePath(mazeStart, mazeEnd)cout &

13、lt;< "n走通迷宫" << endl;elsecout << "n走不通迷宫" << endl;system("PAUSE");return 0;四测试与分析1、在编程序时迷宫的出入栈掌握的还好，可是编到迷宫方向的选择，与迷宫路径错误的情况时，不知道怎么处理，然后自己通过看书和网上查阅资料基本解决了问题。2、在写代码的过程中，没有弄清使用指针与引用之后，结构体如何使用。当使用指针的时候要使用.，当使用引用或数的时候，要使用->。源程序：#define OK 1#define ERRO

14、R 0#define TRUE 1#define FALSE 0#define OVERFLOW -2#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef int Status;typedef struct/迷宫中x行y列的位置int x;int y;PosType;typedef struct/栈类型int ord; /通道块在路径上的“序号”PosType seat; /通道块在迷宫中的“坐标位置”int di; /从此通道块走向下一通道块的“方向”, /1:东 2:北 3:西 （顺时针)MazeType;typedef s

15、tructMazeType *base;MazeType *top;int stacksize;MazeStack;#include <iostream>using namespace std;Status InitStack(MazeStack &S);Status Push(MazeStack &S, MazeType &e);Status Pop(MazeStack &S, MazeType &e);Status StackEmpty(MazeStack &S);Status MazePath(PosType start, Po

16、sType end);Status Pass(PosType &pos);void FootPrint(PosType pos);PosType NextPos(PosType curPos, int &i);void MakePrint(PosType pos);/迷宫地图，0表示墙壁，1表示通路,入口:mazeMap11,出口mazeMap88int mazeMap1010 = /0,1,2,3,4,5,6,7,8,90,0,0,0,0,0,0,0,0,0, /00,1,1,0,1,1,1,0,1,0, /10,1,1,0,1,1,1,0,1,0, /20,1,1,1,1,

17、0,0,1,1,0, /30,1,0,0,0,1,1,1,1,0, /40,1,1,1,0,1,1,1,1,0, /50,1,0,1,1,1,0,1,1,0, /60,1,0,0,0,1,0,0,1,0, /70,0,1,1,1,1,1,1,1,0, /80,0,0,0,0,0,0,0,0,0 /9;int main()PosType mazeStart, mazeEnd;mazeStart.x = 1;/开始与结束点mazeStart.y = 1;mazeEnd.x = 8;mazeEnd.y = 8;cout << "迷宫: " << endl;

18、for(int i = 0; i < 10; +i)for(int j = 0; j < 10; +j)cout << mazeMapij;cout << endl;cout << endl << endl;if(MazePath(mazeStart, mazeEnd)cout << "n走通迷宫" << endl;elsecout << "n走不通迷宫" << endl;system("PAUSE");return 0;Sta

19、tus InitStack(MazeStack &S)/新建一个栈S.base = (MazeType *)malloc(STACK_INIT_SIZE * sizeof(MazeType);if(!S.base)exit(OVERFLOW);S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK;Status Push(MazeStack &S, MazeType &e)/入栈if(S.top - S.base >= S.stacksize)S.base = (MazeType *)realloc(S.bas

20、e, (S.stacksize + STACKINCREMENT) * sizeof(MazeType);if(!S.base)exit(OVERFLOW);S.top = S.base + S.stacksize;S.stacksize += STACKINCREMENT;*S.top+ = e;return OK;Status Pop(MazeStack &S, MazeType &e)/出栈if(S.top = S.base)return ERROR;e = *-S.top;return OK;Status StackEmpty(MazeStack &S)/判断是

21、否为空if(S.base = S.top)return OK;return ERROR;Status MazePath(PosType start, PosType end)/迷宫路径求解PosType curpos;MazeStack S;MazeType e;int curstep;InitStack(S);curpos = start; /设定当前位置为入口位置curstep = 1; /探索第一步cout << "起点: "<< "(" <<start.y << "," <

22、< start.x << ")" << endl;doif(Pass(curpos) /当前位置可以通过，即是未曾走到的通道块FootPrint(curpos); /留下足迹e.ord = curstep;e.seat = curpos;e.di = 1;Push(S, e); /加入路径if(curpos.x = end.x && curpos.y = end.y)cout << "n终点 (" << e.seat.y << "," <<

23、e.seat.x << ")"return TRUE; /到达终点（出口）curpos = NextPos(curpos, e.di); /下一位置是当前位置的东邻+curstep; /探索下一步else /当前位置不能通过if(!StackEmpty(S)Pop(S, e);while(e.di = 4 && !StackEmpty(S)MakePrint(e.seat); /留下不能通过的标记Pop(S, e);cout << "倒退到(" << e.seat.y << "," << e.seat.x << ")"if(e.di < 4)+e.di; /换下一个方向探索Push(S, e);curpos = NextPos(e.seat, e.di); /设定当前位置是该新方向上的相邻块while(!StackEmpty(S);return FALSE;Status Pass(PosType &