C語言數(shù)據(jù)結(jié)構(gòu)迷宮問題

1、#include <stdio.h> #include <stdlib.h>#include <time.h>#define M 20#define N 20#define visited 2#define TRUE 1#define FALSE 0#define INITSIZE 100typedef int Status;typedef struct / 坐標(biāo)點結(jié)構(gòu)體int y; / 每個可通的行坐標(biāo)int x; / 每個可通的列坐標(biāo)PosType;typedef structint ord; / 通道塊在路徑上的“序號”int di; / 從此通道塊走

2、向下一通道塊的“方向”PosType seat; / 通道塊在迷宮中的“坐標(biāo)位置” MazeNode; / 迷宮節(jié)點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

3、 StackIsFull(Stack *);int 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); / 判斷指定坐標(biāo)是否可通過int FootPrin

4、t(PosType pos);/ 標(biāo)記能通過的PosType NextCoord(PosType pos,int i);/ 獲取下一位置int MarkPrint(PosType pos);/ 留下不能通過的標(biāo)記，并退回一步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(&quo

5、t; 創(chuàng)建迷宮 n"); InitStack1(&P);RandMatrix();printf("n");printf("1 、重新生成迷宮， 0 、就這個 :"); scanf("%d",&h);do / 輸入迷宮入口坐標(biāo)printf("n 輸入迷宮入口坐標(biāo) "); scanf("%d%d",&start.x,&start.y);if(start.x>N | start.y>M)printf(" 輸入的坐標(biāo)越界，請重新輸入 !n&

6、quot;); continue; while(start.x>N | start.y>M); do / 輸入迷宮出口坐標(biāo)printf("n 輸入迷宮出口坐標(biāo) :"); scanf("%d%d",&end.x,&end.y);if(end.x>N | end.y>M)printf(" 輸入的坐標(biāo)越界，請重新輸入 !n"); continue;while(end.x>N | end.y>M);if(!MazePath(start,end,&P) / 調(diào)用函數(shù)查找路徑printf

7、("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 *

8、s)if(s->top=INITSIZE-1)return 1;elsereturn 0;int StackIsFull1(Postion *s)if(s->top=INITSIZE-1) return 1;else return 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;

9、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) / 判斷指定坐標(biāo)是否可通過if(mg

10、pos.ypos.x=0) / 可通 return 1;else return 0;/ 標(biāo)記能通過的/2 表示可通int FootPrint(PosType pos) mgpos.ypos.x=2;return 1;PosType NextCoord(PosType pos,int i)/ 獲取下一位置switch(i) /1,2,3,4,5,6,7,8 代表方向順時針case 1:pos.x+=1; / 向右側(cè)查找 break;case 2: pos.x+=1; pos.y+=1; break;case 3: pos.y+=1; break;case 4: pos.y+=1; pos.x-=

11、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; pos.x+=1; break;default :exit(0); return pos;int MarkPrint(PosType pos) / 留下不能通過的標(biāo)記，并退回一步 mgpos.ypos.x=3; /3 表示曾走過，但不通 return 1;void RandMatrix()int i=0,j=0; srand(unsigned)time(NULL);for(i=0;

12、i<M;i+) for(j=0;j<N;j+)mgij=rand()%2;i=0;for(j=0;j<N;j+)mgij=1;mgji=1;i=N-1; for(j=0;j<M;j+)mgji=1;mgij=1; mg11=0;mgM-2N-2=0; printf("n");for(i=0;i<M;i+) for(j=0;j<N;j+)if(mgij=1) / 若是障礙printf(”");else if(mgij=2)/ 若是可通路徑printf(" ");else if(mgij=3)printf(&qu

13、ot; "); / 其他位置elseprintf(" ");printf("n");int MazePath(PosType start,PosType end,Postion *P)/ 從迷宮的入口到出口查找/ 若迷宮 maze 中存在從入口 start 到出口 end 的通道，則求得一條存放在棧中(從棧底到棧頂) / 并返回 TRUE ，否則返回 FALSEStack S; / 定義棧PosType curpos;int curstep; / 當(dāng)前序號 1,2,3,4,5,6,7,8 代表方向， 1 代表向右，后依次順時針 MazeNode

14、 e;InitStack(&S);curpos=start; / 設(shè)定“當(dāng)前位置”為“入口位置”, 從入口位置開始查找curstep=1; / 探索第一步doif(Pass(curpos)/ 從當(dāng)前位置可以通過，即是未曾走到過的通道塊FootPrint(curpos);/ 標(biāo)記能通過的e.ord=curstep; / 保存步數(shù) e.seat=curpos;e.di=1;/ 向右側(cè)探測Push(&S,e); / 加入路徑 Push1(P,curpos);if(curpos.y=end.x && curpos.x=end.y)/ 若當(dāng)前位置是出口坐標(biāo)DestroyS

15、tack(&S); / 釋放棧占用的空間 return 1;/ 返回查找成功else / 與出口坐標(biāo)不同/ 向右側(cè)探測查找下一個應(yīng)該探curpos=NextCoord(curpos,1);curstep+; / 探索下一步else / 當(dāng)前位置不能通過 ( 為障礙或已走過 )if(!StackEmpty(&S) / 若棧不為空，之前有走過的位置Pop(&S,&e);/ 出棧 (返回上一步的位置 )Pop1(P,&curpos);while(e.di=8 && !StackEmpty(&S) / 上一步，四個方向都探測定，且棧不為空

16、 MarkPrint(e.seat); / 留下不能通過的標(biāo)記，并退回一步Pop(&S,&e); / 出棧，返回上一步Pop1(P,&curpos);if(e.di<8)e.di+; / 換下一個方向探索，準(zhǔn)備探測下一個方向 Push(&S,e); / 將當(dāng)前節(jié)點入棧Push1(P,curpos); curpos=NextCoord(e.seat,e.di); / 設(shè)定當(dāng)前位置是該新方向上的相鄰塊， 測的方向while(!StackEmpty(&S);/ 程序運行到這里，表示沒有能通達的路徑DestroyStack(&S); / 釋放占用的

17、空間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");/ 在這里可以設(shè)置迷宮的界面for(i=0;i<M;i+)for(j=0;j<N;j+)if(mgij=1) /printf(”");else if(mgij=2)printf(" ");else