數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-迷宮求解

1、<p>　　院 系： 網(wǎng)絡(luò)工程 </p><p>　　班 級(jí)： 網(wǎng)絡(luò)09 – 1班 </p><p>　　姓 名： </p><p>　　合 作 者： </p><p>　　指導(dǎo)教師： </p><p&g

2、t;　　2010 年 12 月 20 日</p><p>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)任務(wù)書</p><p>　　一、題目： 迷宮求解</p><p><b>　　二、設(shè)計(jì)要求</b></p><p>　　（1）李斌（組長(zhǎng)）、尚賀和張雪城組成設(shè)計(jì)小組。</p><p>　　（2）小組成員分工協(xié)作完成。要求

3、每個(gè)成員有自己相對(duì)獨(dú)立的模塊，同時(shí)要了解其他組員完成的內(nèi)容。</p><p>　?。?）查閱相關(guān)資料，自學(xué)具體課題中涉及到的新知識(shí)。</p><p>　?。?）采用結(jié)構(gòu)化、模塊化程序設(shè)計(jì)方法設(shè)計(jì)，功能要完善，界面美觀。</p><p>　?。?）所設(shè)計(jì)的系統(tǒng)要至少應(yīng)用一個(gè)課程中或者與其密切相關(guān)的算法。</p><p>　?。?）按要求寫出課程

4、設(shè)計(jì)報(bào)告。其主要內(nèi)容包括：封皮、課程設(shè)計(jì)任務(wù)書，指導(dǎo)教師評(píng)語與成績(jī)、目錄、概述、軟件總體設(shè)計(jì)、詳細(xì)設(shè)計(jì)、軟件的調(diào)試、總結(jié)、附錄：帶中文注釋的程序清單、參考文獻(xiàn)。報(bào)告一律用A4紙打印，中文字體為宋體，西文字體用Time New Roma，一律用小四號(hào)字，行距采用“固定值”18磅，首行縮進(jìn)2字符?？傮w設(shè)計(jì)應(yīng)配合軟件總體模塊結(jié)構(gòu)圖來說明軟件應(yīng)具有的功能。詳細(xì)設(shè)計(jì)闡述本人設(shè)計(jì)模塊部分的設(shè)計(jì)思想、應(yīng)用到的理論和算法、程序流程等等，調(diào)試的敘述應(yīng)配合

5、出錯(cuò)場(chǎng)景的抓圖來說明出現(xiàn)了哪些錯(cuò)誤，如何解決的。</p><p>　?。?）課程設(shè)計(jì)報(bào)告中的軟件總體設(shè)計(jì)、詳細(xì)設(shè)計(jì)、軟件的調(diào)試等主體內(nèi)容要以文字描述、圖表等形式為主，可配以主要核心代碼，在附錄中附程序清單。</p><p><b>　　三、課程設(shè)計(jì)工作量</b></p><p>　　由于是設(shè)計(jì)小組團(tuán)結(jié)協(xié)作完成設(shè)計(jì)任務(wù)，一般每人的程序量在200行

6、有效程序行左右，不得抄襲。</p><p>　　四、課程設(shè)計(jì)工作計(jì)劃</p><p>　　2010年12月20日，指導(dǎo)教師講課，學(xué)生根據(jù)題目準(zhǔn)備資料；</p><p>　　2010年12月21日，設(shè)計(jì)小組進(jìn)行總體方案設(shè)計(jì)和任務(wù)分工；</p><p>　　2010年12月22日～2010年12月27日，每人完成自己承擔(dān)的程序模塊并通過獨(dú)立編譯；

7、</p><p>　　2010年12月28日～2009年12月30日，將各模塊集成為一個(gè)完整的系統(tǒng)，并錄入足夠的數(shù)據(jù)進(jìn)行調(diào)試運(yùn)行；</p><p>　　2010年12月31日，驗(yàn)收、開始撰寫報(bào)告；</p><p>　　2011年01月4日前，提交課程設(shè)計(jì)報(bào)告。</p><p>　　指導(dǎo)教師簽章： </p>

8、;<p>　　教研室主任簽章 </p><p>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)指導(dǎo)教師評(píng)語與成績(jī)</p><p><b>　　目 錄</b></p><p><b>　　第1章 概述5</b></p><p>　　1.1 性能需求5</p>&

