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

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)迷宮求解 院 系： 網(wǎng)絡(luò)工程 班 級： 網(wǎng)絡(luò)09 1班 姓 名： 合 作 者： 指導(dǎo)教師： 2010 年 12 月 20 日數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)任務(wù)書一、題目： 迷宮求解二、設(shè)計(jì)要求（1）李斌（組長）、尚賀和張雪城組成設(shè)計(jì)小組。（2）小組成員分工協(xié)作完成。要求每個(gè)成員有自己相對獨(dú)立的模塊，同時(shí)要了解其他組員完成的內(nèi)容。（3）查閱相關(guān)資料，自學(xué)具體課題中涉及到的新知識(shí)。（4）采用結(jié)構(gòu)化、模塊化程序設(shè)計(jì)方法設(shè)計(jì)，功能要完善，界面美觀。（5）所設(shè)計(jì)的系統(tǒng)要至少應(yīng)用一個(gè)課程中或者與其密切相關(guān)的算法。（6）按要求寫出課程設(shè)計(jì)報(bào)告。其主要內(nèi)容包括：封皮、課程設(shè)計(jì)任務(wù)書，指導(dǎo)教師

2、評語與成績、目錄、概述、軟件總體設(shè)計(jì)、詳細(xì)設(shè)計(jì)、軟件的調(diào)試、總結(jié)、附錄：帶中文注釋的程序清單、參考文獻(xiàn)。報(bào)告一律用a4紙打印，中文字體為宋體，西文字體用time new roma，一律用小四號字，行距采用“固定值”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)配合出錯(cuò)場景的抓圖來說明出現(xiàn)了哪些錯(cuò)誤，如何解決的。（7）課程設(shè)計(jì)報(bào)告中的軟件總體設(shè)計(jì)、詳細(xì)設(shè)計(jì)、軟件的調(diào)試等主體內(nèi)容要以文字描述、圖表等形式為主，可配以主要核心代碼，在附錄中附程序清單。三、課程設(shè)計(jì)工作量由于是設(shè)計(jì)小組

3、團(tuán)結(jié)協(xié)作完成設(shè)計(jì)任務(wù)，一般每人的程序量在200行有效程序行左右，不得抄襲。四、課程設(shè)計(jì)工作計(jì)劃2010年12月20日，指導(dǎo)教師講課，學(xué)生根據(jù)題目準(zhǔn)備資料；2010年12月21日，設(shè)計(jì)小組進(jìn)行總體方案設(shè)計(jì)和任務(wù)分工；2010年12月22日2010年12月27日，每人完成自己承擔(dān)的程序模塊并通過獨(dú)立編譯；2010年12月28日2009年12月30日，將各模塊集成為一個(gè)完整的系統(tǒng)，并錄入足夠的數(shù)據(jù)進(jìn)行調(diào)試運(yùn)行；2010年12月31日，驗(yàn)收、開始撰寫報(bào)告；2011年01月4日前，提交課程設(shè)計(jì)報(bào)告。 指導(dǎo)教師簽章： 教研室主任簽章 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)指導(dǎo)教師評語與成績指導(dǎo)教師評語：課程設(shè)計(jì)表現(xiàn)成績： 課程

4、設(shè)計(jì)驗(yàn)收成績： 課程設(shè)計(jì)報(bào)告成績： 課程設(shè)計(jì) 總成績： 指導(dǎo)教師簽章 2011年 01 月 04 日目 錄第1章 概述51.1 性能需求51.2 功能需求5第2章 概要設(shè)計(jì)62.1 功能模塊設(shè)計(jì)62.2 算法分析與設(shè)計(jì)7第3章 詳細(xì)設(shè)計(jì)83.1 迷宮求解功能模塊設(shè)計(jì)83.2 文件的存取模塊設(shè)計(jì)8第4章 調(diào)試分析與測試結(jié)果104.1 調(diào)試分析104.2 測試結(jié)果10第5章 總結(jié)13參考文獻(xiàn)14附錄15第1章 概述1.1 性能需求隨著社會(huì)經(jīng)濟(jì)和人們物質(zhì)生活的不斷提高，人們對精神生活的需求也越來越高，在現(xiàn)今社會(huì)里，人們對諸如智商、情商等的重視無疑反映了對精神生活的態(tài)度。當(dāng)然具體到我們每個(gè)人來說，想必

