迷宮問(wèn)題實(shí)驗(yàn)報(bào)告

1、迷宮問(wèn)題班級(jí)：2012計(jì)算機(jī)科學(xué)與技術(shù) 姓名： 學(xué)號(hào)： 日期：2013/10/15一、 需求分析 1 、輸入。以二維數(shù)組migongmn 表示迷宮。數(shù)組中以元素值為0 表示通路，1 表示障礙，2表示入口，3表示出口。 用戶以文件的形式讀入迷宮的數(shù)據(jù)：文件中第一行的數(shù)據(jù)為迷宮的行數(shù) m 和列數(shù)n ；文件儲(chǔ)存在D:migong.txt中 2、輸出。若設(shè)定的迷宮存在通路，則以坐標(biāo)方式輸出其通路。3、功能。本程序只求出一條成功的通路。然而，只需要對(duì)迷宮求解的函數(shù)作小量修改，便可求得全部路徑。 3、測(cè)試數(shù)據(jù) 10 101 1 1 1 1 1 1 1 1 11 2 0 1 0 0 0 1 0 11 0 0

2、 1 0 0 0 1 0 11 0 0 0 0 1 1 0 0 11 0 1 1 1 0 0 0 0 11 0 0 0 1 0 0 0 0 11 0 1 0 0 0 1 0 0 11 0 1 1 1 0 1 1 0 11 1 0 0 0 0 0 0 3 11 1 1 1 1 1 1 1 1 1二、 概要設(shè)計(jì)說(shuō)明本程序中用到的所有抽象數(shù)據(jù)類型的定義、主程序的流程以及各程序模塊之間的層次（調(diào)用）關(guān)系1. 設(shè)定棧的抽象數(shù)據(jù)類型定義： ADT Stack 數(shù)據(jù)對(duì)象：D=ai|ai CharSet,i=1,2,n,n>=0 數(shù)據(jù)關(guān)系：R1=<ai-1,ai>|ai-1,ai D,i=2

3、,n 基本操作：棧的構(gòu)造函數(shù)（賦予棧的正確性）：Stack:Stack()top=NULL; 棧的析構(gòu)函數(shù)（及時(shí)回收未使用的空間）： Stack()壓棧操作：Push(T e); 彈棧操作（輸出top的元素）：Pop(); 獲得棧頂元素：GetPop(); 清空棧：Clear(); 判斷是否?？眨ㄝ敵霾紶栃停篹mpty()2、迷宮的基本操作：從文本中讀入數(shù)據(jù)建立迷宮GetMaze(int &m,int &n);尋找迷宮maze中從（0，0）到（m,n）的路徑Mazepath(int *maze,int m,int n); 打印出通路的路線 PrintPath(Stack p,

4、 int m, int n, int *maze); 恢復(fù)迷宮矩陣的原始狀態(tài)Restore(int *maze,int m,int n);三、 詳細(xì)設(shè)計(jì)1 迷宮類型class mgprivate:int footprint;int data;int i,j;int direct;mg *next;public:friend void putin(); /輸入迷宮、迷宮矩陣初始化friend mg *start(); /尋找入口，并返回入口指針friend void seek(); /尋找路徑并輸出路徑friend mg *turn(mg *top); / 將棧倒置;2、輸入迷宮void put

5、in() /輸入迷宮、迷宮矩陣初始化fin>>m>>n;for(int i=0;i<m;+i)for(int j=0;j<n;+j)fin>>migongij.data;migongij.footprint=0;migongij.i=i;migongij.j=j;migongij.direct=0;cout<<migongij.data<<" "cout<<endl;3、尋找并輸出路徑void seek() /尋找路徑mg *top,*tail,*now,*p; /棧中只用類mg里的i，j，

6、next，要改變和使用其它元素都在矩陣中進(jìn)行now=start();p=top=tail=new mg;tail->next=NULL;*top=*now;int x=now->i;int y=now->j;while(migongxy.footprint!=2)int i=now->i;int j=now->j;if(top->data=3)break;elseif(now->data=0|now->data=2|now->data=3)if(now->footprint!=2) /滿足條件就入棧if(now->footpri

7、nt=0)top=new mg;top->next=p;p=top;now->next=top->next;now->footprint=1;now->direct=1;*top=*now; /入棧now=&migongij+1;elseswitch (migongtop->itop->j.direct)case 1:migongtop->itop->j.direct=2; now=&migongtop->i+1top->j; break;case 2:migongtop->itop->j.direc