9、lt;p>　　1.2 功能需求5</p><p>　　第2章 概要設(shè)計(jì)6</p><p>　　2.1 功能模塊設(shè)計(jì)6</p><p>　　2.2 算法分析與設(shè)計(jì)7</p><p>　　第3章 詳細(xì)設(shè)計(jì)8</p><p>　　3.1 迷宮求解功能模塊設(shè)計(jì)8</p><p>　　3

10、.2 文件的存取模塊設(shè)計(jì)8</p><p>　　第4章 調(diào)試分析與測(cè)試結(jié)果10</p><p>　　4.1 調(diào)試分析10</p><p>　　4.2 測(cè)試結(jié)果10</p><p><b>　　第5章 總結(jié)13</b></p><p><b>　　參考文獻(xiàn)14</b>

11、;</p><p><b>　　附錄15</b></p><p><b>　　第1章 概述</b></p><p><b>　　1.1 性能需求</b></p><p>　　隨著社會(huì)經(jīng)濟(jì)和人們物質(zhì)生活的不斷提高，人們對(duì)精神生活的需求也越來越高，在現(xiàn)今社會(huì)里，人們對(duì)諸如智商、情

12、商等的重視無疑反映了對(duì)精神生活的態(tài)度。當(dāng)然具體到我們每個(gè)人來說，想必大多數(shù)人小時(shí)候都曾玩過魔方、迷宮吧。作為這種智力游戲，人們是百玩不厭的。正是鑒于這種需求，本設(shè)計(jì)應(yīng)用計(jì)算機(jī)語言及其算法，將人的意志賦予機(jī)器實(shí)現(xiàn)，使人們不必再陷于枯燥的重復(fù)勞動(dòng)，從而將更多的精力投入到對(duì)未知領(lǐng)域的探索上。</p><p><b>　　1.2 功能需求</b></p><p>　　本設(shè)計(jì)的

13、關(guān)鍵在于將人的想法自能化，由所編軟件自動(dòng)的搜索可行路徑。因此，軟件必須擁有自動(dòng)搜索并記錄可行路徑的功能，除此之外，軟件還應(yīng)設(shè)置人機(jī)交互接口，以便能夠人為的建立迷宮圖；軟件要能保存以輸入的迷宮圖，并能調(diào)取外部現(xiàn)有的迷宮圖；當(dāng)然對(duì)于迷宮問題還有很多要考慮的地方，比如由用戶自己來探索可行路徑，但由于本設(shè)計(jì)側(cè)重于迷宮求解的算法設(shè)計(jì)，并非以游戲的形式為初衷，定有不全之處。</p><p><b>　　第2章 概要

14、設(shè)計(jì)</b></p><p>　　2.1 功能模塊設(shè)計(jì)</p><p>　　本設(shè)計(jì)主要分為個(gè)模塊：初始化棧模塊、迷宮建立模塊、迷宮求解模塊、文件的保存與調(diào)取模塊。</p><p>　　初始化棧模塊，由InitStack(SqStack &S)、Push(SqStack &S,SElemType e)、Pop(SqStack &S,

15、SElemType &e)、StackEmpty(SqStack S)函數(shù)構(gòu)成，此模塊是解決問題的關(guān)鍵算法，貫穿整個(gè)設(shè)計(jì)的始終。</p><p>　　迷宮建立模塊，由initmaze(int maze[M][N])構(gòu)成，此模塊用于用戶自己設(shè)計(jì)并建立迷宮。</p><p>　　迷宮求解模塊：由MazePath(PostType start,PostType end,int maze[

16、M][N],int diradd[4][2])構(gòu)成，此模塊是基于棧的特點(diǎn)與迷宮實(shí)際相結(jié)合來實(shí)現(xiàn)的。</p><p>　　文件的保存與調(diào)取模塊：由File_Save(int maze[][50],int x,int y)、File_Get(int maze[M][N])構(gòu)成，此模塊用來存儲(chǔ)用戶建立的迷宮，并方便其調(diào)取外部的現(xiàn)有迷宮。</p><p><b>　　流程圖如下：<

17、/b></p><p>　　2.2 算法分析與設(shè)計(jì)</p><p>　　棧：假設(shè)棧S=(a1,a2,…,an),則稱a1為棧底元素，an為棧頂元素。棧中元素按a1,a2,…,an的次序進(jìn)棧，退棧的第一個(gè)元素為棧頂元素。換句話說，棧的修改是按后進(jìn)先出的原則進(jìn)行的。因此，棧又稱為后進(jìn)先出的線性表。</p><p>　　由于計(jì)算機(jī)解謎宮時(shí)，通常用的是“窮舉求解”的方

