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

1、 目錄第一部分 需求分析第二部分 詳細(xì)設(shè)計(jì)第三部分 調(diào)試分析第四部分 用戶手冊第五部分 測試結(jié)果第六部分 附錄第七部分 參考文獻(xiàn)一、 需求分析 1、對于給定的一個(gè)迷宮，給出一個(gè)出口和入口，找一條從入口到出口的通路，并把這條通路顯示出來；如果沒有找到這樣的通路給出沒有這樣通路的信息。2、可以用一個(gè)mn的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計(jì)一個(gè)程序，對任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。3、編寫一個(gè)求解迷宮的非遞歸程序。求得的通路以三元組(i，j，d)的形式輸出，其中：(i，j)指示迷宮中的一個(gè)坐標(biāo)，d表示走到下一坐標(biāo)的方向。4、由于迷宮是任意給定的

2、，所以程序要能夠?qū)o定的迷宮生成對應(yīng)的矩陣表示，所以程序的輸入包括了矩陣的行數(shù)、列數(shù)、迷宮內(nèi)墻的個(gè)數(shù)、迷宮內(nèi)墻的坐標(biāo)、所求的通路的入口坐標(biāo)、出口坐標(biāo)。二、詳細(xì)設(shè)計(jì) 1、計(jì)算機(jī)解迷宮通常用的是“窮舉求解“方法，即從人口出發(fā)，順著某一個(gè)方向進(jìn)行探索，若能走通，則繼續(xù)往前進(jìn)；否則沿著原路退回，換一個(gè)方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達(dá)出口，則所設(shè)定的迷宮沒有通路。可以二維數(shù)組存儲迷宮數(shù)據(jù)，通常設(shè)定入口點(diǎn)的下標(biāo)為(1，1)，出口點(diǎn)的下標(biāo)為(n，n)。為處理方便起見，可在迷宮的四周加一圈障礙。對于迷宮中任一位置，均可約定有東、南、西、北四個(gè)方向可通。2、如果在某

3、個(gè)位置上四個(gè)方向都走不通的話，就退回到前一個(gè)位置，換一個(gè)方向再試，如果這個(gè)位置已經(jīng)沒有方向可試了就再退一步，如果所有已經(jīng)走過的位置的四個(gè)方向都試探過了，一直退到起始點(diǎn)都沒有走通，那就說明這個(gè)迷宮根本不通。3、所謂走不通不單是指遇到墻擋路，還有已經(jīng)走過的路不能重復(fù)走第二次，它包括曾經(jīng)走過而沒有走通的路。顯然為了保證在任何位置上都能沿原路退回，需要用一個(gè)后進(jìn)先出的結(jié)構(gòu)即棧來保存從入口到當(dāng)前位置的路徑。并且在走出出口之后，棧中保存的正是一條從入口到出口的路徑。4、若當(dāng)前位置“可通”，則納入“當(dāng)前路徑”，并繼續(xù)朝“下一位置”探索；若當(dāng)前位置“不可通”，則應(yīng)順著“來的方向”退回到“前一通道塊”，然后朝著

4、除“來向”之外的其他方向繼續(xù)探索；若該通道塊的四周四個(gè)方塊均“不可通”，則應(yīng)從“當(dāng)前路徑”上刪除該通道塊。所謂“下一位置”指的是“當(dāng)前位置”四周四個(gè)方向（東、南、西、北）上相鄰的方塊。假設(shè)以棧S記錄“當(dāng)前路徑”，則棧頂中存放的是“當(dāng)前路徑上最后一個(gè)通道塊”。由此，“納入路徑”的操作即為“當(dāng)前位置入?！保弧皬漠?dāng)前路徑上刪除前一通道塊”的操作即為“出?！?。5、找通路的程序的關(guān)鍵部分可以表示如下：do 若當(dāng)前位置可通， 則將當(dāng)前位置插入棧頂； / 納入路徑 若該位置是出口位置，則算法結(jié)束； / 此時(shí)棧中存放的是一條從入口位置到出口位置的路徑否則切換當(dāng)前位置的東鄰方塊為新的當(dāng)前位置； 否則若棧不空且棧

5、頂位置尚有其他方向未被探索， 則設(shè)定新的當(dāng)前位置為: 沿順時(shí)針方向旋轉(zhuǎn)找到的棧頂位置的下一相鄰塊； 若棧不空但棧頂位置的四周均不可通， 則 刪去棧頂位置； / 從路徑中刪去該通道塊若棧不空，則重新測試新的棧頂位置， 直至找到一個(gè)可通的相鄰塊或出棧至棧空； while (棧不空)； 6、程序中用的數(shù)據(jù)結(jié)構(gòu)解析： 程序中用了順序棧保存當(dāng)前找到的路徑，當(dāng)前位置不可通時(shí)，可以出棧，退回到前一個(gè)位置再繼續(xù)探索通路，棧的定義如下：struct SqStack SElemType *base; / 在棧構(gòu)造之前和銷毀之后，base的值為NULL SElemType *top; / 棧頂指針 int stac

