1、下載可編輯數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計(jì)迷宮求解班級(jí)：學(xué)號(hào) ：姓名 ：指導(dǎo)老師 ：.專業(yè) .整理 .下載可編輯迷宮求解1、問(wèn)題描述輸入一個(gè)任意大小的迷宮數(shù)據(jù)，用遞歸和非遞歸兩種方法求出一條走出迷宮的路徑，并將路徑輸出。2、設(shè)計(jì)思路從入口出發(fā) ，按某一方向向前探索 ，若能走通并且未走過(guò) ，即某處可以到達(dá) ，則到達(dá)新點(diǎn) ，否則試探下一個(gè)方向 ；若所有的方向均沒(méi)有通路 ，則沿原路返回前一點(diǎn) ，換下一個(gè)方向再繼續(xù)試探 ，直到找到一條通路 ，或無(wú)路可走又返回入口點(diǎn) 。在求解過(guò)程中 ，為了保證在到達(dá)某一點(diǎn)后不能向前繼續(xù)行走（無(wú)路）時(shí)，能正確返回前一點(diǎn)以便繼續(xù)從下一個(gè)方向向前試探 ，則需要用一個(gè)棧 （遞歸不需要 ）保存

2、所能夠到達(dá)的每一點(diǎn)的下標(biāo)及從該點(diǎn)前進(jìn)的方向 。設(shè)迷宮為 m 行 n 列，利用 mazemn 來(lái)表示一個(gè)迷宮，mazeij=0 或 1；其中：0 表示通路 ，1 表示不通 ，當(dāng)從某點(diǎn)向下試探時(shí) ，中間點(diǎn)有四個(gè)方向可以試探 ，而四個(gè)角點(diǎn)有兩個(gè)方向 ，其他邊緣點(diǎn)有三個(gè)方向 ，為使問(wèn)題簡(jiǎn)單化 ，用 mazem+2n+2 來(lái)表示迷宮 ，而迷宮的四周的值全部為 1 ，這樣做使問(wèn)題簡(jiǎn)單了 ，每個(gè)點(diǎn)的試探方向全部為 4，不用再判斷當(dāng)前點(diǎn)的試探方向有幾個(gè) 。3、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)在上述表示迷宮的情況下 ，每個(gè)點(diǎn)有 4 個(gè)方向去試探 ，如當(dāng)前點(diǎn)的坐標(biāo)（x，y），與其相鄰的 4 個(gè)點(diǎn)的坐標(biāo)都可根據(jù)與該點(diǎn)的相鄰方位而得到

3、。 因?yàn)槌隹谠?（ m，n ），因此試探順序規(guī)定為 ：從當(dāng)前.專業(yè) .整理 .下載可編輯位置向前試探的方向?yàn)閺恼龞|沿順時(shí)針?lè)较蜻M(jìn)行 。 為了簡(jiǎn)化問(wèn)題 ，方便求出新點(diǎn)的坐標(biāo) ，將從正東開(kāi)始沿順時(shí)針進(jìn)行的 4 個(gè)方向的坐標(biāo)增量放在一個(gè)結(jié)構(gòu)數(shù)組 move4 中，在 move 數(shù)組中，每個(gè)元素有兩個(gè)域組成 ，x 為橫坐標(biāo)增量 ，y 為縱坐標(biāo)增量 。這樣對(duì) move 設(shè)計(jì)會(huì)很方便地求出從某點(diǎn) （x，y）按某一方向 v(0<=v<=3) 到達(dá)的新點(diǎn)（ i，j）的坐標(biāo)：i=x+movev.x;j=y+movev.y;當(dāng)?shù)竭_(dá)了某點(diǎn)而無(wú)路可走時(shí)需返回前一點(diǎn) ，再?gòu)那耙稽c(diǎn)開(kāi)始向下一個(gè)方向繼續(xù)試探。因此

