迷宮求解課程設(shè)計(jì)說(shuō)明書(shū)

1、<p><b>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)</b></p><p><b>　　設(shè)計(jì)說(shuō)明書(shū)</b></p><p><b>　　計(jì)算機(jī)科學(xué)與技術(shù)系</b></p><p>　　2011年 9 月 9 日</p><p>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)評(píng)閱書(shū)</p>&l

2、t;p>　　注：指導(dǎo)教師成績(jī)60%，答辯成績(jī)40%，總成績(jī)合成后按五級(jí)制記入。</p><p><b>　　課程設(shè)計(jì)任務(wù)書(shū)</b></p><p>　　2011 —2012 學(xué)年第 一 學(xué)期</p><p>　　專業(yè)： 學(xué)號(hào)： 姓名： </p><p>　　課程設(shè)計(jì)名稱：

3、 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) </p><p>　　設(shè)計(jì)題目： 迷宮問(wèn)題求解 </p><p>　　完成期限：自 2011 年 8 月 29 日至 2011 年 9 月 9 日共 2 周</p

4、><p>　　設(shè)計(jì)依據(jù)、要求及主要內(nèi)容（可另加附頁(yè)）：</p><p>　　輸入一個(gè)任意大小的迷宮數(shù)據(jù)，設(shè)置入口、出口及障礙，借助棧結(jié)構(gòu)求解走出迷宮的路徑并輸出。1.遵循結(jié)構(gòu)化程序設(shè)計(jì)思想，采用C/C++實(shí)現(xiàn)。 2.界面友好，操作簡(jiǎn)便，容錯(cuò)性。 </p>&l

5、t;p>　　基本要求如下： </p><p>　　1）問(wèn)題分析和任務(wù)定義：根據(jù)設(shè)計(jì)題目的要求，充分地分析和理解問(wèn)題，明確問(wèn)題要求做什么？（而不是怎么做？）限制條件是什么？確定問(wèn)題的輸入數(shù)據(jù)集合。</p><p>　　2）邏輯設(shè)計(jì)：對(duì)問(wèn)題描述中涉及的操作對(duì)象定義相應(yīng)的數(shù)據(jù)類型，

6、并按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊，定義主程序模塊和各抽象數(shù)據(jù)類型。邏輯設(shè)計(jì)的結(jié)果應(yīng)寫(xiě)出每個(gè)抽象數(shù)據(jù)類型的定義（包括數(shù)據(jù)結(jié)構(gòu)的描述和每個(gè)基本操作的功能說(shuō)明），各個(gè)主要模塊的算法，并畫(huà)出模塊之間的調(diào)用關(guān)系圖；</p><p>　　3）詳細(xì)設(shè)計(jì)：定義相應(yīng)的存儲(chǔ)結(jié)構(gòu)。在這個(gè)過(guò)程中，要綜合考慮系統(tǒng)功能，使得系統(tǒng)結(jié)構(gòu)清晰、合理、簡(jiǎn)單和易于調(diào)試，抽象數(shù)據(jù)類型的實(shí)現(xiàn)盡可能做到數(shù)據(jù)封裝，基本操作的規(guī)格說(shuō)明盡可能明確具體。詳細(xì)設(shè)

7、計(jì)的結(jié)果是對(duì)數(shù)據(jù)結(jié)構(gòu)和基本操作做出進(jìn)一步的求精，寫(xiě)出數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的類型定義；</p><p>　　4）程序編碼：把詳細(xì)設(shè)計(jì)的結(jié)果進(jìn)一步求精為程序設(shè)計(jì)語(yǔ)言程序。同時(shí)加入一些注解和斷言，使程序中邏輯概念清楚；</p><p>　　5）程序調(diào)試與測(cè)試：能夠熟練掌握調(diào)試工具的各種功能，設(shè)計(jì)測(cè)試數(shù)據(jù)確保程序正確。調(diào)試正確后，認(rèn)真整理源程序及其注釋，形成格式和風(fēng)格良好的源程序清單和結(jié)果；</p&