18、法，即從入口出發(fā)，順某一方向向前探索，若能走通，則繼續(xù)往前走；否則沿原路退回，換一個(gè)方向再繼續(xù)探索，直至所有可能的通路都探索到為止。為了保證在任何位置上都能沿原路退回，顯然需要用一個(gè)后進(jìn)先出的結(jié)構(gòu)來保存從入口到當(dāng)前位置的路徑。因此，在求迷宮通路的算法中應(yīng)用“?！币簿褪亲匀欢坏氖铝?。</p><p>　　首先，迷宮圖用方塊表示，每個(gè)方塊或?yàn)橥ǖ溃驗(yàn)閴?。所求路徑必須是?jiǎn)單路徑，即在求得的路徑上不能重復(fù)出現(xiàn)同一通道

19、塊。</p><p>　　假設(shè)“當(dāng)前位置”指的是“在搜索過程中某一時(shí)刻所在圖中某個(gè)方塊位置”，則求迷宮中一條路徑的算法的基本思想是：若當(dāng)前位置“可通”，則納入“當(dāng)前路徑”，并繼續(xù)朝“下一位置”探索，即切換“下一位置”為“當(dāng)前位置”，如此重復(fù)直至到達(dá)出口；若當(dāng)前位置“不可通”，則應(yīng)順著“來向”退回到“前一通道塊”，然后朝著除“來向”之外的其他方向繼續(xù)探索；若該通道塊的四周4個(gè)方塊均“不可通”，則應(yīng)從“當(dāng)前路徑”上刪

20、除該通道塊。所謂“下一位置”指的是“當(dāng)前位置”四周4個(gè)方向（東、南、西、北）上相鄰的方塊。假設(shè)以棧S記錄“當(dāng)前路徑”，則棧頂中存放的是“當(dāng)前路徑”上最后一個(gè)通道塊。由此，“納入路徑”的操作即為“當(dāng)前位置入?！保弧皬漠?dāng)前路徑上刪除前一通道塊”的操作即為“出?！?。</p><p>　　其中需要說明的是，所謂當(dāng)前位置可通，指的是未曾走到過的通道塊，即要求該方塊位置不僅是通道塊，而且既不在當(dāng)前路徑上（否則所求路徑就不是簡(jiǎn)

21、單路徑），也不是曾經(jīng)納入路徑的通道塊（否則只能在死胡同內(nèi)轉(zhuǎn)圈）。</p><p>　　此軟件的主要實(shí)現(xiàn)均是按照上述分析設(shè)計(jì)而成。</p><p><b>　　第3章 詳細(xì)設(shè)計(jì)</b></p><p>　　3.1 迷宮求解功能模塊設(shè)計(jì)</p><p>　　此模塊主要由函數(shù)MazePath(PostType start,Po

22、stType end,int maze[M][N],int diradd[4][2])來實(shí)現(xiàn)，當(dāng)然此功能實(shí)現(xiàn)主要基于對(duì)棧的操作。</p><p>　　模塊用：typedef struct</p><p><b>　　{</b></p><p><b>　　int x;</b></p><p><

23、;b>　　int y;</b></p><p>　　}PostType;</p><p>　　typedef struct</p><p><b>　　{</b></p><p><b>　　int x,y;</b></p><p>　　int d;/*&q

24、uot;1"表示右，"2"表示下，"3"表示左，"4"表示上*/</p><p>　　}SElemType;</p><p>　　來表示坐標(biāo)類型及迷宮中每一方塊的屬性（包括坐標(biāo)、下一步的方向），用1和0分別表示墻和通路并用二維數(shù)組存儲(chǔ)，從而將實(shí)際問題轉(zhuǎn)化成數(shù)學(xué)模型，方便程序的設(shè)計(jì)，以實(shí)現(xiàn)其自能化。</p>

25、<p>　　具體的程序?qū)崿F(xiàn)可參見附錄。</p><p>　　3.2 文件的存取模塊設(shè)計(jì)</p><p>　　此模塊由File_Save(int maze[][50],int x,int y)、File_Get(int maze[M][N])來實(shí)現(xiàn)，此功能主要是對(duì)文件的操作。</p><p>　　其中FILE *fp;是對(duì)文件指針的定義，if((fp = f

26、open(str,"w"))==NULL)return;和if((fp=fopen(str,"rb"))==NULL)return;分別是以寫和讀的方式打開文件，以便對(duì)文件進(jìn)行相應(yīng)的操作，最后以fclose(fp);來關(guān)閉文件。</p><p>　　以向文件中寫數(shù)據(jù)為例的部分程序?qū)崿F(xiàn)如下：</p><p><b>　　FILE *fp;&l

