迷宮問題實(shí)驗(yàn)報(bào)告(c編寫,附源代碼)匯總,推薦文檔

1、迷宮問題實(shí)驗(yàn)報(bào)告級(jí)班年 月日姓名學(xué)號(hào)_1. 實(shí)驗(yàn)題目以一個(gè) mxn 的長(zhǎng)方陣表示迷宮，0 和 1 分別表示迷宮中的通路和障礙。設(shè)計(jì)一個(gè)程序，對(duì)任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。2. 需求分析本程序使用 vc 編寫，實(shí)現(xiàn)設(shè)定迷宮或自動(dòng)生成迷宮長(zhǎng)方陣表的功能，并且求出一條從指定入口到指定出口的通路，或得出沒有通路的結(jié)論。 輸入的形式和輸入值的范圍：a. 輸入指定的數(shù)字，以此選擇迷宮的創(chuàng)建方式，分為手動(dòng)創(chuàng)建迷宮和自動(dòng)創(chuàng)建迷宮b. 輸入迷宮陣表的行數(shù)和列數(shù)，行數(shù)和列數(shù)不超過 40 行c. 手動(dòng)創(chuàng)建迷宮時(shí)，需要輸入迷宮結(jié)點(diǎn)的通暢和障礙情況，0 和 1 分別表示迷宮中的通路

2、和障礙。 輸出的形式：輸出沒有通路的結(jié)論，或者輸出一個(gè)長(zhǎng)方陣表，其中路徑的每個(gè)結(jié)點(diǎn)都輸出、之一，表示從當(dāng)前結(jié)點(diǎn)到下一個(gè)結(jié)點(diǎn)的方向。 程序所能達(dá)到的功能：實(shí)現(xiàn)設(shè)定迷宮或自動(dòng)生成迷宮長(zhǎng)方陣表的功能，并且求出一條從指定入口到指定出口的通路（迷宮的入口指定為坐標(biāo)為（1,1）的結(jié)點(diǎn)，迷宮的出口指定為坐標(biāo)為（迷宮最大行,迷宮最大列）的結(jié)點(diǎn)），或得出沒有通路的結(jié)論。 測(cè)試數(shù)據(jù)：輸入數(shù)據(jù)：a. 出現(xiàn)選擇生成迷宮方式的菜單時(shí)，輸入 1（即手動(dòng)輸入數(shù)據(jù)，生成迷宮）；b. 輸入迷宮的行數(shù)和列數(shù)，行數(shù)輸入 3，列數(shù)輸入 3；c. 輸入每個(gè)迷宮結(jié)點(diǎn)的信息：001100100輸出結(jié)果：111003. 概要設(shè)計(jì)1) 為了實(shí)

3、現(xiàn)上述程序功能，需要定義迷宮的抽象數(shù)據(jù)類型：typedef struct/定義迷宮結(jié)構(gòu)體int maze_arraymaxsizemaxsize;/二維數(shù)組存放迷宮每個(gè)點(diǎn)是通暢或阻隔的信息int max_x,max_y;/迷宮的行數(shù)和和列數(shù)第 25 頁，共 19 頁2) 定義迷宮中點(diǎn)的指針的結(jié)構(gòu)體typedef struct pointint vex_x,vex_y;/結(jié)點(diǎn)的橫縱坐標(biāo)（橫坐標(biāo)為行號(hào),縱坐標(biāo)為列號(hào)） struct point *ahead;/在鏈棧中，指向前一個(gè)結(jié)點(diǎn)的指針int direction;/從當(dāng)前結(jié)點(diǎn)走至下一個(gè)結(jié)點(diǎn)的方向;基本操作：a. maze creat_manua

4、l()初始條件：無操作結(jié)果：手動(dòng)創(chuàng)建一個(gè)迷宮。b. maze creat_automatic()初始條件：無操作結(jié)果：自動(dòng)創(chuàng)建一個(gè)迷宮。c. int found(int x,int y,point *head)初始條件：存在一個(gè)存放結(jié)點(diǎn)的鏈棧操作結(jié)果：查找棧中是否有 head 指針內(nèi)所含的坐標(biāo)；若含，則返回 1，否則返回0。d. point * find_road(maze a)初始條件：存在一個(gè)迷宮操作結(jié)果：返回一條通路或者 nulle. void display(point *po,maze a)初始條件：存在一個(gè)迷宮操作結(jié)果：輸出結(jié)果。程序包含6個(gè)函數(shù)：1 主函數(shù)main()2 手動(dòng)創(chuàng)建