8、gt;<p>　　6）結(jié)果分析：程序運(yùn)行結(jié)果包括正確的輸入及其輸出結(jié)果和含有錯(cuò)誤的輸入及其輸出結(jié)果；</p><p>　　7）編寫(xiě)課程設(shè)計(jì)報(bào)告；</p><p>　　以上要求中前三個(gè)階段的任務(wù)完成后，先將設(shè)計(jì)說(shuō)明書(shū)的草稿交指導(dǎo)老師面審，審查合格后方可進(jìn)入后續(xù)階段的工作。設(shè)計(jì)工作結(jié)束后，經(jīng)指導(dǎo)老師驗(yàn)收合格后將設(shè)計(jì)說(shuō)明書(shū)打印裝訂，并進(jìn)行答辯。</p><p&g

9、t;　　指導(dǎo)教師（簽字）： 教研室主任（簽字）： </p><p>　　批準(zhǔn)日期： 2011年 8 月 29 日</p><p><b>　　摘 要</b></p><p>　　設(shè)計(jì)了一個(gè)尋找迷宮出口路徑的程序，該程序具有設(shè)置任意大小的迷宮數(shù)據(jù)，通過(guò)設(shè)置的迷宮入口出口及障礙，探索

10、出一條簡(jiǎn)單路徑并輸出的功能。該程序采用VC作為軟件開(kāi)發(fā)環(huán)境，借助棧先入后出的特點(diǎn)，先將入口作為檢索的起點(diǎn)，順著某個(gè)方向向前探索，若能走通，則繼續(xù)往前走；否則沿原路返回，換個(gè)方向在繼續(xù)探索，直到所有可能的通路都探索到為止，最后把探索到的路徑輸出。</p><p>　　關(guān)鍵詞：迷宮路徑；探索；輸出</p><p><b>　　目 錄</b></p>

11、<p><b>　　1.課題描述1</b></p><p>　　2.問(wèn)題分析和任務(wù)定義2</p><p><b>　　3.邏輯設(shè)計(jì)3</b></p><p><b>　　4.詳細(xì)設(shè)計(jì)4</b></p><p>　　4.1迷宮數(shù)據(jù)的存儲(chǔ)4</p>

12、<p>　　4.2當(dāng)前位置可通性的判斷及探索方向的改變5</p><p>　　4.3無(wú)通路時(shí)沿原路返回6</p><p>　　4.4路徑信息入棧和出棧7</p><p>　　4.5 當(dāng)前探索位置的切換8</p><p>　　4.6最終探索路徑的輸出及標(biāo)記9</p><p>　　4.7打印迷宮信息

13、10</p><p><b>　　5.程序代碼11</b></p><p>　　5.1文件包含和結(jié)構(gòu)體的定義11</p><p>　　5.2棧的初始化及入棧出棧函數(shù)11</p><p>　　5.3申請(qǐng)迷宮大小及障礙的設(shè)置12</p><p>　　5.4通道可通性測(cè)試13</p>

14、;<p>　　5.5為走過(guò)的通道留下足跡13</p><p>　　5.6探索位置的切換13</p><p>　　5.7入口到出口的路徑探索14</p><p>　　5.8打印迷宮信息15</p><p><b>　　5.9主函數(shù)16</b></p><p><b>

15、;　　6.程序測(cè)試18</b></p><p><b>　　總結(jié)21</b></p><p><b>　　參考文獻(xiàn)22</b></p><p><b>　　1.課題描述</b></p><p>　　本次課題是實(shí)現(xiàn)迷宮問(wèn)題的求解，利用C語(yǔ)言設(shè)計(jì)一個(gè)能實(shí)現(xiàn)輸入一個(gè)

