迷宮問(wèn)題實(shí)驗(yàn)報(bào)告(c++編寫-附源代碼)(共19頁(yè))

1、精選優(yōu)質(zhì)文檔-傾情為你奉上迷宮問(wèn)題實(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ù)不超過(guò)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)的信息：0 0 11 0 01 0 0輸出結(jié)果： 11 1 0 03概要設(shè)計(jì)

3、1) 為了實(shí)現(xiàn)上述程序功能，需要定義迷宮的抽象數(shù)據(jù)類型：typedef struct/定義迷宮結(jié)構(gòu)體int maze_arraymaxsizemaxsize;/二維數(shù)組存放迷宮每個(gè)點(diǎn)是通暢或阻隔的信息int max_x,max_y; /迷宮的行數(shù)和和列數(shù)2) 定義迷宮中點(diǎn)的指針的結(jié)構(gòu)體typedef struct point 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)的指針int direction; /從當(dāng)前結(jié)點(diǎn)走至下一個(gè)結(jié)點(diǎn)的方向;基本操作： A. Maze creat_manual()

4、初始條件：無(wú) 操作結(jié)果：手動(dòng)創(chuàng)建一個(gè)迷宮。B. Maze creat_automatic()初始條件：無(wú)操作結(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é)果：返回一條通路或者NULL E. void display(Point *po,Maze a) 初始條件：存在一個(gè)迷宮操作結(jié)果：輸出結(jié)果。程序包含6個(gè)函數(shù)：主函數(shù)main()手動(dòng)創(chuàng)建一個(gè)迷宮 Maz

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

6、信息int max_x,max_y; /迷宮的行數(shù)和和列數(shù)Maze;2) 定義迷宮中點(diǎn)的指針的結(jié)構(gòu)體typedef struct point 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)的指針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)生各點(diǎn)的值； 入口結(jié)

7、點(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ù)，返回一條通路或者NULL int j,find,x,y;do while(方向j<4) find=0； switch(j)/1234分別表示東南西北 case 1:if(縱坐標(biāo)加1后在迷宮內(nèi)，且當(dāng)前結(jié)點(diǎn)為0，且當(dāng)前結(jié)點(diǎn)沒有在棧中出現(xiàn)) 當(dāng)前結(jié)點(diǎn)進(jìn)棧； 把方向j賦予當(dāng)前結(jié)點(diǎn)方向； find=1;break; case 2: if(橫坐標(biāo)加1后在迷宮

8、內(nèi)，且當(dāng)前結(jié)點(diǎn)為0，且當(dāng)前結(jié)點(diǎn)沒有在棧中出現(xiàn)) 當(dāng)前結(jié)點(diǎn)進(jìn)棧； 把方向j賦予當(dāng)前結(jié)點(diǎn)方向； find=1;break；case 3: if(縱坐標(biāo)減1后在迷宮內(nèi)，且當(dāng)前結(jié)點(diǎn)為0，且當(dāng)前結(jié)點(diǎn)沒有在棧中出現(xiàn)) 當(dāng)前結(jié)點(diǎn)進(jìn)棧； 把方向j賦予當(dāng)前結(jié)點(diǎn)方向； find=1;break；case 4: if(橫標(biāo)減1后在迷宮內(nèi)，且當(dāng)前結(jié)點(diǎn)為0，且當(dāng)前結(jié)點(diǎn)沒有在棧中出現(xiàn)) 當(dāng)前結(jié)點(diǎn)進(jìn)棧； 把方向j賦予當(dāng)前結(jié)點(diǎn)方向； find=1;break;if(find=1) j+;break;else 方向加1，即換方向;if(j>4) if(棧頂前一個(gè)結(jié)點(diǎn)不為空) 當(dāng)前結(jié)點(diǎn)出棧且方向加1else return

9、NULL;while(當(dāng)前結(jié)點(diǎn)不是出口) return top;7) void display(Point *po,Maze a)/輸出結(jié)果int i,j,top=0;Point *stackmaxsize;if(指針=NULL)cout<<"沒有找到迷宮通路！"<<endl;elsewhile(指針!=NULL)/通過(guò)一個(gè)棧將鏈棧逆序stacktop+=指針;po指針指向前一個(gè)結(jié)點(diǎn);cout<<"迷宮通道如下："<<endl;while(top>1)將棧中的通路所含結(jié)點(diǎn)的方向值加10top-;a.m

10、aze_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)值<<" "else/根據(jù)結(jié)點(diǎn)內(nèi)所存儲(chǔ)的方向值，對(duì)應(yīng)輸出四個(gè)方向的箭頭之一，指示從該結(jié)點(diǎn)到下一個(gè)結(jié)點(diǎn)的方向switch(結(jié)點(diǎn)值)case 東:輸出->； break; case 南: 輸出；break; case 西: 輸出<- ；break; cas

