數(shù)據(jù)結構課程設計--求解迷宮問題

上傳人：奔*** IP屬地：河北更新時間：2024-04-02 格式：doc 頁數(shù)：17 大小：230.00KB 人氣指數(shù)：12 舉報 版權申訴

已閱讀1頁，還剩16頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、　　課程設計(論文)　　題目名稱迷宮求解 　　課程名稱數(shù)據(jù)結構課程設計 　　學生姓名

2、 　　學號 　　系、專業(yè) 信息工程系、電氣信息類（信息類） 　　指導教師 　　2010年 1 月 3

3、日　　摘要　　設計一個簡單迷宮程序，從入口出發(fā)找到一條通路到達出口。編制程序給出一條通過迷宮的路徑或報告一個“無法通過”的信息。　　首先實現(xiàn)一個以鏈表作存儲結構的棧類型，然后編寫一個求解迷宮的非遞歸程序。用“窮舉求解”方法，即從入口出發(fā)，順著某一個方向進行探索，若能走通，

4、則繼續(xù)往前進；否則沿著原路退回，換一個方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達出口，則所設定的迷宮沒有通路?？梢杂枚S數(shù)組存儲迷宮數(shù)據(jù)，通常設定入口點的下標為（1，1），出口點的下標為（n，n）。為處理方便起見，可在迷宮的四周加一障礙。對于迷宮任一位置，均可約定有東、南、西、北四個方向可通。　　關鍵詞：迷宮；棧；鏈表；二維數(shù)組<

5、p>　　目錄　　1 問題描述1　　2 需求分析1　　3 概要設計1　　3．1抽象數(shù)據(jù)類型定義1<

6、/p>　　3．2模塊劃分2　　4 詳細設計2　　4．1數(shù)據(jù)類型的定義2　　4．2主要模塊的算法描述3　　5 測試分析6&

7、lt;/p>　　6 課程設計總結7　　參考文獻8　　附錄（源程序清單）9　　1 問題描述　　迷宮是一個M行N列的0-1矩陣，其中0表示無障礙，1表示有障礙。設入口

8、為(1，1)出口為(M，N)每次移動只能從一個無障礙的單元移到其周圍8個方向上任一無障礙的單元，編制程序給出一條通過迷宮的路徑或報告一個“無法通過”的信息。　　2 需求分析　　（1）首先實現(xiàn)一個以鏈表作存儲結構的棧類型，然后編寫一個求解迷宮的非遞歸程序。求得的通路以三元組（i，j，d）的形式輸出，其中：（i，j）指示

9、迷宮中的一個坐標，d表示走到下一坐標的方向。否則報告一個無法通過的信息。　?。?）建立InitStack函數(shù)，用于構造一個空棧。　?。?）建立DestroyStack函數(shù)，用于銷毀棧。　?。?）建立Pop函數(shù)，用于刪除棧頂元素，返回棧頂元素的值。　?。?）建立Push函數(shù)

10、，用于插入新的棧頂元素。　?。?）建立NextPos函數(shù)，用于定位下一個位置。　　3 概要設計　　3．1抽象數(shù)據(jù)類型定義　?。?）棧的抽象數(shù)據(jù)類型定義　　InitStack( LStack *

11、S )　　操作結果：構造一個空棧S。　　DestroyStack( LStack *S )　　操作結果：棧S被銷毀。　　Pop( LStack *S，ElemType *e )　　操作結果：刪除S的棧頂元素。用e返回棧頂元素的值。

12、若棧為空則返回0。　　Push( LStack *S，ElemType e )　　操作結果：在棧頂之上插入元素e為新的棧頂元素。若棧S為空棧，則返回0。　?。?）迷宮的抽象數(shù)據(jù)類型定義　　NextPos(unsigned *x，unsigned *y，short di)&

13、lt;/p>　　操作結果：找到下一個位置。　　3．2模塊劃分　　本程序包括三個模塊：　?。?）主程序模塊　　void main()<p&g

