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

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

一、

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

的長(zhǎng)方陣表示迷宮，0

和

1

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

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

0

和

1

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

和

1

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

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

S

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

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

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

沿順時(shí)針?lè)较蛐D(zhuǎn)找到的棧頂位置的下一相鄰塊；若棧不空但棧頂位置的四周均不可通，則{

刪去棧頂位置； //

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

while

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

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

SqStack{SElemType

*base;

//

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

的值為

NULLSElemType

*top;

//

棧頂指針int

stacksize;

//

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

//

順序棧②

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

PosType

//

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

x;

//

行值int

y;

//

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

SElemType

//

棧的元素類(lèi)型{int

ord;

//

通道塊在路徑上的＂序號(hào)＂PosType

seat;

//

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

di;

//

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

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

三、

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

printf

和

scanf

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

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

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

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.*****************