6、ksize; / 當(dāng)前已分配的存儲空間，以元素為單位; / 順序棧 棧中元素的類型結(jié)構(gòu)程序中先定義了一個(gè)表示坐標(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; / 從此通道塊走向下一通道塊的方向(03表示東北) ;7、主函數(shù)的流程圖輸出從起點(diǎn)到終點(diǎn)的坐標(biāo)顯示當(dāng)前含有通路的迷宮結(jié)構(gòu)輸出沒有這樣的通路輸入所求通路的起點(diǎn)終點(diǎn)坐標(biāo)顯示當(dāng)前的迷宮的

7、結(jié)構(gòu)設(shè)置內(nèi)墻設(shè)置外墻輸入迷宮的行數(shù)列數(shù)（包括外墻） 三、 調(diào)試分析1、對于程序的設(shè)計(jì)由簡單到復(fù)雜，先設(shè)計(jì)一個(gè)整體的輪廓然后再慢慢的增加程序的功能，這樣能夠有效的減少錯(cuò)誤，功能慢慢的增加，在前一步的程序運(yùn)行通過之后再繼續(xù)增加功能，這樣在檢查錯(cuò)誤的時(shí)候比較有目的性，提高寫程序的效率。2、對于程序中的錯(cuò)誤，如果遇到說變量沒有定義或者數(shù)據(jù)結(jié)構(gòu)沒定義的錯(cuò)誤，可能是由于你在定義這種數(shù)據(jù)結(jié)構(gòu)的變量時(shí)數(shù)據(jù)結(jié)構(gòu)還沒有定義，也就是說在定義此數(shù)據(jù)結(jié)構(gòu)的變量的語句要放在聲明這種結(jié)構(gòu)體之后。3、在寫程序時(shí)要注意printf和scanf語句的格式，格式不對會得不到你想要的結(jié)果。4、寫程序時(shí)一定要瞻前顧后，前后一致，包括名

8、稱、數(shù)據(jù)類型等等。四、用戶手冊在使用程序時(shí)嚴(yán)格按照程序給出的提示一步一步來，下面給出程序正常執(zhí)行的步驟：1、程序會提示“請輸入迷宮的行數(shù)，列數(shù)（包括外墻）：”，這時(shí)就需要輸入表示迷宮的二維數(shù)組的行數(shù)和列數(shù)，需要注意的是由于我們在迷宮周圍加了一道墻，所以要輸入的行列數(shù)要比實(shí)際表示迷宮的行列數(shù)多兩行兩列。2、程序提示“請輸入迷宮內(nèi)墻單元數(shù)：”，此時(shí)需要輸入迷宮中墻的數(shù)目。3、程序提示“請依次輸入迷宮內(nèi)墻每個(gè)單元的行數(shù)，列數(shù)：”，此時(shí)要輸入迷宮中所有墻的坐標(biāo)，我們用數(shù)組中的一個(gè)元素來表示墻。4、在輸入了迷宮所有內(nèi)墻的坐標(biāo)后，程序會顯示出迷宮的結(jié)構(gòu)，然后程序會提示“請輸入起點(diǎn)的行數(shù)，列數(shù)：”，此時(shí)需要

9、輸入所求通路的起點(diǎn)坐標(biāo)。5、程序提示“請輸入終點(diǎn)的行數(shù)，列數(shù)：”，此時(shí)需要輸入所求通路的終點(diǎn)的坐標(biāo)。6、終點(diǎn)坐標(biāo)輸入完畢之后，程序會顯示出兩種運(yùn)行的結(jié)果，一種是輸出了迷宮的結(jié)構(gòu)，此時(shí)迷宮中已包含了所找的通路，用連續(xù)的數(shù)字表示出了通路在迷宮中是如何走的，此時(shí)迷宮中的-1表示找通路時(shí)走過的單元但是通路不通。注意：再輸入內(nèi)墻單元的坐標(biāo)是一定要細(xì)心，不要錯(cuò)輸，也不要漏輸。否則程序會出錯(cuò)。五、測試結(jié)果迷宮的測試數(shù)據(jù)如下：左上角(1，1)為入口，右下角(9，8)為出口。 1 2 3 4 5 6 7 800100010001000100000110101110010000100000100010101111

10、0011100010111000000程序的測試結(jié)果為：1、程序的開始界面2、輸入迷宮的行數(shù)列數(shù)之后3、輸入內(nèi)墻的個(gè)數(shù)之后4、再輸入了所有內(nèi)墻的坐標(biāo)后，程序會給出迷宮的結(jié)構(gòu)5、輸入所求通路的起點(diǎn)坐標(biāo)6、輸入所求通路的終點(diǎn)坐標(biāo)后會得到結(jié)果 結(jié)果以迷宮的形式輸出 結(jié)果用坐標(biāo)和下一位值的方向表示六、附錄（附有完整的源程序）源程序如下：#includestdio.h#includestdlib.h#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;#define ST

11、ACK_INIT_SIZE 10 / 存儲空間初始分配量#define STACKINCREMENT 2 / 存儲空間分配增量struct PosType / 迷宮坐標(biāo)位置類型 int x; / 行值 int y; / 列值 ;struct SElemType / 棧的元素類型 int ord; / 通道塊在路徑上的序號 PosType seat; / 通道塊在迷宮中的坐標(biāo)位置 int di; / 從此通道塊走向下一通道塊的方向(03表示東北) ;struct SqStack SElemType *base; / 在棧構(gòu)造之前和銷毀之后，base的值為NULL SElemType *top;

12、/ 棧頂指針 int stacksize; / 當(dāng)前已分配的存儲空間，以元素為單位; / 順序棧SqStack S;#define MAXLENGTH 25 / 設(shè)迷宮的最大行列為25typedef int MazeTypeMAXLENGTHMAXLENGTH; / 迷宮數(shù)組行列 / 全局變量 MazeType m; / 迷宮數(shù)組 int curstep=1; / 當(dāng)前足跡,初值為1 Status InitStack(SqStack &S) / 構(gòu)造一個(gè)空棧S if(!(S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType) e

13、xit(OVERFLOW); / 存儲分配失敗 S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; Status StackEmpty(SqStack S) / 若棧S為空棧，則返回TRUE，否則返回FALSE if(S.top=S.base) return TRUE; else return FALSE; Status Push(SqStack &S,SElemType e) / 插入元素e為新的棧頂元素 if(S.top-S.base=S.stacksize) / 棧滿，追加存儲空間 S.base=(SElemType*) reall

14、oc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType); if(!S.base) exit(OVERFLOW); / 存儲分配失敗 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *(S.top)+=e; return OK; Status Pop(SqStack &S,SElemType &e) / 若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR if(S.top=S.base) return ERROR; e=*-S.top; return O