5、一個(gè)迷宮maze creat_manual();3 自動(dòng)創(chuàng)建一個(gè)迷宮maze creat_automatic();4 查找棧中是否有head指針內(nèi)所含的坐標(biāo)int found(int x,int y,point *head);5 迷宮尋路函數(shù)point * find_road(maze a);6 顯示迷宮信息函數(shù)void display(point *po,maze a);各函數(shù)間關(guān)系如下：主函數(shù)創(chuàng)建迷宮找到出口？符和條件？進(jìn)棧改變條件迷宮求解函數(shù)初始化輸出路徑4. 詳細(xì)設(shè)計(jì)1) 定義迷宮結(jié)構(gòu)體typedef structint maze_arraymaxsizemaxsize;/二維數(shù)組存放

6、迷宮每個(gè)點(diǎn)是通暢或阻隔的信息int max_x,max_y;/迷宮的行數(shù)和和列數(shù)maze;2) 定義迷宮中點(diǎn)的指針的結(jié)構(gòu)體typedef struct pointint vex_x,vex_y;/結(jié)點(diǎn)的橫縱坐標(biāo)（橫坐標(biāo)為行號(hào),縱坐標(biāo)為列號(hào)） struct point *ahead;/在鏈棧中，指向前一個(gè)結(jié)點(diǎn)的指針int direction;/從當(dāng)前結(jié)點(diǎn)走至下一個(gè)結(jié)點(diǎn)的方向point;迷宮的基本操作如下3) maze creat_manual()/手動(dòng)創(chuàng)建迷宮輸入迷宮的行數(shù)和列數(shù)； 依次輸入各點(diǎn)的值；4) maze creat_automatic()/自動(dòng)創(chuàng)建迷宮輸入迷宮的行數(shù)和列數(shù)； 隨機(jī)產(chǎn)生

7、各點(diǎn)的值；入口結(jié)點(diǎn)和出口結(jié)點(diǎn)賦值為0； 打印迷宮；5) int found(int x,int y,point *head)查找棧中是否有 head 指針內(nèi)所含的坐標(biāo)若含，則返回 1；否則返回 06) point * find_road(maze a)/迷宮尋路函數(shù)，返回一條通路或者 nullint j,find,x,y; do while(方向 j4) if(棧頂前一個(gè)結(jié)點(diǎn)不為空)當(dāng)前結(jié)點(diǎn)出棧且方向加 1 else return null;while(當(dāng)前結(jié)點(diǎn)不是出口) return top;7) void display(point *po,maze a)/輸出結(jié)果int i,j,top=

8、0;point *stackmaxsize;if(指針=null)cout沒有找到迷宮通路！endl; elsewhile(指針!=null)/通過一個(gè)棧將鏈棧逆序stacktop+=指針;po 指針指向前一個(gè)結(jié)點(diǎn);cout迷宮通道如下：1)將棧中的通路所含結(jié)點(diǎn)的方向值加 10top-;a.maze_array當(dāng)前新棧中所存的行坐標(biāo)當(dāng)前新棧中所存的列坐標(biāo)=新棧中當(dāng)前結(jié)點(diǎn)到下一個(gè)結(jié)點(diǎn)的方向+10;/11、12、13、14 分別為東、南、西、北for(i=1;i=行最大值;i+)/打印迷宮for(j=1;j=列最大值;j+)if(結(jié)點(diǎn)值=1)cout結(jié)點(diǎn)值； break; case 南: 輸出；b

