迷宮的生成與路由

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告撰寫要求（一）紙張與頁面要求 1采用國際標(biāo)準(zhǔn)A4型打印紙或復(fù)印紙，縱向打印。 2封頁和頁面按照下面模板書寫（正文為：小四宋體1.5倍行距）。3圖表及圖表標(biāo)題按照模板中的表示書寫。 （二） 課設(shè)報(bào)告書的內(nèi)容應(yīng)包括以下各個(gè)部分：（按照以下順序裝訂）1.封頁(見課設(shè)模版)2.任務(wù)書(學(xué)生教師均要簽字,信息填寫完整)3.目錄4.正文一般應(yīng)包括以下內(nèi)容: （1)題目介紹和功能要求（或描述）課程設(shè)計(jì)任務(wù)的詳細(xì)描述(注意不能直接抄任務(wù)書),將內(nèi)容做更詳細(xì)的具體的分析與描述；（2) 系統(tǒng)功能模塊結(jié)構(gòu)圖 繪制系統(tǒng)功能結(jié)構(gòu)框圖及主要模塊的功能說明； （3) 使用的數(shù)據(jù)結(jié)構(gòu)的描述: 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

2、及用法說明;（4) 涉及到的函數(shù)的描述 ; （5) 主要算法描述( 程序流程圖)（6) 給出程序測試/運(yùn)行的結(jié)果設(shè)計(jì)多組數(shù)據(jù)加以描述（包括輸入數(shù)據(jù)和輸出結(jié)果） （7) 課程設(shè)計(jì)的總結(jié)及體會(huì)（8) 參考文獻(xiàn) 格式要求：1作者，等. 書名.出版地：出版社，出版年 5.附錄：程序清單 (應(yīng)帶有必要的注釋) 沈陽航空航天大學(xué)課 程 設(shè) 計(jì) 報(bào) 告課程設(shè)計(jì)名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)課程設(shè)計(jì)題目： 迷宮的生成與路由院（系）：計(jì)算機(jī)學(xué)院專 業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù)班 級： 學(xué) 號(hào)： 姓 名： 指導(dǎo)教師： 目 錄1 題目介紹和功能要求11.1 題目介紹11.2 功能介紹12 系統(tǒng)功能模塊結(jié)構(gòu)圖22.1 系統(tǒng)功能結(jié)構(gòu)

