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

1、<p>　　計算機與信息工程學(xué)院</p><p><b>　　課程設(shè)計報告</b></p><p>　　課程名稱 《數(shù)據(jù)結(jié)構(gòu)》 </p><p>　　課題名稱 迷宮求解 </p><p>　　專業(yè) 計算機科學(xué)與技術(shù) </p

2、><p>　　班級 </p><p>　　學(xué)號</p><p>　　姓名 </p><p>　　聯(lián)系方式 </p><p>　　指導(dǎo)教師</p><p&g

3、t;　　2011年12月20日</p><p><b>　　目 錄</b></p><p>　　1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計任務(wù)書１</p><p><b>　　1.1、題目１</b></p><p><b>　　1.2、要求１</b></p><p&

4、gt;<b>　　2、總體設(shè)計１</b></p><p>　　2.1、功能模塊設(shè)計１</p><p>　　2.2、所有功能模塊的流程圖１</p><p><b>　　3、詳細設(shè)計１</b></p><p>　　3.1、程序中所采用的數(shù)據(jù)結(jié)構(gòu)及存儲結(jié)構(gòu)的說明１</p><

5、p>　　3.2、算法的設(shè)計思想２</p><p>　　3.3、稀疏矩陣各種運算的性質(zhì)變換２</p><p>　　4、調(diào)試與測試：２</p><p>　　4.1、調(diào)試方法與步驟：２</p><p>　　4.2、測試結(jié)果的分析與討論：３</p><p>　　4.3、測試過程中遇到的主要問題及采取的解決措施：

6、３</p><p>　　5、時間復(fù)雜度的分析：４</p><p>　　6、源程序清單和執(zhí)行結(jié)果４</p><p>　　7、C程序設(shè)計總結(jié)８</p><p><b>　　8、致謝８</b></p><p><b>　　9、參考文獻８</b></p>&

7、lt;p>　　1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計任務(wù)書</p><p><b>　　1.1、題目</b></p><p><b>　　迷宮求解</b></p><p><b>　　1.2、要求</b></p><p>　　以一個m×n的長方形表示迷宮，0和1分別表示迷宮中的通

8、路和障礙。設(shè)計一個程序，對任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。</p><p>　　首先實現(xiàn)一個以鏈表作存儲結(jié)構(gòu)的棧類型，然后編寫一個求解迷宮的非遞歸程序。求得的通路以三元組（i,j,d）的形式輸出，其中：（i,j）指示迷宮中的一個坐標(biāo)，d表示走到下一坐標(biāo)的方向。如：對于下列數(shù)據(jù)的迷宮，輸出的一條通路為：（1,1,1）, （1,2,2）, （2,2,2），（3,2,3）, （3,1,

9、2）,…。</p><p><b>　　2、總體設(shè)計</b></p><p>　　2.1、功能模塊設(shè)計</p><p>　　2.2、所有功能模塊的流程圖</p><p><b>　　3、詳細設(shè)計</b></p><p>　　以一個m×n的長方形表示迷宮，0和1分別表

10、示迷宮中的通路和障礙。設(shè)計一個程序，對任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。</p><p>　　首先實現(xiàn)一個以鏈表作存儲結(jié)構(gòu)的棧類型，然后編寫一個求解迷宮的非遞歸程序。求得的通路以三元組（i,j,d）的形式輸出，其中：（i,j）指示迷宮中的一個坐標(biāo)，d表示走到下一坐標(biāo)的方向。如：對于下列數(shù)據(jù)的迷宮，輸出的一條通路為：（1,1,1）, （1,2,2）, （2,2,2），（3,2,3）,

11、 （3,1,2）,…。</p><p>　　3.1、程序中所采用的數(shù)據(jù)結(jié)構(gòu)及存儲結(jié)構(gòu)的說明</p><p>　　typedef struct {</p><p>　　unsigned ord, x, y; /* 通道塊在路徑上的“序號”，通道快在迷宮中的“坐標(biāo)位置” */</p><p>　　short di; /* 從此通道塊走向下一通道

12、塊的“方向” */</p><p>　　} ElemType;</p><p>　　typedef struct Node { /* 定義單鏈表 */</p><p>　　ElemType data;</p><p>　　struct Node* next;</p><p>　　} Node, *LinkList;&l