9、reak; case 西: 輸出- ；break;5. 調(diào)試分析case 北: 輸出；break; 通過本試驗(yàn)我對(duì)鏈棧有了更深入的了解。在編寫程序的過程中，我們更容易發(fā)現(xiàn)問題所在，對(duì)算法有更深會(huì)的理解。判斷方向的轉(zhuǎn)變使其不會(huì)重復(fù)走過的路經(jīng)，這個(gè)比較麻煩，當(dāng)時(shí)也不知道如何不讓迷宮走“回頭路”，只能是查資料，和同學(xué)討論，最終找到了解決辦法。6. 使用說明程序名為：迷宮.exe，運(yùn)行環(huán)境為 dos。程序執(zhí)行后顯示請(qǐng)選擇手動(dòng)或自動(dòng)生成迷宮1. 手動(dòng)生成迷宮2. 自動(dòng)生成迷宮輸入數(shù)字選擇執(zhí)行不同的功能。輸入 1，使用手動(dòng)生成迷宮功能； 輸入 2，使用自動(dòng)生成迷宮功能；輸入其他數(shù)字，則提示輸入錯(cuò)誤，需要重

10、新輸入數(shù)字選擇功能，直至輸入的數(shù)字為 1 或2 為止。輸入其他數(shù)字后，輸出的畫面如下： 您輸入的數(shù)值有誤，請(qǐng)重新輸入請(qǐng)選擇手動(dòng)或自動(dòng)生成迷宮1. 手動(dòng)生成迷宮2. 自動(dòng)生成迷宮此時(shí)請(qǐng)依次輸入每個(gè)結(jié)點(diǎn)的值，其中入口和出口必須輸入 0：輸入 1 后，接著輸入迷宮的行數(shù)和列數(shù)，最后出現(xiàn)如下畫面接著程序會(huì)輸出迷宮通路或者是沒有通路的信息使用自動(dòng)創(chuàng)建迷宮功能時(shí)，只需輸入行數(shù)和列數(shù)，接著程序會(huì)輸出迷宮通路或者是沒有通路的信息7. 測(cè)試結(jié)果1) 5x5 迷宮，沒路的情況，輸入和輸出如下所示：2) 5x5 迷宮，有通路情況，輸入和輸出如下所示：3) 4x3 迷宮，沒路情況，輸入和輸出如下所示：4) 4x3 迷

11、宮，有路情況，輸入和輸出如下所示：源代碼如下：# include using namespace std; #include #include# define maxsize 20typedef struct/定義迷宮結(jié)構(gòu)體int maze_arraymaxsizemaxsize;/二維數(shù)組存放迷宮每個(gè)點(diǎn)是通暢或阻隔的信息int max_x,max_y;/迷宮的行數(shù)和和列數(shù)maze;typedef struct point/定義迷宮中點(diǎn)的指針的結(jié)構(gòu)體int vex_x,vex_y;/結(jié)點(diǎn)的橫縱坐標(biāo)（橫坐標(biāo)為行號(hào),縱坐標(biāo)為列號(hào)） struct point *ahead;/在鏈棧中，指向前一個(gè)結(jié)點(diǎn)

12、的指針int direction;/從當(dāng)前結(jié)點(diǎn)走至下一個(gè)結(jié)點(diǎn)的方向point;maze creat_manual()/手動(dòng)創(chuàng)建迷宮int i,j;maze temp;couttemp.max_x;couttemp.max_y;cout迷宮的入口和出口已經(jīng)指定；endl;cout迷宮的入口結(jié)點(diǎn)坐標(biāo)為（1,1），輸入該結(jié)點(diǎn)的值時(shí)，請(qǐng)輸入 0。endl; cout迷宮的出口結(jié)點(diǎn)坐標(biāo)為（temp.max_x,temp.max_y），輸入該結(jié)點(diǎn)的值時(shí)，請(qǐng)輸入 0。endl;cout結(jié)點(diǎn)值為 0 表示通暢，值為 1 表示阻隔endlendl; for(i=1;i=temp.max_x;i+)cout請(qǐng)輸入

