迷宮求解課程設(shè)計(jì)含引言需求分析偽代碼數(shù)據(jù)結(jié)構(gòu)代碼分析附錄

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

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

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

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

5、t node int x; int y; int c; linkstack;3) 創(chuàng)造一個(gè)棧包括(top表示棧頂元素) linkstack topn1*n2;三、算法設(shè)計(jì)首先，創(chuàng)建數(shù)組的大小，此數(shù)組大小要求用戶自己輸入。具體算法： printf("輸入迷宮大小(提示:行列數(shù)不能超過(guò)50!):"); /在此提示用戶輸入數(shù)組大小的界限 scanf("%d",&g); /再次用scanf來(lái)輸入使用者要?jiǎng)?chuàng)建的迷宮大小，并且把值賦給g這個(gè)參量，用于對(duì)與迷宮數(shù)組的創(chuàng)建 printf("大小創(chuàng)建完畢,請(qǐng)輸入迷宮:n"); /用來(lái)提示用戶要進(jìn)

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

7、)，算法： void scsu(int g,int h) /創(chuàng)建迷宮輸出函數(shù),設(shè)定參量并從主函數(shù)中獲得要使用的參量int a,b; printf("生成的迷宮是:n"); /提示要現(xiàn)實(shí)的內(nèi)容是什么 for(a=0;a<g;a+) for(b=0;b<h;b+) printf(mazeab?"#":" "); printf("n"); /使用循環(huán)語(yǔ)句來(lái)實(shí)現(xiàn)迷宮的實(shí)化，輸出迷宮 最后，迷宮尋路，在尋路的時(shí)候，我們應(yīng)從入口(1、0)進(jìn)入迷宮，當(dāng)迷宮的入口處有障礙或者出口被堵，再或者沒(méi)有通路時(shí)整個(gè)程序結(jié)束，并輸

8、出迷宮無(wú)解的提示。如果迷宮求解過(guò)程中沒(méi)有出現(xiàn)無(wú)解情況，那么在求解的過(guò)程中，會(huì)輸出迷宮的通路路徑，并且輸出坐標(biāo)值，讓使用者更清楚路徑的走法。在尋路的過(guò)程中，每走過(guò)一個(gè)格，那個(gè)格得知就會(huì)被賦值為2，用來(lái)標(biāo)記此處已走過(guò)，免去了來(lái)來(lái)回回的重走，以免出現(xiàn)死循環(huán)，所以開(kāi)始時(shí)的入口則直接的定義為了2，這樣程序就能達(dá)到入口，并從入口進(jìn)入到迷宮當(dāng)中，如果在迷宮當(dāng)中沒(méi)有通路的話，則會(huì)使topi.c的值變?yōu)榱?，這樣當(dāng)其為0時(shí)，可以結(jié)束循環(huán)輸出“迷宮無(wú)解！”，則當(dāng)迷宮如果出現(xiàn)有解時(shí)，則到最后的出口時(shí)仍然會(huì)將topi.c賦值為0，但是此時(shí)的出口處被復(fù)制為2，也就是用這個(gè)來(lái)判斷是否存在通路，所以才實(shí)現(xiàn)了圖中所示的功能。這

9、樣就簡(jiǎn)單的實(shí)現(xiàn)了，有解無(wú)解的輸出。從而實(shí)現(xiàn)了要求的程序！代碼如下：switch(方向) case 0: /為0時(shí)有兩種情況走完全程或者沒(méi)有通路 run=0;if(v=1) /當(dāng)V為1時(shí)說(shuō)明此路沒(méi)有走到出口就已經(jīng)沒(méi)有路了，所以無(wú)通路 printf("此迷宮無(wú)通路!"); break; case 向右: if(mazetopi.xtopi.y+1=0) /用來(lái)判斷此處是否有障礙 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é)束了那么出

10、口處的坐標(biāo)值變?yōu)?，使V等于0 else topi.c+=1; /如果沒(méi)有則進(jìn)行下一步操作（一下各個(gè)方向的操作與第一個(gè)方向的相同） break; 剩余的方向： case向上：代碼操作與向右一樣 break;case向左：代碼操作與向右一樣 break;case向下：代碼操作與向右一樣 break;其中要尋求所有的通路，在這里則使用了一個(gè)dowhile循環(huán)，這樣可以找到所有的通路，其條件使run。如果run等于1，則進(jìn)行循環(huán)，否則循環(huán)結(jié)束程序結(jié)束。另外的，菜單操作（圖在測(cè)試中）則是使用了switch操作，這樣可以選擇操作的步驟，如果選擇1，則迷宮求解開(kāi)始，如果選擇2則直接結(jié)束操作（只有兩個(gè)操作

