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

2、評語與成績、目錄、概述、軟件總體設計、詳細設計、軟件的調試、總結、附錄：帶中文注釋的程序清單、參考文獻。報告一律用a4紙打印，中文字體為宋體，西文字體用time new roma，一律用小四號字，行距采用“固定值”18磅，首行縮進2字符。總體設計應配合軟件總體模塊結構圖來說明軟件應具有的功能。詳細設計闡述本人設計模塊部分的設計思想、應用到的理論和算法、程序流程等等，調試的敘述應配合出錯場景的抓圖來說明出現了哪些錯誤，如何解決的。（7）課程設計報告中的軟件總體設計、詳細設計、軟件的調試等主體內容要以文字描述、圖表等形式為主，可配以主要核心代碼，在附錄中附程序清單。三、課程設計工作量由于是設計小組

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

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

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

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

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

8、棧又稱為后進先出的線性表。由于計算機解謎宮時，通常用的是“窮舉求解”的方法，即從入口出發，順某一方向向前探索，若能走通，則繼續往前走；否則沿原路退回，換一個方向再繼續探索，直至所有可能的通路都探索到為止。為了保證在任何位置上都能沿原路退回，顯然需要用一個后進先出的結構來保存從入口到當前位置的路徑。因此，在求迷宮通路的算法中應用“棧”也就是自然而然的事了。首先，迷宮圖用方塊表示，每個方塊或為通道，或為墻。所求路徑必須是簡單路徑，即在求得的路徑上不能重復出現同一通道塊。假設“當前位置”指的是“在搜索過程中某一時刻所在圖中某個方塊位置”，則求迷宮中一條路徑的算法的基本思想是：若當前位置“可通”，則納

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

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

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

12、e(fp);來關閉文件。以向文件中寫數據為例的部分程序實現如下：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);具體功能的程序實現可參見附錄。(文件存儲流程圖如下)開 始定義文件指針fp輸入字符串str定義i ,j以“w”打開文件成功？返回空y

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

14、路徑可走*/ pop(s1,elem); i=elem.x; j=elem.y; while(d4) /*試探東南西北各個方向*/ 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通路為:(行坐標,列坐標,方向

15、)n);更正：在代碼pop(s1,elem); i=elem.x; j=elem.y; 后加一條語句：d=elem.d+1; /*下一個方向 */更正后實際運行結果圖如下：此結果與預期結果一致。2. 文件的存取模塊：根據調試分析進行測試預期結果：可從外部文件中調取數據。實際測試結果：調取數據時產生混亂。部分程序代碼如下：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);。更正后實際運行結果圖如下：此結果與預期結果一致。第5章 總結通過迷宮求解的編程練習思考數據結構的使用，比如對棧、指針、鏈表等的深入了解，讓我們感受到了數據結構及其算法的重要。此外還熟悉了各種函數的應用。對于我們初學者來說，學習編寫迷宮求解，對我們掌握了解數據結構的知識有很大的幫助。我們通過編程實踐，還能拓展思路，讓我們主動去尋找所需要的算法，怎樣提高程序的質量等。通過編程

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

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

19、，在設計中給予我很大的幫助。正是由于我們團結協作，才順利地完成了課程設計任務。在設計中，我確實感到了團隊合作的力量。課程設計完成之后，留下的必將是美好的回憶。參考文獻1譚浩強主編. c語言程序設計（第三版）.北京：清華大學出版社2009.2嚴蔚敏、吳偉民主編. 數據結構（c語言版）.北京：清華大學出版社 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;/*迷宮求解*/*求迷宮路徑函數*/ 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; /*入口點作上標記 */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; /*下一個方向 */while(d(%d,%d,%d),e.x,e.y,e.d);

24、return; /*跳出兩層循環，本來用break,但發現出錯，exit又會結束程序，選用return還是不錯滴o(_)o.*/ if(mazeab=0) /*找到可以前進的非出口的點*/ mazeab=2; /*標記走過此點 */elem.x=i; elem.y=j; elem.d=d; push(s1,elem); /*當前位置入棧*/ i=a; /*下一點轉化為當前點 */j=b; d=-1; d+; printf(no road!n); /*建立迷宮*/ void file_save(int maze50,int x,int y)/存儲數據到文件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)/從文件中抽取數據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,