《數據結構課程設計 迷宮問題》由會員分享，可在線閱讀，更多相關《數據結構課程設計 迷宮問題（23頁珍藏版）》請在裝配圖網上搜索。

1、課程設計(論文)任務書軟件 學院軟件工程+電子商務2009專業(yè)2班一、 課程設計(論文)題目迷宮問題二、課程設計(論文)工作自2010 年12月27日起至2011年1月_2_日止三、課程設計(論文)地點:創(chuàng)新大樓實訓中心四、課程設計(論文)內容要求：1本課程設計的目的(1)鞏固和加深對數據結構基本知識的理解，提高綜合運用課程知識的能力。(2) 使學生掌握軟件設計的基本內容和設計方法，并培養(yǎng)學生進行規(guī)范化軟 件設計的能力。(3) 使學生掌握使用各種計算機資料和有關參考資料，提高學生進行程序設 計的基本能力。2 課程設計的任務及要求1) 基本要求:(1) 對系統(tǒng)進行功能模塊分析、控制模塊分析；(2

2、)系統(tǒng)設計要能完成題目所要求的功能;(3) 編程簡練，可用，盡可能的使系統(tǒng)的功能更加完善和全面；(4) 說明書、流程圖要清楚；(5) 提高學生的論文寫作能力； (6)特別要求自己獨立完成;2) 創(chuàng)新要求：在基本要求達到后，可進行創(chuàng)新設計，如改善算法性能、友好的人機界面。3) 課程設計論文編寫要求(1) 要按照書稿的規(guī)格打印與寫課程設計論文(2) 論文包括目錄、正文、小結、參考文獻、附錄等(3)課程設計論文裝訂按學校的統(tǒng)一要求完成4）課程設計進度安排內容天數地點構思及收集資料1圖書館編碼與調試3實驗室撰寫論文1圖書館、實驗室學生簽名：20011年1 月3日課程設計（論文）評審意見（1）基本算法（

3、20 分）：優(yōu)（）、良（）、中（）、一般（）、差（）；（2）設計分析（20 分）：優(yōu)（）、良（）、中（）、一般（）、差（）；（3）調試分析（20 分）：優(yōu)（）、良（）、中（）、一般（）、差（）；（4）論文內容（20 分）：優(yōu)（）、良（）、中（）、一般（）、差（）；（5）答辯分析（20 分）：優(yōu)（）、良（）、中（）、一般（）、差（）；（6）格式規(guī)范性及考勤是否降等級：是（）、否（）目錄一、需求分析1二、概要設計2三、詳細設計5四、調試分析及測試15五、個人工作及創(chuàng)新18六、小結19參考文獻20、需求分析1. 選題理由本次課設我選擇了迷宮問題，迷宮求解是數據結構課程的一個經典問題, 迷宮問題要求尋

4、找一條從入口到出口的路徑。通常用的是“窮舉求解” 的方法。為了保證在任何位置上都能原路退回，顯然需要用一個后進先出的 結構來保存從入口到當前位置的路徑。因此，在求解迷宮通路的算法中要應 用“?！钡乃枷搿τ跅５膬热菰谡麄€學期的學習中我也有了一定的了解， 所以選擇了迷宮這一經典問題作為本次課設的內容。2. 基本原理分析迷宮問題通常是用“窮舉求解”方法解決，即從入口出發(fā)，順著某一個 方向進行探索，若能走通，則繼續(xù)往前走；否則沿著原路退回，換一個方向 繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而 未能到達出口，則所設定的迷宮沒有通路。棧是一個后進先出的結構，可以 用來保存從入口

5、到當前位置的路徑。以二維數組存儲迷宮數據，通常設定入口點的下標為（1，1），出口點的 下標為（n,n）。為處理方便起見，在迷宮的四周加一圈障礙。對于迷宮任何 一個位置，均約定東、南、西、北四個方向可通。3. 功能要求（1）以一個二維數組Mazem+2n+2表示迷宮，其中：MazeOj和 Mazem+1j（0=j=n+1）及 MazeiO和 Mazein+1 （0=i=m+1）為做 外層的一圈障礙。數組中以0表示通路，1表示障礙，限定迷宮的大小為： m,n=0 數據關系：R1=| aiT, ai WD,i=2, n 基本操作：InitStack(&S)操作結果：構造一個空棧SoDestroySt