27、t;/b></p><p><b>　　int i,j;</b></p><p>　　char str[]="";</p><p>　　cout<<"Input the file name:";</p><p><b>　　cin>>str;

28、</b></p><p>　　if((fp = fopen(str,"w"))==NULL)</p><p><b>　　return;</b></p><p>　　fprintf(fp,"%d ",x);</p><p>　　fprintf(fp,"%d &

29、quot;,y);</p><p>　　fprintf(fp,"\n");</p><p>　　for(i = 0;i < x;i ++)</p><p><b>　　{</b></p><p>　　for(j = 0;j < y;j ++)</p><p>　　f

30、printf(fp,"%d ",maze[i][j]);</p><p>　　fprintf(fp,"\n");</p><p><b>　　}</b></p><p>　　fclose(fp);</p><p>　　具體功能的程序?qū)崿F(xiàn)可參見附錄。(文件存儲(chǔ)流程圖如下)</p

31、><p>　　第4章 調(diào)試分析與測(cè)試結(jié)果</p><p><b>　　4.1 調(diào)試分析</b></p><p>　　1. 迷宮求解模塊：此模塊的調(diào)試主要在于迷宮中每個(gè)方塊出棧入棧的時(shí)機(jī)及對(duì)棧本身的操作。</p><p>　　2. 文件的存取模塊：此模塊的調(diào)試主要在于對(duì)文件輸入、輸出操作及文件打開不成功時(shí)的應(yīng)對(duì)。</p&

32、gt;<p><b>　　4.2 測(cè)試結(jié)果</b></p><p>　　1．迷宮求解模塊：根據(jù)調(diào)試分析進(jìn)行測(cè)試</p><p>　　預(yù)期結(jié)果：程序能夠自動(dòng)搜索下一步的方向，并能記錄已經(jīng)走過的方向。</p><p>　　實(shí)際測(cè)試結(jié)果：程序只能沿著固定的方向搜索，而不能退回到該方塊繼續(xù)從其他方向開始搜索。</p><

33、;p>　　程序部分代碼如下：while(!StackEmpty(S1)) //*棧不為空 有路徑可走*/ </p><p><b>　　{ </b></p><p>　　Pop(S1,elem); </p><p>　　i=elem.x; </p><p>　　j=elem.y; </p><p

34、>　　while(d<4) //*試探東南西北各個(gè)方向*/ </p><p><b>　　{ </b></p><p>　　a=i+diradd[d][0]; </p><p>　　b=j+diradd[d][1]; </p><p>　　if(a==end.x && b==end.y &am

35、p;& maze[a][b]==0) //*如果到了出口*/ </p><p><b>　　{ </b></p><p>　　elem.x=i; </p><p>　　elem.y=j; </p><p>　　elem.d=d; </p><p>　　Push(S1,elem); <

36、/p><p>　　elem.x=a; </p><p>　　elem.y=b; </p><p>　　elem.d=886; //*方向輸出為-1 判斷是否到了出口*/ </p><p>　　Push(S1,elem); </p><p>　　printf("\n0=右 1=下 2=左 3=上 886為走出迷宮\

37、n\n通路為:(行坐標(biāo),列坐標(biāo),方向)\n");</p><p>　　更正：在代碼Pop(S1,elem); </p><p>　　i=elem.x; </p><p>　　j=elem.y; </p><p>　　后加一條語句：d=elem.d+1; //*下一個(gè)方向 */</p><p>　　更正后實(shí)際運(yùn)

38、行結(jié)果圖如下：</p><p>　　此結(jié)果與預(yù)期結(jié)果一致。</p><p>　　2. 文件的存取模塊：根據(jù)調(diào)試分析進(jìn)行測(cè)試</p><p>　　預(yù)期結(jié)果：可從外部文件中調(diào)取數(shù)據(jù)。</p><p>　　實(shí)際測(cè)試結(jié)果：調(diào)取數(shù)據(jù)時(shí)產(chǎn)生混亂。</p><p><b>　　部分程序代碼如下：</b><