14、t;　　{　　初始化；　　構造迷宮；　　迷宮求解；　　迷宮輸出；

15、;　　}　　（2）棧模塊——實現(xiàn)棧的抽象數(shù)據(jù)類型　?。?）迷宮模塊——實現(xiàn)迷宮的抽象數(shù)據(jù)類型　　4 詳細設計　　4．1數(shù)據(jù)類型的定義

16、　?。?）迷宮類型　　typedef struct {　　unsigned ord, x, y；　　short di；　　} ElemType；　　uns

17、igned x, y, curstep,i=0；　　char maze[10][10]；　?。?）棧類型　　typedef struct Node { 　　ElemType data；　　st

18、ruct Node* next；　　} Node, *LinkList；　　typedef struct {　　LinkList top；　　unsigned length；　　} LStack；</b&g

19、t;　　LinkList q；　　LStack S,T；　　ElemType e；　　4．2主要模塊的算法描述　　4.1函數(shù)尋找下一個位置流程圖　　此函數(shù)的功能是尋找下一個位置。首先判斷d

20、i的值，如果di=1，指針x++，退出。如果di=2，指針y++，退出。如果di=3，指針x--，退出。如果di=4，指針y--，退出。如果di為其它值，則直接退出。見圖4.1。　　圖4.1 函數(shù)尋找下一個位置流程圖　　4.2 函數(shù)銷毀棧流程圖　　此函數(shù)的功能是銷毀棧，首先建立單鏈表q，判斷top指針是否為空，

21、若為空則釋放s的空間，否則出棧，直到top指針為空，釋放s的空間。見圖4.2。　　圖4.2 函數(shù)銷毀棧流程圖　　4.3 函數(shù)出棧流程圖　　此函數(shù)的功能是出棧。首先建立單鏈表q，如果棧s為空則返回0，若棧s不為空，則出棧，修改指針。返回1。見圖4.3。　　圖4.3 函數(shù)出

22、棧流程圖　　4.4 函數(shù)入棧流程圖　　此函數(shù)的功能是入棧。首先在鏈表中生成結點p，判斷p是否為空。若為空則返回0，若非空，則入棧，修改指針，返回0。見圖4.4。　　圖4.4 函數(shù)入棧流程圖　　4.5 主函數(shù)流程圖　　主函數(shù)實現(xiàn)了求

23、解迷宮，首先建立棧s和t，輸出迷宮圖形，然后探索路徑，實現(xiàn)迷宮求解，最后輸出出迷宮順序。如果有完整路徑則輸出完整路徑，如果沒有完整路徑則輸出無法通過信息。見圖4.5。　　圖4.5 主函數(shù)流程圖　　5 測試分析　?。?）有一條完整路徑通過迷宮的測試數(shù)據(jù)及結果。見圖5.1。<

24、;/p>　　圖5.1 有一條完整路徑通過迷宮的測試數(shù)據(jù)及結果　　從入口出發(fā)，順著某一個方向進行探索，若能走通，則繼續(xù)往前進；否則沿著原路退回，換一個方向繼續(xù)探索，直至出口位置，求得一條通路。輸出通路的坐標，即出迷宮的順序。　?。?）沒有路徑能通過迷宮的測試數(shù)據(jù)及結果。見圖5.2。　　圖

25、5.2 沒有路徑能通過迷宮的測試數(shù)據(jù)及結果　　從入口出發(fā)，順著某一個方向進行探索，若能走通，則繼續(xù)往前進；否則沿著原路退回，換一個方向繼續(xù)探索，直至前面沒有路徑。輸出此時無法通過，沒有能夠通過迷宮的路徑的信息！　　6 課程設計總結　　通過這次課程設計使我充分的理解了用棧實現(xiàn)迷

26、宮問題的基本原理，知道了棧存儲結構的定義和算法描述，同時也學會了編寫簡單的迷宮問題的程序。雖然此次的程序不是很完備，但是總體還是一個比較能體現(xiàn)數(shù)據(jù)結構知識點能力的程序了，當然只是相對于我這個初學者來說。在剛開始編程的時候，錯誤百出，不知道怎么樣改正，但是通過自己的仔細的分析和老師的細心的指導，在認真分析了原程序后，終于認識并理解了自己錯誤的地方，使自己加以改正，汲取教訓。為以后知識水平的提高，做了最好的準備。&l