13、t;/p><p>　　typedef struct { /* 定義鏈棧結(jié)構(gòu) */</p><p>　　LinkList top; /* 棧頂指針 */</p><p>　　unsigned length; /* 棧中元素個數(shù) */</p><p><b>　　} LStack;</b></p&

14、gt;<p>　　3.2、算法的設(shè)計思想</p><p>　　設(shè)定當(dāng)前位置為初始位置；</p><p><b>　　do{</b></p><p><b>　　若當(dāng)前位置可通，</b></p><p><b>　　則{</b></p><p&g

15、t;　　將當(dāng)前位置插入棧頂；</p><p>　　若該位置是出口位置，則結(jié)束；</p><p>　　否則切換當(dāng)前位置的東鄰方塊為新的當(dāng)前位置；</p><p><b>　　}</b></p><p><b>　　否則，</b></p><p>　　若棧不空且棧頂位置尚有其他方

16、向未經(jīng)探索，</p><p>　　則設(shè)定新的當(dāng)前位置為沿順時針方向旋轉(zhuǎn)找到的下一位置；</p><p>　　若棧不空但棧頂位置的四周皆不可通過，</p><p>　　則{ 刪去棧頂位置；</p><p>　　若棧不空，則重新測試新的棧頂位置，</p><p>　　直至找到一個可通的下一位置為止至棧空；</p&g

17、t;<p><b>　　}</b></p><p>　　}while(棧不空);</p><p>　　4.2、測試結(jié)果的分析與討論：</p><p>　?。y試要寫出測試用例及每個用例結(jié)果的的截圖）</p><p>　　4.3、測試過程中遇到的主要問題及采取的解決措施：</p><p&g

18、t;　　1. vc6.0中文版平臺在編譯程序時出現(xiàn)少了mspdb60.dll文件，因此無法運行，在下載了改文件后正常運行。</p><p>　　2.在輸入程序時有很多關(guān)鍵字輸入錯誤，語句使用不正確，在編譯后有系統(tǒng)提示一一改正后，正確運行。</p><p>　　5、時間復(fù)雜度的分析：</p><p>　　函數(shù)共探索了39步，（用數(shù)組中為1的和為0的相加，即為所有探索過

19、的步數(shù)），出棧次數(shù)為24次，（用一個監(jiān)視參數(shù)i來監(jiān)視，Pop一次i+1，最后顯示結(jié)果為24）。</p><p>　　6、源程序清單和執(zhí)行結(jié)果</p><p>　　(清單中應(yīng)有足夠的注釋)</p><p>　　#include <stdio.h></p><p>　　#include <stdlib.h></p&g

20、t;<p>　　typedef struct {</p><p>　　unsigned ord, x, y; /* 通道塊在路徑上的“序號”，通道快在迷宮中的“坐標(biāo)位置” */</p><p>　　short di; /* 從此通道塊走向下一通道塊的“方向” */</p><p>　　} ElemType;</p><p>　

21、　typedef struct Node { /* 定義單鏈表 */</p><p>　　ElemType data;</p><p>　　struct Node* next;</p><p>　　} Node, *LinkList;</p><p>　　typedef struct { /* 定義鏈棧結(jié)構(gòu) */</p>

22、;<p>　　LinkList top; /* 棧頂指針 */</p><p>　　unsigned length; /* 棧中元素個數(shù) */</p><p><b>　　} LStack;</b></p><p>　　void DestroyStack( LStack *S ) /* 銷毀棧 */</p>

23、;<p>　　{LinkList q;</p><p>　　while ( S->top ) {</p><p>　　q = S->top;</p><p>　　S->top = S->top->next; /* 修改棧頂指針 */</p><p>　　free( q ); /* 釋放被刪除的結(jié)點

24、空間 */</p><p><b>　　}</b></p><p>　　S->length = 0;</p><p><b>　　} </b></p><p>　　void InitStack( LStack *S ) /* 構(gòu)造空棧 */</p><p><b&