4、，壓入棧中的不僅是順序到達(dá)的各點(diǎn)的坐標(biāo)，而且還要有從前一點(diǎn)到達(dá)本點(diǎn)的方向 。棧中元素是一個(gè)由行 、列、方向組成 。具體結(jié)構(gòu)定義如下 ：#define m 3#define n 3typedef structint x,y;item;/* 路線移動(dòng)的方向坐標(biāo),x 為橫向,y 縱向 */item move4; （遞歸只需定義到這里 ）typedef structint x,y,d;Datatype;/* 路線移動(dòng)的方向坐標(biāo)，x 為橫坐標(biāo)，y 為總坐標(biāo) */typedef struct.專業(yè) .整理 .下載可編輯Datatype dataMAXSIZE;/* 存儲(chǔ)路線移動(dòng)的方向坐標(biāo)*/int top

5、;SeqStack,*PSeqStack;4、功能函數(shù)設(shè)計(jì)迷宮棧的實(shí)現(xiàn)函數(shù)mazepath()迷宮遞歸的實(shí)現(xiàn)函數(shù)path()為了防止重復(fù)達(dá)到某點(diǎn)，以避免發(fā)生死循環(huán) ，每次達(dá)到了某點(diǎn) (i,j)后，改變 mazei j的值，迷宮棧的實(shí)現(xiàn)直接置 -1 ，算法結(jié)束前恢復(fù)原迷宮 ；而迷宮遞歸是將當(dāng)前值置為已走的步驟，這樣輸出時(shí)對(duì)走過(guò)的路更顯而易見(jiàn)。（1）棧的函數(shù)設(shè)計(jì) ：棧的初始化函數(shù)Init_SeqStack()判棧空Empty_SeqStack()入棧函數(shù)Push_SeqStack()出棧函數(shù)Pop_SeqStack()取棧頂函數(shù)GetTop_SeqStack()銷毀棧Destroy_SeqStac

6、k()5、程序代碼迷宮棧：#include<stdio.h>#include<stdlib.h>.專業(yè) .整理 .下載可編輯#define MAXSIZE 100#define m 3#define n 3/* 定義迷宮的行數(shù)和列數(shù) ，可更改 */typedef structint x,y;item;item move4;/* 路線移動(dòng)的方向坐標(biāo) */typedef structint x,y,d;Datatype;/* 橫縱坐標(biāo)及方向 */typedef structDatatype dataMAXSIZE;int top;SeqStack,*PSeqStack;/*