3、框圖22.2 系統(tǒng)主要模塊的功能說明錯(cuò)誤！未定義書簽。3 使用的數(shù)據(jù)結(jié)構(gòu)的描述33.1 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)43.2 數(shù)據(jù)結(jié)構(gòu)用法說明44 函數(shù)的描述54.1 主要函數(shù)設(shè)計(jì)64.2 主要函數(shù)流程圖65程序測試和運(yùn)行的結(jié)果115.1 程序測試115.2 運(yùn)行結(jié)果13參考文獻(xiàn).10附 錄（關(guān)鍵部分程序清單）11 1 題目介紹和功能要求1.1 題目介紹 設(shè)計(jì)算法生成一個(gè)N*M(N行M列）的迷宮，并完成迷宮的組織和存儲(chǔ)。實(shí)現(xiàn)兩種不同的迷宮路由算法：廣度搜索，深度優(yōu)先搜索。 要求： 1.N和M是用戶可配置的，缺省值為50和50。 2.迷宮的入口和出口分別在第0行和第N-1行上，隨機(jī)選擇。 3.生成的迷宮要求是連

4、通的。 4.實(shí)現(xiàn)圖像化界面（選作）。1.2 功能要求 (1)迷宮用二維數(shù)組表示； (2)rand()函數(shù)隨機(jī)確定入口和出口，使用真隨機(jī)數(shù)使得每次隨機(jī)的結(jié)果不同。 (3)入口和出口間的路徑是連通的，使用數(shù)據(jù)結(jié)構(gòu)的并查集來表示連通性。 (4)使用數(shù)據(jù)結(jié)構(gòu)的兩種搜索方式：深度和廣度優(yōu)先搜索來確定入口和出口間的路徑。2 系統(tǒng)功能模塊結(jié)構(gòu)圖開始初始化迷宮模塊2.1 系統(tǒng)功能結(jié)構(gòu)框圖隨機(jī)化生成迷宮路徑模塊廣度優(yōu)先搜索模塊深度優(yōu)先搜索模塊形象化顯示迷宮模塊 結(jié)束 圖2.1 系統(tǒng)功能結(jié)構(gòu)框圖2.2 系統(tǒng)主要模塊的功能說明1. 初始化迷宮模塊： Inint（）函數(shù)用來初始化迷宮，使用二維數(shù)組來表示迷宮，假設(shè)迷宮

5、是用一個(gè)個(gè)封閉的小格子組成的，每個(gè)格子的四周是封閉的。首先隨機(jī)生成入口和出口的位置。2.隨機(jī)化生成迷宮路徑模塊： 并查集（數(shù)據(jù)結(jié)構(gòu)）：(1)并查集可以用來表示元素之間的集合關(guān)系，即這些元素是不是屬于哪個(gè)集合。通俗理解是，若兩個(gè)元素是屬于統(tǒng)一集合，就將這兩個(gè)元素并在一起。(2)存儲(chǔ)結(jié)構(gòu)上，用樹結(jié)構(gòu)模擬。一開始，每個(gè)元素自己構(gòu)成一個(gè)集合，所以自己構(gòu)成一棵樹。然后，若有兩個(gè)元素并成一個(gè)集合，則將這兩個(gè)元素所在的樹，合并成一棵樹。具體實(shí)現(xiàn)的話，就是將一棵樹的根看成是另一棵樹根的新根。(3)并查集的作用是可以統(tǒng)計(jì)并判定兩個(gè)元素是否屬于統(tǒng)一集合。利用并查集實(shí)現(xiàn)入口和出口的連通：find()函數(shù)和unite

6、()函數(shù)，初始化迷宮的每個(gè)元素都是一個(gè)獨(dú)立的集合，隨機(jī)化選擇一個(gè)數(shù)組元素，再隨機(jī)選擇一個(gè)方向，使其與相鄰的元素放入同一集合。直到入口和出口處于同一個(gè)集合。3. 深度優(yōu)先搜索模塊：Bfs()函數(shù)利用隊(duì)列從入口開始找到一條路徑抵達(dá)出口。4. 深度優(yōu)先搜索模塊： Dfs()函數(shù)利用遞歸從入口開始找到一條路徑抵達(dá)出口。5. 形象化顯示迷宮模塊： 迷宮數(shù)組中任意相鄰的元素如果屬于同一集合，則之間是連通的，否則不連通，并標(biāo)注出入口和出口的位置。3 使用的數(shù)據(jù)結(jié)構(gòu)的描述3.1 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) 并查集：并查集可以用來表示元素之間的集合關(guān)系，即這些元素是不是屬于哪個(gè)集合。通俗理解是，若兩個(gè)元素是屬于統(tǒng)一集合，就將