25、gt;　　{</b></p><p>　　S->top = NULL; /* 棧頂指針初值為空 */</p><p>　　S->length = 0; /* 空棧中元素個數(shù)為 0 */</p><p><b>　　} </b></p><p>　　int Pop( LStack *S, E

26、lemType *e )</p><p>　　{ /* 若棧不空，則刪除 S 的棧頂元素，用 e 返回棧頂元素的值。*/</p><p>　　LinkList q;</p><p>　　if ( !S->top ) {</p><p><b>　　return 0;</b></p><p&g

27、t;<b>　　}</b></p><p>　　*e = S->top->data; /* 返回棧頂元素 */</p><p>　　q = S->top;</p><p>　　S->top = S->top->next; /* 修改棧頂指針 */</p><p>　　--S->l

28、ength; /* 棧的長度減1 */</p><p>　　free( q ); /* 釋放被刪除的結(jié)點空間 */</p><p><b>　　return 1;</b></p><p><b>　　} </b></p><p>　　int Push( LStack *S, ElemType e )

29、</p><p><b>　　{</b></p><p>　　/* 在棧頂之上插入元素 e 為新的棧頂元素 */</p><p>　　LinkList p = malloc( sizeof *p ); /* 建新的結(jié)點 */</p><p>　　if ( !p ) {</p><p>　　retu

30、rn 0; /* 存儲分配失敗 */</p><p><b>　　}</b></p><p>　　p->data = e;</p><p>　　p->next = S->top; /* 鏈接到原來的棧頂 */</p><p>　　S->top = p; /* 移動棧頂指針 */<

31、/p><p>　　++S->length; /* 棧的長度增1 */</p><p><b>　　return 1;</b></p><p><b>　　} </b></p><p>　　void NextPos(unsigned *, unsigned *, short); /* 定位

32、下一個位置 */</p><p>　　int main( void )</p><p><b>　　{</b></p><p>　　LStack S,T;</p><p>　　unsigned x, y, curstep,i=0; /* 迷宮坐標(biāo)，探索步數(shù) */</p><p>　　ElemTyp

33、e e;</p><p>　　char maze[10][10] = {</p><p>　　{'#',' ','#','#','#','#','#','#','#','#'},</p><p>　　{

34、9;#',' ',' ','#',' ',' ',' ','#',' ','#'},</p><p>　　{'#',' ',' ','#',' ',' ','

35、','#',' ','#'},</p><p>　　{'#',' ',' ',' ',' ','#','#',' ',' ','#'},</p><p>　　{'#&#

36、39;,' ','#','#','#',' ',' ',' ',' ','#'},</p><p>　　{'#',' ',' ',' ','#',' ',' '

37、,' ',' ','#'},</p><p>　　{'#',' ','#',' ',' ',' ','#',' ',' ','#'},</p><p>　　{'#',&

38、#39; ','#','#','#','#','#','#',' ','#'},</p><p>　　{'#','#',' ',' ',' ',' ',' ','

39、; ',' ','#'},</p><p>　　{'#','#','#','#','#','#','#','#',' ','#'},</p><p><b>　　};</b&g

40、t;</p><p>　　InitStack(&S);</p><p>　　InitStack(&T);</p><p>　　printf("迷宮圖形,#號代表墻壁，空格代表通路：\n");</p><p>　　for ( x = 0; x < 10; x++) {</p><p&

41、gt;　　for ( y = 0; y < 10; y++ ) {</p><p>　　printf("%c", maze[x][y]);</p><p><b>　　}</b></p><p>　　printf("\n");</p><p><b>　　}<

42、/b></p><p><b>　　/*迷宮起點*/</b></p><p><b>　　x = 1;</b></p><p><b>　　y = 0;</b></p><p>　　curstep = 1; /* 探索第一步 */</p><p>

43、　　/* 進入迷宮 */</p><p><b>　　do {</b></p><p>　　if ( maze[y][x] == ' ' ) { /* 如果當(dāng)前位置可以通過 */</p><p>　　maze[y][x] = '1'; /* 留下足跡 */</p><p><b>

44、;　　e.x = x;</b></p><p><b>　　e.y = y;</b></p><p><b>　　e.di = 1;</b></p><p>　　e.ord = curstep;</p><p>　　if ( !Push(&S, e) ) { /* 加入路徑，即壓

45、棧 */</p><p>　　fprintf( stderr, "內(nèi)存不足。\n" );</p><p><b>　　}</b></p><p>　　if ( x == 8 && y == 9 ) { /* 到達終點 */</p><p><b>　　break;</b

46、></p><p><b>　　}</b></p><p>　　NextPos(&x, &y, 1); /* 下一位置是當(dāng)前位置的東鄰 */</p><p>　　curstep++;</p><p>　　} else { /* 如果當(dāng)前位置不能通過 */</p><p>　　

47、if (S.length!=0) {</p><p>　　Pop(&S, &e);</p><p>　　while (e.di == 4 && S.length!=0) {</p><p>　　maze[e.y][e.x] = '0'; /* 留下不能通過足跡 */</p><p>　　Pop(

48、&S, &e); /* 退回一步，即出棧 */</p><p><b>　　}</b></p><p>　　if (e.di < 4) {</p><p><b>　　e.di++;</b></p><p>　　if ( !Push(&S, e) ) { /* 加入路徑

49、，即壓棧 */</p><p>　　fprintf( stderr, "內(nèi)存不足。\n" );</p><p><b>　　}</b></p><p>　　/* 重置坐標(biāo) */</p><p><b>　　x = e.x;</b></p><p><

50、b>　　y = e.y;</b></p><p>　　NextPos(&x, &y, e.di); /* 尋找下一位置 */</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b>

51、</p><p>　　} while (S.length!=0);</p><p>　　printf("走出迷宮路線,1代表走過的路，0代表試探過的路徑\n");</p><p>　　for ( x = 0; x < 10; x++ ) {</p><p>　　for ( y = 0; y < 10; y++

52、) {</p><p>　　printf("%c", maze[x][y]);</p><p>　　if(maze[x][y]=='1')</p><p><b>　　i++;</b></p><p><b>　　}</b></p><p>

53、;　　printf("\n");</p><p><b>　　}</b></p><p>　　for(x=0;x<i;x++)</p><p>　　{Pop(&S,&e);</p><p>　　Push(&T,e);</p><p><b&

54、gt;　　}</b></p><p>　　printf("出迷宮順序，(X坐標(biāo)，Y坐標(biāo)，前進方向):\n");</p><p>　　while(T.length!=0)</p><p>　　{printf("(%d,%d,%d)\t",T.top->data.x,T.top->data.y,T.top

55、->data.di);</p><p>　　Pop(&T,&e);</p><p><b>　　}</b></p><p>　　DestroyStack(&S);</p><p>　　getchar();</p><p><b>　　return 0;<

56、;/b></p><p><b>　　}</b></p><p>　　void NextPos(unsigned *x, unsigned *y, short di) /* 定位下一個位置 */</p><p><b>　　{</b></p><p>　　switch (di) {</p

57、><p><b>　　case 1:</b></p><p><b>　　++(*x);</b></p><p><b>　　break;</b></p><p><b>　　case 2:</b></p><p><b>　

58、　++(*y);</b></p><p><b>　　break;</b></p><p><b>　　case 3:</b></p><p><b>　　--(*x);</b></p><p><b>　　break;</b></p&g

59、t;<p><b>　　case 4:</b></p><p><b>　　--(*y);</b></p><p><b>　　break;</b></p><p><b>　　default:</b></p><p><b>　　

60、break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　7、C程序設(shè)計總結(jié)</b></p><p>　　本次實驗主要考的是棧的使用：鏈棧的初始化，入棧，出棧，釋放?？臻g等，另外還考察了我們對一

61、次實驗的細心和重視程度。重要的是我們要學(xué)會模塊化編程和團體合作的意識，這次實驗對我們對基礎(chǔ)知識的掌握和其他一些編程需要的知識與意識的掌握都有重要的作用。</p><p><b>　　8、致謝</b></p><p>　　能夠完成這次課程設(shè)計必須感謝數(shù)據(jù)結(jié)構(gòu)課程設(shè)計指導(dǎo)教師，和室友的大力支持，幫我解決了一個個自己無法發(fā)現(xiàn)的問題。</p><p>