數(shù)據(jù)結(jié)構(gòu)上機(jī)作業(yè)迷宮求解(共5頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)集中上機(jī)報告第一題：迷宮求解（參見教材描述）任務(wù)：可以輸入一個任意大小的迷宮數(shù)據(jù)，用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出；源程序：#include #include #define M 15 #define N 15 struct mark /定義迷宮內(nèi)點的坐標(biāo)類型 int x; int y; ; struct Element int x,y; /x行,y列 int d; /d下一步的方向 ; typedef struct LStack /鏈棧 Element elem; struct LStack *next; *PLStack; int Ini

2、tStack(PLStack &S)/構(gòu)造空棧 S=NULL; return 1; int StackEmpty(PLStack S)/判斷棧是否為空 if(S=NULL) return 1; else return 0; int Push(PLStack &S, Element e)/壓入新數(shù)據(jù)元素 PLStack p; p=(PLStack)malloc(sizeof(LStack); p-elem=e; p-next=S; S=p; return 1; int Pop(PLStack &S,Element &e) /棧頂元素出棧 PLStack p; if(!StackEmpty(S)

3、e=S-elem; p=S; S=S-next; free(p); return 1; else return 0; void MazePath(struct mark start,struct mark end,int mazeMN,int diradd42) int i,j,d;int a,b; Element elem,e; PLStack S1, S2; InitStack(S1); InitStack(S2); mazestart.xstart.y=2; /入口點作上標(biāo)記 elem.x=start.x; elem.y=start.y; elem.d=-1; /開始為-1 Push(S

4、1,elem); while(!StackEmpty(S1) /棧不為空 有路徑可走 Pop(S1,elem); i=elem.x; j=elem.y; d=elem.d+1; /下一個方向 while(d(%d,%d,%d),e.x,e.y,e.d); return; /跳出兩層循環(huán) if(mazeab=0) /找到可以前進(jìn)的非出口的點 mazeab=2; /標(biāo)記走過此點 elem.x=i; elem.y=j; elem.d=d; Push(S1,elem); /當(dāng)前位置入棧 i=a; /下一點轉(zhuǎn)化為當(dāng)前點 j=b; d=-1; d+; printf(沒有找到可以走出此迷宮的路徑n); /*

5、建立迷宮*/ void initmaze(int mazeMN) int i,j; int m,n; /迷宮行,列 printf(請輸入迷宮的行數(shù) m=); scanf(%d,&m); printf(請輸入迷宮的列數(shù) n=); scanf(%d,&n); printf(n請輸入迷宮的各行各列:n用空格隔開,0代表路,1代表墻n,m,n); for(i=1;i=m;i+) for(j=1;j=n;j+) scanf(%d,&mazeij); printf(你建立的迷宮為:n); for(i=0;i=m+1;i+) / mazei0=1; mazein+1=1; for(j=0;j=n+1;j+)

6、 maze0j=1; mazem+1j=1; for(i=0;i=m+1;i+) /輸出迷宮 for(j=0;j=n+1;j+) printf(%d ,mazeij); printf(n); void main() int stoMN; struct mark start,end; /start,end入口和出口的坐標(biāo) int add42=0,1,1,0,0,-1,-1,0;/行增量和列增量 方向依次為東西南北 initmaze(sto);/建立迷宮 printf(輸入入口的橫坐標(biāo),縱坐標(biāo)逗號隔開n); scanf(%d,%d,&start.x,&start.y); printf(輸入出口的橫坐標(biāo),縱坐標(biāo)逗號隔開