數(shù)據(jù)結(jié)構(gòu)-迷宮實(shí)驗(yàn)報(bào)告

1、第1 頁共19頁課程名稱：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)考查內(nèi)容：迷宮問題求解學(xué)院：計(jì)算機(jī)與信息工程學(xué)院任課教師：專業(yè)年級：計(jì)算機(jī)科學(xué)與技術(shù)2018 級、軟件工程2018 級、物聯(lián)網(wǎng) 2018 級、大數(shù)據(jù) 2018 級問題描述：以方格為基本單位，給定一個(gè)15*15 的迷宮問題，其中至少5 條不同路徑。該迷宮的形成可選擇兩種方式：1、人工定義，采用文件方式輸入；2、采用隨機(jī)數(shù)算法自動生成，無需任何輸入。請借鑒深度優(yōu)先或廣度優(yōu)先搜索策略，用非遞歸的方法，設(shè)計(jì)并實(shí)現(xiàn)一個(gè)迷宮問題求解算法。輸出求解得到的迷宮路徑以及路徑長度；要求：請寫明：解決方案設(shè)計(jì)思路（包括邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、算法思路）、實(shí)現(xiàn)源程序、測試數(shù)據(jù)和結(jié)果、

2、分析算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；不允許抄襲他人代碼或者解決方案，一經(jīng)發(fā)現(xiàn)，雷同者均按照不及格處理。教師評語總分閱卷教師*學(xué)號：姓名：*學(xué)院：專業(yè)年級：*第2 頁共19頁一、解決方案設(shè)計(jì)思路1.邏輯結(jié)構(gòu)歡迎界面switch 1,2,31. 手動2. 自動3. 退出m,nm,n結(jié)束手動輸入自動生成生成迷宮查找路徑迷宮無解迷宮有解輸出路徑打印通路123第3 頁共19頁2.存儲結(jié)構(gòu)2.1. 設(shè)定迷宮的抽象數(shù)據(jù)類型定義：adt maze 數(shù)據(jù)對象：d = ai, j | ai, j 、 、 、 、 、 、 , 0 i row+1, 0j col+1, row, col18 數(shù)據(jù)關(guān)系：

3、r = row, col row = | ai-1, j, ai, jd, i=1, , row+1, j=0, , col+1 col = | ai, j-1, ai, jd, i=0, , row+1, j=1, , col+1 基本操作：init_hand_maze( maze, row, col) 初始條件：二維數(shù)組maze 已存在。操作結(jié)果：手動初始化迷宮，0 表示通路， 1 表示障礙。init_automatic_maze( maze, row, col) 初始條件：二維數(shù)組maze 已存在。操作結(jié)果：自動初始化迷宮，0 表示通路， 1 表示障礙。printmaze( maze)

4、初始條件：迷宮 maze 已存在。操作結(jié)果：將迷宮輸出到屏幕，“”表示通路， “”表示障礙。mazepath( maze) 初始條件：迷宮 maze 已存在。操作結(jié)果：計(jì)算路徑。printpath( maze) 初始條件：迷宮 maze 已存在。操作結(jié)果：若迷宮存在一條通路，將路徑輸出至屏幕，以“”“”“”“”表示可行路徑， “ ” 表示途徑過卻無法到達(dá)出口的位置；若不存在通路，報(bào)告相應(yīng)信息。 adt maze ；第4 頁共19頁2.2 設(shè)定棧的抽象數(shù)據(jù)類型定義：adt stack 數(shù)據(jù)對象： d = ai | ai charset, i=1, 2, , n, n0 數(shù)據(jù)關(guān)系： r1 = |

5、ai-1, aid, i=2, , n基本操作：initstack(&s) 操作結(jié)果：構(gòu)造一個(gè)空棧。push(&s, e) 初始條件：棧 s 已存在。操作結(jié)果：在棧 s 的棧頂插入新的棧頂元素e。pop(&s, &e) 初始條件：棧 s 已存在 . 操作結(jié)果：刪除 s 的棧頂元素，并以e 返回其值。 adt stack ；2.3 本程序包含三個(gè)模塊1)主程序模塊：void main() 初始化 ; do 接受命令 ; 處理命令 ; while ( 命令! = 退出); 2)棧模塊實(shí)現(xiàn)棧抽象數(shù)據(jù)類型；3)迷宮模塊 實(shí)現(xiàn)迷宮抽象數(shù)據(jù)類型。第5 頁共19頁2.4 各模

6、塊之間的調(diào)用關(guān)系如下：主程序模塊迷宮模塊棧模塊3：算法思路本實(shí)驗(yàn)的目的是設(shè)計(jì)一個(gè)程序，實(shí)現(xiàn)手動或者自動生成一個(gè)nm矩陣的迷宮， 尋找一條從入口點(diǎn)到出口點(diǎn)的通路。 我們將其簡化成具體實(shí)驗(yàn)內(nèi)容如下：選擇手動或者自動生成一個(gè)nm的迷宮，將迷宮的左上角作入口，右下角作出口，設(shè)“ 0”為通路，“1”為墻，即無法穿越。假設(shè)從起點(diǎn)出發(fā)，目的為右下角終點(diǎn)，可向“上、下、左、右、左上、左下、右上、右下”8 個(gè)方向行走。如果迷宮可以走通，則用“”代表“1” ，用“”代表“ 0” ，用“”代表行走迷宮的路徑。 輸出迷宮原型圖、 迷宮路線圖以及迷宮行走路徑。如果迷宮為死迷宮，輸出信息?？梢远S數(shù)組存儲迷宮數(shù)據(jù)， 用戶