39、/p><p><b>　　FILE *fp;</b></p><p>　　int i,j,pos[2];</p><p>　　char str[]="";</p><p>　　cout<<"Input the file name:";</p><p>

40、;<b>　　cin>>str;</b></p><p>　　if((fp=fopen(str,"rb"))==NULL)</p><p><b>　　return;</b></p><p>　　for(i = 0;i < 2;i ++)</p><p>　　f

41、scanf("%d ",&pos[i]);</p><p>　　for(i=0;i<pos[0];i++)</p><p><b>　　{</b></p><p>　　for(j =0;j<pos[1];j++)</p><p><b>　　{</b><

42、/p><p>　　fscanf(fp,"%d ",&maze[i][j]);</p><p>　　printf("%d ",maze[i][j]);</p><p><b>　　}</b></p><p>　　printf("\n");</p>

43、<p><b>　　}</b></p><p>　　fclose(fp);</p><p>　　更正：將fscanf("%d ",&pos[i]);改為fscanf(fp,"%d ",&pos[i]);。</p><p>　　更正后實(shí)際運(yùn)行結(jié)果圖如下：</p>&

44、lt;p>　　此結(jié)果與預(yù)期結(jié)果一致。</p><p><b>　　第5章 總結(jié)</b></p><p>　　通過迷宮求解的編程練習(xí)思考數(shù)據(jù)結(jié)構(gòu)的使用，比如對(duì)棧、指針、鏈表等的深入了解，讓我們感受到了數(shù)據(jù)結(jié)構(gòu)及其算法的重要。此外還熟悉了各種函數(shù)的應(yīng)用。</p><p>　　對(duì)于我們初學(xué)者來說，學(xué)習(xí)編寫迷宮求解，對(duì)我們掌握了解數(shù)據(jù)結(jié)構(gòu)的知識(shí)有

45、很大的幫助。我們通過編程實(shí)踐，還能拓展思路，讓我們主動(dòng)去尋找所需要的算法，怎樣提高程序的質(zhì)量等。</p><p>　　通過編程我知道了想要寫出好的程序，需要有扎實(shí)的基礎(chǔ)，這樣才會(huì)遇到一些基本算法時(shí)做的游刃有余。在編程時(shí)，我們要有豐富的想象力，不拘泥于固定的思維方式，試試別人從沒想過的方法。豐富的想象力是建立在豐富的知識(shí)的基礎(chǔ)上，所以我們要通過多個(gè)途徑來幫助自己建立較豐富的知識(shí)結(jié)構(gòu)。</p><

46、p>　　在編程時(shí)，我們遇到了很多的困難，這就需要我們多與別人交流。在編程時(shí)我們也看到了有良好的編程風(fēng)格是十分重要的，至少在時(shí)間效率上就體現(xiàn)了這一點(diǎn)。</p><p>　　現(xiàn)在自己也能運(yùn)用數(shù)據(jù)結(jié)構(gòu)的算法編寫小程序了，卻沒想到的是算法并沒想象的那么簡(jiǎn)單（還有這份文檔）。這兩周，我們整天為了編程而忙碌，但看到自己的迷宮求解程序終于完成了，我們還是覺得很開心。</p><p>　　當(dāng)一切都完

47、成以后，除了學(xué)會(huì)運(yùn)用基本的算法外，我們也學(xué)會(huì)了許多別的東西。首先，我們學(xué)會(huì)了合作。合作，必然會(huì)產(chǎn)生分歧；學(xué)會(huì)去解決分歧，留下更多的是友誼。其次，我們學(xué)會(huì)了分工。分工是為了更好的合作，分工才能提高合作的效率。最后，我們學(xué)會(huì)了奮斗。我們相信，通過在北華大學(xué)的四年學(xué)習(xí)，我們定能寫出更精彩的程序，描繪出更精彩的人生。</p><p>　　在這里，我們要感謝指導(dǎo)我們課程設(shè)計(jì)的薛曼玲老師，給予我們悉心的指導(dǎo)。老師多次詢問我們

48、編寫進(jìn)程，并為我們指點(diǎn)迷津，幫助我們開拓研究思路，精心點(diǎn)撥、熱枕鼓勵(lì)。老師一絲不茍的工作作風(fēng)，嚴(yán)謹(jǐn)求實(shí)的態(tài)度以及踏踏實(shí)實(shí)的精神，不僅授我以文，更教會(huì)我做人，給以終生受益無窮之道。我還要感謝我們開發(fā)小組的另外2名同學(xué)，在設(shè)計(jì)中給予我很大的幫助。正是由于我們團(tuán)結(jié)協(xié)作，才順利地完成了課程設(shè)計(jì)任務(wù)。在設(shè)計(jì)中，我確實(shí)感到了團(tuán)隊(duì)合作的力量。</p><p>　　課程設(shè)計(jì)完成之后，留下的必將是美好的回憶。</p>

