數(shù)據(jù)結構課程設計-迷宮問題(2)

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

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

3、能走通，則繼續(xù)往前進；否則沿著原路退回，換一個方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達出口，則所設定的迷宮沒有通路?？梢远S數(shù)組存儲迷宮數(shù)據(jù)，通常設定入口點的下標為 （1 ， 1） ，出口點的下標為 （n ， n） 。為處理方便起見，可在迷宮的四周加一圈障礙。對于迷宮中任一位置，均可約定有東、南、西、北四個方向可通。2、如果在某個位置上四個方向都走不通的話，就退回到前一個位置，換一個方向再試，如果這個位置已經沒有方向可試了就再退一步，如果所有已經走過的位置的四個方向都試探過了，一直退到起始點都沒有走通，那就說明這個迷宮根本不通。3、所謂 "走不通

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

5、則應從“當前路徑”上刪除該通道塊。所謂“下一位置”指的是“當前位置”四周四個方向（東、南、西、北）上相鄰的方塊。假設以棧S 記錄“當前路徑” ，則棧頂中存放的是“當前路徑上最后一個通道塊” 。 由此， “納入路徑” 的操作即為 “當前位置入?！?；“從當前路徑上刪除前一通道塊”的操作即為“出?！?。5、找通路的程序的關鍵部分可以表示如下：do若當前位置可通，則將當前位置插入棧頂； / 納入路徑若該位置是出口位置，則算法結束；/ 此時棧中存放的是一條從入口位置到出口位置的路徑否則切換當前位置的東鄰方塊為新的當前位置；否則若棧不空且棧頂位置尚有其他方向未被探索，則設定新的當前位置為 : 沿順時針方

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

7、棧 棧中元素的類型結構程序中先定義了一個表示坐標的類型結構：struct PosType /迷宮坐標位置類型int x; /行值int y; /列值；棧中元素的類型結構如下：struct SElemType 棧的元素類型int ord; 通道塊在路徑上的序號PosType seat; 通道塊在迷宮中的坐標位置int di; /從此通道塊走向下一通道塊的方向（03表示東;7、主函數(shù)的流程圖輸入迷宮的行數(shù)列數(shù)（包括外墻）設置外墻設置內墻顯示當前輸入所求通路的起點終點坐標輸出沒有顯示當前含有通路的迷宮結構輸出從起點到終點的坐標手動設置自動生三、調試分析1、對于程序的設計由簡單到復雜，先設計一個整體的

8、輪廓然后再慢慢的增 加程序的功能，這樣能夠有效的減少錯誤，功能慢慢的增加，在前一步的程 序運行通過之后再繼續(xù)增加功能，這樣在檢查錯誤的時候比較有目的性，提高寫程序的效率。2、對于程序中的錯誤，如果遇到說變量沒有定義或者數(shù)據(jù)結構沒定義的錯誤，可能是由于你在定義這種數(shù)據(jù)結構的變量時數(shù)據(jù)結構還沒有定義，也就是說在定義此數(shù)據(jù)結構的變量的語句要放在聲明這種結構體之后。3、在寫程序時要注意printf 和 scanf 語句的格式，格式不對會得不到你想要的結果。4、寫程序時一定要瞻前顧后，前后一致，包括名稱、數(shù)據(jù)類型等等。四、用戶手冊在使用程序時嚴格按照程序給出的提示一步一步來，下面給出程序正常執(zhí)行的步驟：

9、1、程序會提示“請輸入迷宮的行數(shù)，列數(shù)（包括外墻） ： ” ，這時就需要輸入表示迷宮的二維數(shù)組的行數(shù)和列數(shù)， 需要注意的是由于我們在迷宮周圍加了一道墻，所以要輸入的行列數(shù)要比實際表示迷宮的行列數(shù)多兩行兩列。 、 程序提示 “請輸入迷宮內墻單元數(shù)： ” ， 此時需要輸入迷宮中墻的數(shù)目。3、程序提示“請依次輸入迷宮內墻每個單元的行數(shù)，列數(shù)：” ，此時要輸入迷宮中所有墻的坐標，我們用數(shù)組中的一個元素來表示墻。4、在輸入了迷宮所有內墻的坐標后，程序會顯示出迷宮的結構，然后程序會提示 “請輸入起點的行數(shù)， 列數(shù)： ” ， 此時需要輸入所求通路的起點坐標。5、程序提示“請輸入終點的行數(shù)，列數(shù)：” ，此時需

