數(shù)據(jù)結(jié)構(gòu)課程設(shè)計迷宮問題

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計

一、

需求分析1、對于給定的一個迷宮，給出一個出口和入口，找一條從入口到出有這樣通路的信息。2、可以用一個

的長方陣表示迷宮，0

和

1

分別表示迷宮中的通路和障礙。設(shè)計一個程序，對任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。3、編寫一個求解迷宮的非遞歸程序。求得的通路以三元組(i，j，

表示走到下一坐標(biāo)的方向。對應(yīng)的矩陣表示，所以程序的輸入包括了矩陣的行數(shù)、列數(shù)、迷宮內(nèi)墻的個數(shù)、迷宮內(nèi)墻的坐標(biāo)、所求的通路的入口坐標(biāo)、出口坐標(biāo)。

0

和

1

分別代表通道和障礙物，所以只需要隨機生成0

和

1

然后再給最外圍都賦值為1，就形成了新的迷宮。二、詳細設(shè)計1、計算機解迷宮通常用的是“窮舉求解“方法，即從人口出發(fā)，順著某一個方向進行探索，若能走通，則繼續(xù)往前進；否則沿著原路退回，換一個方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達出口，則所設(shè)定的迷宮沒有通路。點的下標(biāo)為(n，n)。為處理方便起見，可在迷宮的四周加一圈障礙。對于迷宮中任一位置，均可約定有東、南、西、北四個方向可通。2、如果在某個位置上四個方向都走不通的話，就退回到前一個位沒有走通，那就說明這個迷宮根本不通。重復(fù)走第二次"，它包括"曾經(jīng)走過而沒有走通的路"。顯然為了保證在任何位置上都能沿原路退回，需要用一個"后進先出"的結(jié)構(gòu)即棧來保存從入口到當(dāng)前位置的路徑。并且在走出出口之后，棧中保存的正是一條從入口到出口的路徑。，

，道塊。北）上相鄰的方塊。假設(shè)以棧

S

“ ?！?。5、找通路的程序的關(guān)鍵部分可以表示如下：do{若當(dāng)前位置可通，則{將當(dāng)前位置插入棧頂； //

納入路徑若該位置是出口位置，則算法結(jié)束；//

此時棧中存放的是一條從入口位置到出口位置的路徑否則切換當(dāng)前位置的東鄰方塊為新的當(dāng)前位置；}否則{若棧不空且棧頂位置尚有其他方向未被探索，則設(shè)定新的當(dāng)前位置為:

沿順時針方向旋轉(zhuǎn)找到的棧頂位置的下一相鄰塊；若棧不空但棧頂位置的四周均不可通，則{

刪去棧頂位置； //

從路徑中刪去該通道塊若棧不空，則重新測試新的棧頂位置，直至找到一個可通的相鄰塊或出棧至棧空；}}}

while

6、程序中用的數(shù)據(jù)結(jié)構(gòu)解析：①

可以出棧，退回到前一個位置再繼續(xù)探索通路，棧的定義如下：struct

SqStack{SElemType

*base;

//

在棧構(gòu)造之前和銷毀之后，base

的值為

NULLSElemType

*top;

//

棧頂指針int

stacksize;

//

當(dāng)前已分配的存儲空間，以元素為單位};

//

順序棧②

棧中元素的類型結(jié)構(gòu)程序中先定義了一個表示坐標(biāo)的類型結(jié)構(gòu)：struct

PosType

//

迷宮坐標(biāo)位置類型{int

x;

//

行值int

y;

//

列值};棧中元素的類型結(jié)構(gòu)如下：struct

SElemType

//

棧的元素類型{int

ord;

//

通道塊在路徑上的＂序號＂PosType

seat;

//

通道塊在迷宮中的＂坐標(biāo)位置＂int

di;

//

從此通道塊走向下一通道塊的＂方向＂(0～3

表示東～北)};7、主函數(shù)的流程圖

三、

調(diào)試分析1、對于程序的設(shè)計由簡單到復(fù)雜，先設(shè)計一個整體的輪廓然后再慢慢的增加程序的功能，這樣能夠有效的減少錯誤，功能慢慢的增加，候比較有目的性，提高寫程序的效率。2、對于程序中的錯誤，如果遇到說變量沒有定義或者數(shù)據(jù)結(jié)構(gòu)沒定構(gòu)體之后。

printf

和

scanf

到你想要的結(jié)果。4、寫程序時一定要瞻前顧后，前后一致，包括名稱、數(shù)據(jù)類型等等。四、用戶手冊在使用程序時嚴格按照程序給出的提示一步一步來，下面給出程序正常執(zhí)行的步驟：行列數(shù)多兩行兩列。的數(shù)目。”3、程序提示“請依次輸入迷宮內(nèi)墻每個單元的行數(shù)，列數(shù)：，此”時要輸入迷宮中所有墻的坐標(biāo)，我們用數(shù)組中的一個元素來表示墻。4、在輸入了迷宮所有內(nèi)墻的坐標(biāo)后，程序會顯示出迷宮的結(jié)構(gòu)，”然后程序會提示“請輸入起點的行數(shù)，列數(shù)：，此時需要輸入所求通”路的起點坐標(biāo)?！?、程序提示“請輸入終點的行數(shù)，列數(shù)：，此時需要輸入所求通”路的終點的坐標(biāo)。6、終點坐標(biāo)輸入完畢之后，程序會顯示出兩種運行的結(jié)果，一種字表示出了通路在迷宮中是如何走的，此時迷宮中的-1

表示找通路時走過的單元但是通路不通。注意：再輸入內(nèi)墻單元的坐標(biāo)是一定要細心，不要錯輸，也不要漏輸。否則程序會出錯。五、測試結(jié)果迷宮的測試數(shù)據(jù)如下：左上角(1，1)為入口，右下角(9，8)為出口。

程序的測試結(jié)果為： 程序的開始界面六、附錄（附有完整的源程序）源程序如下：

TRUE

FALSE

ERROR

STACKINCREMENT

STACK_INIT_SIZE

//

{

x;

y;};

{

//

//

//};

{

};

S;

MAXLENGTH

//

//

//

{

OK;}

{

//

OK;}

{

ERROR;

FALSE;}

{{

*)

*

}

OK;}

{ //{

OK;}{

ERROR;}}

{}

{//

}

{}

//{

i,j;{{");");}}}

{

i,j;{{{");}

{");}

{");}}}}

{

do{

{

//

e

//

}

{{

{}

{}}}

FALSE;}

{

i,j;

}

{

i,j;

{}{}{{}}:");{}printf("**************************************************************************\n");printf("**************************************************************************\n");}

{{

}}

{

T;{{}{}}}

{

x,y;

i,j;{printf("*****************1.*****************\n");printf("*****************2.*****************