7、指定入口下標(biāo)和出口下標(biāo)。 為處理方便起見，可在迷宮的四周加一圈障礙。對于迷宮中任一位置，均可約定有東、南、西、北四個(gè)方向可通。1.打印路徑int printpath(stack s,int mazemn,int row,int col) if(s.top=s.base) coutn=n; cout 此迷宮無解 nn; return error; mazetype e; while(s.top!=s.base) 第6 頁共19頁 pop(s,e); mazee.me.n=(e.direc+10); coutn=n; cout 路徑為 :endl; int i,j; for(i=1;irow+1;

8、i+) for(j=1;jcol+1;j+) switch(mazeij) case 0: cout ; break; case 1: cout ; break; case 2: cout ; break; case 10: cout ; break; case 11: cout ; break; case 12: cout ; break; case 13: cout ; break; coutendl; cout 完成 !endl; 第7 頁共19頁return ok; 2.主函數(shù)int main() switch(i) case 1: init_hand_maze(maze,m,n);

9、printmaze(maze,m,n); initstack(s); mazepath(s,start,maze,end.m,end.n); printpath(s,maze,m,n); break; case 2: init_automatic_maze(maze,m,n); printmaze(maze,m,n); initstack(s); mazepath(s,start,maze,end.m,end.n); printpath(s,maze,m,n); break; case 3: cycle=(-1);break; default: coutn;cout你的輸入有誤 !n; bre

10、ak; 第8 頁共19頁二、源程序#include / 庫中包含system(pause) 和 rand() 函數(shù)#include /c 語言里的庫#include #include #define ok 1 #define error 0 #define stack_init_size 100 #define stackincrement 10 #define overflow -1 #define m 49 #define n 49 using namespace std; int mazemn; typedef int status; typedef struct int m,n,dir

