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

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)課程名稱：數(shù)據(jù)結(jié)構(gòu)題目：迷宮設(shè)計(jì)系別：軟件學(xué)院專業(yè)：移動(dòng)設(shè)備應(yīng)用開發(fā)班級(jí)：15級(jí)移動(dòng) 1班姓名：黃國峰學(xué)期： 2016-2017 第一學(xué)期指導(dǎo)教師：李博時(shí)間： 2016 年 12 月目錄第一部分需求分析第二部分詳細(xì)設(shè)計(jì)第三部分調(diào)試分析第四部分用戶手冊(cè)第五部分測(cè)試結(jié)果第六部分附錄第七部分參考文獻(xiàn)一、需求分析1 、對(duì)于給定的一個(gè)迷宮，給出一個(gè)出口和入口，找一條從入口到出口的通路，并把這條通路顯示出來； 如果沒有找到這樣的通路給出沒有這樣通路的信息。2、可以用一個(gè)m×n 的長(zhǎng)方陣表示迷宮， 0 和 1 分別表示迷宮中的通路和障礙。設(shè)計(jì)一個(gè)程序，對(duì)任意設(shè)定的迷宮，求出一條從入

2、口到出口的通路，或得出沒有通路的結(jié)論。3、編寫一個(gè)求解迷宮的非遞歸程序。求得的通路以三元組(i ，j ，d) 的形式輸出，其中： (i ，j) 指示迷宮中的一個(gè)坐標(biāo)， d 表示走到下一坐標(biāo)的方向。4、手動(dòng)設(shè)置迷宮是任意給定的，所以程序要能夠?qū)o定的迷宮生成對(duì)應(yīng)的矩陣表示，所以程序的輸入包括了矩陣的行數(shù)、列數(shù)、迷宮內(nèi)墻的個(gè)數(shù)、迷宮內(nèi)墻的坐標(biāo)、所求的通路的入口坐標(biāo)、出口坐標(biāo)。5、自動(dòng)生成的迷宮原理很簡(jiǎn)單， 因?yàn)?0 和 1 分別代表通道和障礙物，所以只需要隨機(jī)生成0 和 1 然后再給最外圍都賦值為1，就形成了新的迷宮。二、詳細(xì)設(shè)計(jì)1 、計(jì)算機(jī)解迷宮通常用的是“窮舉求解“方法，即從人口出發(fā)，順著某一

3、個(gè)方向進(jìn)行探索，若能走通，則繼續(xù)往前進(jìn)；否則沿著原路退回，換一個(gè)方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達(dá)出口，則所設(shè)定的迷宮沒有通路。可以二維數(shù)組存儲(chǔ)迷宮數(shù)據(jù)，通常設(shè)定入口點(diǎn)的下標(biāo)為(1 ，1) ，出口點(diǎn)的下標(biāo)為 (n ，n) 。為處理方便起見，可在迷宮的四周加一圈障礙。對(duì)于迷宮中任一位置，均可約定有東、南、西、北四個(gè)方向可通。2、如果在某個(gè)位置上四個(gè)方向都走不通的話，就退回到前一個(gè)位置，換一個(gè)方向再試，如果這個(gè)位置已經(jīng)沒有方向可試了就再退一步，如果所有已經(jīng)走過的位置的四個(gè)方向都試探過了，一直退到起始點(diǎn)都沒有走通，那就說明這個(gè)迷宮根本不通。3、所謂 &qu

4、ot; 走不通 " 不單是指遇到 " 墻擋路 " ，還有 " 已經(jīng)走過的路不能重復(fù)走第二次 " ，它包括 " 曾經(jīng)走過而沒有走通的路" 。顯然為了保證在任何位置上都能沿原路退回，需要用一個(gè)" 后進(jìn)先出 " 的結(jié)構(gòu)即棧來保存從入口到當(dāng)前位置的路徑。并且在走出出口之后，棧中保存的正是一條從入口到出口的路徑。4、若當(dāng)前位置“可通” ，則納入“當(dāng)前路徑” ，并繼續(xù)朝“下一位置”探索；若當(dāng)前位置“不可通”，則應(yīng)順著“來的方向” 退回到“前一通道塊”，然后朝著除“來向”之外的其他方向繼續(xù)探索；若該通道塊的四周四個(gè)方塊

5、均“不可通” ，則應(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)前位置；否則若棧不空且棧頂位置尚有其他方向未被探索，則設(shè)定新的當(dāng)前位置為:沿順