5、大多數(shù)人小時(shí)候都曾玩過魔方、迷宮吧。作為這種智力游戲，人們是百玩不厭的。正是鑒于這種需求，本設(shè)計(jì)應(yīng)用計(jì)算機(jī)語言及其算法，將人的意志賦予機(jī)器實(shí)現(xiàn)，使人們不必再陷于枯燥的重復(fù)勞動(dòng)，從而將更多的精力投入到對未知領(lǐng)域的探索上。1.2 功能需求本設(shè)計(jì)的關(guān)鍵在于將人的想法自能化，由所編軟件自動(dòng)的搜索可行路徑。因此，軟件必須擁有自動(dòng)搜索并記錄可行路徑的功能，除此之外，軟件還應(yīng)設(shè)置人機(jī)交互接口，以便能夠人為的建立迷宮圖；軟件要能保存以輸入的迷宮圖，并能調(diào)取外部現(xiàn)有的迷宮圖；當(dāng)然對于迷宮問題還有很多要考慮的地方，比如由用戶自己來探索可行路徑，但由于本設(shè)計(jì)側(cè)重于迷宮求解的算法設(shè)計(jì)，并非以游戲的形式為初衷，定有不全

6、之處。第2章 概要設(shè)計(jì)2.1 功能模塊設(shè)計(jì)本設(shè)計(jì)主要分為個(gè)模塊：初始化棧模塊、迷宮建立模塊、迷宮求解模塊、文件的保存與調(diào)取模塊。1. 初始化棧模塊，由initstack(sqstack &s)、push(sqstack &s,selemtype e)、pop(sqstack &s,selemtype &e)、stackempty(sqstack s)函數(shù)構(gòu)成，此模塊是解決問題的關(guān)鍵算法，貫穿整個(gè)設(shè)計(jì)的始終。2. 迷宮建立模塊，由initmaze(int mazemn)構(gòu)成，此模塊用于用戶自己設(shè)計(jì)并建立迷宮。3. 迷宮求解模塊：由mazepath(posttype start,posttype

7、end,int mazemn,int diradd42)構(gòu)成，此模塊是基于棧的特點(diǎn)與迷宮實(shí)際相結(jié)合來實(shí)現(xiàn)的。4. 文件的保存與調(diào)取模塊：由file_save(int maze50,int x,int y)、file_get(int mazemn)構(gòu)成，此模塊用來存儲(chǔ)用戶建立的迷宮，并方便其調(diào)取外部的現(xiàn)有迷宮。流程圖如下：開 始初始化棧模塊迷宮建立模塊迷宮求解模塊文件的保存與調(diào)取模塊結(jié) 束2.2 算法分析與設(shè)計(jì)棧：假設(shè)棧s=(a1,a2,an),則稱a1為棧底元素，an為棧頂元素。棧中元素按a1,a2,an的次序進(jìn)棧，退棧的第一個(gè)元素為棧頂元素。換句話說，棧的修改是按后進(jìn)先出的原則進(jìn)行的。因此，

8、棧又稱為后進(jìn)先出的線性表。由于計(jì)算機(jī)解謎宮時(shí)，通常用的是“窮舉求解”的方法，即從入口出發(fā)，順某一方向向前探索，若能走通，則繼續(xù)往前走；否則沿原路退回，換一個(gè)方向再繼續(xù)探索，直至所有可能的通路都探索到為止。為了保證在任何位置上都能沿原路退回，顯然需要用一個(gè)后進(jìn)先出的結(jié)構(gòu)來保存從入口到當(dāng)前位置的路徑。因此，在求迷宮通路的算法中應(yīng)用“?！币簿褪亲匀欢坏氖铝?。首先，迷宮圖用方塊表示，每個(gè)方塊或?yàn)橥ǖ溃驗(yàn)閴?。所求路徑必須是簡單路徑，即在求得的路徑上不能重?fù)出現(xiàn)同一通道塊。假設(shè)“當(dāng)前位置”指的是“在搜索過程中某一時(shí)刻所在圖中某個(gè)方塊位置”，則求迷宮中一條路徑的算法的基本思想是：若當(dāng)前位置“可通”，則納

