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

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

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--求解迷宮問題_第1頁(yè)

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

版權(quán)說(shuō)明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、　　課程設(shè)計(jì)(論文)　　題目名稱迷宮求解 　　課程名稱數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 　　學(xué) 生姓名

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

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

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

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

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

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

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

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

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

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

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

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

14、t;　　{　　初始化；　　構(gòu)造迷宮；　　迷宮求解；　　迷宮輸出；

15、;　　}　?。?）棧模塊——實(shí)現(xiàn)棧的抽象數(shù)據(jù)類型　?。?）迷宮模塊——實(shí)現(xiàn)迷宮的抽象數(shù)據(jù)類型　　4 詳細(xì)設(shè)計(jì)　　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ù)尋找下一個(gè)位置流程圖　　此函數(shù)的功能是尋找下一個(gè)位置。首先判斷d

20、i的值，如果di=1，指針x++，退出。如果di=2，指針y++，退出。如果di=3，指針x--，退出。如果di=4，指針y--，退出。如果di為其它值，則直接退出。見圖4.1。　　圖4.1 函數(shù)尋找下一個(gè)位置流程圖　　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ù)的功能是入棧。首先在鏈表中生成結(jié)點(diǎn)p，判斷p是否為空。若為空則返回0，若非空，則入棧，修改指針，返回0。見圖4.4。　　圖4.4 函數(shù)入棧流程圖　　4.5 主函數(shù)流程圖　　主函數(shù)實(shí)現(xiàn)了求

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

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

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

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

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

28、008　　[2] 董建寅，黃俊民，黃同成．?dāng)?shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)與題解[M]．北京：中國(guó)電力出版社，2008　　[3] 嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）[M]. 北京：清華大學(xué)出版社，2002　　[4] 劉振鵬，張曉莉，郝杰．?dāng)?shù)據(jù)結(jié)構(gòu)[M]．北京：中國(guó)鐵道出版社，2003

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

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

31、 Node* next；　　} Node，*LinkList；　　typedef struct { /* 定義鏈棧結(jié)構(gòu) */　　LinkList top； /* 棧頂指針 */　　unsigned length； /* 棧中元素個(gè)數(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 )；/* 釋放被刪除的結(jié)點(diǎn)空間 */　　}　　S->length = 0；&l

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

35、length = 0； /* 空棧中元素個(gè)數(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；/* 棧的長(zhǎng)度減1 */　　free( q )；/* 釋放被刪除的結(jié)點(diǎn)空間 */　　retur

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

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

40、鏈接到原來(lái)的棧頂 */　　S->top = p； /* 移動(dòng)棧頂指針 */　　++S->length； /* 棧的長(zhǎng)度增1 */　　return 1；　　} &

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

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

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

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

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

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

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

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

49、' '，'#'}，　　}；　　InitStack(&S)；　　InitStack(&T)；　　printf("迷宮圖形，#號(hào)代表墻壁，空格代表通路：\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； /*迷宮起點(diǎn)*/　　y = 0；　　curstep = 1； /* 探索第一步 */　　do { /* 進(jìn)入迷宮 */　　i

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

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

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

55、&y, 1)； /* 下一位置是當(dāng)前位置的東鄰 */　　curstep++；　　} 　　else { /* 如果當(dāng)前位置不能通過 */　　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èi)存不足。\n" )；　　}　　x = e.x； /* 重置坐標(biāo) */　　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坐標(biāo)，Y坐標(biāo)，前進(jìn)方向）：\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) /* 定位下一個(gè)位置 */　　{　　switch (di) {　　case 1：++(*x)；break；　　case 2：++(*y)；break；<p&

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

67、　　}　　課程設(shè)計(jì)（論文）任務(wù)書　　注：1．此表由指導(dǎo)教師填寫，經(jīng)系、教研室審批，指導(dǎo)教師、學(xué)生簽字后生效；　　2．此表1式3份，學(xué)生、指導(dǎo)教師、教研室各1份。　　指導(dǎo)教師（簽字）：

眾賞文庫(kù)> 全部分類> 畢業(yè)設(shè)計(jì)

溫馨提示

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

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

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

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

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載