《数据结构(C语言)迷宫问题》由会员分享，可在线阅读，更多相关《数据结构(C语言)迷宫问题（7页珍藏版）》请在金锄头文库上搜索。
1、【问题描述】 以一个 m*n 的长方阵表示迷宫， 0 和 1 分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路。或得出没有通路的结论 【基本要求】【测试数据】【实现提示】使用 穷举法和栈求解【代码过程】 1。/base.h/- 公用的常量和类型 -#include#include #include #include /函数结果状态代码#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2 typedef int Stat
2、us; /函数的返回值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.SE
3、lemType *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)
4、 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;
5、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/- 迷宫程序 -/*/*迷宫问题算法: 从入口出发 ,顺着某一个方向进行探索,若能走通,则继续前进;否则沿着原路退回,换一个方向继续探索 ,直至出口位置,求得一条通路,假如所
6、有可能的通路都探索到而未能达到出口,则所设定的迷宫没有通路.说明:可通: 未增走到过的通道快.*/#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
7、;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,Po
8、sType 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 curp
9、os, 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(MazeTy
10、pe 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 的一条路径/若存在,
11、返回 TRUE,否则返回 FALSESqStack 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); /获得下一
12、节点:当前位置的东邻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;/4。/test.cpp#include base.h #incl
13、ude 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 start,end;start.row = 1;start.col=1;end.row = 9; end.col = 8;MazeType maze;InitMaze(maze,a,ROW,COL);Status ok = MazePath(maze,start,end);if(ok) PrintMaze(maze,RO