27、t;p>　　在此我非常要感謝的是我們的指導老師申壽云老師，同時也要感謝我們的成婭輝老師平時上課的教導，和編程時細心認真的輔導，教給我許多知識。這次課程設計能夠順利的完成，當然有我個人的努力，但同時更離不開指導老師的答疑解惑。　　參考文獻　　[1] 黃同成，黃俊民，董建寅．數(shù)據(jù)結構[M]．北京：中國電力出版社，2

28、008　　[2] 董建寅，黃俊民，黃同成．數(shù)據(jù)結構實驗指導與題解[M]．北京：中國電力出版社，2008　　[3] 嚴蔚敏，吳偉民. 數(shù)據(jù)結構（C語言版）[M]. 北京：清華大學出版社，2002　　[4] 劉振鵬，張曉莉，郝杰．數(shù)據(jù)結構[M]．北京：中國鐵道出版社，2003

29、　　附錄（源程序清單）　　#include <stdio.h>　　#include <stdlib.h>　　typedef struct {　　unsigned ord，x，y；/*通道塊在路徑上的序號和在迷宮

30、中的坐標位置*/　　short di； /* 從此通道塊走向下一通道塊的“方向” */　　} ElemType；　　typedef struct Node { /* 定義單鏈表 */　　ElemType data；　　struct

31、 Node* next；　　} Node，*LinkList；　　typedef struct { /* 定義鏈棧結構 */　　LinkList top； /* 棧頂指針 */　　unsigned length； /* 棧中元素個數(shù) */<

32、/p>　　} LStack；　　void DestroyStack( LStack *S ) /* 銷毀棧 */　　{LinkList q；　　while ( S->top ) {　　q = S-&

33、gt;top；　　S->top = S->top->next； /* 修改棧頂指針 */　　free( q )；/* 釋放被刪除的結點空間 */　　}　　S->length = 0；&l

34、t;p>　　} 　　void InitStack( LStack *S ) /* 構造空棧 */　　{　　S->top = NULL； /* 棧頂指針初值為空 */　　S->

35、length = 0； /* 空棧中元素個數(shù)為 0 */　　} 　　int Pop( LStack *S，ElemType *e )　　{ /* 若棧不空，則刪除 S 的棧頂元素，用 e 返回棧頂元素的值。*/　　LinkLi

36、st q；　　if (！S->top ) {　　return 0；　　}　　*e = S->top->data； /* 返回棧頂元素 */

37、;　　q = S->top；　　S->top = S->top->next； /* 修改棧頂指針 */　　--S->length；/* 棧的長度減1 */　　free( q )；/* 釋放被刪除的結點空間 */　　retur

38、n 1；　　} 　　int Push( LStack *S，ElemType e )　　{ /* 在棧頂之上插入元素 e 為新的棧頂元素 */　　LinkList p = malloc( sizeof *p )；

39、 /* 建新的結點 */　　if (！p ) {　　return 0； /* 存儲分配失敗 */　　}　　p->data = e；　　p->next = S->top； /*

40、鏈接到原來的棧頂 */　　S->top = p； /* 移動棧頂指針 */　　++S->length； /* 棧的長度增1 */　　return 1；　　} &

