迷宮問題實驗報告.doc

1、迷宮問題實驗報告武漢紡織大學數(shù)學與計算機學院 數(shù)據(jù)構造課程設計報告 迷宮問題 求解 學生姓名：學 學 號：班 班 級：指導教師：報告日期：一、 問題描繪 以一個 m _ n 的長方矩陣表示迷宮，1 和 0 分別表示迷宮中的通路和障礙。設計一個程序，對任意設定的迷宮，求出從入口到出口的通路，或者沒有通路的結論。二、 需求分析p 1、 以二維數(shù)組 maze1010表示迷宮，數(shù)組中以元素 1 表示通路，0 表示障礙，迷宮的大小理論上可以不限制，但如今只提供 10_10 大小迷宮。2、 迷宮的入口和出口需由用戶自行設置。3、 以長方形矩陣的形式將迷宮及其通路輸出，輸出中“#”表示迷宮通路，“1”表示障

2、礙。4、 本程序只求出一條成功的通路。但是只要對函數(shù)進展小量的修改，就可以求出其他全部的途徑。5、 程序執(zhí)行命令為：1輸入迷宮；2、求解迷宮；3、輸出迷宮。三、 概要設計 1 1 、 設定棧的抽象數(shù)據(jù)類型定義：ADT zhan 根本操作：InitStack(SqStack S) 操作結果：構造一個空棧 push_s，_e 初始條件：棧已經存在 操作結果：將 e 所指向的數(shù)據(jù)參加到棧 s 中 pop_s,_e 初始條件：棧已經存在 操作結果：假設棧不為空，用 e 返回棧頂元素，并刪除棧頂元素 getpop_s，_e 初始條件：棧已經存在 操作結果：假設棧不為空，用 e 返回棧頂元素 stacke

3、mpty(_s) 初始條件：棧已經存在 操作結果：判斷棧是否為空。假設棧為空，返回 1，否那么返回 0 ADT zhan 2 2 、 設定迷宮的抽象數(shù)據(jù)類型定義 ADT migong 根本操作：Status print(MazeType maze) ； /顯示迷宮 Status Pass(MazeType maze,PosType curpos); /判斷當前位置是否可通 Status FootPrint(MazeType maze,PosType curpos);/標記當前位置已經走過 Status MarkPrint(MazeType maze,PosType curpos); /標記當前

4、位置不可通 PosType Ne_tP os(PosType curpos,Di rectiveType di); / 進入下一位置 ADT yanshu 3 3 、 本程序包括三個模塊 a、 主程序模塊 void main 初始化； 迷宮求解； 迷宮輸出； b、 棧模塊-實現(xiàn)棧的抽象數(shù)據(jù)類型 c、 迷宮模塊-實現(xiàn)迷宮的抽象數(shù)據(jù)類型 四、流程圖 五、 、 數(shù)據(jù) 構造 t typedef struct /位置構造 int row; /行位置 int col; /列位置 PosType; typedef struct /迷宮類型 int arr1010; MazeType; typedef str

5、uct int step; /當前位置在途徑上的“序號” PosType seat; /當前的坐標位置 DirectiveType di; /往下一個坐標位置的方向 SElemType; 將入口、出口位置傳入方法里 判斷當前位置是否可通 將元素入棧 是否到達迷宮出口 右邊是否存在通路 上邊是否存在通路 左邊是否存在通路 下邊是否存在通路 存儲結點入棧 循環(huán)完畢，無解迷宮 有解迷宮 typedef struct / 棧類型 SElemType _base; /棧的尾指針 SElemType _; /棧的頭指針 int stacksize; /棧的大小 SqStack; 六 、調試結果和分析p a

6、) 測試結果 實際程序執(zhí)行過程如下列圖所示：【參考文獻】：p 】： 1 嚴蔚敏、吳偉民：數(shù)據(jù)構造C 語言版M，清華大學出版社 20_7 年版 2 譚浩強：C 語言設計第三版M，清華大學出版社 20_5 年版 心得體會 通過這段時間的課程設計，本人對計算機的應用，數(shù)據(jù)構造的作用以及 C語言的使用都有了更深的理解。尤其是 C 語言的進步讓我深化的感受到任何所學的知識都需要理論，沒有理論就無法真正理解這些知識以及掌握它們，使其成為自己的財富。在設計此程序時，剛開場感到比擬迷茫，然后一步步分析p ，試著寫出根本的算法，思路漸漸明晰，最后完成程序。當然也遇到不少的問題，也正是因為這些問題引發(fā)的考慮給我?guī)?/p>

7、了收獲。在遇到描寫迷宮途徑的算法時，我感到有些困難，后來經過一步步分析p 和借鑒書本上的窮舉求解的算法，最后把算法寫出來。這次課程設計讓我更加深化理解很多方面的知識，如數(shù)組的運用等等。在程序的編寫中不要一味的模擬，要自己去探究，只有帶著問題反復理論，才能純熟地掌握和運用。附錄、 、 代碼 #include /頭文件 #include #include #include #define OK 1 /宏定義 #define ERROR 0 #define OVERFLOW -2 typedef int Status; /函數(shù)的返回值 typedef int DirectiveType; /下一個通

