迷宮問題實驗報告

1、精選優(yōu)質(zhì)文檔-傾情為你奉上武漢紡織大學(xué)數(shù)學(xué)與計算機學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告迷宮問題求解學(xué)生姓名：學(xué) 號：班 級：指導(dǎo)老師：報告日期：一、   問題描述以一個m x n的長方矩陣表示迷宮，1和0分別表示迷宮中的通路和障礙。設(shè)計一個程序，對任意設(shè)定的迷宮，求出從入口到出口的通路，或者沒有通路的結(jié)論。二、   需求分析1、    以二維數(shù)組maze1010表示迷宮，數(shù)組中以元素1表示通路，0表示障礙，迷宮的大小理論上可以不限制，但現(xiàn)在只提供10*10大小迷宮。2、  迷宮的入口和出口需由用戶自行設(shè)置。

2、3、   以長方形矩陣的形式將迷宮及其通路輸出，輸出中“#”表示迷宮通路，“1”表示障礙。4、      本程序只求出一條成功的通路。但是只要對函數(shù)進行小量的修改，就可以求出其他全部的路徑。5、      程序執(zhí)行命令為：（1）輸入迷宮；（2）、求解迷宮；（3）、輸出迷宮。三、   概要設(shè)計1、 設(shè)定棧的抽象數(shù)據(jù)類型定義：ADT zhan基本操作：InitStack(SqStack &S)操作結(jié)果：構(gòu)造一個空棧push（*s，*e）初始條

3、件：棧已經(jīng)存在操作結(jié)果：將e所指向的數(shù)據(jù)加入到棧s中pop（*s,*e）初始條件：棧已經(jīng)存在操作結(jié)果：若棧不為空，用e返回棧頂元素，并刪除棧頂元素getpop（*s，*e）初始條件：棧已經(jīng)存在操作結(jié)果：若棧不為空，用e返回棧頂元素stackempty(*s)初始條件：棧已經(jīng)存在操作結(jié)果：判斷棧是否為空。若棧為空，返回1，否則返回0ADT zhan2、 設(shè)定迷宮的抽象數(shù)據(jù)類型定義ADT migong基本操作： Status print(MazeType maze)；           /顯示迷宮

4、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)前位置不可通PosType NextPos(PosType curpos,DirectiveTypedi); / 進入下一位置ADT yanshu3、 本程序包括三個模塊a

5、、 主程序模塊void main()初始化；迷宮求解；迷宮輸出；b、 棧模塊實現(xiàn)棧的抽象數(shù)據(jù)類型c、 迷宮模塊實現(xiàn)迷宮的抽象數(shù)據(jù)類型四、流程圖將入口、出口位置傳入方法里判斷當(dāng)前位置是否可通將元素入棧是否到達迷宮出口右邊是否存在通路上邊是否存在通路左邊是否存在通路下邊是否存在通路存儲結(jié)點入棧循環(huán)結(jié)束，無解迷宮有解迷宮五、  數(shù)據(jù)結(jié)構(gòu) typedef struct /位置結(jié)構(gòu) int row; /行位置 int col; /列位置 PosType;typedef struct /迷宮類型 int arr1010; MazeType; typedef structint step

6、; /當(dāng)前位置在路徑上的"序號" PosType seat; /當(dāng)前的坐標(biāo)位置 DirectiveType di; /往下一個坐標(biāo)位置的方向 SElemType;typedef struct / 棧類型SElemType *base; /棧的尾指針 SElemType *top; /棧的頭指針 int stacksize; /棧的大小 SqStack;六、調(diào)試結(jié)果和分析a) 測試結(jié)果實際程序執(zhí)行過程如下圖所示： 參考文獻1 嚴(yán)蔚敏、吳偉民：數(shù)據(jù)結(jié)構(gòu)（C語言版）M，清華大學(xué)出版社 2007年版2 譚浩強：C語言設(shè)計（第三版）M，清華大學(xué)出版社 2005年版心得體會通過這段時間

7、的課程設(shè)計，本人對計算機的應(yīng)用，數(shù)據(jù)結(jié)構(gòu)的作用以及C語言的使用都有了更深的了解。尤其是C語言的進步讓我深刻的感受到任何所學(xué)的知識都需要實踐，沒有實踐就無法真正理解這些知識以及掌握它們，使其成為自己的財富。在設(shè)計此程序時，剛開始感到比較迷茫，然后一步步分析，試著寫出基本的算法，思路漸漸清晰，最后完成程序。當(dāng)然也遇到不少的問題，也正是因為這些問題引發(fā)的思考給我?guī)Я耸斋@。在遇到描寫迷宮路徑的算法時，我感到有些困難，后來經(jīng)過一步步分析和借鑒書本上的窮舉求解的算法，最后把算法寫出來。這次課程設(shè)計讓我更加深入了解很多方面的知識，如數(shù)組的運用等等。在程序的編寫中不要一味的模仿，要自己去摸索，只有帶著問題反復(fù)