11、ec; mazetype,*lmazetype; typedef struct lmazetype top; lmazetype base; int stacksize; int over; stack; void init_hand_maze(int mazemn,int m,int n) int i,j; for(i=1;i=m+1;i+) for(j=1;j=n+1;j+) mazeij=1; cout 請按行輸入迷宮，0 表示通路， 1 表示障礙 :endl; for(i=1;im+1;i+) for(j=1;jmazeij; for(i=1;im+1;i+) for(j=1;jn+1

12、;j+) if(mazeij!=0&mazeij!=1) cout 您輸入有誤，請重新輸入; init_hand_maze(maze,m,n); 第9 頁共19頁 void init_automatic_maze(int mazemn,int m,int n) / 自動生成迷宮 int i,j; coutn迷宮生成中 nn; system(pause); for(i=1;im+1;i+) for(j=1;jn+1;j+) mazeij=rand()%2; / 隨機(jī)生成 0、1 void printmaze(int mazemn,int row,int col) int i,j; cou

13、t 迷宮如圖所示 .endl; for(i=1;irow+1;i+) for(j=1;jcol+1;j+) if(mazeij=1) cout ; else cout ; cout=s.stacksize) s.base=(lmazetype)realloc(s.base,(s.stacksize+stackincrement) * sizeof(mazetype); if(!s.base)exit(overflow); s.top=s.base+s.stacksize; s.stacksize+=stackincrement; *s.top+=e; return ok; 第10 頁共19頁s

14、tatus pop(stack &s,mazetype &e) if(s.top=s.base)return error; e=*-s.top; return ok; status mazepath(stack &s,mazetype &e,int mazemn,int m,int n) do if(mazee.me.n=0)/0可通， 1 不可通， 2 為已走過 push(s,e); mazee.me.n=2; if(e.m=m&e.n=n) s.over=1;/表示存滿一條路徑return ok; else e.n+; e.direc=0;/來這一點(diǎn)

15、時(shí)的方向，0 右 1 下 2 左 3 上mazepath(s,e,maze,m,n); else if(s.top!=s.base&s.over!=1) switch(e.direc) /回到上一位置并同時(shí)改變方向走下一步 case 0: e.n-; e.m+; e.direc=1; break; case 1: e.m-; e.n-; e.direc=2; break; case 2: e.n+; e.m-; e.direc=3; break; case 3: pop(s,e); break; 第11 頁共19頁 while(s.top!=s.base&s.over!=1);

16、 return ok; int printpath(stack s,int mazemn,int row,int col) if(s.top=s.base) coutn=n; cout 此迷宮無解 nn; return error; mazetype e; while(s.top!=s.base) pop(s,e); mazee.me.n=(e.direc+10); cout 完成 !endl; coutn=n; cout 路徑為 :endl; int i,j; for(i=1;irow+1;i+) for(j=1;jcol+1;j+) switch(mazeij) case 0: cout

17、;break; case 1: cout ; break; case 2: cout ; break; case 10: cout ; break; case 11: cout ; break; case 12: cout ; break; case 13: cout ; break; 第12 頁共19頁 coutendl; cout 入口 endl; cout 完成 !endl; return ok; int main() int i,m,n,mazemn,cycle=0; while(cycle!=(-1) cout*n; cout 歡迎進(jìn)入迷宮求解系統(tǒng)n; coutendl; cout*

18、n; cout 手動生成迷宮請按： 1n; cout 自動生成迷宮請按： 2n; cout 退出請按： 3nn; cout*n; coutn; couti; switch(i) case 1: coutm; coutn; coutn; while(m49)|(n49) coutn抱歉，你輸入的行列數(shù)超出預(yù)設(shè)范圍(1-49,1-49), 請重新輸入： nn; coutm; coutn; coutn; init_hand_maze(maze,m,n); printmaze(maze,m,n); mazetype start,end; cout 請輸入起點(diǎn)m n:start.mstart.n; st

19、art.direc=0; cout 請輸入終點(diǎn)m n:end.mend.n; 第13 頁共19頁stack s; cout 尋找路徑 .endl; initstack(s); mazepath(s,start,maze,end.m,end.n); printpath(s,maze,m,n); system(pause); coutnnpress enter contiue!n; getchar(); while(getchar()!=n); / 接受一個(gè)輸入， 當(dāng)為回車時(shí)執(zhí)行break 跳出， 否則一直執(zhí)行接受數(shù)據(jù)break; case 2: coutm; coutn; coutn; whil

20、e(m49)|(n49) coutn抱歉，你輸入的行列數(shù)超出預(yù)設(shè)范圍(0-49,0-49),請重新輸入： nn; coutm; coutn; coutn; init_automatic_maze(maze,m,n); printmaze(maze,m,n); cout 請輸入起點(diǎn)m n:start.mstart.n; start.direc=0; cout 請輸入終點(diǎn)m n:end.mend.n; cout 尋找路徑 .endl; initstack(s); mazepath(s,start,maze,end.m,end.n); printpath(s,maze,m,n); system(pa

21、use); coutnnpress enter contiue!n; getchar(); while(getchar()!=n); / 接受一個(gè)輸入， 當(dāng)為回車時(shí)執(zhí)行break 跳出， 否則一直執(zhí)行接受數(shù)據(jù)break; case 3: cycle=(-1);break; default: coutn;cout你的輸入有誤 !n; coutnpress enter contiue!n; getchar(); 第14 頁共19頁while(getchar()!=n); break; 三、測試數(shù)據(jù)和結(jié)果自動生成 15*15 的迷宮輸入起點(diǎn)坐標(biāo)，終點(diǎn)坐標(biāo)，然后得出路第15 頁共19頁四、算法的時(shí)間復(fù)

22、雜度1.迷宮與棧類型int mazemn, row, col ; typedef struct /存放迷宮訪問到點(diǎn)的行，列，方向 int m,n,direc; mazetype,*lmazetype; typedef struct lmazetype top; /路徑第一個(gè)元素的位置lmazetype base; /路徑最后一個(gè)元素的位置int stacksize; /棧大小int over; /溢出stack; 2.棧操作函數(shù)void init_hand_maze(int mazemn,int m,int n) int i,j; for(i=1;i=m+1;i+) for(j=1;j=n+1

23、;j+) mazeij=1; cout 請按行輸入迷宮，0 表示通路， 1 表示障礙 :endl; for(i=1;im+1;i+) for(j=1;jmazeij; for(i=1;im+1;i+) 第16 頁共19頁for(j=1;jn+1;j+) if(mazeij!=0&mazeij!=1) cout 您輸入有誤，請重新輸入; init_hand_maze(maze,m,n); 時(shí)間復(fù)雜度為 o(m*n) void init_automatic_maze(int mazemn,int m,int n) /自動生成迷宮 int i,j; coutn迷宮生成中nn; system(

24、pause); for(i=1;im+1;i+) for(j=1;j=s.stacksize) s.base=(lmazetype)realloc(s.base,(s.stacksize+stackincrement) * sizeof(mazetype); if(!s.base)exit(overflow); s.top=s.base+s.stacksize; s.stacksize+=stackincrement; *s.top+=e; return ok; status pop(stack &s, mazetype &e) /將能走通的路徑的點(diǎn)依次出棧 if(s.top=s.base)return error; 第17 頁共19頁e=*-s.top; return ok; 3.求解迷宮status mazepath(stack &s, mazetype &e, int mazemn, int m, int n) do if(mazee.me.n=0)/0可通， 1 不可通， 2 為已走過 push(s,e); mazee.me.n=2; if (e.m=m&e.n=n) s.over=1;/ 表示存滿