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; / 通道块在迷宫中的“坐标位置” Maze

2、Node; / 迷宫节点typedef struct MazeNode baseINITSIZE;int top; / 栈顶指针Stack;typedef struct / 用于存储迷宫的路径PosType coorINITSIZE;int top;Postion;void RandMatrix(); / intInitStack(Stack *); / intInitStack1(Postion *); intStackEmpty(Stack *); / intStackEmpty1(Postion *); intStackIsFull(Stack *); / intStackIsFull1

3、(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(PosT

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

5、;printf(1 、重新生成迷宫， 0、就这个 :);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( 输入的坐

6、标越界，请重新输入 !n); continue;while(end.xN | end.yM);if(!MazePath(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 StackEmpty

7、1(Postion *s)if(s-top=-1)return 1;return 0;int StackIsFull(Stack *s)if(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(!StackIs

8、Full1(s)s-top+; s-coors-top=m;return 1;int Pop(Stack *s,MazeNode *m)if(s-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

9、.x=0) /return 1;elsereturn 0;int FootPrint(PosType pos) / default :exit(0);可通标记能通过的mgpos.ypos.x=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

10、; 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;pos.x+=1; break;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

11、=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=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)

12、/ 从迷宫的入口到出口查找/若迷宫 maze 中存在从入口 start 到出口 end 的通道，则求得一条存放在栈中(从栈底到栈顶)/并返回 TRUE 否则返回 FALSEStack S; / 定义栈PosType curpos;int curstep; /MazeNode e;InitStack(&S);当前序号 1,2,3,4,5,6,7,8代表方向， 1 代表向右，后依次顺时针curpos=start; /curstep=1; /设定“当前位置”为“入口位置” ,从入口位置开始查找 探索第一步doif(Pass(curpos)/ 从当前位置可以通过，即是未曾走到过的通道块Foot

13、Print(curpos); / 标记能通过的e.ord=curstep; / 保存步数e.seat=curpos;e.di=1; / 向右侧探测Push(&S,e); / 加入路径Push1(P,curpos);if(curpos.y=end.x & curpos.x=end.y) /若当前位置是出口坐标DestroyStack(&S); / 释放栈占用的空间 return 1; / 返回查找成功else / 与出口坐标不同curpos=NextCoord(curpos,1); / 向右侧探测 curstep+; / 探索下一步else / 当前位置不能通过 ( 为障

14、碍或已走过 )if(!StackEmpty(&S) /若栈不为空，之前有走过的位置Pop(&S,&e); / 出栈 (返回上一步的位置 )Pop1(P,&curpos);while(e.di=8 & !StackEmpty(&S) / 上一步，四个方向都探测定，且栈不为空MarkPrint(e.seat); / 留下不能通过的标记，并退回一步Pop(&S,&e); / 出栈，返回上一步Pop1(P,&curpos);if(e.di8)e.di+; / 换下一个方向探索，准备探测下一个方向Push(&S,e); /

15、将当前节点入栈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