数据结构-迷宫-实验报告与代码 

.

一．需求分析

本程序是利用非递归的方法求出一条走出迷宫的路径，并将路径输出。首先由用户输入一组二维数组来组成迷宫，确认后程序自动运行，当迷宫有完整路径可以通过时，以0和1所组成的迷宫形式输出，标记所走过的路径结束程序；当迷宫无路径时，提示输入错误结束程序。程序执行的命令：1创建迷宫 ；2求解迷宫；3输出迷宫求解；

二．算法设计

本程序中采用的数据模型，用到的抽象数据类型的定义，程序的主要算法流程及各模块之间的层次调用关系 程序基本结构：

设定栈的抽象数据类型定义：

.

.

ADT Stack {

数据对象：D={ai|ai∈CharSet，i=1,2,3,…..,n,n>=0;} 数据关系：R={|ai?1，ai∈D,i=2,…,n}

设置迷宫的抽象类型 ADT maze{

数据对象：D={ai|ai∈‘ ’，‘@’，‘#’，‘1’,i=1,2,…,n,n>=0} 数据关系：R={r,c}

r={|ai-1,ai∈D, i=1,2,…,n,} c=|ai-1,ai∈D, i=1,2,…,n,}

结构体定义：

typedef struct //迷宫中x行y列的位置 {

int x; int y; }PosType;

typedef struct //栈类型

{ int ord; //通道块在路径上的“序号” PosType seat; //通道块在迷宫中的“坐标位置”

int di; //从此通道块走向下一通道块的“方向” }MazeType; typedef struct { MazeType *base; MazeType *top;

基本函数：

Status InitStack(MazeStack &S)//新建一个栈 Status Push(MazeStack &S, MazeType &e)//入栈 Status Pop(MazeStack &S, MazeType &e)//出栈 Status StackEmpty(MazeStack &S)//判断是否为空

int stacksize;

}MazeStack;

.

.

Status MazePath(PosType start, PosType end)//迷宫路径求解 void 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.top++ = e; return OK;

S.base = (MazeType *)realloc(S.base, (S.stacksize + if(!S.base)

exit(OVERFLOW);

S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT;

STACKINCREMENT) * sizeof(MazeType));

2）出栈操作

Status Pop(MazeStack &S, MazeType &e)//出栈 { }

if(S.top == S.base)

return ERROR; e = *--S.top; return OK;

3）判断栈是否为空

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 << \起点: \do {

if(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) { }

curpos = NextPos(curpos, e.di); //下一位置是当前位置++curstep; //探索下一步

cout << \终点 (\return TRUE; //到达终点（出口）

endl;

<< \

的东邻

.