7、 定義棧 */PSeqStack Init_SeqStack(void)/* 初始化棧 */PSeqStack S;S=(PSeqStack)malloc(sizeof(SeqStack);.專業(yè) .整理 .下載可編輯if(S)S->top=-1;return S;int Empty_SeqStack(PSeqStack S)/* 判棧空 */if(S->top=-1)return 1;elsereturn 0;int Push_SeqStack(PSeqStack S,Datatype x)/* 入棧 */if(S->top=MAXSIZE-1)return 0;elseS

8、->top+;S->dataS->top=x;return 1;.專業(yè) .整理 .下載可編輯int Pop_SeqStack(PSeqStack S,Datatype *x)/* 出棧 */if(Empty_SeqStack(S)return 0;else*x=S->dataS->top;S->top-;return 1;void Destroy_SeqStack(PSeqStack *S)/* 毀棧 */if(*S)free(*S);*S=NULL;return;.專業(yè) .整理 .下載可編輯int mazepath(int mazen+2,item mov

9、e4,int x0,int y0)/* 迷宮功能實(shí)現(xiàn)函數(shù) */* 求迷宮路徑，入口參數(shù) ：迷宮數(shù)組 ，下標(biāo)移動(dòng)的增量數(shù)組，開(kāi)始點(diǎn)（ x0，y0）， 0（m,n ）是終點(diǎn)，返回值：1 表示求出路徑 ，0 表示無(wú)路徑 */ PSeqStack S;Datatype temp;int x,y,d,i,j;temp.x=x0;temp.y=y0;temp.d=-1;S=Init_SeqStack();/* 初始化棧 */if(!S)printf(" 棧初始化失敗 ");return 0;Push_SeqStack(S,temp);while(!Empty_SeqStack(S)Po

10、p_SeqStack(S,&temp);x=temp.x;.專業(yè) .整理 .下載可編輯y=temp.y;d=temp.d+1;while(d<4)/* 存在剩余方向可以搜索 */i=x+moved.x;j=y+moved.y;if(mazeij=0)/* 此方向可以走 */temp.x=x;temp.y=y;temp.d=d;mazexy=-1;Push_SeqStack(S,temp); /* 點(diǎn)（x，y）可以走 ，用棧保存可以走的路徑 */x=i;y=j;if(x=m&&y=n)/* 迷宮有路 */while(!Empty_SeqStack(S)Pop_Seq

11、Stack(S,&temp);printf("(%d,%d)<-",temp.x,temp.y);/* 打印可以走的路徑 */.專業(yè) .整理 .下載可編輯Destroy_SeqStack(&S);/* 銷毀棧 */return 1;else d=0;/* 方向復(fù)位 ，從第一個(gè)方向開(kāi)始試探 */else d+;/* 試探下一個(gè)方向 */ /*while(d<4)*/*while*/Destroy_SeqStack(&S);/* 銷毀棧 */printf(" 迷宮無(wú)路徑 n");return 0;/* 迷宮無(wú)路 */voi

12、d main()item move4;int mazem+2n+2;int i,j;for(i=0;i<m+2;i+)/* 輸入迷宮 ，四周為 1*/.專業(yè) .整理 .下載可編輯for(j=0;j<n+2;j+)scanf("%d",&mazeij);move0.x=1;move0.y=0;move1.x=0;move1.y=1;move2.x=-1;move2.y=0;move3.x=0;move3.y=-1;/* 給方向坐標(biāo)賦值 */mazepath(maze,move,1,1);getch();迷宮遞歸 :#include<stdio.h&g

13、t;#include<stdlib.h>#define m 3#define n 3typedef structint x,y;item;item move4;int path(int mazen+2,item move,int x,int y,int step).專業(yè) .整理 .下載可編輯/* 求迷宮路徑 ，入口參數(shù) ：迷宮數(shù)組 ，下標(biāo)移動(dòng)的增量數(shù)組，開(kāi)始點(diǎn) （ x，y），以及開(kāi)始點(diǎn)對(duì)應(yīng)的步數(shù)step ，（ m,n ）是終點(diǎn)，返回值：1 表示求出路徑，0 表示無(wú)路徑 */int i;step+;mazexy=step;if(x=m&&y=n)return 1;/*

14、 起始位置是出口 ，找到路徑 ，結(jié)束 */for(i=0;i<4;i+)if(mazex+movei.xy+movei.y=0)if(path(maze,move,x+movei.x,y+movei.y,step)return 1;/* 下一個(gè)是出口 ，則返回 */step-;mazexy=0;return 0;void main().專業(yè) .整理 .下載可編輯item move4;int mazem+2n+2;int i,j;for(i=0;i<m+2;i+)for(j=0;j<n+2;j+)scanf("%d",&mazeij);printf(

15、"n");move0.x=1;move0.y=0;move1.x=0;move1.y=1;move2.x=-1;move2.y=0;move3.x=0;move3.y=-1;if(path(maze,move,1,1,1)for(i=0;i<m+2;i+)for(j=0;j<n+2;j+)printf("%d ",mazeij);printf("n");/* 輸出有路迷宮的路線 */.專業(yè) .整理 .下載可編輯else printf(迷宮無(wú)“路徑 n ” );getch();6、運(yùn)行與測(cè)試迷宮棧（無(wú)路徑）：有路徑：迷宮遞歸 （無(wú)路徑）：.專業(yè) .整理 .下載可編輯有路徑：7、設(shè)計(jì)心得迷宮這個(gè)問(wèn)題也是老師經(jīng)常講的例子 ，是加深對(duì)棧運(yùn)用的好程序。這個(gè)程序又加了個(gè)遞歸的算法 ，相同的程序不同的算法 。我結(jié)合老師提過(guò)的