49、<p><b>　　參考文獻(xiàn)</b></p><p>　　[1]譚浩強(qiáng)主編. C語言程序設(shè)計(jì)（第三版）.北京：清華大學(xué)出版社2009.</p><p>　　[2]嚴(yán)蔚敏、吳偉民主編. 數(shù)據(jù)結(jié)構(gòu)（C語言版）.北京：清華大學(xué)出版社 2010</p><p><b>　　附錄</b></p><

50、;p>　　#include <stdio.h></p><p>　　#include <iostream.h></p><p>　　#include <stdlib.h></p><p>　　#include <malloc.h></p><p>　　#define STACK_INIT_

51、SIZE 100</p><p>　　#define STACKINCREMENT 10</p><p>　　#define OK 1</p><p>　　#define ERROR 0</p><p>　　#define OVERFLOW -2</p><p>　　#define M 50</p>&l

52、t;p>　　#define N 50</p><p>　　typedef int Status;</p><p>　　typedef struct</p><p><b>　　{</b></p><p><b>　　int x;</b></p><p><b>

53、;　　int y;</b></p><p>　　}PostType;</p><p>　　typedef struct</p><p><b>　　{</b></p><p><b>　　int x,y;</b></p><p>　　int d;/*"1

54、"表示右，"2"表示下，"3"表示左，"4"表示上*/</p><p>　　}SElemType;</p><p>　　/*///////////////////////////////////棧*/</p><p>　　typedef struct SqStack</p><

55、p><b>　　{</b></p><p>　　SElemType * base;</p><p>　　SElemType * top;</p><p>　　int stacksize;</p><p><b>　　}SqStack;</b></p><p>　　Sta

56、tus InitStack(SqStack &S)</p><p><b>　　{</b></p><p>　　S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));</p><p>　　if(!S.base) exit(OVERFLOW);</p>&

57、lt;p>　　S.top=S.base;</p><p>　　S.stacksize=STACK_INIT_SIZE;</p><p>　　return OK;</p><p><b>　　}</b></p><p>　　Status StackEmpty(SqStack S)</p><p&g

58、t;　　{ if (S.base==S.top)</p><p>　　return OK;</p><p><b>　　else</b></p><p>　　return ERROR;</p><p><b>　　}</b></p><p>　　Status Push(SqS

59、tack &S,SElemType e)</p><p><b>　　{</b></p><p>　　if(S.top-S.base>=S.stacksize)</p><p><b>　　{</b></p><p>　　S.base=(SElemType *)realloc(S.ba

60、se,</p><p>　　(S.stacksize+STACKINCREMENT)*sizeof(SElemType));</p><p>　　if(!S.base) exit(OVERFLOW);</p><p>　　S.top=S.base+S.stacksize;</p><p>　　S.stacksize+=STACKINCREME

61、NT;</p><p><b>　　}</b></p><p>　　*S.top++=e;</p><p>　　return OK;</p><p><b>　　}</b></p><p>　　Status Pop(SqStack &S,SElemType &

62、e)</p><p><b>　　{</b></p><p>　　if(S.top==S.base) return ERROR;</p><p>　　e=*--S.top;</p><p>　　return OK;</p><p><b>　　}</b></p&g

63、t;<p>　　//////////////////////////////////////////////////////////////////////*迷宮求解*/</p><p>　　/***************求迷宮路徑函數(shù)***********************/ </p><p>　　void MazePath(PostType start,PostT