7、這兩個(gè)元素并在一起。存儲(chǔ)結(jié)構(gòu)上，用樹結(jié)構(gòu)模擬。一開始，每個(gè)元素自己構(gòu)成一個(gè)集合，所以自己構(gòu)成一棵樹。然后，若有兩個(gè)元素并成一個(gè)集合，則將這兩個(gè)元素所在的樹，合并成一棵樹。具體實(shí)現(xiàn)的話，就是將一棵樹的根看成是另一棵樹根的新根。并查集的作用是可以統(tǒng)計(jì)并判定兩個(gè)元素是否屬于統(tǒng)一集合。 廣度優(yōu)先搜索：(1)從隊(duì)列頭取出一個(gè)結(jié)點(diǎn)，檢查它按照擴(kuò)展規(guī)則是否能夠擴(kuò)展，如果能則產(chǎn)生一個(gè)新節(jié)點(diǎn)。(2) 檢查新生成的結(jié)點(diǎn)，看它是否已在隊(duì)列中存在，如果新節(jié)點(diǎn)已在隊(duì)列中，就放棄此節(jié)點(diǎn)，然后回到第(1)步。否則，加入隊(duì)尾。(3) 檢查新節(jié)點(diǎn)是否為目標(biāo)結(jié)點(diǎn)，如果是則搜索成功，程序結(jié)束，如果不是，回到第(1)步，再從隊(duì)列頭取

8、出結(jié)點(diǎn)進(jìn)行擴(kuò)展(4) 當(dāng)需要給出解的路徑時(shí)，則要保存每個(gè)節(jié)點(diǎn)的來源，也就是它是從哪個(gè)結(jié)點(diǎn)擴(kuò)展來的。 深度優(yōu)先搜索：初始化所有頂點(diǎn)均未被訪問過，選擇初始點(diǎn)后，遞歸調(diào)用以下步驟： (1)訪問搜索到的未被訪問的鄰接點(diǎn)； (2)將此頂點(diǎn)的visited數(shù)組元素值置1； (3)搜索該頂點(diǎn)的違背訪問的鄰接點(diǎn)，若該鄰接點(diǎn)存在，則從此鄰接點(diǎn)開始進(jìn)行同樣的訪問和搜索。3.2 數(shù)據(jù)結(jié)構(gòu)用法說明 并查集：首先將所有的迷宮元素處理成獨(dú)立的集合，fatheri=i;當(dāng)選擇將兩個(gè)元素連通時(shí)，即將兩個(gè)元素處于同一集合下，具體做法是將一棵樹的根看成是另一棵樹根的新根。假設(shè)元素i的樹根是b,元素j的樹根是h,則將fatherb

9、=h;即將兩個(gè) 元素放在了同一集合里，也就是兩個(gè)元素的樹根相同。 廣度優(yōu)先搜索：搜索時(shí)用到了隊(duì)列，廣度優(yōu)先搜索的結(jié)果是最優(yōu)的，也就是從入口到出口的最短的路徑，因?yàn)橐谰唧w的路徑，所以需要標(biāo)記每個(gè)入隊(duì)列的元素的來源，這樣就能從出口返回到入口。 深度優(yōu)先搜索：搜索時(shí)用到了棧，遞歸操作是深度搜索的關(guān)鍵，標(biāo)記的添加與刪除是非常重要的。我們需要存儲(chǔ)遍歷的路徑，每當(dāng)我們深入一層遞歸時(shí)，我們需要將坐標(biāo)入棧，每當(dāng)遞歸回退時(shí)，表示這個(gè)位置不合適，我們將出棧，最后，當(dāng)我們搜索到出口時(shí)，將棧輸出即為遍歷路徑。 4 函數(shù)的描述4.1 主要函數(shù)設(shè)計(jì)1. inint（）函數(shù)： 作用：按照規(guī)定尺寸申請二維數(shù)組表示迷宮，并

10、將每個(gè)數(shù)組元素設(shè)置為獨(dú)立的集合，用并查集表示，規(guī)定每個(gè)元素與四周相鄰的元素是不連通的，用arry.state表示，當(dāng)為1表示連通，0時(shí)表示不連通。2.void maze()函數(shù)： 作用：隨機(jī)生成迷宮。構(gòu)造路徑從入口到出口是連通的。按并查集來說就是將入口和出口以及二者間的路徑元素都處于同一個(gè)集合，也就是有著相同的樹根。3. void bfs()函數(shù)： 作用：廣度優(yōu)先搜索從入口遍歷至出口，并記錄具體路徑。 4.void dfs（）函數(shù)：作用：深度優(yōu)先搜索從入口遍歷至出口，并記錄具體路徑。5. void finalprint()函數(shù)：作用：按照遍歷路徑掃描二維數(shù)組，形象化表示迷宮。4.2 主要函數(shù)流