16、任意大小的迷宮數(shù)據(jù)，利用二維數(shù)組來(lái)儲(chǔ)存設(shè)置的入口、出口及障礙，借助棧先入后出的結(jié)構(gòu)特性保存迷宮探索過(guò)程中留下的路徑信息，以便在遇到障礙時(shí)沿原路返回，在探索結(jié)束后輸出棧中保存的最終路徑。</p><p>　　2.問(wèn)題分析和任務(wù)定義</p><p>　　迷宮求解的實(shí)現(xiàn)依賴于路徑探索的算法，路徑探索的算法采用的是“窮舉求解”的方法。因此有以下問(wèn)題：</p><p>　　(

17、1)數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的選擇。</p><p>　　(2)當(dāng)前位置的可通性判斷及探索方向的改變。</p><p>　　(3)道路不通時(shí)沿原路返回的算法。</p><p>　　(4)路徑信息的入棧和出棧。</p><p>　　(5)最終路徑的輸出。</p><p><b>　　3.邏輯設(shè)計(jì)</b><

18、/p><p>　　程序要實(shí)現(xiàn)路徑探索及輸出即要實(shí)現(xiàn)當(dāng)前位置可通性的判斷；路徑可通時(shí)朝默認(rèn)方向繼續(xù)向前探索，路徑不可通時(shí)沿原路返回改變探索方向，輸出最終探索結(jié)果。其關(guān)系如圖3.1 所示。</p><p>　　圖3.1 迷宮路徑探索功能結(jié)構(gòu)</p><p><b>　　4.詳細(xì)設(shè)計(jì)</b></p><p>　　4.1迷宮數(shù)據(jù)的存

19、儲(chǔ)</p><p>　　Maze是指向指針的指針，用行h和列l(wèi)來(lái)存儲(chǔ)迷宮的大小，使用malloc申請(qǐng)一個(gè)二維數(shù)組，根據(jù)用戶輸入的障礙坐標(biāo)在maze數(shù)組的相應(yīng)位置存入1作為障礙標(biāo)記，直到用戶輸入0 0結(jié)束障礙的設(shè)置。該模塊的執(zhí)行過(guò)程如圖4.1 所示。</p><p>　　圖4.1 迷宮數(shù)據(jù)的存儲(chǔ)</p><p>　　4.2當(dāng)前位置可通性的判斷及探索方向的改變</

20、p><p>　　當(dāng)前位置curpos的坐標(biāo)在maze數(shù)組中對(duì)應(yīng)位置儲(chǔ)存的數(shù)據(jù)若非1和8即為可通在此留下足跡，由變量di來(lái)記錄下一個(gè)探索方向，把下一個(gè)位置作為當(dāng)前位置并繼續(xù)探索，若當(dāng)前位置不可通，則后退一步按順時(shí)針?lè)较蚋淖兲剿鞣较颉２僮髁鞒倘鐖D4.2所示。</p><p>　　圖4.2 可通性的判斷及探索方向的改變</p><p>　　4.3無(wú)通路時(shí)沿原路返回</p

21、><p>　　借助棧先入后出的特性，把探索過(guò)的路徑信息e壓入棧s中。若當(dāng)前位置curpos的下一個(gè)探索方向的變量值di為4時(shí)，表示當(dāng)前位置周?chē)膫€(gè)方向均無(wú)通道，沿原路退回一步將路徑信息e逐個(gè)出棧，一退直到di<4，改變方向繼續(xù)探索。該模塊的執(zhí)行過(guò)程如圖4.3所示。</p><p>　　圖4.3 無(wú)通路時(shí)沿原路返回</p><p>　　4.4路徑信息入棧和出棧<

22、;/p><p>　　當(dāng)前位置curpos可通時(shí)maze數(shù)組中的對(duì)應(yīng)位置留下足跡，標(biāo)記下一個(gè)探索方向，若棧s滿則追加?？臻g，路徑信息入e棧*s.top=e，s.top++。若當(dāng)前位置不可通且棧不為空則后退一步，路徑信息e出棧e=*--s.top并改變探索方向。程序的操作流程如圖4.4所示。</p><p>　　圖4.4路徑信息入棧和出棧</p><p>　　4.5 當(dāng)前探