6、時(shí)針方向旋轉(zhuǎn)找到的棧頂位置的下一相鄰塊；若棧不空但棧頂位置的四周均不可通，則刪去棧頂位置；/從路徑中刪去該通道塊若棧不空，則重新測(cè)試新的棧頂位置，直至找到一個(gè)可通的相鄰塊或出棧至?？?； while (棧不空 ) ；6 、程序中用的數(shù)據(jù)結(jié)構(gòu)解析： 程序中用了順序棧保存當(dāng)前找到的路徑， 當(dāng)前位置不可通時(shí)，可以出棧，退回到前一個(gè)位置再繼續(xù)探索通路，棧的定義如下：struct SqStackSElemType *base; /在棧構(gòu)造之前和銷毀之后，base 的值為 NULLSElemType *top; /棧頂指針int stacksize; /當(dāng)前已分配的存儲(chǔ)空間，以元素為單位; /順序棧 棧中元

7、素的類型結(jié)構(gòu)程序中先定義了一個(gè)表示坐標(biāo)的類型結(jié)構(gòu)：struct PosType /迷宮坐標(biāo)位置類型int x; /行值int y; /列值;棧中元素的類型結(jié)構(gòu)如下：struct SElemType /棧的元素類型int ord; /通道塊在路徑上的序號(hào)PosType seat; /通道塊在迷宮中的坐標(biāo)位置int di; /從此通道塊走向下一通道塊的方向(0 3 表示東北 );7、主函數(shù)的流程圖輸入迷宮的行數(shù)設(shè)置外墻列數(shù)（包括外墻）手動(dòng)設(shè)置自動(dòng)生成自動(dòng)生成迷宮不需要進(jìn)行設(shè)置內(nèi)墻一步，其他都一樣 。設(shè)置內(nèi)墻顯示當(dāng)前的迷宮的結(jié)構(gòu)輸入所求通路的起點(diǎn)終點(diǎn)坐標(biāo)輸出沒有這顯示當(dāng)前含有通樣的通路路的迷宮結(jié)構(gòu)輸

