迷宮求解課程設(shè)計

1、引言數(shù)據(jù)結(jié)構(gòu)是一門理論性很強(qiáng)、思維抽象、難度較大的課程，是基 礎(chǔ)課和專業(yè)課之間的橋梁。該課程的先行課程是計算機(jī)基礎(chǔ)、程 序設(shè)計語言、離散數(shù)學(xué)等，后續(xù)課程有操作系統(tǒng)、編譯原理、數(shù) 據(jù)庫原理、軟件工程等。通過本門課程的學(xué)習(xí)，我們應(yīng)該能透徹 地理解各種數(shù)據(jù)對象的特點，學(xué)會數(shù)據(jù)的組織方法和實現(xiàn)方法， 并進(jìn)一步培養(yǎng)良好的程序設(shè)計能力和解決實際問題的能力，而且 該課程的研究方法對我們學(xué)生在學(xué)校和離校后的工作和學(xué)習(xí)，也 有重要意義。數(shù)據(jù)結(jié)構(gòu)是電子信息科學(xué)與技術(shù)專業(yè)的一門核心專 業(yè)基礎(chǔ)課程，在該專業(yè)的課程體系中起著承上啟下的作用，學(xué)好 了數(shù)據(jù)結(jié)構(gòu)對于提高理論認(rèn)知水平和實踐能力有著極為重要的 作用。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)

2、的最終目的是為了獲得求解問題問能力。對 于現(xiàn)實世界中的問題，應(yīng)該能從中抽象出一個適當(dāng)?shù)臄?shù)學(xué)模型， 該數(shù)學(xué)模型在計算機(jī)內(nèi)部的數(shù)據(jù)結(jié)構(gòu)來表示，然后設(shè)計一個解此 數(shù)學(xué)模型的算法，在進(jìn)行編程調(diào)試，最后活的問題的解答。基于此原因，現(xiàn)在我們開設(shè)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計。針對數(shù)據(jù)結(jié)構(gòu)課 程的特點，著眼于培養(yǎng)我們的實踐能力。實習(xí)課程是為了加強(qiáng)編 程能力的培養(yǎng)，鼓勵學(xué)生使用新興的編程語言。相信通過數(shù)據(jù)結(jié) 構(gòu)課程實踐，無論是理論知識，還是動手能力，同學(xué)們都會有不 同程度的提高。一、需求分析本課程設(shè)計是解決迷宮求解的問題，從入口出發(fā)，順某一方向向 前探索，若能走通，則繼續(xù)往前走；否則沿原路退回，換一個方 向再繼續(xù)探索，直至

3、所有可能的通路都探索到為止。為了保證在 任何位置上都能沿原路退回，顯然需要用一個后進(jìn)先出的結(jié)構(gòu)來 保存從入口到當(dāng)前位置的路徑。因此，在求迷宮通路的算法中要 應(yīng)用“?！钡乃枷爰僭O(shè)“當(dāng)前位置”指的是“在搜索過程中的某 一時刻所在圖中某個方塊位置”，則求迷宮中一條路徑的算法的 基本思想是：若當(dāng)前位置“可通”，則納入“當(dāng)前路徑”，并繼續(xù) 朝“下一位置”探索，即切換“下一位置”為“當(dāng)前位置”，如 此重復(fù)直至到達(dá)出口；若當(dāng)前位置“不可通”，則應(yīng)順著“來向” 退回到“前一通道塊”，然后朝著除“來向”之外的其他方向繼 續(xù)探索；若該通道塊的四周4個方塊均“不可通”，則應(yīng)從“當(dāng) 前路徑”上刪除該通道塊。所謂“下一