23、索位置的切換</p><p>　　利用二維數(shù)組來(lái)確定當(dāng)前探索位置curpos。方向變量e.di的數(shù)值為1時(shí)，則橫坐標(biāo)加1；e.di的數(shù)值為2時(shí)，則縱坐標(biāo)加1；e.di的數(shù)值為3時(shí)，則橫坐標(biāo)減1；e.di的數(shù)值為4時(shí)，則縱坐標(biāo)減1。程序的操作流程如圖4.5所示。</p><p>　　圖4.5當(dāng)前探索位置的切換</p><p>　　4.6最終探索路徑的輸出及標(biāo)記<

24、/p><p>　　迷宮探索結(jié)束時(shí)若找不到出口則輸出尋找不到路徑。若成功找到出口則根據(jù)棧s儲(chǔ)存的路徑坐標(biāo)信息e在迷宮數(shù)據(jù)maze數(shù)組的相應(yīng)位置標(biāo)記2。程序的操作流程如圖4.6所示。</p><p>　　圖4.6最終探索路徑的輸出及標(biāo)記</p><p><b>　　4.7打印迷宮信息</b></p><p>　　根據(jù)棧s儲(chǔ)存的路

25、徑坐標(biāo)信息在迷宮數(shù)據(jù)maze[x][x]的不同輸出不同的符號(hào)，分別表示迷宮的障礙和走出迷宮的路徑。程序的操作流程如圖4.7所示。</p><p>　　圖4.7打印迷宮信息</p><p><b>　　5.程序代碼</b></p><p>　　5.1文件包含和結(jié)構(gòu)體的定義</p><p>　　#include<std

26、io.h></p><p>　　#include<malloc.h></p><p>　　#include<stdlib.h></p><p>　　#define STACK_INIT_SIZE 10</p><p>　　int h,l;//保存迷宮大小的行數(shù)和列數(shù)</p><p>　　t

27、ypedef struct{</p><p><b>　　int x;</b></p><p><b>　　int y;</b></p><p>　　}point;//定義坐標(biāo)變量結(jié)構(gòu)體</p><p>　　typedef struct{</p><p>　　point po

28、s;//保存當(dāng)前路徑的坐標(biāo)</p><p>　　int di;//保存下一個(gè)探索方向的標(biāo)記值</p><p>　　}selemtype;//定義路徑信息結(jié)構(gòu)體</p><p>　　typedef struct{</p><p>　　selemtype *base;//棧頂</p><p>　　selemtype *to

29、p;//棧底</p><p>　　int stacksize;//棧的容量</p><p>　　}sqstack;//棧的定義</p><p>　　point start,end;//迷宮出入口的聲明</p><p>　　5.2棧的初始化及入棧出棧函數(shù)</p><p><b>　　//棧的初始化</b&

30、gt;</p><p>　　int initstack(sqstack &s){</p><p><b>　　//申請(qǐng)棧的空間</b></p><p>　　s.base=(selemtype *)malloc(STACK_INIT_SIZE*sizeof(selemtype));</p><p>　　if(!s.

31、base)//判斷棧是否申請(qǐng)成功</p><p><b>　　exit(-2);</b></p><p>　　s.top=s.base;//使棧為空</p><p>　　s.stacksize=STACK_INIT_SIZE;//給棧的容量賦值</p><p><b>　　return 1;</b>

32、</p><p><b>　　}</b></p><p><b>　　//入棧函數(shù)</b></p><p>　　int push(sqstack &s,selemtype e){</p><p>　　if(s.top-s.base>=s.stacksize)//判斷棧是否已滿</

33、p><p><b>　　{</b></p><p>　　s.base=(selemtype *)realloc(s.base,(s.stacksize+10)*sizeof(selemtype));//棧滿時(shí)追加申請(qǐng)空間</p><p>　　if(!s.base) exit(0);</p><p>　　s.top=s.bas

34、e+s.stacksize;</p><p>　　s.stacksize+=10;}</p><p>　　*s.top=e;//元素入棧</p><p><b>　　s.top++;</b></p><p><b>　　return 1;</b></p><p><b&

35、gt;　　}</b></p><p><b>　　//出棧函數(shù)</b></p><p>　　int pop(sqstack &s,selemtype &e){</p><p>　　//棧不為空時(shí)元素出棧</p><p>　　if(s.top==s.base)exit(0);</p>