15、K; Status Pass(PosType b) / 當(dāng)迷宮m的b點(diǎn)的序號為0(可通過路徑)，return OK; 否則，return ERROR。 if(mb.xb.y=0) return OK; else return ERROR; void FootPrint(PosType a) / 使迷宮m的a點(diǎn)的序號變?yōu)樽阚E(curstep) ma.xa.y=curstep; PosType NextPos(PosType c,int di) / 根據(jù)當(dāng)前位置及移動(dòng)方向，返回下一位置 PosType direc4=0,1,1,0,0,-1,-1,0; / 行增量,列增量 / 移動(dòng)方向,依次為東南

16、西北 c.x+=direcdi.x; c.y+=direcdi.y; return c; void MarkPrint(PosType b) / 使迷宮m的b點(diǎn)的序號變?yōu)?1(不能通過的路徑) mb.xb.y=-1; Status MazePath(PosType start,PosType end) / 算法3.3 / 若迷宮maze中存在從入口start到出口end的通道，則求得一條 / 存放在棧中(從棧底到棧頂)，并返回TRUE；否則返回FALSE PosType curpos; InitStack(S); SElemType e; curpos=start; do if(Pass(cu

17、rpos) / 當(dāng)前位置可以通過，即是未曾走到過的通道塊 FootPrint(curpos); / 留下足跡 e.ord=curstep; e.seat.x=curpos.x; e.seat.y=curpos.y; e.di=0; Push(S,e); / 入棧當(dāng)前位置及狀態(tài) curstep+; / 足跡加1 if(curpos.x=end.x&curpos.y=end.y) / 到達(dá)終點(diǎn)(出口) return TRUE; curpos=NextPos(curpos,e.di); else / 當(dāng)前位置不能通過 if(!StackEmpty(S) Pop(S,e); / 退棧到前一位置 cur

18、step-; while(e.di=3&!StackEmpty(S) / 前一位置處于最后一個(gè)方向(北) MarkPrint(e.seat); / 留下不能通過的標(biāo)記(-1) Pop(S,e); / 退回一步 curstep-; if(e.di3) / 沒到最后一個(gè)方向(北) e.di+; / 換下一個(gè)方向探索 Push(S,e); curstep+; curpos=NextPos(e.seat,e.di); / 設(shè)定當(dāng)前位置是該新方向上的相鄰塊 while(!StackEmpty(S); return FALSE; void Print(int x,int y) / 輸出迷宮的解 int i,j; for(i=0;ix;i+) for(j=0;jy;j+) printf(%3d,mij); printf(n); void main() PosType begin,end; int i,j,x,y,x1,y1; SElemType a; SqStack T; InitStack(T); printf(請輸入迷宮的行數(shù),列數(shù)(包括外墻)：); scanf(%d%d,&x,&y); for(i=0;iy;i+) / 定義周邊值為0(同墻) m0i=1; / 行周邊 mx-1i=1; for(j=1;jx-1