9、入“當(dāng)前路徑”，并繼續(xù)朝“下一位置”探索，即切換“下一位置”為“當(dāng)前位置”，如此重復(fù)直至到達(dá)出口；若當(dāng)前位置“不可通”，則應(yīng)順著“來向”退回到“前一通道塊”，然后朝著除“來向”之外的其他方向繼續(xù)探索；若該通道塊的四周4個(gè)方塊均“不可通”，則應(yīng)從“當(dāng)前路徑”上刪除該通道塊。所謂“下一位置”指的是“當(dāng)前位置”四周4個(gè)方向（東、南、西、北）上相鄰的方塊。假設(shè)以棧s記錄“當(dāng)前路徑”，則棧頂中存放的是“當(dāng)前路徑”上最后一個(gè)通道塊。由此，“納入路徑”的操作即為“當(dāng)前位置入?！?；“從當(dāng)前路徑上刪除前一通道塊”的操作即為“出?！?。其中需要說明的是，所謂當(dāng)前位置可通，指的是未曾走到過的通道塊，即要求該方塊位置不

10、僅是通道塊，而且既不在當(dāng)前路徑上（否則所求路徑就不是簡單路徑），也不是曾經(jīng)納入路徑的通道塊（否則只能在死胡同內(nèi)轉(zhuǎn)圈）。此軟件的主要實(shí)現(xiàn)均是按照上述分析設(shè)計(jì)而成。第3章 詳細(xì)設(shè)計(jì)3.1 迷宮求解功能模塊設(shè)計(jì)此模塊主要由函數(shù)mazepath(posttype start,posttype end,int mazemn,int diradd42)來實(shí)現(xiàn)，當(dāng)然此功能實(shí)現(xiàn)主要基于對棧的操作。模塊用：typedef structint x;int y;posttype;typedef structint x,y;int d;/*1表示右，2表示下，3表示左，4表示上*/selemtype;來表示坐標(biāo)類型及

11、迷宮中每一方塊的屬性（包括坐標(biāo)、下一步的方向），用1和0分別表示墻和通路并用二維數(shù)組存儲(chǔ)，從而將實(shí)際問題轉(zhuǎn)化成數(shù)學(xué)模型，方便程序的設(shè)計(jì)，以實(shí)現(xiàn)其自能化。具體的程序?qū)崿F(xiàn)可參見附錄。3.2 文件的存取模塊設(shè)計(jì)此模塊由file_save(int maze50,int x,int y)、file_get(int mazemn)來實(shí)現(xiàn)，此功能主要是對文件的操作。其中file *fp;是對文件指針的定義，if(fp = fopen(str,w)=null)return;和if(fp=fopen(str,rb)=null)return;分別是以寫和讀的方式打開文件，以便對文件進(jìn)行相應(yīng)的操作，最后以fclos

12、e(fp);來關(guān)閉文件。以向文件中寫數(shù)據(jù)為例的部分程序?qū)崿F(xiàn)如下：file *fp;int i,j;char str=;coutstr;if(fp = fopen(str,w)=null)return;fprintf(fp,%d ,x);fprintf(fp,%d ,y);fprintf(fp,n);for(i = 0;i x;i +)for(j = 0;j y;j +)fprintf(fp,%d ,mazeij);fprintf(fp,n);fclose(fp);具體功能的程序?qū)崿F(xiàn)可參見附錄。(文件存儲(chǔ)流程圖如下)開 始定義文件指針fp輸入字符串str定義i ,j以“w”打開文件成功？返回空y