36、<p>　　e=*--s.top;</p><p><b>　　return 1;</b></p><p><b>　　}</b></p><p>　　5.3申請(qǐng)迷宮大小及障礙的設(shè)置</p><p><b>　　//迷宮大小初始化</b></p>&

37、lt;p>　　int **initmaze()</p><p><b>　　{</b></p><p>　　int **maze;//指向二維數(shù)組的指針</p><p>　　printf("設(shè)置迷宮的行和列(如3 3)");</p><p>　　scanf("%d%d",&

38、amp;h,&l);</p><p>　　//用malloc函數(shù)動(dòng)態(tài)申請(qǐng)一個(gè)二維數(shù)組</p><p>　　maze=(int**)malloc(sizeof(int)*h);</p><p>　　for(int i=0;i<h;i++)</p><p>　　maze[i]=(int*)malloc(sizeof(int)*l);

39、</p><p>　　return maze;</p><p><b>　　}</b></p><p>　　//迷宮障礙設(shè)置函數(shù)</p><p>　　void setza(int **maze)</p><p><b>　　{</b></p><p>

40、<b>　　char n,m;</b></p><p><b>　　int x,y;</b></p><p>　　printf("設(shè)置入口的坐標(biāo)(如1 1)");</p><p>　　scanf("%d%d",&y,&x);//設(shè)置入口坐標(biāo)</p>&l

41、t;p>　　while(!((y==h||y==1||x==l||x==1)&&(x<=l&&y<=h)&&(x!=0&&y!=0))){</p><p>　　printf("請(qǐng)把入口設(shè)置在迷宮的邊緣\n");</p><p>　　scanf("%d%d",&y

42、,&x);//設(shè)置入口坐標(biāo)</p><p><b>　　}</b></p><p>　　start.x=x-1;start.y=y-1;</p><p>　　printf("設(shè)置出口的坐標(biāo)(如2 3)");</p><p>　　scanf("%d%d",&y,&am

43、p;x);//設(shè)置出口坐標(biāo)</p><p>　　while(!((y==h||y==1||x==l||x==1)&&(x<=l&&y<=h)&&(x!=0&&y!=0)&&!(y==start.y+1&&x==start.x+1))){</p><p>　　printf("

44、請(qǐng)把出口設(shè)置在迷宮的邊緣,不要與入口重合\n");</p><p>　　scanf("%d%d",&y,&x);//設(shè)置出口坐標(biāo)</p><p><b>　　}</b></p><p>　　end.x=x-1;end.y=y-1;</p><p>　　printf("

45、;設(shè)置障礙的坐標(biāo)\n");</p><p>　　scanf("%d%d",&n,&m);//設(shè)置障礙坐標(biāo)</p><p>　　//當(dāng)輸入# #時(shí)結(jié)束障礙設(shè)置</p><p>　　while(!(n==0&&m==0)){</p><p>　　maze[n-1][m-1]=1;<

46、;/p><p>　　scanf("%d%d",&n,&m);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　5.4通道可通性測(cè)試</p><p>　　//當(dāng)前位置可通性測(cè)試</p>

47、;<p>　　int pass(int **maze,point curpos)</p><p><b>　　{</b></p><p>　　//根據(jù)maze二維數(shù)組儲(chǔ)存的數(shù)值判斷當(dāng)前位置是否可通</p><p>　　if(maze[curpos.y][curpos.x]!=1&&maze[curpos.y][cu

48、rpos.x]!=8){</p><p>　　return (true);</p><p><b>　　}</b></p><p>　　else return(false);</p><p><b>　　}</b></p><p>　　5.5為走過(guò)的通道留下足跡</p&

49、gt;<p><b>　　//留下足跡</b></p><p>　　void footprint(int **maze,point curpos)</p><p><b>　　{</b></p><p>　　maze[curpos.y][curpos.x]=8;</p><p><