11、程圖Inint（）： 開始 輸入迷宮尺寸 結(jié)束隨機(jī)選擇入口和出口申請二維數(shù)組，并將所有數(shù)組元素設(shè)置為獨(dú)立的集合將任意兩個(gè)相鄰的數(shù)組元素設(shè)置為不連通 圖4.2.1初始化迷宮函數(shù)流程圖Void maze（）： 開始入口和出口是否連通？ 否 是隨機(jī)選擇一個(gè)數(shù)組元素從上述元素的四周隨機(jī)選擇一個(gè)方向?qū)⑦@兩個(gè)元素連通起來 結(jié)束 圖4.2.2隨機(jī)生成連通函數(shù)流程圖取隊(duì)頭元素將入口坐標(biāo)入隊(duì)列 開始Void bfs()函數(shù)：判斷是否是出口？ 是否將與隊(duì)頭元素相鄰的四個(gè)方向的元素入隊(duì)列，并記錄父節(jié)點(diǎn)坐標(biāo) 結(jié)束 圖4.2.3廣度優(yōu)先遍歷迷宮函數(shù)流程圖Void dfs（）函數(shù)： 開始以迷宮入口作為遞歸入口，并依此為初

12、始點(diǎn)判斷此點(diǎn)是否為出口？ 是 否遞歸回退，返回上一個(gè)初始點(diǎn)判斷初始點(diǎn)的相鄰四個(gè)方向是否都查看完畢？ 是否以此點(diǎn)作為遞歸的新入口，并標(biāo)記 圖4.2.4深度優(yōu)先遍歷迷宮函數(shù)流程圖 結(jié)束 5程序測試和運(yùn)行的結(jié)果5.1 程序測試 由用戶自行規(guī)定迷宮的尺寸 截圖5.1.1：迷宮的初始化迷宮的隨機(jī)形成截圖5.1.2 ：迷宮的形成 5.2 運(yùn)行結(jié)果迷宮的廣度優(yōu)先搜索 截圖5.2.1：迷宮的廣度搜索 迷宮的深度優(yōu)先搜索 圖5.2.2：迷宮的深度優(yōu)先搜索輸出迷宮圖5.2.3：輸出迷宮參考文獻(xiàn)1 高富平，張楚 . 電子商務(wù)法M. 北京：北京大學(xué)出版社，20022譚浩強(qiáng)著. C程序設(shè)計(jì)（ 第三版）. 北京: 清華大

13、學(xué)出版社,20053數(shù)據(jù)結(jié)構(gòu): C語言版 /嚴(yán)蔚敏,吳偉明編著.北京:清華大學(xué)出版社,2007附 錄（關(guān)鍵部分程序清單）#include<stdio.h>#include<stdlib.h>#include<time.h>#include<string.h>struct node int state4;/0123表示上下左右四扇門的閉合情況，0表示關(guān)閉，1表示打開arry5000;struct stuint x,y;int loc;q10000,stack1000,cun100000,bor1000;int n,m,en,ex,father500

14、0,front,rear,vis1000010000,der42=0,1,0,-1,-1,0,1,0,mark10001000,top,xian10001000;/將二維數(shù)組轉(zhuǎn)化為一維數(shù)組，二維坐標(biāo)（a,b),轉(zhuǎn)化為一維坐標(biāo)a*m+b;一維坐標(biāo)x,轉(zhuǎn)化為二維坐標(biāo)(x/m,x%m),二維數(shù)組的行和列從0開始int find(int x) if(fatherx=x)return x;else fatherx=find(fatherx);void unite(int hx,int hy) int i,j; i=find(hx); j=find(hy); fatheri=j;void inint()f