13、迷宮第i行各點(diǎn)的值：; for(j=1;jtemp.maze_arrayij;coutendl; return temp;maze creat_automatic()/自動(dòng)創(chuàng)建迷宮int i,j;maze temp;couttemp.max_x;couttemp.max_y;unsigned int t; t=time(null)%1000;srand(t);/產(chǎn)生隨機(jī)數(shù)種子for(i=1;i=temp.max_x;i+)for(j=1;j=temp.max_y;j+)temp.maze_arrayij=rand()%2;temp.maze_array11=0;/迷宮入口置值為 0temp.m

14、aze_arraytemp.max_xtemp.max_x=0;/迷宮出口置值為 0，否則程序不能正常運(yùn)行for(i=1;i=temp.max_x;i+)/打印迷宮for(j=1;j=temp.max_y;j+)couttemp.maze_arrayij;coutendl;coutvex_x&y=p-vex_y) return 1;p=p-ahead;return 0;point * find_road(maze a)/迷宮尋路函數(shù)，返回一條通路或者 nullpoint *top,*p;/top 為棧的棧頂指針int j,find,x,y;p=(point *)malloc(sizeof(po

15、int); p-ahead=null;p-vex_x=1;p-vex_y=1;top=p;j=1;/j 為方向，1、2、3、4 分別為東、南、西、北dowhile(jvex_x;y=p-vex_y;switch(j)case 1:if(y+1vex_x=x;p-vex_y=y+1;p-ahead=top;top-direction=j;/從上一結(jié)點(diǎn)至該結(jié)點(diǎn)的方向，存放在上一結(jié)點(diǎn)的結(jié)點(diǎn)指針內(nèi)top=p; find=1;break;case 2:if(x+1vex_x=x+1;p-vex_y=y;p-ahead=top;top-direction=j; top=p;find=1;break;cas

16、e 3:if(y-1=1&!a.maze_arrayxy-1&!found(x,y-1,top)p=(point *)malloc(sizeof(point); p-vex_x=x;p-vex_y=y-1;p-ahead=top;top-direction=j; top=p;find=1;break;case 4:if(x-1vex_x=x-1;p-vex_y=y;p-ahead=top; top-direction=j;top=p; find=1;break;if(find=1)/若找到符合條件的結(jié)點(diǎn)，則 j 賦值為 1，然后退出內(nèi)層 while 循環(huán)j=1;break;elsej+;/若沒

17、有，j 加 1if(j4)/4 個(gè)方向都找不到符合條件的結(jié)點(diǎn)時(shí)if(top-ahead!=null)/若 top 不為空，則出棧，上一個(gè)結(jié)點(diǎn)的方向 j 加 1p=p-ahead;top=p;/使棧頂結(jié)點(diǎn)指向前一個(gè)節(jié)點(diǎn)，原節(jié)點(diǎn)刪除j=top-direction+1;top-direction=j;elsereturn null;/若 top 為空，則返回 nullwhile(top-vex_x!=a.max_x | top-vex_y!=a.max_y);/若果當(dāng)前結(jié)點(diǎn)不是出口，則繼續(xù)進(jìn)行 do-while 循環(huán)return top;void display(point *po,maze a)/

18、輸出結(jié)果int i,j,top=0;point *stackmaxsize;if(po=null)cout沒有找到迷宮通路！ahead;cout迷宮通道如下：1)/出口結(jié)點(diǎn)值為 0，無方向，不需要把方向賦值給該結(jié)點(diǎn)top-;a.maze_arraystacktop-vex_xstacktop-vex_y=stacktop-direction+10;/把迷宮通路走的方向賦值給迷宮中相應(yīng)的結(jié)點(diǎn)/11、12、13、14 分別為東、南、西、北for(i=1;i=a.max_x;i+)/打印迷宮for(j=1;j=a.max_y;j+)if(a.maze_arrayij=1) couta.maze_ar

19、rayij break;case 12:printf(%c,25);/輸出向下的箭頭break;case 13:printf(%c,27);/輸出- break;case 14:printf(%c,24);/輸出向上的箭頭break;coutendl;coutendl;void main()maze a;point *po;int selection;cout請(qǐng)選擇手動(dòng)或自動(dòng)生成迷宮endl; cout1.手動(dòng)生成迷宮endl;cout2.自動(dòng)生成迷宮selection;while(selection!=1&selection!=2)cout您輸入的數(shù)值有誤，請(qǐng)重新輸入endl; cout請(qǐng)選擇手動(dòng)或自動(dòng)生成迷宮endl; cout1.手動(dòng)生成迷宮endl;cout2.自動(dòng)生成迷宮selection;if(selection=1) a=creat_manual();elsea=creat_automatic();po=find_road(a); display(po,a); getchar(); getchar();“”“”at the end, xiao bian gives you a passage. min