50、;b>　　}</b></p><p>　　5.6探索位置的切換</p><p>　　//當(dāng)前探索位置到下一個(gè)探索位置坐標(biāo)的切換</p><p>　　point nextpos(point curpos,int a)</p><p><b>　　{</b></p><p>　　sw

51、itch(a){</p><p>　　case 1://向右移動(dòng)</p><p>　　if(curpos.x<l-1)curpos.x++;</p><p><b>　　break;</b></p><p>　　case 2://向下移動(dòng)</p><p>　　if(curpos.y<h

52、-1)curpos.y++;</p><p><b>　　break;</b></p><p>　　case 3://向左移動(dòng)</p><p>　　if(curpos.x>0)curpos.x--;</p><p><b>　　break;</b></p><p>　　

53、case 4://向上移動(dòng)</p><p>　　if(curpos.y>0)curpos.y--;</p><p><b>　　break;</b></p><p><b>　　}</b></p><p>　　return curpos;</p><p><b&g

54、t;　　}</b></p><p>　　5.7入口到出口的路徑探索</p><p><b>　　//路徑探索函數(shù)</b></p><p>　　int mazepath(int **maze,point start,point end,sqstack &s,selemtype e)</p><p>&l

55、t;b>　　{</b></p><p>　　initstack(s);//棧的初始化為路徑信息入棧做準(zhǔn)備</p><p>　　point curpos=start;//把迷宮入口作為探索的起始位置</p><p><b>　　do{</b></p><p>　　if(pass(maze,curpos))

56、{</p><p>　　footprint(maze,curpos);//若當(dāng)前位置可通，則留下足跡</p><p>　　e.pos=curpos;//把當(dāng)前位置的坐標(biāo)賦值給路徑信息元素e.pos</p><p>　　e.di=1;//標(biāo)記下一個(gè)探索位置的方向</p><p>　　push(s,e);//當(dāng)前路徑信息入棧</p>

57、<p>　　//若當(dāng)前位置為迷宮出口則返回true結(jié)束探索</p><p>　　if(curpos.x==end.x&&curpos.y==end.y)</p><p>　　return (true);</p><p>　　curpos=nextpos(curpos,e.di);//切換當(dāng)前位置繼續(xù)判斷可通性</p><

58、;p><b>　　}</b></p><p>　　else{//當(dāng)前位置不可通</p><p>　　if(s.top!=s.base){//棧不為空</p><p>　　pop(s,e);//路徑信息出棧</p><p>　　while(e.di==4&&s.top!=s.base){</p&

59、gt;<p>　　//退回一步后，檢查一下個(gè)探索位置的方向標(biāo)記值</p><p>　　//若e.di=4且棧不為空，則將路徑信息元素不斷出棧，</p><p>　　//直到e.di小于4為止</p><p><b>　　pop(s,e);</b></p><p><b>　　}</b>

60、</p><p>　　if(e.di<4){//若當(dāng)前位置標(biāo)記的下一個(gè)探索方向的值小于4</p><p>　　e.di++;//e.di自增改變探索方向</p><p>　　push(s,e);//改變下一個(gè)探索方向后將元素信息再次入棧</p><p>　　curpos=nextpos(e.pos ,e.di);//切換當(dāng)前位置繼續(xù)判斷

61、可通性}</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　}while(s.top!=s.base);//若棧不為空則繼續(xù)執(zhí)行路徑探索循環(huán)</p><p>　　return (false);//尋找不到路徑返回false</p>

62、<p><b>　　}</b></p><p><b>　　5.8打印迷宮信息</b></p><p><b>　　//打印迷宮信息</b></p><p>　　void printmaze(int **maze)</p><p><b>　　{<

63、/b></p><p><b>　　int k;</b></p><p>　　char b=1;//把迷宮障礙和最終路徑分別標(biāo)記為a和b兩種字符</p><p>　　//逐行輸出迷宮信息</p><p>　　for(k=0;k<l+2;k++){</p><p>　　if((start

64、.y==0&&start.x+1==k)||(end.y==0&&end.x+1==k))</p><p>　　printf("- ");</p><p>　　else printf("█");</p><p><b>　　}</b></p><p>