10、要輸入所求通路的終點的坐標。6、終點坐標輸入完畢之后，程序會顯示出兩種運行的結果，一種是輸出了迷宮的結構，此時迷宮中已包含了所找的通路，用連續(xù)的數(shù)字表示出了通路在迷宮中是如何走的，此時迷宮中的-1表示找通路時走過的單元但是通路 不通。注意：再輸入內墻單元的坐標是一定要細心，不要錯輸，也不要漏輸。否則程序會出錯。五、測試結果 迷宮的測試數(shù)據(jù)如下：左上角(1 , 1)為入口，右下角(9, 8)為出口。1 2 3 4 5 6 7 8001000100010001000001101011100100001000001000101011110011100010111000000程序的測試結果為:1、 程

11、序的開始界面六、附錄（附有完整的源程序）源程序如下：#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/ 初始長度 typedef int Status;struct PosType /坐標豎直為x,橫為yint x;int y;struct SElemType int ord; /

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

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

14、rn OK;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)/ 進棧if(S.top-S.base>=S.stacksize)/ 棧不滿 S.base=(SElemType *) realloc (S.base,(S.stacksize+STACKINCREMENT) * sizeof(SElemType);/ 開空間if(

15、!S.base) exit(OVERFLOW);/ 檢查是否開空間成功S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;/ 壓進棧里面return OK;Status Pass(PosType a)/ 傳參傳的是當前位置的坐標 / 檢查當前位置是墻還是通道if(ma.xa.y=0)return OK; elsereturn ERROR;Status FootPrint(PosType a)/ 對已經走過的路做成標記1 ， 2， 3， 4. 。ma.xa.y=curstep;PosType NextPos(PosType

16、 c,int di)/0-3 上下左右/ 作用是移動一個位置，所以需要傳進來位置，移動方向，畢竟位移量已經確定為 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(&q

17、uot; 匚"); printf("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)/

18、找通路InitStack(S);/ 保存可以走的路徑SElemType e;PosType curpos=start;/curpos 是指當前位置，將開始位置設為當前位置 doif(Pass(curpos)/ 如果當前位置的序號為0，即此位置不是迷宮中的墻即為能走的路。 FootPrint(curpos);/ 留下標記e.ord=curstep; / 輸出的時候的 1， 2， 3， 4， 5e.di=0;Push(S,e);/ 將這一步記錄，壓進棧中curstep+; / 再走一步 和 ord 一個性質，路徑的步數(shù)if(curpos.x=end.x&&curpos.y=end.

19、y) return TRUE;/ 如果已經是出口就完 成棧的記錄curpos=NextPos(curpos,e.di);/ 否則就 走一步else/ 如果當前位置是走過得 意思就是它的 序號不是 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);curstep+;c

20、urpos=NextPos(e.seat,e.di);/ 下一步怎么移動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;/ 障礙物坐標for(i=0;i<y;i+)m0i=1;mx-

21、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（" 輸入迷宮里面阻礙物的個數(shù):"）;scanf("%d",&j);printf(" 請輸入迷宮中障礙物坐標： n");for(i=0;i<j;i+)scanf("%d%d",&x1,&y1);mx1y1=1;printf("I*n");Print(x,y);printf("I*

22、迷宮圖迷宮圖*n");void Movingdirection(SElemType a)/ 用來顯示迷宮通路怎么走的switch(a.di)case 0:printf("%d%3dTbreak;case 1:printf("%d%3d break;case 2:printf("%d%3d break;case 3:printf("%d%3d break;void MazePathway(PosType begin,PosType end,int x,int y)/ 顯示迷宮通路圖 SElemType a;SqStack T;InitStack(

23、T);if(MazePath(begin,end)printf(" 迷宮通路如下圖所示:n");Print1(x,y);while(!StackEmpty(S)Pop(S,a);Push(T,a);printf(" 找到的路徑用坐標表示如下 :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.手動輸入。*n");printf("*2.自動生成。*n");printf("*3.退 出。*n");printf(" 請輸入： ")