8、道方向 #define STACK_INIT_SIZE 500 /棧的最大值 #define STACKINCREMENT 10 /增量 /-存儲構造 typedef struct int row; int col; PosType; typedef struct int step; /當前位置在途徑上的“序號” PosType seat; /當前的坐標位置 DirectiveType di; /往下一個坐標位置的方向 SElemType; typedef struct SElemType _base; SElemType _; int stacksize; SqStack;/棧的存儲 typ

9、edef struct int arr1010; MazeType;/迷宮類型 /-函數(shù)聲明 Status InitStack(SqStack S); Status Pop(SqStack S,SElemType e); Status Push(SqStack S,SElemType e); Status StackEmpty(SqStack S); Status MazePath(MazeType maze,PosType start,PosType end); Status Pass(MazeType maze,PosType curpos); Status FootPrint(MazeT

10、ype maze,PosType curpos); PosType Ne_tPos(PosType curpos,DirectiveType di); Status MarkPrint(MazeType maze,PosType curpos); Status print(MazeType maze); void main PosType start,end; MazeType a; printf(“請輸入迷宮數(shù)據(jù)n”); for(int i=0;i<10;i+) /承受輸入的迷宮數(shù)據(jù) for(int j=0; j<10;j+) scanf(“d”,a.arrij); printf

11、(“請輸入起始位置：行列 ”); / 用戶自定義起始點與終點 scanf(“dd”,start.row,start.col); printf(“請輸入完畢位置：行列 ”); scanf(“dd”,end.row,end.col); if(MazePath(a,start,end) /尋找途徑 print(a); else printf(“沒有找到途徑n”); Status InitStack(SqStack S) S.base=(SElemType _)malloc(STACK_INIT_SIZE_sizeof(SElemType); / 為棧申請存儲地址 if(!S.base) e_it(O

12、VERFLOW); S.=S.base; S.stacksize=STACK_INIT_SIZE; return OK; /end InitStack Status Pop(SqStack S,SElemType e) if(S.=S.base) return ERROR; e=_(S.-1);/假如沒有這句話就會在原地打轉，導致在死胡同堵死 S.-; return OK; /end Pop Status Push(SqStack S,SElemType e) _S.=e; S.+; return OK; /end Push Status StackEmpty(SqStack S) if(S.

13、=S.base) return OK; else return ERROR; /end StackEmpty Status MazePath(MazeType maze,PosType start,PosType end) PosType curpos; curpos=start; int curstep=1; SElemType e; SqStack S; InitStack(S); do if(Pass(maze,curpos) /當前位置可以通過，即未曾走過的模塊 e.step=curstep; e.seat=curpos; e.di=1; FootPrint(maze,curpos);

14、/留下足跡 Push(S,e); /參加到途徑棧中 if(curpos.col=end.colcurpos.row=end.row)/ 到達終點出口 return OK; curpos=Ne_tPos(curpos,1);/下一位置是當前位置的東鄰 curstep+;/探究下一步 /end if else /當前位置不能通過 if(!StackEmpty(S) Pop(S,e); while(e.di=4!StackEmpty(S) MarkPrint(maze,e.seat); Pop(S,e);/ 留下不能通過的標記，并回退一步 /end while if(e.di<4) e.di+

15、;/ 換一個方向探究 Push(S,e); curpos=Ne_tPos(e.seat,e.di);/設定當前位置是該新方向的相鄰快 /end if /end if /end else while(!StackEmpty(S);/end if printf(“nn”); for(int i=0;i<10;i+) for(int j=0; j<10;j+) printf(“d ”,maze.arrij); printf(“n”); return ERROR; /end MazePath Status Pass(MazeType maze,PosType curpos) if(maze

16、.arrcurpos.rowcurpos.col=0) /判斷當前途徑對應數(shù)組值是否等于 0，即當前途徑是否可通 return OK; else return ERROR; Status FootPrint(MazeType maze,PosType curpos) maze.arrcurpos.rowcurpos.col=2; /為當前途徑留下可以通過的標志 return OK; /end Pass PosType Ne_tPos(PosType curpos,DirectiveType di) PosType pos = curpos; switch(di) case 1:pos.col+; /向東尋找 break; case 2:pos.row+; /向西尋找 break; case 3:pos.col-; /向南尋找 break; case 4:pos.row-; /向北尋找 break; return pos; /end Ne_tPos Status MarkPrint(MazeType maze,PosType curpos) maze.arrcurpos.rowcurpos.col=3; /為當前途徑留下不可通過的標志 return OK; /end MarkPrint Status print(MazeType maze) /迷宮的輸出顯示 int i,j; p