65、;　　printf("\n");</p><p>　　for(int i=0;i<h;i++){</p><p>　　if((start.x==0&&start.y==i&&start.y!=0&&start.y!=h-1)||(end.x==0&&end.y==i&&end.y!=0

66、&&end.y!=h-1))</p><p>　　printf("- ");</p><p>　　else printf("█");</p><p>　　for(int j=0;j<l;j++){</p><p>　　if(maze[i][j]==1)//maze[x][x]的值為

67、1則輸出方塊</p><p>　　printf("■");</p><p>　　else if(maze[i][j]==2)//否則maze[x][x]的值為2則輸出b字符</p><p>　　printf("%c ",b);</p><p><b>　　else</b></

68、p><p>　　printf(" ");//maze[x][x]的值為不為1也不為2則輸出空格</p><p><b>　　}</b></p><p>　　if((start.x==l-1&&start.y==i&&start.y!=0&&start.y!=h-1)||(en

69、d.x==l-1&&end.y==i&&end.y!=0&&end.y!=h-1))</p><p>　　printf("- ");</p><p>　　else printf("█");</p><p>　　printf("\n");</p>

70、<p><b>　　}</b></p><p>　　for(k=0;k<l+2;k++){</p><p>　　if((start.y+1==h&&start.x+1==k)||(end.y+1==h&&end.x+1==k))</p><p>　　printf("- ");&

71、lt;/p><p>　　else printf("█");</p><p><b>　　}</b></p><p>　　printf("\n");</p><p><b>　　}</b></p><p><b>　　5.9主函數(shù)&

72、lt;/b></p><p>　　void main()</p><p><b>　　{</b></p><p>　　sqstack s;//棧的聲明</p><p>　　selemtype e;//路徑信息元素聲明</p><p>　　int **maze;//指向迷宮信息的指針聲明<

73、;/p><p>　　bool flag=1;//程序循環(huán)使用的旗幟</p><p>　　while(flag){</p><p>　　printf(" 尋找迷宮的出口\n");</p><p>　　printf(" ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

74、~~~~~~~~~~~~~~~~\n");</p><p>　　printf(" * *\n");</p><p>　　printf(" * 程序使用說(shuō)明: *

75、\n");</p><p>　　printf(" * *\n");</p><p>　　printf(" * 輸入橫縱坐標(biāo)請(qǐng)用整數(shù),并用空格將其分開(kāi) *\n");</p><p&g

76、t;　　printf(" * *\n");</p><p>　　printf(" * 障礙物的設(shè)置以0 0作為結(jié)束標(biāo)志 *\n");</p><p>　　printf("

77、 * *\n");</p><p>　　printf(" * 歡迎使用! *\n");</p><p>　　printf(" *

78、 *\n");</p><p>　　printf(" ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");</p><p>　　maze=initmaze();//迷宮大小初始化</p><

79、p>　　setza(maze,start,end);//迷宮障礙和出入口的設(shè)置</p><p>　　printf("開(kāi)始尋找出路?(entrt)\n");</p><p>　　getchar();//程序暫停</p><p>　　getchar();</p><p>　　system("cls")

80、;//清屏</p><p><b>　　//打印迷宮信息</b></p><p>　　printf("迷宮大小為%d行%d列\(zhòng)n",h,l);</p><p>　　printf("入口坐標(biāo)為:%d,%d",start.y+1,start.x+1);</p><p>　　printf

81、("出口坐標(biāo)為:%d,%d\n",end.y+1,end.x+1);</p><p>　　printf("設(shè)置的迷宮如下圖所示:\n");</p><p>　　printmaze(maze);</p><p>　　//當(dāng)成功探索到路徑是輸出路徑</p><p>　　if(mazepath(maze,s,

82、e)==true){</p><p>　　printf("從出口到入口的路徑坐標(biāo)依次為:\n");</p><p>　　//當(dāng)棧不為空時(shí)把探索到的路徑信息依次出棧</p><p>　　while(s.top!=s.base){</p><p><b>　　pop(s,e);</b></p>

83、<p>　　maze[e.pos.y][e.pos.x]=2;//在maze數(shù)組的對(duì)應(yīng)數(shù)據(jù)為最終路徑標(biāo)記記號(hào)</p><p>　　printf("(%d,%d)",e.pos.y+1,e.pos.x+1);//輸出路徑坐標(biāo)</p><p><b>　　}</b></p><p>　　printf("\

84、n");</p><p>　　printf("迷宮出路如下圖所示:\n");</p><p>　　printmaze(maze);//打印迷宮信息及最終探索到的路徑</p><p><b>　　}</b></p><p>　　else printf("尋找不到路徑\n")

85、;</p><p>　　printf("繼續(xù)請(qǐng)按1,退出請(qǐng)按0.\n選擇:");</p><p>　　scanf("%d",&flag);//選擇是否繼續(xù)使用該程序</p><p>　　system("cls");</p><p><b>　　}</b>

86、</p><p><b>　　}</b></p><p><b>　　6.程序測(cè)試</b></p><p>　　設(shè)置4行4列的迷宮，設(shè)置迷宮入口不在邊緣上提示出錯(cuò)，設(shè)置出口坐標(biāo)與入口重合提示出錯(cuò)。迷宮草圖如圖6.1所示。程序運(yùn)行圖如圖6.2設(shè)置4行列迷宮數(shù)據(jù)及6.3尋找不到路徑探索結(jié)果所示。</p><