41、lt;/p>　　void NextPos(unsigned *，unsigned *，short)； /* 定位下一個位置 */　　int main( void )　　{　　LStack S，T；　　uns

42、igned x，y，curstep，i=0；/* 迷宮坐標，探索步數(shù) */　　ElemType e；　　char maze[10][10] = {　　{'#'，' '，'#'，'#'，'#'，'#'，'#

43、9;，'#'，'#'，'#'}，　　{'#'，' '，' '，'#'，' '，' '，' '，'#'，' '，'#'}，　　{'#'

44、，' '，' '，'#'，' '，' '，' '，'#'，' '，'#'}，　　{'#'，' '，' '，' '，' '，'#'，'#'，&#

45、39; '，' '，'#'}，　　{'#'，' '，'#'，'#'，'#'，' '，' '，' '，' '，'#'}，　　{'#'，'

46、; '，' '，' '，'#'，' '，' '，' '，' '，'#'}，　　{'#'，' '，'#'，' '，' '，' '，'#'，' &

47、#39;，' '，'#'}，　　{'#'，' '，'#'，'#'，'#'，'#'，'#'，'#'，' '，'#'}，　　{'#'，'#

48、9;，' '，' '，' '，' '，' '，' '，' '，'#'}，　　{'#'，'#'，'#'，'#'，'#'，'#'，'#'，'#'，

49、' '，'#'}，　　}；　　InitStack(&S)；　　InitStack(&T)；　　printf("迷宮圖形，#號代表墻壁，空格代表通路：\n")；<

50、/p>　　for ( x = 0；x < 10；x++) {　　for ( y = 0；y < 10；y++ ) 　　printf("%c"，maze[x][y])；　　printf("\n")；<p&g

51、t;　　}　　x = 1； /*迷宮起點*/　　y = 0；　　curstep = 1； /* 探索第一步 */　　do { /* 進入迷宮 */　　i

52、f ( maze[y][x] == ' ' ) { /* 如果當前位置可以通過 */　　maze[y][x] = '1'；/* 留下足跡 */　　e.x = x；　　e.y = y；

53、　　e.di = 1；　　e.ord = curstep；　　if (！Push(&S，e) ) { /* 加入路徑，即壓棧 */　　fprintf( stderr，"內存不足。\n" )；

54、;　　}　　if ( x == 8 && y == 9 ) { /* 到達終點 */　　break；　　}　　NextPos(&x,

55、&y, 1)； /* 下一位置是當前位置的東鄰 */　　curstep++；　　} 　　else { /* 如果當前位置不能通過 */　　if (S.length！=0) {　　Pop

56、(&S，&e)；　　while (e.di == 4 && S.length!=0) {　　maze[e.y][e.x] = '0'； /* 留下不能通過足跡 */　　Pop(&S, &e)； /* 退回一步，即出棧 */&l

57、t;p>　　}　　if (e.di < 4) {　　e.di++；　　if (！Push(&S，e) ) { /* 加入路徑，即壓棧 */　　fprintf( stderr，&

58、quot;內存不足。\n" )；　　}　　x = e.x； /* 重置坐標 */　　y = e.y；　　NextPos(&x，&y，e.di)； /* 尋找下一位置 */

59、　　}　　}　　}　　} while (S.length！=0)；　　printf("走出迷宮路線，1代表

60、走過的路，0代表試探過的路徑\n")；　　for ( x = 0；x < 10；x++ ) {　　for ( y = 0；y < 10；y++ ) {　　printf("%c"，maze[x][y])；　　if(maze[x][y

61、]=='1')　　i++；　　}　　printf("\n")；　　}　　for(

62、x=0；x<i；x++)　　{Pop(&S，&e)；　　Push(&T，e)；　　}　　printf("出迷宮順序，（X坐標，Y坐標，前進方向）：\n")；&

63、lt;p>　　while(T.length！=0)　　{printf("(%d，%d，%d)\t"，T.top->data.x，T.top->data.y，T.top->data.di)；　　Pop(&T，&e)；　　}</b&

64、gt;　　DestroyStack(&S)；　　getchar()；　　return 0；　　}　　void NextPos(unsigned *

65、x，unsigned *y，short di) /* 定位下一個位置 */　　{　　switch (di) {　　case 1：++(*x)；break；　　case 2：++(*y)；break；<p&

66、gt;　　case 3：--(*x)；break；　　case 4：--(*y)；break；　　default：　　break；　　}

67、　　}　　課程設計（論文）任務書　　注：1．此表由指導教師填寫，經系、教研室審批，指導教師、學生簽字后生效；　　2．此表1式3份，學生、指導教師、教研室各1份。　　指導教師（簽字）：

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
6. 下載文件中如有侵權或不適當內容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

數(shù)據(jù)結構課程設計--求解迷宮問題

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結構課程設計--求解迷宮問題

文檔簡介

溫馨提示

最新文檔

評論

免費下載