数据结构迷宫问题.doc

/base.h/- 公用的常量和类型 -#include#include #include #include /函数结果状态代码#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status; /函数的返回值typedef int DirectiveType; /下一个通道方向#define RANGE 100 /迷宫大小/2。/stack.h#define STACK_INIT_SIZE 100#define STACKINCREMENT 10/- 栈的顺序存储实现 -typedef struct. int row; int col;PosType;typedef struct. int step; /当前位置在路径上的序号 PosType seat; /当前的坐标位置 DirectiveType di; /往下一个坐标位置的方向SElemType;typedef struct. SElemType *base; SElemType *top; int stacksize;SqStack;/- 栈的基本操作的算法实现 -Status InitStack(SqStack &s). s.base = (SElemType * ) malloc(STACK_INIT_SIZE * sizeof(SElemType); if(!s.base) exit(OVERFLOW); s.top=s.base; s.stacksize=STACK_INIT_SIZE; return OK;Status GetTop(SqStack s, SElemType &e ). if( s.top = s.base) return ERROR; e = *(s.top-1); return OK;Status Push(SqStack &s, SElemType e). if(s.top-s.base = s.stacksize). /栈满，追加存储空间 s.base = (SElemType *)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(SElemType); if(!s.base) exit(OVERFLOW);s.top = s.base + s.stacksize; s.stacksize += STACKINCREMENT; *s.top+ = e; return OK;Status Pop(SqStack &s, SElemType &e). if(s.top=s.base)return ERROR; e = * -s.top; return OK;int StackEmpty(SqStack s). return s.base = s.top;Status ClearStack(SqStack &s). s.top = s.base; return OK;/3。/maze.h/- 迷宫程序 -/*/* 迷宫问题算法: 从入口出发,顺着某一个方向进行探索,若能走通,则继续前进;否则沿着原路退回,换一个方向继续探索,直至出口位置,求得一条通路,假如所有可能的通路都探索到而未能达到出口,则所设定的迷宫没有通路. 说明:可通: 未增走到过的通道快. */#define ROW 9 /迷宫的行数#define COL 8 /迷宫的列数typedef struct. int m,n; int arrRANGERANGE;MazeType; /迷宫类型Status InitMaze(MazeType &maze, int aCOL, int row, int col). /按照用户输入的row行和col列的二维数组(0/1) /设置迷宫maze的初值,包括加上边缘一圈的值 for(int i=1;i=row;i+). for(int j=1;j=col;j+). maze.arrij = ai-1j-1; /加上围墙 for(int j=0;j=col+1;j+). maze.arr0j = maze.arrrow+1j=1; for(i=0;i=row+1;i+). maze.arri0 = maze.arricol+1=1; maze.m = row, maze.n = col; return OK;Status Pass(MazeType maze,PosType curpos). /判断当前节点是否通过 return maze.arrcurpos.rowcurpos.col = 0;Status FootPrint(MazeType &maze,PosType curpos). /留下足迹 maze.arrcurpos.rowcurpos.col=*; return OK;Status MarkPrint(MazeType &maze,PosType curpos). /留下不能通过的标记 maze.arrcurpos.rowcurpos.col=; return OK;SElemType CreateSElem(int step, PosType pos, int di). SElemType e; e.step = step; e.seat = pos; e.di = di; return e;PosType NextPos(PosType curpos, DirectiveType di). /返回当前节点的下一节点 PosType pos = curpos; switch(di) . case 1: /东 pos.col+; break; case 2: /南 pos.row+; break; case 3: /西 pos.col-; break; case 4: /北 pos.row-; break; return pos;Status PosEquare(PosType pos1, PosType pos2). /判断两节点是否相等 return pos1.row=pos2.row & pos1.col=pos2.col ;void PrintMaze(MazeType maze,int row,int col). /打印迷宫信息 for(int i=1;i=row;i+). for(int j=1;j=col;j+). switch(maze.arrij) . case 0: printf( ); break; case *: printf(* ); break; case : printf( ); break; case 1: printf(# ); break; printf( ); Status MazePath(MazeType &maze,PosType start, PosType end). /求解迷宫maze中,从入口start到出口end的一条路径 /若存在,返回TRUE,否则返回FALSE SqStack s;SElemType e; InitStack(s); PosType curpos = start; int curstep = 1; /探索第一部 do. if( Pass(maze,curpos) ). /如果当前位置可以通过,即是未曾走到的通道块 FootPrint(maze,curpos); /留下足迹 e = CreateSElem(curstep,curpos,1); /创建元素 Push(s,e); if( PosEquare(curpos,end) ) return TRUE; curpos =NextPos(curpos,1); /获得下一节点:当前位置的东邻 curstep+; /探索下一步 else. /当前位置不能通过 if(!StackEmpty(s). Pop(s,e); while(e.di=4 & !StackEmpty(s) ). MarkPrint(maze,e.seat); Pop(s,e);curstep-; /留下不能通过的标记,并退回一步 if(e.di4). e.di+; Push(s,e); /换一个方向探索 curpos = NextPos(e.seat,e.di); /求下一个节点 while(!StackEmpty(s); return FALSE;/test.cpp#include base.h#include stack.h#include maze.h/*/* 测试 */void main(). int aROWCOL; printf(enter the mazes data: ); for(int i=0;iROW;i+) . for(int j=0; jCOL;j+) . scanf(%d,&aij); PosType