6、ack(&S) 初始條件：棧S已存在。 操作結果：銷毀棧S。ClearStack(&S) 初始條件：棧S已存在。操作結果：將S清為空棧。StackLength(S) 初始條件：棧S已存在。 操作結果：返回棧S的長度。StackEmpty(S)初始條件：棧S已存在。操作結果：若S為空棧，則返回TRUE,否則返回FALSE。GetTop(S, &e) 初始條件：棧S已存在。 操作結果：若棧S不空，則以e返回棧頂元素。Push(&S, e) 初始條件：棧S已存在。 操作結果：在棧S的棧頂插入新的棧頂元素e。Pop(&S, &e) 初始條件：棧S已存在。 操作結果：刪除S的棧頂元素，并以e返回其值。S

7、tackTraverse (S, visit () 初始條件：棧S已存在。操作結果：從棧底到棧頂依次對S中的每個元素調用函數visit ()。 ADT Stack(2)迷宮的抽象數據類型ADT maze數據對象：D=ai,j| ai,j e *,0二i二m+1,0二j二n+l,m,n=10數據關系：R=ROW,COL基本操作：InitM aze( &M ,a,row,col)初始條件：二維數組arow+2col+2已存在，其中自第1行至第row+1 行，每行中自第1列至第col+1列的元素已有值，并且以值0表示通路，以 值1表示障礙。操作結果：構成迷宮的字符型數組，以空白字符表示通路，以字符#

8、 表示障礙，并在迷宮四周加上一圈障礙。MazePath(&M)初始條件：迷宮M已被賦值。操作結果：若迷宮M中存在一條通路，則按以下規(guī)定改變迷宮M的狀態(tài): 以字符*表示路徑上的位置，字符表示“死胡同”，否則迷宮的狀 態(tài)不變。PrintMaze (M)初始條件：迷宮M已存在。操作結果：以字符形式輸出迷宮。 ADT maze2、整體框架 本程序包含三個模塊(1) 棧模塊一一實現棧抽象數據類型(2) 迷宮模塊一一實現迷宮抽象數據類型(3) 主程序模塊： void mian()初始化； Do 接受命令； 處理命令； while(命令!= “退出”)； 各模塊之間的調用關系如圖一:主程序模塊挫宮權塊棧模塊

9、圖一：調用關系圖主稈序InitMaze MazePath PrintMaze函數的調用關系圖反映了程序的層次結構如圖二:InitializationRcadCcmma ti dlnitStack Push Pop StnckEmpty StackTraverseFootPrint MarkPrint Pass NextPos Same圖二-:函數的調用關系圖三、詳細設計源程序：#include #include #include #define MAXLEN 10/迷宮包括外墻最大行列數目#define TRUE 1#define FALSE 0#define OK 1#define ERRO

10、R 0typedef int Status;/坐標位置類型typedef structint r,c; PosType;/迷宮中r行c列的位置/迷宮類型typedef struct int r;int c;char arrMAXLENMAXLEN;/可取， MazeType;typedef struct/int st ep; /當前位置在路徑上的“序號”PosType sea t; /當前的坐標位置 int di; /往下一坐標位置的方向 SElemType;/結點類型typedef struct NodeTypeSElemType data;NodeType *next;NodeType ,

11、*LinkType;/棧類型typedef struet LinkType top; int staeksize;SqStack;PosType start;PosType end;MazeType maze;bool found;/創(chuàng)建棧Status InitStack(SqStack &S)S.to p=(LinkType)malloc(sizeof(NodeType);S.to p-nex t二N ULL;S.s tacksize=O; return OK;/進棧Status Push(SqS tack & S,SElemType &e)LinkType p; p=(NodeType*)

12、malloc(sizeof(NodeType); p-data二e;p-nex t二S.top;S.to p=p;S.s tacksize+; return OK;/判斷是否為?？誗tatus StackEmpty(SqStack S)if(S .top-next二二NULL) return OK; return ERROR;/出棧Status Pop(SqStack &S,SElemType &e)LinkType p;if(StackEmpty(S) return ERROR; p=S .top;e=p-data;S.to p=S .to p-nex t;S.stacksize-; fre

13、e(p);return OK;/銷毀棧Status DestroyStack(SqStack &S)LinkType p;while(S. top!二NULL)p=S .top;S.to p=S .to p-nex t; free(p);/一個一個刪除if(S.top二二NULL) return OK; else return ERROR;/曾走過但不是通路標記并返回OKStatus MarkPrint(MazeType &maze,PosType curpos)maze.arrcurpos.rcurpos.c=;/ 表示曾走過但不通 return OK; /曾走過而且是通路標記并返回OKSt

14、atus FootPrint(MazeType &maze,PosType curpos) maze.arrcurpos.rcurpos.c二* ;/*表示可通 return OK;/選擇下一步的方向PosType NextPos(PosType &curpos,int i)PosType cpos;epos二curpos;分別表示東，南,西,北方向case 1 : cpos.c+=1;break;case 2 : cpos.r+=1; break;case 3 : cpos.c=l; break;case 4 : cpos.r=1; break;return cpos;/判斷當前位置是否可通

15、Status Pass(MazeType &maze, PosType curpos) if(maze.arrcurpos.rcurpos.c二二)return TRUE;else return FALSE;/創(chuàng)建迷宮/按照用戶輸入的二維數組(0或1),設置迷宮maze的初值，包括加上 邊緣一圈的值void InitMaze(MazeType &maze, char aMAXLENMAXLEN, int row, int col)maze.r二row;maze.c二col;for(int i=0;i二col+l;i+) a0i=1; arow+1i=1; for(i=0;i=row+1;i+)

16、ai0=1; aicol+1=1; for(i=0;i=maze.r+2;i+) for(i nt j=0;jmaze.c+2;j+)if(aij=1) maze.arrij二#; else maze.arrij二; /求迷宮路徑的偽碼算法：Status MazePath(MazeType &maze,PosType start ,PosType end) /求解迷宮maze中，從入口 start到出口 end的一條路徑，若存在，返 回TRUE,否則返回FALSEPosType curpos;SqStack S;SElemType e;InitSt ack(S);curpos二s tart;

17、/設定“當前位置為“入口位置/curs tep=l; /探索第一步found二false;doif(Pass(maze,curpos)/當前位置可以通過，即是未曾走到過的通道塊留下足跡 Foo tPrin t( maze,curpos);/做可以通過的標識/e.s tep二curs tep;e.sea t二 curpos;e.di=l;/為棧頂元素賦值Push(S,e); /加入路徑if(curpos.r二二end.r & curpos.c二二end.c) found 二t rue;/如果到達 終點返回trueelsecurpos二Nex tPos(curpos,l);/下一位置是當前位置的東

18、鄰 else/當前位置不能通過if(!S tackEmp ty (S)Pop(S,e);while(e.di=4 & !St ackEmp ty (S)MarkPrin t(maze,e.sea t);/留下不能通過的標記Pop(S,e);if(e.di=2)if(ncnum)m+;n=l;a2mn=da tai;n+;i+;fclose(fp);InitM aze(maze, a2, rnum, cnum);printf(n迷宮建立完成！ n);break;case m :printf(n請輸入迷宮入口的坐標，以空格為間隔:一); scanf(%d %d，&start.r,&start .c

19、);printf(n請輸入迷宮出口的坐標，以空格為間隔:一); scanf(%d %d，& end.r，& end.c);MazePa th(maze, start, end);break;case p :if(found)printf(n求解迷宮的結果如下-n);Pri ntM aze(maze);else printf(n 找不到路徑！ n);void main()char cmd;Initi aliza tion();doReadCommand(cmd);Int erpre(cmd); while(cmd!二q); /讀入一個操作符命令/解釋執(zhí)行命令操作符調試分析及測試1、調試分析：(1

20、) 本程序有一個核心算法，即求迷宮的路徑，在調試的時候，出現了 兩個問題：沒有想到要用記號，導致迷宮走不出來；沒有設置found,不知何時跳出。(2) 原本棧的元素e中除了 di往下一坐標位置的方向和seat當前 的坐標位置，還有一個step當前位置在路徑上的序號，后來發(fā)現step沒什 么用，就刪掉了。(3) 函數ReadCommand中，cmd=getchar();的位置找不準，最后是試出 來的。(4) 調試的時候多次出現，沒有錯誤，但是dos環(huán)境下就是執(zhí)行不起來, 所以采用了一些輸出變量，判斷到底是哪里出了問題。(5) 本程序中三個主要的算法：InitMaze, MazePath和Mark

21、Print的時 間復雜度均為O (m*n),本程序的空間復雜度也為O (m*n)(棧所占最大空 間)(1)2、使用說明和運行結果:亠11】11宀11】亠11】111 1ILO ,u. iI 1首先以文件形式輸入迷宮數據，如圖三:rll.txt -記事本1 =回 ld文徉(E 鋸 梧式回 w(v)幫助(to圖三(2) 進入演示程序后，會出現以下界面如圖四: gUserstoshibaDesktop已經完成的作業(yè)遨曇制切設Debtigl.exe = I 回圖四(3) 進入“創(chuàng)建迷宮”的命令后，即提示輸入迷宮數據的文件名，結束 符為“回車符，該命令執(zhí)行之后輸出“迷宮建立完成，且輸出下面可執(zhí) 行的操作

22、。如圖五：圖五(4) 進入“執(zhí)行迷宮”的命令后，即提示輸入迷宮入口，出口的坐標， 結束符為“回車符”，該命令執(zhí)行之后表示迷宮路徑已尋找完成或未找到路 徑。請注意：若迷宮中存在路徑，執(zhí)行此命令后，迷宮狀態(tài)已經改變，若要 重復執(zhí)行此命令，需重新輸入迷宮數據。如圖六：圖六(5) 進入“輸出迷宮”的命令后，即輸出迷宮求出路徑之后的狀態(tài)。# 表示障礙，表示曾走過但不通，*表示路徑。如圖七：圖七(6) 進入“退出”的命令后，按任意鍵結束。如圖八:圖八3、缺點與改進：(1) 在定義函數Mazepa th的時候，開始的循環(huán)語句的結束條件不對， 沒有出路時，導致一直出現了不正確的結果，最后沒有新位置入棧，則返回

23、 上一個位置，否則沒有路徑。(2) 只是以文件形式輸入迷宮，如果迷宮數據量大時，要先建好文件 還是很浪費時間，如果以隨機產生函數自動產生迷宮會更好。五、個人工作及創(chuàng)新為了準備這次課程設計我查找了很多的資料，對于迷宮問題的求解中迷 宮的產生方式有很多的不同，有的是直接輸入迷宮，有的是用文件輸入，有 的是隨機函數產生，我的課設是參考了用文件輸入的方法，這樣做相比直接 輸入迷宮操作要更簡單。當然用隨機函數產生迷宮比如用：for (i = 0; i MAX_R0W; i+)for(j = 0; j MAX_COL; j+) mazeij = (int) (rand() % 2);mazel0 = 1;

24、 /* start poi nt */mazeMAX_ROW - 1MAX_COL - 2 = 1; /* end point */ 這樣產生迷宮要更加的方便。結果也有不確定性，可能可以有通路也可能沒 有。對于迷宮的求解都是采用的“窮舉求解”的方法，用到了一些棧的知識。 把以前學過的棧的基本操作實際應用了一番也使有了更加清楚的認識。在求解迷宮的算法中，先設定當前位置的初值為入口位置，然后Do若當前位置可通，則將當前位置插入棧頂；若該位置是出口位置，則結束；否則切換當前位置的東鄰方塊為新的當前位置；否則若棧不為空且棧頂位置尚有其它方向未被探索，則設定新的當前位置為延順時針方向旋轉找到的棧頂位置的

25、下 一相鄰塊；若棧不空但棧頂位置四周均不通，則刪去棧頂位置；若棧不為空，則重新測試新的棧頂位置，直至找到一個可通的相鄰塊或出棧至棧空；求解迷宮的算法大概就是這么個思路。六、小結要能很好的掌握編程，僅僅通過幾個簡單的程序的編寫是無法達成的， 更需要的是大量的積累和深入研究才可能。在程序的編寫中也不能一味的向 已有的程序進行模仿，而要自己去探索，去尋找最好的解決方法，只有帶著 問題去反復實踐，才能更熟練的掌握和運用，當然，對現有的程序也要多去 接觸，因為有些程序是我們在短時間內無法想出來的，我們也應該去參考別 人的作品，這樣可以節(jié)約時間獲得更多的知識。最重要的是持之以恒，要經 常性的復習原來接觸到的程序，這樣才能保證我們有足夠的經驗去面對程序 問題。參考文獻1 .嚴蔚敏，吳偉民數據結構（C語言版）清華大學出版社.20072 .嚴蔚敏，數據結構題集（C語言版）清華大學出版社.20073 .譚浩強，C程序設計（第四版）清華大學出版社.2007