1、課程設計（論文）題目名稱迷宮求解課程名稱學生姓名學號系、專 業 信息工程系、電氣信息類（信息類）指導教師申壽云2010年1月3日摘要設計一個簡單迷宮程序，從入口出發找到一條通路到達出口。編制程序給 出一條通過迷宮的路徑或報告一個“無法通過”的信息。首先實現一個以鏈表作存儲結構的棧類型，然后編寫一個求解迷宮的非遞 歸程序。用“窮舉求解”方法，即從入口出發，順著某一個方向進行探索，若 能走通，則繼續往前進；否則沿著原路退回，換一個方向繼續探索，直至出口 位置，求得一條通路。假如所有可能的通路都探索到而未能到達出口，則所設 定的迷宮沒有通路。可以用二維數組存儲迷宮數據，通常設定入口點的下標為(1 ,

2、 1),出口點的下標為(n , n)。為處理方便起見，可在迷宮的四周加一 障礙。對于迷宮任一位置，均可約定有東、南、西、北四個方向可通。 關鍵詞：迷宮；棧；鏈表；二維數組目錄1 問題描述 12 需求分析 13 概要設計 131 抽象數據類型定義 132 模塊劃分 24 詳細設計 241 數據類型的定義 242 主要模塊的算法描述 35 測試分析 66 課程設計總結 7參考文獻 7附錄（源程序清單） 91 問題描述迷宮是一個 M 行 N 列的 0-1 矩陣，其中 0 表示無障礙， 1 表示有障礙。 設入口為 （1 ，1）出口為 （M，N） 每次移動只能從一個無障礙的單元移到其周圍8個方向上任一無

3、障礙的單元，編制程序給出一條通過迷宮的路徑或報告一個 “無法通過”的信息。2 需求分析（1）首先實現一個以鏈表作存儲結構的棧類型，然后編寫一個求解迷宮的非遞歸程序。求得的通路以三元組（i, j, d ）的形式輸出，其中：（i, j）指示 迷宮中的一個坐標， d 表示走到下一坐標的方向。否則報告一個無法通過的信 息。（ 2）建立 InitStack 函數，用于構造一個空棧。（ 3 ）建立 DestroyStack 函數，用于銷毀棧。（ 4）建立 Pop 函數，用于刪除棧頂元素，返回棧頂元素的值。（ 5）建立 Push 函數，用于插入新的棧頂元素。（ 6 ）建立 NextPos 函數，用于定位下一

4、個位置。3 概要設計3 1 抽象數據類型定義（ 1 ）棧的抽象數據類型定義 InitStack（ LStack *S ） 操作結果：構造一個空棧 S。DestroyStack（ LStack *S ） 操作結果：棧 S 被銷毀。Pop（ LStack *S ， ElemType *e ）操作結果：刪除S的棧頂元素。用e返回棧頂元素的值。若棧為空則返回Push( LStack *S ， ElemType e )操作結果：在棧頂之上插入元素 e 為新的棧頂元素。若棧 S 為空棧，則返 回 0 。（2）迷宮的抽象數據類型定義NextPos（unsigned *x ，unsigned *y ， sho

5、rt di） 操作結果：找到下一個位置。3 2 模塊劃分本程序包括三個模塊：（ 1）主程序模塊void main（）初始化；構造迷宮；迷宮求解；迷宮輸出；（ 2）棧模塊實現棧的抽象數據類型（ 3）迷宮模塊實現迷宮的抽象數據類型4 詳細設計4 1 數據類型的定義（1）迷宮類型typedef struct unsigned ord, x, y ；short di ； ElemType ；unsigned x, y, curstep,i=0 ；char maze1010 ；（2）棧類型typedef struct Node ElemType data ；struct Node* next Node,

6、 *L in kList;typedef struct Lin kList top ; un sig ned len gth LStack ;LinkList q ;LStack S,T ;ElemType e ;4. 2主要模塊的算法描述 4.1函數尋找下一個位置流程圖此函數的功能是尋找下一個位置。 首先判斷di的值，如果di=1，指針x+， 退出。如果di=2，指針y+，退出。如果di=3，指針x-，退出。如果di=4， 指針y-，退出。如果di為其它值，則直接退出。見圖 4.1 0結束圖4.1函數尋找下一個位置流程圖4.2函數銷毀棧流程圖此函數的功能是銷毀棧，首先建立單鏈表q，判斷top

