C语言数据结构迷宫问题#仅供借鉴

1、#include #include #include #define M 20#define N 20#define visited 2#define TRUE 1#define FALSE 0#define INITSIZE 100typedef int Status;typedef struct /坐标点结构体int y; /每个可通的行坐标int x; /每个可通的列坐标PosType;typedef structint ord; /通道块在路径上的“序号”int di; /从此通道块走向下一通道块的“方向”PosType seat; /通道块在迷宫中的“坐标位置”MazeNode; /

2、迷宫节点typedef struct MazeNode baseINITSIZE;int top; /栈顶指针Stack;typedef struct /用于存储迷宫的路径PosType coorINITSIZE;int top;Postion;void RandMatrix(); /随机生成迷宫int InitStack(Stack *); /初始化栈int InitStack1(Postion *);int StackEmpty(Stack *); /判断栈是否为空int StackEmpty1(Postion *);int StackIsFull(Stack *); /判断栈是否满了in

3、t StackIsFull1(Postion *); /判断栈是否满了int Push(Stack *s,MazeNode m); /压栈int Push1(Postion *,PosType);int Pop(Stack *s,MazeNode *m); /出栈int Pop1(Postion *,PosType *);int DestroyStack(Stack *s); /撤销栈int Pass(PosType pos); /判断指定坐标是否可通过int FootPrint(PosType pos); /标记能通过的PosType NextCoord(PosType pos,int i)

4、; /获取下一位置int MarkPrint(PosType pos); /留下不能通过的标记，并退回一步int MazePath(PosType start,PosType end,Postion *); /从迷宫的入口到出口查找void PrintMaze(Postion *); /输出迷宫int mgMN; /生成一个M*N 的迷宫int main()int h=1;PosType start,end;Postion P;while(h)printf(创建迷宫n);InitStack1(&P);RandMatrix();printf(n);printf(1、重新生成迷宫，0、就这个:);

5、scanf(%d,&h);do /输入迷宫入口坐标printf(n输入迷宫入口坐标);scanf(%d%d,&start.x,&start.y);if(start.xN | start.yM)printf(输入的坐标越界，请重新输入!n);continue;while(start.xN | start.yM);do /输入迷宫出口坐标printf(n输入迷宫出口坐标:);scanf(%d%d,&end.x,&end.y);if(end.xN | end.yM)printf(输入的坐标越界，请重新输入!n);continue;while(end.xN | end.yM);if(!MazePath

6、(start,end,&P) /调用函数查找路径printf(n无法通过!n);elsePrintMaze(&P); /打印找到的路径return 0;int InitStack(Stack *s)s-top=-1;return 1;int InitStack1(Postion *s)s-top=-1;return 1;int StackEmpty(Stack *s)if(s-top=-1)return 1;return 0;int StackEmpty1(Postion *s)if(s-top=-1)return 1;return 0;int StackIsFull(Stack *s)if(

7、s-top=INITSIZE-1)return 1;elsereturn 0;int StackIsFull1(Postion *s)if(s-top=INITSIZE-1)return 1;elsereturn 0;int Push(Stack *s,MazeNode m)if(!StackIsFull(s)s-top+;s-bases-top=m;return 1;int Push1(Postion *s,PosType m)if(!StackIsFull1(s)s-top+;s-coors-top=m;return 1;int Pop(Stack *s,MazeNode *m)if(s-

8、top!=-1)*m=s-bases-top;s-top-;return 1;return 1;int Pop1(Postion *s,PosType *m)if(s-top!=-1)*m=s-coors-top;s-top-;return 1;return 1;int DestroyStack(Stack *s)s-top=-1;return 1;int Pass(PosType pos) /判断指定坐标是否可通过if(mgpos.ypos.x=0) /可通return 1;elsereturn 0;int FootPrint(PosType pos) /标记能通过的mgpos.ypos.x

9、=2; /2表示可通return 1;PosType NextCoord(PosType pos,int i) /获取下一位置switch(i) /1,2,3,4,5,6,7,8代表方向顺时针case 1:pos.x+=1; /向右侧查找break;case 2:pos.x+=1;pos.y+=1;break;case 3:pos.y+=1;break;case 4:pos.y+=1;pos.x-=1;break;case 5:pos.x-=1;break;case 6:pos.x-=1;pos.y-=1;break;case 7:pos.y-=1;break;case 8:pos.y-=1;

10、pos.x+=1;break;default :exit(0);return pos;int MarkPrint(PosType pos) /留下不能通过的标记，并退回一步mgpos.ypos.x=3; /3表示曾走过，但不通return 1;void RandMatrix()int i=0,j=0;srand(unsigned)time(NULL);for(i=0;iM;i+)for(j=0;jN;j+)mgij=rand()%2;i=0;for(j=0;jN;j+)mgij=1;mgji=1;i=N-1;for(j=0;jM;j+)mgji=1;mgij=1;mg11=0;mgM-2N-2

11、=0;printf(n);for(i=0;iM;i+)for(j=0;jN;j+)if(mgij=1) /若是障碍printf();else if(mgij=2) /若是可通路径printf();else if(mgij=3)printf(); /其他位置elseprintf( );printf(n); int MazePath(PosType start,PosType end,Postion *P) /从迷宫的入口到出口查找/若迷宫maze中存在从入口start到出口end的通道，则求得一条存放在栈中（从栈底到栈顶）/并返回TRUE，否则返回FALSEStack S; /定义栈PosTyp

12、e curpos;int curstep; /当前序号1,2,3,4,5,6,7,8代表方向，1代表向右，后依次顺时针MazeNode e;InitStack(&S);curpos=start; /设定“当前位置”为“入口位置”,从入口位置开始查找curstep=1; /探索第一步do if(Pass(curpos)/从当前位置可以通过，即是未曾走到过的通道块FootPrint(curpos); /标记能通过的e.ord=curstep; /保存步数e.seat=curpos;e.di=1; /向右侧探测Push(&S,e); /加入路径Push1(P,curpos);if(curpos.y=

13、end.x & curpos.x=end.y) /若当前位置是出口坐标DestroyStack(&S); /释放栈占用的空间return 1; /返回查找成功else /与出口坐标不同curpos=NextCoord(curpos,1); /向右侧探测curstep+; /探索下一步else /当前位置不能通过(为障碍或已走过)if(!StackEmpty(&S) /若栈不为空，之前有走过的位置Pop(&S,&e); /出栈(返回上一步的位置)Pop1(P,&curpos);while(e.di=8 & !StackEmpty(&S) /上一步，四个方向都探测定，且栈不为空MarkPrint(

14、e.seat); /留下不能通过的标记，并退回一步Pop(&S,&e); /出栈，返回上一步Pop1(P,&curpos);if(e.di8)e.di+; /换下一个方向探索，准备探测下一个方向Push(&S,e); /将当前节点入栈Push1(P,curpos);curpos=NextCoord(e.seat,e.di); /设定当前位置是该新方向上的相邻块，查找下一个应该探测的方向while(!StackEmpty(&S);/程序运行到这里，表示没有能通达的路径DestroyStack(&S); /释放占用的空间return FALSE; /返回失败void PrintMaze(Postion *P) /输出迷宫int i,j;PosType e;Postion W;InitStack1(&W);while(!StackEmpty1(P)Pop1(P,&e);Push1(&W,e);printf(n可以通过,迷宫路径:n); /在这里可以设置迷宫的界面for(i=0;iM;i+)for(j=0;jN;