64、ype end,int maze[M][N],int diradd[4][2]) </p><p><b>　　{ </b></p><p>　　int i,j,d;int a,b; </p><p>　　SElemType elem,e; </p><p>　　SqStack S1, S2; </p>&

65、lt;p>　　InitStack(S1); </p><p>　　InitStack(S2); </p><p>　　maze[start.x][start.y]=2; /*入口點(diǎn)作上標(biāo)記 */</p><p>　　elem.x=start.x; </p><p>　　elem.y=start.y; </p><p&

66、gt;　　elem.d=-1; //*開始為-1*/ </p><p>　　Push(S1,elem); </p><p>　　while(!StackEmpty(S1)) //*棧不為空 有路徑可走*/ </p><p><b>　　{ </b></p><p>　　Pop(S1,elem); </p>

67、<p>　　i=elem.x; </p><p>　　j=elem.y; </p><p>　　d=elem.d+1; //*下一個(gè)方向 */</p><p>　　while(d<4) //*試探東南西北各個(gè)方向*/ </p><p><b>　　{ </b></p><p>　　

68、a=i+diradd[d][0]; </p><p>　　b=j+diradd[d][1]; </p><p>　　if(a==end.x && b==end.y && maze[a][b]==0) //*如果到了出口*/ </p><p><b>　　{ </b></p><p>　　e

69、lem.x=i; </p><p>　　elem.y=j; </p><p>　　elem.d=d; </p><p>　　Push(S1,elem); </p><p>　　elem.x=a; </p><p>　　elem.y=b; </p><p>　　elem.d=886; //*方向輸

70、出為-1 判斷是否到了出口*/ </p><p>　　Push(S1,elem); </p><p>　　printf("\n0=右 1=下 2=左 3=上 886為走出迷宮\n\n通路為:(行坐標(biāo),列坐標(biāo),方向)\n"); </p><p>　　while(!StackEmpty(S1)) //*逆置序列 并輸出迷宮路徑序列*/ </p&

71、gt;<p><b>　　{ </b></p><p>　　Pop(S1,e); </p><p>　　Push(S2,e); </p><p><b>　　} </b></p><p>　　while(!StackEmpty(S2)) </p><p><

72、;b>　　{ </b></p><p>　　Pop(S2,e); </p><p>　　printf("-->(%d,%d,%d)",e.x,e.y,e.d); </p><p><b>　　} </b></p><p>　　return; //*跳出兩層循環(huán)，本來用break

73、,但發(fā)現(xiàn)出錯(cuò)，exit又會(huì)結(jié)束程序，選用return還是不錯(cuò)滴o(∩_∩)o...*/ </p><p><b>　　} </b></p><p>　　if(maze[a][b]==0) //*找到可以前進(jìn)的非出口的點(diǎn)*/ </p><p><b>　　{ </b></p><p>　　maze[a

74、][b]=2; //*標(biāo)記走過此點(diǎn) */</p><p>　　elem.x=i; </p><p>　　elem.y=j; </p><p>　　elem.d=d; </p><p>　　Push(S1,elem); //*當(dāng)前位置入棧*/ </p><p>　　i=a; //*下一點(diǎn)轉(zhuǎn)化為當(dāng)前點(diǎn) */</p&g

75、t;<p><b>　　j=b; </b></p><p><b>　　d=-1; </b></p><p><b>　　} </b></p><p><b>　　d++; </b></p><p><b>　　} </b&g

76、t;</p><p><b>　　} </b></p><p>　　printf("NO ROAD!\n"); </p><p><b>　　} </b></p><p>　　/*************建立迷宮*******************/ </p>&

77、lt;p>　　void File_Save(int maze[][50],int x,int y)//存儲(chǔ)數(shù)據(jù)到文件</p><p><b>　　{</b></p><p><b>　　FILE *fp;</b></p><p><b>　　int i,j;</b></p><

78、;p>　　char str[]="";</p><p>　　cout<<"Input the file name:";</p><p><b>　　cin>>str;</b></p><p>　　if((fp = fopen(str,"w"))==NULL

79、)</p><p><b>　　return;</b></p><p>　　fprintf(fp,"%d ",x);</p><p>　　fprintf(fp,"%d ",y);</p><p>　　fprintf(fp,"\n");</p>&l