4、位置”指的是當(dāng)前位置四 周4個方向（上、下、左、右）上相鄰的方塊。假設(shè)以棧記錄“當(dāng) 前路徑”，則棧頂中存放的是“當(dāng)前路徑上最后一個通道塊”。由 此，“納入路徑”的操作即為“當(dāng)前位置入?！保弧皬漠?dāng)前路徑上刪除前一通道塊”的操作即為“出?！?。二、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)設(shè)計考慮1）建立一個二維數(shù)組表示迷宮的路徑（0表示通道，1表示墻壁）;2）創(chuàng)建一個棧，用來存儲“當(dāng)前路徑”，即“在搜索過程中某一 時刻所在圖中某個方塊位置”。邏輯結(jié)構(gòu)存儲結(jié)構(gòu)1）創(chuàng)建一個Int類型的二維數(shù)組int mazen1n2,用來存放0 和1 （0表示通道，1表示墻壁）；2）創(chuàng)建一個結(jié)構(gòu)體用來儲存數(shù)組信息（數(shù)組的橫坐標(biāo)X，數(shù)組的 縱坐

5、標(biāo)Y，方向C）結(jié)構(gòu)體：typedef struct nodeint x;int y;int c;linkstack;3）創(chuàng)造一個棧包括（top表示棧頂元素）linkstack topn1*n2;三、算法設(shè)計首先，創(chuàng)建數(shù)組的大小，此數(shù)組大小要求用戶自己輸入。具體算 法：printf （-輸入迷宮大?。ㄌ崾?行列數(shù)不能超過50!）:）;在此提示用戶輸入數(shù)組大小的界限scanf（%d,&g）; 再次用scanf來輸入使用者要 創(chuàng)建的迷宮大小，并且把值賦給g這個參量，用于對與迷宮數(shù)組 的創(chuàng)建printf（大小創(chuàng)建完畢，請輸入迷宮:n）; /用來提示用 戶要進(jìn)行下面操作其次，用戶自己定義迷宮的內(nèi)容（其中

6、自定義迷宮入口（1,0）,迷 宮的出口為（g-2、h-1）,迷宮的生成算法：void shuzu（int g,int h）/創(chuàng)建數(shù)組函數(shù)，設(shè)定參量并從主函數(shù)中獲得要使用的參量int a,b;for（a=0;ag;a+）for（b=0;bh;b+）scanf（%d,&mazeab）;使用循環(huán)來給數(shù)組賦值，也就是用來創(chuàng)建迷宮的格式，這是一個自定義的迷宮創(chuàng)建，其中的0和1分別是 表示通路和障礙，定義的數(shù)組其實就是迷宮的設(shè)計圖第三，產(chǎn)生迷宮(其中自定義迷宮入口(1,0),迷宮的出口為(g-2、 h-1)，算法：void scsu(int g,int h) /創(chuàng)建迷宮輸出函數(shù)，設(shè) 定參量并從主函數(shù)中獲得

7、要使用的參量int a,b;printf(生成的迷宮是：n); /提示要現(xiàn)實 的內(nèi)容是什么for(a=0;ag;a+) for(b=0;bh;b+)printf(mazeab?”#”:);printf(n);/使用循環(huán)語句來實現(xiàn)迷宮的實化，輸出迷宮最后，迷宮尋路，在尋路的時候，我們應(yīng)從入口(1、0)進(jìn)入迷宮， 當(dāng)迷宮的入口處有障礙或者出口被堵，再或者沒有通路時整個程 序結(jié)束，并輸出迷宮無解的提示。如果迷宮求解過程中沒有出現(xiàn) 無解情況，那么在求解的過程中，會輸出迷宮的通路路徑，并且 輸出坐標(biāo)值，讓使用者更清楚路徑的走法。在尋路的過程中，每 走過一個格，那個格得知就會被賦值為2,用來標(biāo)記此處已走過

8、， 免去了來來回回的重走，以免出現(xiàn)死循環(huán)，所以開始時的入口則 直接的定義為了 2,這樣程序就能達(dá)到入口，并從入口進(jìn)入到迷 宮當(dāng)中，如果在迷宮當(dāng)中沒有通路的話，則會使topi.c的值 變?yōu)榱?，這樣當(dāng)其為0時，可以結(jié)束循環(huán)輸出“迷宮無解! ”，則 當(dāng)迷宮如果出現(xiàn)有解時，則到最后的出口時仍然會將topi.c 賦值為0，但是此時的出口處被復(fù)制為2,也就是用這個來判斷 是否存在通路，所以才實現(xiàn)了圖中所示的功能。這樣就簡單的實 現(xiàn)了，有解無解的輸出。從而實現(xiàn)了要求的程序！代碼如下： switch(方向) case 0: 為0時有兩種情況走完全程或者沒 有通路 run=0;if(v=1) 當(dāng)V為1時說明此路

9、沒有走到 出口就已經(jīng)沒有路了，所以無通路printf（此迷宮無通路!）；break;case向右：if（mazetopi.xtopi.y+1=0）用來判斷此處是否有障礙 i+;topi.x=topi-1.x;topi.y=topi-1.y+1;mazetopi.xtopi.y=2;/進(jìn)行賦值交換if（mazeg-2h-1=2） v=0; /如果在 這里結(jié)束了那么出口處的坐標(biāo)值變?yōu)?,使V等于0else topi.c+=1; / 如果沒有 則進(jìn)行下一步操作（一下各個方向的操作與第一個方向的相同） break;剩余的方向：case向上：代碼操作與向右一樣break;case向左：代碼操作與向右一樣