87、p>　　圖6.1 4行4列的迷宮示意圖</p><p>　　圖6.2 設(shè)置4行4列迷宮數(shù)據(jù)</p><p>　　圖6.3尋找不到路徑的探索結(jié)果</p><p>　　設(shè)置8行8列的迷宮使其入口在1 1,出口在8 8的位置根據(jù)迷宮草圖6.4所示設(shè)置障礙。</p><p>　　圖6.4 8行8列的迷宮示意圖</p><p&

88、gt;　　在程序中設(shè)置出入口和障礙坐標(biāo)如圖6.5所示</p><p>　　圖6.5設(shè)置8行8列的迷宮</p><p>　　成功探索到迷宮路徑的結(jié)果如圖6.6所示</p><p>　　圖6.6成功探索到迷宮路徑的結(jié)果</p><p><b>　　總 結(jié)</b></p><p>　　這是我第二次做課程

89、設(shè)計(jì)，之前的設(shè)計(jì)經(jīng)驗(yàn)讓我有了下手的方向和技巧，使用模塊化的編程不僅使代碼清晰易讀也使程序的調(diào)試方便了許多。迷宮問(wèn)題求解這個(gè)程序的最大問(wèn)題是尋找迷宮路徑遇到障礙時(shí)改變方向和走入死胡同時(shí)往后退。</p><p>　　程序從整體構(gòu)思到算法設(shè)計(jì)以及編寫(xiě)，調(diào)試歷經(jīng)了種種困難和考驗(yàn)，通過(guò)查看資料與同學(xué)討論總結(jié)得到了一些問(wèn)題的解決方案；總結(jié)了一些常見(jiàn)問(wèn)題的解決方法其中包括一些相對(duì)合理而簡(jiǎn)單程序算法。在這次課程設(shè)計(jì)當(dāng)中讓我在之前

90、所學(xué)的c和數(shù)據(jù)結(jié)構(gòu)知識(shí)得到了鞏固也提高了綜合應(yīng)用能力。鍛煉了自己的實(shí)踐能力和耐心，程序中的每一處錯(cuò)誤都要細(xì)心去分析修改，我從中也得到了許多課堂之外的東西更進(jìn)一步體會(huì)到親自實(shí)踐和光看著書(shū)本學(xué)習(xí)的不同效果。 </p><p>　　通過(guò)這次課程設(shè)計(jì)，我也發(fā)現(xiàn)了自身的很多不足之處，在以后的學(xué)習(xí)中，我會(huì)不斷的完善自我，不斷進(jìn)取，能使自己在程序設(shè)計(jì)方面有所發(fā)展。</p><p><b>