11、1：求解 2：退出）。圖解分析：定義添加迷宮創(chuàng)建迷宮從迷宮入口開(kāi)始尋路上左右下判斷個(gè)方向是否通路迷宮無(wú)解求解完畢程序結(jié)束四、調(diào)試分析第一個(gè)問(wèn)題，在剛開(kāi)始的調(diào)試過(guò)程中，我們遇到了，無(wú)法判斷走過(guò)的路程，從而出現(xiàn)了死循環(huán)，導(dǎo)致程序不能正常進(jìn)行，但是經(jīng)過(guò)我們的討論，我們想出用標(biāo)記的方法來(lái)解決，也就是讓走過(guò)的路程全給標(biāo)示了，這樣就不會(huì)再走重復(fù)的路。第二個(gè)問(wèn)題，就是性用菜單來(lái)實(shí)現(xiàn)操作，那樣程序的操作性就會(huì)更強(qiáng)，所以我們就要把所有的方法，給寫(xiě)成一個(gè)個(gè)的函數(shù)來(lái)調(diào)用，這樣就遇到了參量傳遞的問(wèn)題，但是經(jīng)過(guò)我們的參考以及從書(shū)本上的實(shí)例，我們慢慢地更深的了解到了參量傳遞的應(yīng)用，那么這個(gè)問(wèn)題也就迎刃而解了。從此我們實(shí)現(xiàn)

12、了菜單操作！五、程序?qū)崿F(xiàn)及測(cè)試運(yùn)行界面：測(cè)試：結(jié)果輸出：無(wú)解的時(shí)候：六、體會(huì)及不足之處 通過(guò)此次課程設(shè)計(jì)，是我對(duì)于數(shù)據(jù)結(jié)構(gòu)有了更深的了解，更新的認(rèn)識(shí)。數(shù)據(jù)結(jié)構(gòu)是一門重要的課程，只有數(shù)據(jù)結(jié)構(gòu)學(xué)得扎實(shí)了，才能對(duì)于計(jì)算機(jī)有更深的應(yīng)用，所以學(xué)好數(shù)據(jù)結(jié)構(gòu)是很重要的。經(jīng)過(guò)兩周的上機(jī)設(shè)計(jì)，我實(shí)現(xiàn)了簡(jiǎn)單的迷宮求解，能夠簡(jiǎn)單的實(shí)現(xiàn)求解過(guò)程。但是還存在著不足之處，不能輸入矩形的數(shù)組，而且出口和入口是固定的，也可以改變可是要改變代碼，本程序不能循環(huán)執(zhí)行，只能執(zhí)行一次。有待改進(jìn)！七、參考文獻(xiàn) 數(shù)據(jù)結(jié)構(gòu)(c語(yǔ)言版) 嚴(yán)蔚敏 清華大學(xué)出版社 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)教程 李業(yè)麗、鄭良斌 數(shù)據(jù)結(jié)構(gòu) 高教出版社 數(shù)據(jù)結(jié)構(gòu)習(xí)題 李春保 清

13、華大學(xué)出版社 數(shù)據(jù)結(jié)構(gòu)習(xí)題 嚴(yán)蔚敏 清華大學(xué)出版社 C語(yǔ)言與數(shù)據(jù)結(jié)構(gòu) 王立柱 清華大學(xué)出版社 數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言篇)習(xí)題與解析 李春保 清華大學(xué)出版社八、附錄#include<stdio.h>#include<stdlib.h>#define n1 50#define n2 50typedef struct nodeint x;int y;int c;linkstack;int mazen1n2;linkstack topn1*n2;int i,j,k,m=1,run; void shuzu(int g,int h) int a,b; for(a=0;a<g;a+)

14、 for(b=0;b<h;b+) scanf("%d",&mazeab);void scsu(int g,int h)int a,b; printf("生成的迷宮是:n"); for(a=0;a<g;a+) for(b=0;b<h;b+) printf(mazeab?"#":" "); printf("n"); void main() int g,h,v; int w;printf("*n");printf("*n"); prin

15、tf("* 歡迎使用迷宮求解 *n");printf("*n");printf("*n");printf("n");printf("*n");printf("*n");printf(" *迷宮求解請(qǐng)按:1 n"); printf(" * 退出請(qǐng)按:2 n"); printf("*n");printf("*n"); scanf("%d",&w);switch(w) cas

16、e 1:printf("輸入迷宮大小(提示:行列數(shù)不能超過(guò)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; do if(topi.c<5) if(topi.x=(g-2)&&topi.y=(h-1) printf("第%d條通路是:n"

17、,m+); for(j=0;j<=i;j+) printf("(%d,%d)",topj.x,topj.y); if(v!=0) printf("->"); printf("n"); for(j=0;j<g;j+) for(k=0;k<h;k+) if(mazejk=0) printf(" "); else if(mazejk=2) printf("O"); else printf("*"); printf("n"); mazeto

18、pi.xtopi.y=0; topi.c=1; i-; topi.c+=1; continue; switch(topi.c) case 0: run=0;if(v=1) printf("此迷宮無(wú)通路!"); 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-1.y-1; mazetopi.xtop