7、指針是否為空，若為空則釋放s的空間，否則出棧，直到top指針為空，釋放s的空間。見圖 4.2LinkList q ；出棧;釋放棧s的空間;圖4.2函數銷毀棧流程圖4.3函數出棧流程圖此函數的功能是出棧。 首先建立單鏈表q ,如果棧s為空則返回0,若棧s 不為空，則出棧，修改指針。返回1。見圖4.3 oLinkList q ;Retqrn 0;4 1/ 21出棧;Retur n 1 ;圖4.3函數出棧流程圖4.4函數入棧流程圖此函數的功能是入棧。首先在鏈表中生成結點p，判斷p是否為空。若為空則返回0，若非空，則入棧，修改指針，返回0。見圖4.4 o生成結點p;Retur n 0;入棧;Retur

8、 n 1 ;圖4.4函數入棧流程圖4.5主函數流程圖主函數實現了求解迷宮，首先建立棧s和t，輸出迷宮圖形，然后探索路徑，實現迷宮求解，最后輸出出迷宮順序。如果有完整路徑則輸出完整路徑， 如果沒有完整路徑則輸出無法通過信息。見圖4.5 o圖4.5主函數流程圖5測試分析(1 )有一條完整路徑通過迷宮的測試數據與結果。見圖5.1圖5.1有一條完整路徑通過迷宮的測試數據與結果從入口出發，順著某一個方向進行探索，若能走通，則繼續往前進；否則 沿著原路退回，換一個方向繼續探索，直至出口位置，求得一條通路。輸出通 路的坐標，即出迷宮的順序。(2) 沒有路徑能通過迷宮的測試數據與結果。見圖5.2 o5.2沒有

9、路徑能通過迷宮的測試數據與結果從入口出發，順著某一個方向進行探索，若能走通，則繼續往前進；否則 沿著原路退回，換一個方向繼續探索，直至前面沒有路徑。輸出此時無法通過, 沒有能夠通過迷宮的路徑的信息！6課程設計總結通過這次課程設計使我充分的理解了用棧實現迷宮問題的基本原理，知道 了棧存儲結構的定義和算法描述，同時也學會了編寫簡單的迷宮問題的程序。 雖然此次的程序不是很完備，但是總體還是一個比較能體現數據結構知識點能 力的程序了，當然只是相對于我這個初學者來說。在剛幵始編程的時候，錯誤 百出，不知道怎么樣改正，但是通過自己的仔細的分析和老師的細心的指導， 在認真分析了原程序后，終于認識并理解了自己

10、錯誤的地方， 使自己加以改正, 汲取教訓。為以后知識水平的提高，做了最好的準備。在此我非常要感謝的是我們的指導老師申壽云老師，同時也要感謝我們的 成婭輝老師平時上課的教導，和編程時細心認真的輔導，教給我許多知識。這 次課程設計能夠順利的完成，當然有我個人的努力，但同時更離不幵指導老師 的答疑解惑。參考文獻1 黃同成，黃俊民，董建寅數據結構 M 北京：中國電力出版社， 20082 董建寅，黃俊民，黃同成數據結構實驗指導與題解 M 北京：中國電 力出版社， 20083 嚴蔚敏，吳偉民.數據結構（C語言版）M.北京：清華大學出版社，20024 劉振鵬，張曉莉，郝杰數據結構 M 北京：中國鐵道出版社，

11、 2003附錄（源程序清單）#include <stdio.h> #include <stdlib.h> typedef struct unsigned ord ，x，y； /* 通道塊在路徑上的序號和在迷宮中的坐標位置*/short di ； /* 從此通道塊走向下一通道塊的“方向” */ ElemType ；typedef struct Node /* 定義單鏈表 */ElemType data ；struct Node* next Node ， *LinkList ； typedef struct LinkList top ； unsigned length/*

12、定義鏈棧結構 */* 棧頂指針 */* 棧中元素個數 */ LStack ；void DestroyStack( LStack *S ) /*銷毀棧 */ LinkList q ；while ( S->top ) q = S->top ；S->top = S->top->next ； /* 修改棧頂指針 */ free( q ) ； /* 釋放被刪除的結點空間 */S->length = 0 ；void InitStack( LStack *S ) /*構造空棧 */S->top = NULL ； /* 棧頂指針初值為空 */S->length

13、= 0 ； /* 空棧中元素個數為 0 */int Pop( LStack *S ， ElemType *e ) /* 若棧不空，則刪除 S 的棧頂元素，用 e 返回棧頂元素的值。 */ LinkList q ；if ( ！S->top ) return 0 ；*e = S->top->data ； /* 返回棧頂元素 */q = S->top ；S->top = S->top->next ； /* 修改棧頂指針 */-S->length ； /* 棧的長度減 1 */free( q ) ； /* 釋放被刪除的結點空間 */ return 1 ；

14、int Push( LStack *S ， ElemType e ) /* 在棧頂之上插入元素 e 為新的棧頂元素 */LinkList p = malloc( sizeof *p )； /* 建新的結點 */if (！p ) return 0 ； /* 存儲分配失敗 */* 鏈接到原來的棧頂 */* 移動棧頂指針 */* 棧的長度增 1 */， unsigned * ， short) ； /* 定位下一個位置 */p->data = e ； p->next = S->top S->top = p ； +S->length ； return 1 ；void Nex

