迷宮問題實(shí)驗(yàn)報(bào)告.doc

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

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

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

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

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

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

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

8、道方向 #define STACK_INIT_SIZE 500 /棧的最大值 #define STACKINCREMENT 10 /增量 /-存儲(chǔ)構(gòu)造 typedef struct int row; int col; PosType; typedef struct int step; /當(dāng)前位置在途徑上的“序號(hào)” PosType seat; /當(dāng)前的坐標(biāo)位置 DirectiveType di; /往下一個(gè)坐標(biāo)位置的方向 SElemType; typedef struct SElemType _base; SElemType _; int stacksize; SqStack;/棧的存儲(chǔ) 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(“請(qǐng)輸入迷宮數(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、(“請(qǐng)輸入起始位置：行列 ”); / 用戶自定義起始點(diǎn)與終點(diǎn) scanf(“dd”,start.row,start.col); printf(“請(qǐng)輸入完畢位置：行列 ”); 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); / 為棧申請(qǐng)存儲(chǔ)地址 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);/假如沒有這句話就會(huì)在原地打轉(zhuǎn)，導(dǎo)致在死胡同堵死 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) /當(dāng)前位置可以通過，即未曾走過的模塊 e.step=curstep; e.seat=curpos; e.di=1; FootPrint(maze,curpos);

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

15、;/ 換一個(gè)方向探究 Push(S,e); curpos=Ne_tPos(e.seat,e.di);/設(shè)定當(dāng)前位置是該新方向的相鄰快 /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) /判斷當(dāng)前途徑對(duì)應(yīng)數(shù)組值是否等于 0，即當(dāng)前途徑是否可通 return OK; else return ERROR; Status FootPrint(MazeType maze,PosType curpos) maze.arrcurpos.rowcurpos.col=2; /為當(dāng)前途徑留下可以通過的標(biāo)志 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; /為當(dāng)前途徑留下不可通過的標(biāo)志 return OK; /end MarkPrint Status print(MazeType maze) /迷宮的輸出顯示 int i,j; p