13、向文件中輸出數(shù)據(jù)x ,yi = 0yix？i = 0jy？nyj+向文件輸出mazeiji+關(guān)閉文件結(jié) 束第4章 調(diào)試分析與測試結(jié)果4.1 調(diào)試分析1. 迷宮求解模塊：此模塊的調(diào)試主要在于迷宮中每個(gè)方塊出棧入棧的時(shí)機(jī)及對棧本身的操作。2. 文件的存取模塊：此模塊的調(diào)試主要在于對文件輸入、輸出操作及文件打開不成功時(shí)的應(yīng)對。4.2 測試結(jié)果1迷宮求解模塊：根據(jù)調(diào)試分析進(jìn)行測試預(yù)期結(jié)果：程序能夠自動(dòng)搜索下一步的方向，并能記錄已經(jīng)走過的方向。實(shí)際測試結(jié)果：程序只能沿著固定的方向搜索，而不能退回到該方塊繼續(xù)從其他方向開始搜索。程序部分代碼如下：while(!stackempty(s1) /*棧不為空 有

14、路徑可走*/ pop(s1,elem); i=elem.x; j=elem.y; while(d4) /*試探東南西北各個(gè)方向*/ a=i+diraddd0; b=j+diraddd1; if(a=end.x & b=end.y & mazeab=0) /*如果到了出口*/ elem.x=i; elem.y=j; elem.d=d; push(s1,elem); elem.x=a; elem.y=b; elem.d=886; /*方向輸出為-1 判斷是否到了出口*/ push(s1,elem); printf(n0=右 1=下 2=左 3=上 886為走出迷宮nn通路為:(行坐標(biāo),列坐標(biāo),方向

15、)n);更正：在代碼pop(s1,elem); i=elem.x; j=elem.y; 后加一條語句：d=elem.d+1; /*下一個(gè)方向 */更正后實(shí)際運(yùn)行結(jié)果圖如下：此結(jié)果與預(yù)期結(jié)果一致。2. 文件的存取模塊：根據(jù)調(diào)試分析進(jìn)行測試預(yù)期結(jié)果：可從外部文件中調(diào)取數(shù)據(jù)。實(shí)際測試結(jié)果：調(diào)取數(shù)據(jù)時(shí)產(chǎn)生混亂。部分程序代碼如下：file *fp;int i,j,pos2;char str=;coutstr;if(fp=fopen(str,rb)=null)return;for(i = 0;i 2;i +)fscanf(%d ,&posi);for(i=0;ipos0;i+)for(j =0;jpos1

16、;j+)fscanf(fp,%d ,&mazeij);printf(%d ,mazeij);printf(n);fclose(fp);更正：將fscanf(%d ,&posi);改為fscanf(fp,%d ,&posi);。更正后實(shí)際運(yùn)行結(jié)果圖如下：此結(jié)果與預(yù)期結(jié)果一致。第5章 總結(jié)通過迷宮求解的編程練習(xí)思考數(shù)據(jù)結(jié)構(gòu)的使用，比如對棧、指針、鏈表等的深入了解，讓我們感受到了數(shù)據(jù)結(jié)構(gòu)及其算法的重要。此外還熟悉了各種函數(shù)的應(yīng)用。對于我們初學(xué)者來說，學(xué)習(xí)編寫迷宮求解，對我們掌握了解數(shù)據(jù)結(jié)構(gòu)的知識(shí)有很大的幫助。我們通過編程實(shí)踐，還能拓展思路，讓我們主動(dòng)去尋找所需要的算法，怎樣提高程序的質(zhì)量等。通過編程

17、我知道了想要寫出好的程序，需要有扎實(shí)的基礎(chǔ)，這樣才會(huì)遇到一些基本算法時(shí)做的游刃有余。在編程時(shí)，我們要有豐富的想象力，不拘泥于固定的思維方式，試試別人從沒想過的方法。豐富的想象力是建立在豐富的知識(shí)的基礎(chǔ)上，所以我們要通過多個(gè)途徑來幫助自己建立較豐富的知識(shí)結(jié)構(gòu)。在編程時(shí)，我們遇到了很多的困難，這就需要我們多與別人交流。在編程時(shí)我們也看到了有良好的編程風(fēng)格是十分重要的，至少在時(shí)間效率上就體現(xiàn)了這一點(diǎn)。現(xiàn)在自己也能運(yùn)用數(shù)據(jù)結(jié)構(gòu)的算法編寫小程序了，卻沒想到的是算法并沒想象的那么簡單（還有這份文檔）。這兩周，我們整天為了編程而忙碌，但看到自己的迷宮求解程序終于完成了，我們還是覺得很開心。當(dāng)一切都完成以后，

18、除了學(xué)會(huì)運(yùn)用基本的算法外，我們也學(xué)會(huì)了許多別的東西。首先，我們學(xué)會(huì)了合作。合作，必然會(huì)產(chǎn)生分歧；學(xué)會(huì)去解決分歧，留下更多的是友誼。其次，我們學(xué)會(huì)了分工。分工是為了更好的合作，分工才能提高合作的效率。最后，我們學(xué)會(huì)了奮斗。我們相信，通過在北華大學(xué)的四年學(xué)習(xí)，我們定能寫出更精彩的程序，描繪出更精彩的人生。在這里，我們要感謝指導(dǎo)我們課程設(shè)計(jì)的薛曼玲老師，給予我們悉心的指導(dǎo)。老師多次詢問我們編寫進(jìn)程，并為我們指點(diǎn)迷津，幫助我們開拓研究思路，精心點(diǎn)撥、熱枕鼓勵(lì)。老師一絲不茍的工作作風(fēng)，嚴(yán)謹(jǐn)求實(shí)的態(tài)度以及踏踏實(shí)實(shí)的精神，不僅授我以文，更教會(huì)我做人，給以終生受益無窮之道。我還要感謝我們開發(fā)小組的另外2名同學(xué)

19、，在設(shè)計(jì)中給予我很大的幫助。正是由于我們團(tuán)結(jié)協(xié)作，才順利地完成了課程設(shè)計(jì)任務(wù)。在設(shè)計(jì)中，我確實(shí)感到了團(tuán)隊(duì)合作的力量。課程設(shè)計(jì)完成之后，留下的必將是美好的回憶。參考文獻(xiàn)1譚浩強(qiáng)主編. c語言程序設(shè)計(jì)（第三版）.北京：清華大學(xué)出版社2009.2嚴(yán)蔚敏、吳偉民主編. 數(shù)據(jù)結(jié)構(gòu)（c語言版）.北京：清華大學(xué)出版社 2010附錄#include #include #include #include #define stack_init_size 100#define stackincrement 10#define ok 1#define error 0#define overflow -2#define

20、 m 50#define n 50typedef int status;typedef structint x;int y;posttype;typedef structint x,y;int d;/*1表示右，2表示下，3表示左，4表示上*/selemtype;/*/棧*/typedef struct sqstackselemtype * base;selemtype * top;int stacksize;sqstack;status initstack(sqstack &s) s.base=(selemtype *)malloc(stack_init_size*sizeof(selemt

21、ype); if(!s.base) exit(overflow); s.top=s.base; s.stacksize=stack_init_size; return ok;status stackempty(sqstack s) if (s.base=s.top) return ok; else return error;status push(sqstack &s,selemtype e) if(s.top-s.base=s.stacksize) s.base=(selemtype *)realloc(s.base, (s.stacksize+stackincrement)*sizeof(

22、selemtype); if(!s.base) exit(overflow); s.top=s.base+s.stacksize; s.stacksize+=stackincrement; *s.top+=e; return ok;status pop(sqstack &s,selemtype &e) if(s.top=s.base) return error; e=*-s.top; return ok;/*迷宮求解*/*求迷宮路徑函數(shù)*/ void mazepath(posttype start,posttype end,int mazemn,int diradd42) int i,j,d;

23、int a,b; selemtype elem,e; sqstack s1, s2; initstack(s1); initstack(s2); mazestart.xstart.y=2; /*入口點(diǎn)作上標(biāo)記 */elem.x=start.x; elem.y=start.y; elem.d=-1; /*開始為-1*/ push(s1,elem); while(!stackempty(s1) /*棧不為空 有路徑可走*/ pop(s1,elem); i=elem.x; j=elem.y; d=elem.d+1; /*下一個(gè)方向 */while(d(%d,%d,%d),e.x,e.y,e.d);

24、return; /*跳出兩層循環(huán)，本來用break,但發(fā)現(xiàn)出錯(cuò)，exit又會(huì)結(jié)束程序，選用return還是不錯(cuò)滴o(_)o.*/ if(mazeab=0) /*找到可以前進(jìn)的非出口的點(diǎn)*/ mazeab=2; /*標(biāo)記走過此點(diǎn) */elem.x=i; elem.y=j; elem.d=d; push(s1,elem); /*當(dāng)前位置入棧*/ i=a; /*下一點(diǎn)轉(zhuǎn)化為當(dāng)前點(diǎn) */j=b; d=-1; d+; printf(no road!n); /*建立迷宮*/ void file_save(int maze50,int x,int y)/存儲(chǔ)數(shù)據(jù)到文件file *fp;int i,j;cha

25、r str=;coutstr;if(fp = fopen(str,w)=null)return;fprintf(fp,%d ,x);fprintf(fp,%d ,y);fprintf(fp,n);for(i = 0;i x;i +)for(j = 0;j y;j +)fprintf(fp,%d ,mazeij);fprintf(fp,n);fclose(fp);printf(your maze has been saved as your file!n);void file_get(int mazemn)/從文件中抽取數(shù)據(jù)file *fp;int i,j,pos2;char str=;coutstr;if(fp=fopen(str,r)=null)return;for(i = 0;i 2;i +)fscanf(fp,%d ,&posi);for(i=0;ipos0;i+)for(j =0;jpos1;j+)fscanf(fp,%d ,&mazeij);printf(%d ,mazeij);printf(n);fclose(fp);void initmaze(int mazemn) int i,j; int m,n; /*迷宮行,列 */char c;printf(input mode row: m=); scanf(%d,