15、tPos(unsigned * int main( void )LStack S ，T；unsigned x ，y， curstep ，i=0 ；/* 迷宮坐標，探索步數 */ElemType e ；char maze1010 = '#''#' ，'#' ，'#''#' ， '#' ， '#' ， '#''#'，'#'，'#'，'#'，'#' ，'#'' '

16、，'#' ，'，'#'，' ' ，'#' ，'#'， '#' ， '#'，'#' ，'#''#' ，'#' ，'#'，'#' ，'#'，'#'，'#' ，'#' ，' '，'#'，'#'，'#' ，'#''#' ， '

17、;#' ， '#' ， '#' ， '#''#'，' ' ， '#' ，'#' ，'#' ，'#' ，'#' ， '#' ，'#' ，'#' ，'#' ，'#' ，'#' ，'#' ，' ' ， '#' ， ；InitStack(&S) ；InitStack(&T) ；p

18、rintf(" 迷宮圖形， # 號代表墻壁，空格代表通路： n") ；for ( x = 0 ； x < 10 ； x+) for ( y = 0 ； y < 10 ； y+ ) printf("%c" ， mazexy) ；printf("n") ；x = 1 ； /*迷宮起點 */y = 0 ；curstep = 1 ； /* 探索第一步 */do /* 進入迷宮 */if ( mazeyx = ' ' ) /* 如果當前位置可以通過 */ mazeyx = '1' ； /* 留下足跡

19、*/ e.x = x ； e.y = y ； e.di = 1 ； e.ord = curstep ；if ( ！Push(&S ，e) ) /* 加入路徑，即壓棧 */fprintf( stderr ，"內存不足。 n" ) ；if ( x = 8 && y = 9 ) /*到達終點 */break ；NextPos(&x, &y, 1) ； /* 下一位置是當前位置的東鄰 */ curstep+ ；else /* 如果當前位置不能通過 */if (S.length ！=0) Pop(&S ，&e) ； while

20、(e.di = 4 && S.length!=0) mazee.ye.x = '0' ； /* 留下不能通過足跡 */ Pop(&S, &e) ； /* 退回一步，即出棧 */if (e.di < 4) e.di+ ；if ( ！Push(&S ，e) ) /* 加入路徑，即壓棧 */ fprintf( stderr ，"內存不足。 n" ) ；x = e.x ； /* 重置坐標 */y = e.y ； NextPos(&x ， &y ， e.di) ； /* 尋找下一位置 */ while (S

21、.length ！ =0) ；printf(" 走出迷宮路線， 1 代表走過的路， 0 代表試探過的路徑 n") ； for ( x = 0 ； x < 10 ； x+ ) for ( y = 0 ； y < 10 ； y+ ) printf("%c" ， mazexy) ；n") ；， T.top->data.y ，定位下一個位置 */break ；if(mazexy='1')i+ ；printf("n") ；for(x=0 ； x<i ；x+) Pop(&S ， &

22、e) ；Push(&T ， e) ；printf("出迷宮順序，(X坐標，Y坐標，前進方向)：while(T.length ！ =0) printf("(%d ， %d ， %d)t"， T.top->data.xT.top->data.di) ；Pop(&T ， &e) ；DestroyStack(&S) ；getchar() ；return 0 ；void NextPos(unsigned *x ， unsigned *y ， short di) /*switch (di) case 1 ：+(*x) ； break

23、 ；case 2 ：+(*y) ； break ；case 3 ：-(*x) ； break ；case 4 ：-(*y) ； break ；default ：邵陽學院課程設計（論文）任務書年級專業2008級電氣信息類（信息 類）4班學生 姓名學 號題目 名稱求解迷宮問題設計 時間2009.12.21-2010.1.3課程名稱數據結構課程 設計課程編號131301302設計地點新實驗樓四樓機房一、課程設計（論文）目的學生在教師指導下運用所學課程的知識來研究、解決 些具有 定綜合性問題的專業課題。通過課程設計（論文），提高學生綜合運用所學知識來解決 實際問題、使用文獻資料、與進行科學實驗或技術設計的初步能力，為畢業 設計（論文）打基礎。二、已知技術參數和條件三、任務和要求迷宮是一個M行N列的0-1矩陣，其中0表示無障礙，1表示有障礙 設入口為（1，1）出口為（M , N ）每次移動只能從一個無障礙的單元移到 其周圍8個方向上任一無障礙的單元，編制程序給出一條通過迷宮的路徑或 報告一個“無法通過”的信息。注：1 .