80、t;p>　　for(i = 0;i < x;i ++)</p><p><b>　　{</b></p><p>　　for(j = 0;j < y;j ++)</p><p>　　fprintf(fp,"%d ",maze[i][j]);</p><p>　　fprintf(fp,&

81、quot;\n");</p><p><b>　　}</b></p><p>　　fclose(fp);</p><p>　　printf("Your maze has been saved as your file!\n");</p><p><b>　　}</b>&

82、lt;/p><p>　　void File_Get(int maze[M][N])//從文件中抽取數(shù)據(jù)</p><p><b>　　{</b></p><p><b>　　FILE *fp;</b></p><p>　　int i,j,pos[2];</p><p>　　char

83、 str[]="";</p><p>　　cout<<"Input the file name:";</p><p><b>　　cin>>str;</b></p><p>　　if((fp=fopen(str,"r"))==NULL)</p>&

84、lt;p><b>　　return;</b></p><p>　　for(i = 0;i < 2;i ++)</p><p>　　fscanf(fp,"%d ",&pos[i]);</p><p>　　for(i=0;i<pos[0];i++)</p><p><b&g

85、t;　　{</b></p><p>　　for(j =0;j<pos[1];j++)</p><p><b>　　{</b></p><p>　　fscanf(fp,"%d ",&maze[i][j]);</p><p>　　printf("%d ",ma

86、ze[i][j]);</p><p><b>　　}</b></p><p>　　printf("\n");</p><p><b>　　}</b></p><p>　　fclose(fp);</p><p><b>　　}</b>&

87、lt;/p><p>　　void initmaze(int maze[M][N]) </p><p><b>　　{ </b></p><p><b>　　int i,j; </b></p><p>　　int m,n; //*迷宮行,列 */</p><p><b>

88、　　char c;</b></p><p>　　printf("Input mode row: m="); </p><p>　　scanf("%d",&m); </p><p>　　printf("Input mode col: n="); </p><p>　

89、　scanf("%d",&n); </p><p>　　printf("\nInput (0/1):\n"); </p><p>　　for(i=1;i<=m;i++)</p><p><b>　　{</b></p><p>　　for(j=1;j<=n;j++

90、)</p><p><b>　　{</b></p><p>　　scanf("%d",&maze[i][j]);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　printf

91、("Your mode:\n"); </p><p>　　for(i=0;i<=m+1;i++)//加一圈墻</p><p><b>　　{ </b></p><p>　　maze[i][0]=1; </p><p>　　maze[i][n+1]=1; </p><p>

92、<b>　　} </b></p><p>　　for(j=0;j<=n+1;j++) </p><p><b>　　{ </b></p><p>　　maze[0][j]=1; </p><p>　　maze[m+1][j]=1; </p><p><b>　

93、　} </b></p><p>　　for(i=0;i<=m+1;i++) //*輸出迷宮*/ </p><p><b>　　{ </b></p><p>　　for(j=0;j<=n+1;j++)</p><p>　　printf("%d ",maze[i][j]);<

94、/p><p>　　printf("\n");</p><p><b>　　}</b></p><p>　　printf("Save your maze(Y/N)?\nYour choice:");</p><p><b>　　cin>>c;</b>&l

95、t;/p><p>　　if((c == 'Y')||(c == 'y'))</p><p>　　File_Save(maze,m+2,n+2);</p><p>　　else if((c == 'N')||(c == 'n'))</p><p>　　printf("Your

96、 maze is not saved!\n"); </p><p>　　//File_Get();</p><p><b>　　} </b></p><p>　　void main() </p><p><b>　　{ </b></p><p>　　int sto[

97、M][N]; </p><p>　　PostType start,end; //*start,end入口和出口的坐標(biāo)*/ </p><p>　　int add[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//*行增量和列增量 方向依次為東西南北*/ </p><p><b>　　while(1)</b></p>

98、;<p><b>　　{</b></p><p>　　cout<<"***********************迷宮求解*********************\n";</p><p>　　cout<<"自己建立迷宮(Q)、直接從文件中調(diào)取(P)、退出程序(v)? : ";</p

99、><p><b>　　char cc;</b></p><p>　　loop:cin>>cc;</p><p>　　if((cc == 'P')||(cc == 'p'))</p><p>　　File_Get(sto);</p><p>　　else if

100、((cc == 'Q')||(cc == 'q'))</p><p>　　initmaze(sto);</p><p>　　else if((cc == 'V')||(cc =='v'))</p><p><b>　　exit(0);</b></p><p>

101、;<b>　　else </b></p><p><b>　　{</b></p><p>　　cout<<"字符有誤，請(qǐng)重新輸入：";</p><p>　　goto loop;</p><p><b>　　}</b></p><

102、;p>　　//initmaze(sto);//*建立迷宮*/ </p><p>　　//File_Get(sto);</p><p>　　printf("Input start_x,start_y:\n"); </p><p>　　scanf("%d,%d",&start.x,&start.y); <

103、;/p><p>　　printf("Input end_x,end_y:\n"); </p><p>　　scanf("%d,%d",&end.x,&end.y); </p><p>　　MazePath(start,end,sto,add); //*find path*/ </p><p>