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

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

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

4、Status Pass(MazeType maze,PosType curpos);     /判斷當前位置是否可通Status FootPrint(MazeType &maze,PosType curpos);/標記當前位置已經走過Status MarkPrint(MazeType &maze,PosType curpos);  /標記當前位置不可通PosType NextPos(PosType curpos,DirectiveTypedi); / 進入下一位置ADT yanshu3、 本程序包括三個模塊a

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

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

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

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; /函數的返回值 typedef int DirectiveType; /下一個通道方向 #define STACK_INIT_SIZE 500 /棧的最大值 #defi

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

10、宮類型/-函數聲明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("請輸入迷宮數據n");for(int i=0;i<10;i+) /接受輸入的迷宮數據for(int j=0; j<10;j+)scanf("%d",&a.arri

12、j); printf("請輸入起始位置：行列 "); / 用戶自定義起始點與終點scanf("%d%d",&start.row,&start.col);printf("請輸入結束位置：行列 ");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);/如果沒有這句話就會在原地打轉，導致在死胡同堵死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) /當前位置可以通過，即未曾走過的模塊 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);/下一位置是當前位置的東鄰curstep+;/探索下一步/end ifelse /當前位置不能通過if(!StackEmpty(S)Pop(S,e);while(e.di=4&

16、&!StackEmpty(S)MarkPrint(maze,e.seat);Pop(S,e);/ 留下不能通過的標記，并回退一步/end whileif(e.di<4)e.di+;/ 換一個方向探索Push(S,e);curpos=NextPos(e.seat,e.di);/設定當前位置是該新方向的相鄰快/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) /判斷當前路徑對應數組值是否等于0，即當前路徑是否可通return OK;elsereturn ERROR;Status FootPrint(MazeType &maze,PosType curpos)maze.arrcurpos.rowcurpos.col=2;/為當前路徑留下可以通過的標志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;/為當前路徑留下不可通過的標志return OK;/end MarkPrintStatus print(MazeType maze) /迷宮的輸出顯示int i,j;printf("nn"