8、t=3; now=&migongtop->itop->j-1; break;case 3:migongtop->itop->j.direct=4; now=&migongtop->i-1top->j; break;case 4:migongtop->itop->j.footprint=2; top=top->next; now=&migongtop->itop->j; p=top; break;elsenow=&migongtop->itop->j;elsenow=&migon

9、gtop->itop->j;if(migongmn.footprint=2)cout<<"對(duì)不起，沒(méi)有走出迷宮的路徑！"<<endl;elsecout<<"路徑如下(按順序輸出每一步的坐標(biāo))："<<endl;top=turn(top);while(top!=NULL)cout<<top->i<<" "<<top->j<<endl;top=top->next;四、 調(diào)試分析1、腦袋中想到的第一想法是以類的形式，類

10、可以及時(shí)回收空間，同時(shí)類有繼承特性2、restore函數(shù)有點(diǎn)多余，但可以給用戶一個(gè)好的使用印象3、在調(diào)試過(guò)程中可以多使用cout，在每個(gè)可能出錯(cuò)的步驟都加上一個(gè)cout操作，這樣方便調(diào)試4、以坐標(biāo)形式輸出迷宮通路更加明顯，但無(wú)法得到程序嘗試的步驟，這是一個(gè)大的缺點(diǎn)五、用戶使用說(shuō)明由于程序從文檔中讀入數(shù)據(jù)（包括迷宮的長(zhǎng)寬和整個(gè)迷宮矩陣），所以用戶如果想改變迷宮的形狀等直接在文檔migong.txt中進(jìn)行修改。注：用戶需要將migong.txt放在D:目錄下。六、測(cè)試結(jié)果七、附錄（完整代碼）/= / 迷宮問(wèn)題的解決/-/ 使用方法：略/-/ 姓名： 學(xué)號(hào)： QQ：1794559417 2013/4

11、/16/=#include<iostream>#include<fstream>#include<cstdio>using namespace std;/-class mgprivate:int footprint;int data;int i,j;int direct;mg *next;public:friend void putin(); /輸入迷宮、迷宮矩陣初始化friend mg *start(); /尋找入口，并返回入口指針friend void seek(); /尋找路徑并輸出路徑friend mg *turn(mg *top); / 將棧倒置;

12、/-mg migong3030;int m,n;ifstream fin("D:migong.txt");/-void putin() /輸入迷宮、迷宮矩陣初始化fin>>m>>n;for(int i=0;i<m;+i)for(int j=0;j<n;+j)fin>>migongij.data;migongij.footprint=0;migongij.i=i;migongij.j=j;migongij.direct=0;cout<<migongij.data<<" "cout<

13、;<endl;/-mg *turn(mg *top) /將棧倒置mg *p1,*p2;p1=top;p2=top->next;top->next=NULL;while(p2->next!=NULL)top=p2;p2=top->next;top->next=p1;p1=top;top=p1;return top;/-void seek() /尋找路徑mg *top,*tail,*now,*p; /棧中只用類mg里的i，j，next，要改變和使用其它元素都在矩陣中進(jìn)行now=start();p=top=tail=new mg;tail->next=NUL

14、L;*top=*now;int x=now->i;int y=now->j;while(migongxy.footprint!=2)int i=now->i;int j=now->j;if(top->data=3)break;elseif(now->data=0|now->data=2|now->data=3)if(now->footprint!=2) /滿足條件就入棧if(now->footprint=0)top=new mg;top->next=p;p=top;now->next=top->next;now-&g

15、t;footprint=1;now->direct=1;*top=*now; /入棧now=&migongij+1;elseswitch (migongtop->itop->j.direct)case 1:migongtop->itop->j.direct=2; now=&migongtop->i+1top->j; break;case 2:migongtop->itop->j.direct=3; now=&migongtop->itop->j-1; break;case 3:migongtop->

16、itop->j.direct=4; now=&migongtop->i-1top->j; break;case 4:migongtop->itop->j.footprint=2; top=top->next; now=&migongtop->itop->j; p=top; break;elsenow=&migongtop->itop->j;elsenow=&migongtop->itop->j;if(migongmn.footprint=2)cout<<"對(duì)不起，沒(méi)有走出迷宮的路徑！"<<endl;elsecout<<"路徑如下(按順序輸出每一步的坐標(biāo))："<<endl;top=turn(top);while(top!=NULL)cout<<"("<<top->i<<" , "<<top->j&l