10、break;case向下：代碼操作與向右一樣break;其中要尋求所有的通路，在這里則使用了一個dowhile循環(huán)， 這樣可以找到所有的通路，其條件使run。如果run等于1，則 進(jìn)行循環(huán)，否則循環(huán)結(jié)束程序結(jié)束。另外的，菜單操作（圖在測 試中）則是使用了 switch操作，這樣可以選擇操作的步驟，如 果選擇1，則迷宮求解開始，如果選擇2則直接結(jié)束操作（只有 兩個操作1：求解2：退出）。圖解分析：四、調(diào)試分析第一個問題，在剛開始的調(diào)試過程中，我們遇到了，無法判 斷走過的路程，從而出現(xiàn)了死循環(huán)，導(dǎo)致程序不能正常進(jìn)行，但 是經(jīng)過我們的討論，我們想出用標(biāo)記的方法來解決，也就是讓走 過的路程全給標(biāo)示了，

11、這樣就不會再走重復(fù)的路。第二個問題，就是性用菜單來實現(xiàn)操作，那樣程序的操作性就會更強(qiáng)，所以我們就要把所有的方法，給寫成一個個的函數(shù)來 調(diào)用，這樣就遇到了參量傳遞的問題，但是經(jīng)過我們的參考以及 從書本上的實例，我們慢慢地更深的了解到了參量傳遞的應(yīng)用， 那么這個問題也就迎刃而解了。從此我們實現(xiàn)了菜單操作！五、程序?qū)崿F(xiàn)及測試運行界面：測試：測試：7 _ -商入迷宮天小提示二行列數(shù)不能超過部，n %小創(chuàng)建完畢-請輸入扯虱 L 1 1 1J S S 1 L 1 0 0 L 1 1 1結(jié)果輸出：T -rpr：I ，. - -L : I I -C皿ittt帕廉條逋路是：(1,0) (1,1X1,2X2,2X

12、2,DOOtthfl：OOPr-ess anu keu to continue無解的時候:制人迷宮大小提不:行列數(shù)不能超過弱?:4 矢小創(chuàng)建完畢？1111hail1 1 a akill隹成的迷宮是：m#it#ttitm#此迷宮無通路擰 ress anr to continue六、體會及不足之處通過此次課程設(shè)計，是我對于數(shù)據(jù)結(jié)構(gòu)有了更深的了解，更 新的認(rèn)識。數(shù)據(jù)結(jié)構(gòu)是一門重要的課程，只有數(shù)據(jù)結(jié)構(gòu)學(xué)得扎實 了，才能對于計算機(jī)有更深的應(yīng)用，所以學(xué)好數(shù)據(jù)結(jié)構(gòu)是很重要 的。經(jīng)過兩周的上機(jī)設(shè)計，我實現(xiàn)了簡單的迷宮求解，能夠簡單 的實現(xiàn)求解過程。但是還存在著不足之處，不能輸入矩形的數(shù)組， 而且出口和入口是固

13、定的，也可以改變可是要改變代碼，本程序 不能循環(huán)執(zhí)行，只能執(zhí)行一次。有待改進(jìn)！七、參考文獻(xiàn)數(shù)據(jù)結(jié)構(gòu)（c語言版）嚴(yán)蔚敏清華大學(xué)出版社數(shù)據(jù)結(jié)構(gòu)實驗教程李業(yè)麗、鄭良斌數(shù)據(jù)結(jié)構(gòu)高教出版社數(shù)據(jù)結(jié)構(gòu)習(xí)題李春保清華大學(xué)出版社數(shù)據(jù)結(jié)構(gòu)習(xí)題嚴(yán)蔚敏 清華大學(xué)出版社C語言與數(shù)據(jù)結(jié)構(gòu)王立柱清華大學(xué)出版社數(shù)據(jù)結(jié)構(gòu)（C語言篇）習(xí)題與解析李春保清華大 學(xué)出版社八、附錄#include#include#define n1 50#define n2 50typedef struct nodeint x;int y;int c;linkstack;int mazen1n2;linkstack topn1*n2;int i,j,k

14、,m=1,run;void shuzu(int g,int h)(int a,b;for(a=0;ag;a+)for(b=0;bh;b+)scanf(%d,&mazeab);void scsu(int g,int h)(int a,b;printf(生成的迷宮是:n);for(a=0;ag;a+) for(b=0;bh;b+)printf(mazeab?”#”:);printf(n);void main() int g,h,v;int w;1+ f 業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)pr j_nt_L 亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍

15、亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍 *n);1+ I 業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)pr j_nt_L 亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍亍 *n);printf(*歡迎使用迷宮求解*n); r-ki m+ + I 業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè) pr j_nti k* *n);r-ki m+ + f 業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè) U in* *n);p