8、出從起點(diǎn)到終點(diǎn)的坐標(biāo)三、調(diào)試分析1、對(duì)于程序的設(shè)計(jì)由簡(jiǎn)單到復(fù)雜，先設(shè)計(jì)一個(gè)整體的輪廓然后再慢慢的增加程序的功能，這樣能夠有效的減少錯(cuò)誤，功能慢慢的增加，在前一步的程序運(yùn)行通過之后再繼續(xù)增加功能，這樣在檢查錯(cuò)誤的時(shí)候比較有目的性，提高寫程序的效率。2、對(duì)于程序中的錯(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 語句的格式， 格式不對(duì)會(huì)得不到你想要的結(jié)果。4、寫程序時(shí)一定要瞻前顧后，前后一致，包括名稱、數(shù)據(jù)類型等等。四、用戶手

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

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

11、111000000程序的測(cè)試結(jié)果為：1、程序的開始界面六、附錄（附有完整的源程序）源程序如下：#include <stdio.h>#include <stdlib.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2#define STACKINCREMENT 10#define STACK_INIT_SIZE 100/ 初始長(zhǎng)度typedef int Status;struct PosType/ 坐標(biāo)豎直為 x，橫為 yint x;int y;struct SElem

12、Typeint ord; /序號(hào) 1，2，3，4，5，6.路徑的序號(hào)PosType seat; /坐標(biāo)int di;/移動(dòng)方向：上下左右;struct SqStackSElemType *base;SElemType *top;int stacksize;SqStack S;#define MAXLENGTH 30typedef int MazeTypeMAXLENGTHMAXLENGTH; /MazeType m; / 宏定義，定義一個(gè)數(shù)組地圖int curstep=2; / curstep代表的是足跡，走過的路將數(shù)組做成地圖。Status InitStack(SqStack &S)

13、S.base=(SElemType *)malloc(STACK_INIT_SIZE *sizeof(SElemType);/ 開空間，棧底是表頭if(!S.base) exit(OVERFLOW);/ 檢查是否開辟成功S.top=S.base;/設(shè)為空棧S.stacksize=STACK_INIT_SIZE;/ 設(shè)置長(zhǎng)度return OK;Status Pop(SqStack &S,SElemType &e)/得到棧頂元素if(S.base=S.top) return ERROR;/檢查是否為空棧 ，若為空則沒有棧頂 e=*-S.top; /棧的特殊存儲(chǔ)方式return OK

14、;Status StackEmpty(SqStack &S)/判斷是否為空if(!S.base) return ERROR;if(S.base=S.top) return TRUE;/為空else return FALSE;Status Push(SqStack &S,SElemType e)/進(jìn)棧if(S.top-S.base>=S.stacksize)/棧不滿S.base=(SElemType *) realloc (S.base,(S.stacksize+STACKINCREMENT) * sizeof(SElemType);/ 開空間if(!S.base) exi

15、t(OVERFLOW);/ 檢查是否開空間成功 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT;*S.top+=e;/壓進(jìn)棧里面return OK;Status Pass(PosType a)/傳參傳的是當(dāng)前位置的坐標(biāo)/檢查當(dāng)前位置是墻還是通道 if(ma.xa.y=0)return OK;elsereturn ERROR;Status FootPrint(PosType a)/對(duì)已經(jīng)走過的路做成標(biāo)記1，2，3，4.。ma.xa.y=curstep;PosType NextPos(PosType c,int di)/0-3上下左右/作

16、用是移動(dòng)一個(gè)位置，所以需要傳進(jìn)來位置，移動(dòng)方向，畢竟位移量已經(jīng)確定為 1PosType direc4=-1,0,1,0,0,-1,0,1;/上下左右c.x+=direcdi.x;c.y+=direcdi.y;return c;void MarkPrint(PosType a)/走不通ma.xa.y=-1;/ 此路不通void Print(int x,int y)/ 迷宮的輸出int i,j;for(i=0;i<x;i+)for(j=0;j<y;j+)if(mij=1)printf(" ");elseprintf(" 匚 ");printf(&

17、quot;n");void Print1(int x,int y)/ 有通路的迷宮的輸出int i,j;for(i=0;i<x;i+)for(j=0;j<y;j+)if(mij=1)printf(" ");else if(mij=-1|mij=0)printf(" 匚");else if(mij>=2)printf(" ");printf("n");Status MazePath(PosType start,PosType end)/找通路InitStack(S);/保存可以走的路徑SE

18、lemType e;PosType curpos=start;/curpos是指當(dāng)前位置，將開始位置設(shè)為當(dāng)前位置doif(Pass(curpos)/如果當(dāng)前位置的序號(hào)為 0，即此位置不是迷宮中的墻 即為能走的路。FootPrint(curpos);/留下標(biāo)記e.ord=curstep; /輸出的時(shí)候的 1， 2， 3， 4， 5e.seat.x=curpos.x;e.seat.y=curpos.y;/將當(dāng)前位置信息存入e 中e.di=0;Push(S,e);/將這一步記錄，壓進(jìn)棧中curstep+; /再走一步 和 ord 一個(gè)性質(zhì)，路徑的步數(shù) if(curpos.x=end.x&&a

19、mp;curpos.y=end.y) return TRUE;/ 如果已經(jīng)是出口就完成棧的記錄curpos=NextPos(curpos,e.di);/否則就走一步else/如果當(dāng)前位置是走過得意思就是它的序號(hào)不是 0if(!StackEmpty(S)/ 判斷棧是不是空，不是空就后退到上一步Pop(S,e);/后退到上一步curstep-;while(e.di=3&&!StackEmpty(S)/后退直到找到能走的路MarkPrint(e.seat);Pop(S,e);curstep-;if(e.di<3)/0 3 代表上下左右e.di+;Push(S,e);curste

20、p+;curpos=NextPos(e.seat,e.di);/下一步怎么移動(dòng)while(!StackEmpty(S);return FALSE;void Auto_maze(int x,int y)int i,j;printf("n 迷宮生成中 nn");system("pause");for(i=0;i<x;i+)for(j=0;j<y;j+)mij=rand()%2;void GenerateMaze(int x,int y)/生成迷宮地圖int i,j;int x1,y1;/ 障礙物坐標(biāo)for(i=0;i<y;i+)m0i=1;

21、mx-1i=1;for(j=0;j<x;j+)mj0=1;mjy-1=1;for(i=1;i<x-1;i+)for(j=1;j<y-1;j+)mij=0;printf(" 輸入迷宮里面阻礙物的個(gè)數(shù):");scanf("%d",&j);printf(" 請(qǐng)輸入迷宮中障礙物坐標(biāo)：n");for(i=0;i<j;i+)scanf("%d%d",&x1,&y1);mx1y1=1;printf("*迷宮圖*n");Print(x,y);printf(&quo

22、t;*迷宮圖*n");void Movingdirection(SElemType a)/ 用來顯示迷宮通路怎么走的switch(a.di)case 0:printf("%d%3d n",a.seat.x,a.seat.y);break;case 1:printf("%d%3dn",a.seat.x,a.seat.y);break;case 2:printf("%d%3dn",a.seat.x,a.seat.y);break;case 3:printf("%d%3dn",a.seat.x,a.seat.y

23、);break;void MazePathway(PosType begin,PosType end,int x,int y)/顯示迷宮通路圖SElemType a;SqStack T;InitStack(T);if(MazePath(begin,end)printf(" 迷宮通路如下圖所示 :n");Print1(x,y);while(!StackEmpty(S)Pop(S,a);Push(T,a);printf(" 找到的路徑用坐標(biāo)表示如下:n");while(!StackEmpty(T)Pop(T,a);Movingdirection(a);elseprintf(" 迷宮中沒有出路。n");int main()PosType begin,end;int x,y;int n;int i,j;while(1)printf("*1.printf("*2.printf("*3.手動(dòng)輸入。 *n");自動(dòng)生成。 *n");退出。 *n");printf(" 請(qǐng)輸入：