15、or(int i=0;i<n;i+)for(int j=0;j<m;j+) fatheri*m+j=i*m+j; printf("%d ",fatheri*m+j);printf("n"); for(int k=0;k<m*n;k+)arryk.state0=arryk.state1=arryk.state2=arryk.state3=0;/所有的門都是閉合的void nprint()int i,j;printf(" ");for(i=0;i<m;i+)if(i<10) printf("%d &

16、quot;,i);elseprintf("%d",i);printf("n");printf(" ");for(i=0;i<m;i+)if(i=en)printf(" ");else printf(" _");printf("n");for( i=0;i<n;i+)if(i<10) printf("%d ",i);elseprintf("%d",i);printf("|");for( j=0;j&l

17、t;m;j+) if(arryi*m+j.state3=1)printf(" ");else printf(" |");printf("n");printf(" ");for(j=0;j<m;j+)if(i=n-1&&j=ex)printf(" ");elseif(arryi*m+j.state1=1)printf(" ");else printf(" -");printf("n");void maze()/隨機(jī)生

18、成迷宮int row,col,num,nrow,ncol;clock_t start_time ;start_time = clock();/計(jì)時(shí)函數(shù)，數(shù)據(jù)類型是clock_t(長整型，毫秒)，在time.h文件中syxwhile(find(en)!=find(n-1)*m+ex)/入口和出口不連通 row=rand()%n;/隨機(jī)找出一個(gè)房間 col=rand()%m; num=rand()%4; switch(num) case 0:/與上相通 nrow=row-1; if(row=0) continue; else if(find(nrow*m+col)!=find(row*m+col)

19、/判斷是否連通，如果連通，說明曾經(jīng)操作過，否則，相連通 arryrow*m+col.state0=arrynrow*m+col.state1=1;/將兩個(gè)相鄰方格的相對應(yīng)的墻拆掉 unite(nrow*m+col,row*m+col); break; case 1:/與下相通 nrow=row+1; if(row=n-1) continue; else if(find(nrow*m+col)!=find(row*m+col) arryrow*m+col.state1=arrynrow*m+col.state0=1; unite(nrow*m+col,row*m+col); break; cas

20、e 2:/與左相通 ncol=col-1; if(col=0) continue; else if(find(row*m+col)!=find(row*m+ncol) arryrow*m+col.state2=arryrow*m+ncol.state3=1;unite(row*m+col,row*m+ncol); break; case 3:/與右相通 ncol=col+1; if(col=m-1) continue; else if(find(row*m+col)!=find(row*m+ncol) arryrow*m+col.state3=arryrow*m+ncol.state2=1;u

21、nite(row*m+col,row*m+ncol); break; void bfs()/xy為入口的坐標(biāo)int i,j,k,px,py,hx,hy; while(front<rear)px=qfront.x;py=qfront.y;if(px=n-1&&py=ex)return; for(i=0;i<4;i+) hx=px+deri0; hy=py+deri1; if(vishxhy=0&&hx>=0&&hx<n&&hy>=0&&hy<m) if(px=hx&&

22、;hy=py-1)/左移 if(arrypx*m+py.state2=1) qrear.x=hx; qrear.y=hy; vishxhy=1; qrear.loc=px*m+py; rear+; if(px=hx&&hy=py+1)/右移if(arrypx*m+py.state3=1)qrear.x=hx;qrear.y=hy;vishxhy=1;qrear.loc=px*m+py;rear+;if(hy=py&&hx=px-1)/上移if(arrypx*m+py.state0=1)qrear.x=hx;qrear.y=hy;vishxhy=1;qrear.l

23、oc=px*m+py;rear+;if(hy=py&&hx=px+1)/下移if(arrypx*m+py.state1=1)qrear.x=hx;qrear.y=hy;vishxhy=1; qrear.loc=px*m+py; rear+; front+; void initmaze()int i,j,k;printf(" ");for(i=0;i<m;i+)if(i<10) printf("%d ",i);elseprintf("%d",i);printf("n");printf(&q

24、uot; ");for(i=0;i<m;i+) printf(" _");printf("n");for( i=0;i<n;i+)if(i<10) printf("%d ",i);elseprintf("%d",i);printf("|");for( j=0;j<m;j+) printf(" |");printf("n");printf(" ");for(j=0;j<m;j+) printf(&q

25、uot; -");printf("n");void printbfs()int j,rx,ry,k;printf("打印廣度優(yōu)先搜索的存儲(chǔ)順序：n");for(j=0;j<=front;j+)printf("(%d %d) ",qj.x,qj.y);printf("n");int count=0; while(qfront.loc!=(qfront.x*m+qfront.y) stackcount.x=qfront.x;stackcount.y=qfront.y;count+; rx=qfront.

26、loc/m; ry=qfront.loc%m;for( k=front-1;k>=0;k-)if(qk.x=rx&&qk.y=ry)front=k;printf("根據(jù)廣度搜索記錄父級地址打印從入口到出口的路徑如下:n");for(int t=count-1;t>=0;t-)printf("(%d %d)n",stackt.x,stackt.y);void dfs(int px,int py)int i,j,k,hx,hy;cuntop.x=px;cuntop.y=py;top+;if(px=n-1&&py=e

27、x) for(i=0;i<top;i+) bori.x=cuni.x; bori.y=cuni.y; bori.x=-1; return ;for(i=0;i<4;i+)hx=px+deri0;hy=py+deri1; if(hx>=0&&hx<n&&hy>=0&&hy<m&&markhxhy=0) if(px=hx&&hy=py-1)/左移 if(arrypx*m+py.state2=1) markhxhy=1; dfs(hx,hy); markhxhy=0; top-; if

28、(px=hx&&hy=py+1)/右移if(arrypx*m+py.state3=1) markhxhy=1;dfs(hx,hy); markhxhy=0;top-;if(hy=py&&hx=px-1)/上移if(arrypx*m+py.state0=1) markhxhy=1; dfs(hx,hy); markhxhy=0;top-;if(hy=py&&hx=px+1)/下移if(arrypx*m+py.state1=1) markhxhy=1; dfs(hx,hy); markhxhy=0;top-; markpxpy=0;void fina

29、lprint()int i,j;printf(" ");for(i=0;i<m;i+)if(i<10) printf("%d ",i);elseprintf("%d",i);printf("n");printf(" ");for(i=0;i<m;i+)if(i=en)printf(" ");else printf(" _");printf("n");for( i=0;i<n;i+)if(i<10) prin

30、tf("%d ",i);elseprintf("%d",i);printf("|");for( j=0;j<m;j+) if(arryi*m+j.state3=1)if(xianij=1)printf("* ");else printf(" ");elseif(xianij=1)printf("*|");else printf(" |");printf("n");printf(" ");for(j=0;j<

31、;m;j+)if(i=n-1&&j=ex)printf(" ");elseif(arryi*m+j.state1=1)printf(" ");else printf(" -");printf("n");int main()int j,i;char ch;srand(int)time(NULL);/srand初始化隨機(jī)種子,rand產(chǎn)生隨機(jī)數(shù)time(0)clock_t start_time ; start_time = clock();/計(jì)時(shí)函數(shù)，數(shù)據(jù)類型是clock_t(長整型，毫秒)，在time.h文件中syx printf("是否輸入迷宮的尺寸:輸入請選擇A 否則輸入B,默認(rèn)值為50 50n");scanf("%c",&ch);if(ch='A')printf("請輸入迷宮的尺寸n");scanf("%d%d",&n,&m);if(ch='B')n=50;m=50; inint();initmaze(); en=rand()%m;ex=rand()%m; arryen.state0=1;arry(n-