8、實踐，才能熟練地掌握和運用。附錄、   源代碼 #include <stdio.h> /頭文件 #include <malloc.h> #include <stdlib.h> #include <string.h> #define OK 1 /宏定義 #define ERROR 0 #define OVERFLOW -2 typedef int Status; /函數(shù)的返回值 typedef int DirectiveType; /下一個通道方向 #define STACK_INIT_SIZE 500 /棧的最大值 #defi

9、ne STACKINCREMENT 10 /增量/-存儲結(jié)構(gòu) typedef struct int row; int col; PosType; typedef structint step; /當(dāng)前位置在路徑上的"序號" PosType seat; /當(dāng)前的坐標(biāo)位置 DirectiveType di; /往下一個坐標(biāo)位置的方向 SElemType;typedef struct SElemType *base; SElemType *top; int stacksize; SqStack;/棧的存儲typedef structint arr1010; MazeType;/迷

10、宮類型/-函數(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(MazeType &maze,PosTy

11、pe curpos);PosType NextPos(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.arri

12、j); printf("請輸入起始位置：行列 "); / 用戶自定義起始點與終點scanf("%d%d",&start.row,&start.col);printf("請輸入結(jié)束位置：行列 ");scanf("%d%d",&end.row,&end.col);if(MazePath(a,start,end) /尋找路徑print(a);elseprintf("沒有找到路徑n");Status InitStack(SqStack &S)S.base=(SEl

13、emType *)malloc(STACK_INIT_SIZE*sizeof(SElemType); / 為棧申請存儲地址if(!S.base) exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;/end InitStackStatus Pop(SqStack &S,SElemType &e)if(S.top=S.base)return ERROR; e=*(S.top-1);/如果沒有這句話就會在原地打轉(zhuǎn)，導(dǎo)致在死胡同堵死S.top-;return OK;/end PopStatus Push(

14、SqStack &S,SElemType e)*S.top=e;S.top+;return OK;/end PushStatus StackEmpty(SqStack S)if(S.top=S.base)return OK;elsereturn ERROR;/end StackEmptyStatus MazePath(MazeType &maze,PosType start,PosType end)PosType curpos;curpos=start; int curstep=1;SElemType e;SqStack S;InitStack(S);doif(Pass(maz

15、e,curpos) /當(dāng)前位置可以通過，即未曾走過的模塊 e.step=curstep; e.seat=curpos; e.di=1;FootPrint(maze,curpos);/留下足跡Push(S,e); /加入到路徑棧中if(curpos.col=end.col&&curpos.row=end.row)/達到終點（出口）return OK;curpos=NextPos(curpos,1);/下一位置是當(dāng)前位置的東鄰curstep+;/探索下一步/end ifelse /當(dāng)前位置不能通過if(!StackEmpty(S)Pop(S,e);while(e.di=4&

16、&!StackEmpty(S)MarkPrint(maze,e.seat);Pop(S,e);/ 留下不能通過的標(biāo)記，并回退一步/end whileif(e.di<4)e.di+;/ 換一個方向探索Push(S,e);curpos=NextPos(e.seat,e.di);/設(shè)定當(dāng)前位置是該新方向的相鄰快/end if/end if/end elsewhile(!StackEmpty(S);/end ifprintf("nn");for(int i=0;i<10;i+)for(int j=0; j<10;j+)printf("%d &qu

17、ot;,maze.arrij); printf("n"); return ERROR;/end MazePathStatus Pass(MazeType maze,PosType curpos)if(maze.arrcurpos.rowcurpos.col=0) /判斷當(dāng)前路徑對應(yīng)數(shù)組值是否等于0，即當(dāng)前路徑是否可通return OK;elsereturn ERROR;Status FootPrint(MazeType &maze,PosType curpos)maze.arrcurpos.rowcurpos.col=2;/為當(dāng)前路徑留下可以通過的標(biāo)志return

18、OK;/end PassPosType NextPos(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 NextPosStatus MarkPrint(MazeType &maze,PosType curpos)maze.arrcurpos.rowcurpos.col=3;/為當(dāng)前路徑留下不可通過的標(biāo)志return OK;/end MarkPrintStatus print(MazeType maze) /迷宮的輸出顯示int i,j;printf("nn"