一．需求分析

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

二．算法设计

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

程序基本结构：

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

ADT Stack {

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

c=<ai-1,ai>|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;

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)//迷宫路径求解 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.base = (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）判断栈是否为空

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 << "起点: "<< "(" <<start.y << "," << start.x << ")" << endl; 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)

{

cout << "\n终点 (" << 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 << "倒退到(" << 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:

++curPos.x; //东

if(mazeMap[curPos.y][curPos.x] != 2)

break;

--curPos.x;

case 2:

i = 2;

++curPos.y; //南

if(mazeMap[curPos.y][curPos.x] != 2)

break;

--curPos.y;

case 3:

i = 3;

--curPos.x; //西

if(mazeMap[curPos.y][curPos.x] != 2)

break;

++curPos.x;

case 4:

i = 4;

--curPos.y; //北

if(mazeMap[curPos.y][curPos.x] == 2)

{

++curPos.y;

mazeMap[curPos.y][curPos.x] = 0;

} } } break; return curPos;

6）标记走过的路径

void FootPrint(PosType pos)

{

mazeMap[pos.y][pos.x] = 2; //将走过的路径设为2 }

7）标记作废路径

void MakePrint(PosType pos)

{

cout << "\n(" << pos.y << "," << pos.x << ")走不通，作废";

} mazeMap[pos.y][pos.x] = 0; //将走不通的块替换为墙壁

3函数调用

int main()

{

PosType mazeStart, mazeEnd; mazeStart.x = 1;//开始与结束点 mazeStart.y = 1; mazeEnd.x = 8; mazeEnd.y = 8; cout << "迷宫: " << endl; for(int i = 0; i < 10; ++i) { } cout << endl << endl; if(MazePath(mazeStart, mazeEnd)) cout << "\n走通迷宫" << endl; for(int j = 0; j < 10; ++j) cout << mazeMap[i][j]; cout << endl;

} else cout << "\n走不通迷宫" << endl; system("PAUSE"); return 0;

四．测试与分析

1、在编程序时迷宫的出入栈掌握的还好，可是编到迷宫方向的选择，与迷宫路径错误的情况时，不知道怎么处理，然后自己通过看书和网上查阅资料基本解决了问题。

2、在写代码的过程中，没有弄清使用指针与引用之后，结构体如何使用。当使用指针的时候要使用‘.’，当使用引用或数的时候，要使用‘->’。

源程序：

#define OK 1

#define ERROR 0

#define TRUE 1

#define FALSE 0

#define OVERFLOW -2

#define STACK_INIT_SIZE 100

#define STACKINCREMENT 10

typedef int Status;

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

{

int x; int y;

}PosType;

typedef struct//栈类型

{

int ord; //通道块在路径上的“序号” PosType seat; //通道块在迷宫中的“坐标位置” int di; //从此通道块走向下一通道块的“方向”, //1:东 2:北 3:西 （顺时针)

}MazeType;

typedef struct

{

MazeType *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, PosType end);

Status Pass(PosType &pos);

void FootPrint(PosType pos);

PosType NextPos(PosType curPos, int &i);

void MakePrint(PosType pos);

//迷宫地图，0表示墙壁，1表示通路,入口:mazeMap[1][1],出口mazeMap[8][8]

int mazeMap[10][10] =

{ //0,1,2,3,4,5,6,7,8,9

};

int main()

{ {0,0,0,0,0,0,0,0,0,0}, //0 {0,1,1,0,1,1,1,0,1,0}, //1 {0,1,1,0,1,1,1,0,1,0}, //2 {0,1,1,1,1,0,0,1,1,0}, //3 {0,1,0,0,0,1,1,1,1,0}, //4 {0,1,1,1,0,1,1,1,1,0}, //5 {0,1,0,1,1,1,0,1,1,0}, //6 {0,1,0,0,0,1,0,0,1,0}, //7 {0,0,1,1,1,1,1,1,1,0}, //8 {0,0,0,0,0,0,0,0,0,0} //9

PosType mazeStart, 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 << mazeMap[i][j];

cout << endl;

}

cout << endl << endl;

if(MazePath(mazeStart, mazeEnd))

cout << "\n走通迷宫" << endl;

else

cout << "\n走不通迷宫" << endl;

system("PAUSE");

return 0;

}

Status 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.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;

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

{

}

Status StackEmpty(MazeStack &S)//判断是否为空

{

}

Status MazePath(PosType start, PosType end)//迷宫路径求解 {

块 PosType curpos; MazeStack S; MazeType e; int curstep; InitStack(S); curpos = start; //设定当前位置为入口位置 curstep = 1; //探索第一步 cout << "起点: "<< "(" <<start.y << "," << start.x << ")" << do { if(Pass(curpos)) //当前位置可以通过，即是未曾走到的通道if(S.base == S.top) return OK; return ERROR; if(S.top == S.base) return ERROR; e = *--S.top; return OK; endl;

{ } else //当前位置不能通过 { if(!StackEmpty(S)) { } Pop(S, e); while(e.di == 4 && !StackEmpty(S)) { } if(e.di < 4) { } ++e.di; //换下一个方向探索 Push(S, e); curpos = NextPos(e.seat, e.di); //设定当前位MakePrint(e.seat); //留下不能通过的标记 Pop(S, e); cout << "倒退到(" << e.seat.y << "," << e.seat.x 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 << "\n终点 (" << e.seat.y << "," << e.seat.x return TRUE; //到达终点（出口） << ")"; 的东邻 << ")"; 置是该新方向上的相邻块

} } }while(!StackEmpty(S)); return FALSE;

Status Pass(PosType &pos)

{

}

void FootPrint(PosType pos)

{

}

PosType NextPos(PosType curPos, int &i) {

switch(i) //顺时针方向 { case 1: ++curPos.x; //东 if(mazeMap[curPos.y][curPos.x] != 2) break; --curPos.x; i = 2; ++curPos.y; //南 if(mazeMap[curPos.y][curPos.x] != 2) break; --curPos.y; i = 3; --curPos.x; //西 if(mazeMap[curPos.y][curPos.x] != 2) break; mazeMap[pos.y][pos.x] = 2; //将走过的路径设为2 if(mazeMap[pos.y][pos.x] == 0) return FALSE; cout << "->(" << pos.y << "," << pos.x << ")"; return TRUE; case 2: case 3:

} } ++curPos.x; i = 4; --curPos.y; //北 if(mazeMap[curPos.y][curPos.x] == 2) { } break; ++curPos.y; mazeMap[curPos.y][curPos.x] = 0; case 4: return curPos;

void MakePrint(PosType pos) {

}

cout << "\n(" << pos.y << "," << pos.x << ")走不通，作废"; mazeMap[pos.y][pos.x] = 0; //将走不通的块替换为墙壁