11、e 北: 輸出；break; 5調(diào)試分析通過(guò)本試驗(yàn)我對(duì)鏈棧有了更深入的了解。在編寫程序的過(guò)程中，我們更容易發(fā)現(xiàn)問(wèn)題所在，對(duì)算法有更深會(huì)的理解。判斷方向的轉(zhuǎn)變使其不會(huì)重復(fù)走過(guò)的路經(jīng)，這個(gè)比較麻煩，當(dāng)時(shí)也不知道如何不讓迷宮走“回頭路”，只能是查資料，和同學(xué)討論，最終找到了解決辦法。6使用說(shuō)明程序名為：迷宮.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ò)誤，需要重新輸入數(shù)字選擇功能，直至輸入的數(shù)字為1或2為止。輸入其他數(shù)字后，輸出的畫面如

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

13、ng namespace std;#include<time.h>#include<stdlib.h># 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)的指針int

14、direction; /從當(dāng)前結(jié)點(diǎn)走至下一個(gè)結(jié)點(diǎn)的方向Point;Maze creat_manual()/手動(dòng)創(chuàng)建迷宮int i,j;Maze temp;cout<<"請(qǐng)輸入迷宮的行數(shù): "cin>>temp.max_x;cout<<"請(qǐng)輸入迷宮的列數(shù): "cin>>temp.max_y; cout<<"迷宮的入口和出口已經(jīng)指定；"<<endl;cout<<"迷宮的入口結(jié)點(diǎn)坐標(biāo)為（1,1），輸入該結(jié)點(diǎn)的值時(shí)，請(qǐng)輸入0。"<&l

15、t;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表示阻隔"<<endl<<endl;for(i=1;i<=temp.max_x;i+)cout<<"

16、請(qǐng)輸入迷宮第"<<i<<"行各點(diǎn)的值："for(j=1;j<=temp.max_y;j+)cin>>temp.maze_arrayij;cout<<endl;return temp;Maze creat_automatic()/自動(dòng)創(chuàng)建迷宮int i,j;Maze temp;cout<<"請(qǐng)輸入迷宮的行數(shù): "cin>>temp.max_x;cout<<"請(qǐng)輸入迷宮的列數(shù): "cin>>temp.max_y;unsigned

17、 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.maze_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+)cout<<temp.maze_array

18、ij<<" "cout<<endl;cout<<endl;return temp;int found(int x,int y,Point *head)/查找棧中是否有head指針內(nèi)所含的坐標(biāo)；若含，則返回1，否則返回0Point *p=head;while(p!=NULL)if(x=p->vex_x&&y=p->vex_y)return 1;p=p->ahead;return 0;Point * find_road(Maze a)/迷宮尋路函數(shù)，返回一條通路或者NULLPoint *top,*p;/top

19、為棧的棧頂指針int j,find,x,y;p=(Point *)malloc(sizeof(Point);p->ahead=NULL;p->vex_x=1;p->vex_y=1;top=p;j=1;/j為方向，1、2、3、4分別為東、南、西、北dowhile(j<=4)find=0;/find判斷是否為符合條件的結(jié)點(diǎn)，若有為1，沒有為0 x=p->vex_x;y=p->vex_y;switch(j) case 1: if(y+1<=a.max_x&&!a.maze_arrayxy+1&&!found(x,y+1,top

20、) /若縱坐標(biāo)加1后，在迷宮范圍內(nèi)；且該結(jié)點(diǎn)為0；且該結(jié)點(diǎn)沒有在鏈棧中出現(xiàn)，則當(dāng)前結(jié)點(diǎn)加入鏈棧 p=(Point *)malloc(sizeof(Point); p->vex_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+1<=a.max_x&&!a.maze_arrayx+1y&&!found(x+1,y,top) p=(Point *)malloc(s

21、izeof(Point); p->vex_x=x+1; p->vex_y=y; p->ahead=top; top->direction=j; top=p; find=1; break; case 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; b

22、reak; case 4: if(x-1<=1&&!a.maze_arrayx-1y&&!found(x-1,y,top) p=(Point *)malloc(sizeof(Point); p->vex_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; else j+; /若沒有，j加1if(j>4)/4個(gè)方向都找不到符合條件的結(jié)

23、點(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;else return 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)/輸出結(jié)果int i,j,t

24、op=0;Point *stackmaxsize;if(po=NULL)cout<<"沒有找到迷宮通路！"<<endl;elsewhile(po!=NULL)/通過(guò)一個(gè)棧將鏈棧逆序stacktop+=po;po=po->ahead;cout<<"迷宮通道如下："<<endl;while(top>1)/出口結(jié)點(diǎn)值為0，無(wú)方向，不需要把方向賦值給該結(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)cout<<a.maze_arrayij<<" "else/根據(jù)結(jié)點(diǎn)內(nèi)所存儲(chǔ)的方向值，對(duì)應(yīng)輸出四個(gè)方向的箭頭之一，指示從該結(jié)點(diǎn)到下一個(gè)結(jié)點(diǎn)的方向switch(a.m