16、rintf(n);printf(*n);printf(*n);printf(*迷宮求解請按:1n);printf(* 退出請按：2n);printf(* *n);printf(*n);scanf(%d”,&w);switch(w) case 1:printf(輸入迷宮大小(提示：行列數(shù)不能超過50!):);scanf(%d”,&g);printf(大小創(chuàng)建完畢!n”);h=g;shuzu(g,h);for(i=0;i=g*h;i+)topi.c=1;scsu(g,h);i=0;topi.x=1;topi.y=0;maze10=2;run=1;v=1;doif(topi.c5)if(topi.x

17、=(g-2)&topi.y=(h-1)printf(第%d 條通路是:n,m+);for(j=0;j);printf(n);for(j=0;jg;j+) for(k=0;kh;k+)if(mazejk=0)printf(-);else if(mazejk=2) printf(O);else printf(*);printf(n);mazetopi.xtopi.y=0;topi.c=1;i;topi.c+=1;continue;switch(topi.c) case 0: run=0;if(v=1)printf(此迷宮無通路!)； break;case 1: if(mazetopi.xtopi.y+1=0) i+;topi.x=topi-1.x;topi.y=topi-1.y+1;mazetopi.xtopi.y=2;if(mazeg-2h-1=2) v=0;else topi.c+=1;break;case 2: if(mazetopi.x-1topi.y=0) i+；topi.x=topi-1.x-1;topi.y=topi-1.y;mazetopi.xtopi.y=2;else topi.c+=1;break;case 3: if(mazetopi.xtopi.y-1=0) i+;topi.x=topi-1.x;topi.y=topi