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

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計題 目： 迷宮求解班 級：學(xué) 號：作者姓名：指導(dǎo)教師：2012年12月11日目 錄1需求分析.12概要設(shè)計.12.1數(shù)據(jù)結(jié)構(gòu).12.1.1邏輯結(jié)構(gòu).12.1.1存儲結(jié)構(gòu).22.2.基本操作.3 2.2.1.迷宮中棧的基本操作.3 2.2.2.迷宮的抽象數(shù)據(jù)類型.32.2.3.本程序包含三個模塊.43詳細(xì)設(shè)計.54調(diào)試與分析.95用戶手冊96. 測試結(jié)果.107. 附錄.128. 參考文獻(xiàn).129、心得體會1210、小組成員工作分配.13一、 需求分析(1) 以二維數(shù)組mazen+2m+2表示迷宮，其中：maze0j和mazen+1j(0<=j<=m+1)及mazei

2、0和mazeim+1(0<=i<=j+1)為添加的一圈障礙。數(shù)組中以元素值為0的表示通路，1表示障礙，限定迷宮的大小，m，n<=0。(2) 迷宮的入口位置和出口位置可由用戶自行設(shè)定。(3) 如設(shè)定的迷宮處在通路，則值輸出迷宮中的通路，即0，現(xiàn)實的0連起來就是一個迷宮通路路徑；如設(shè)定的迷宮中不出在通路，則輸出“該迷宮找不到通路!”；(4) 測試樣例：輸入迷宮的長寬為5和6，輸入迷宮為：1 0 0 1 1 10 0 1 1 1 11 0 0 0 1 10 1 0 1 1 11 1 0 0 0 0當(dāng)入口位置為（1,2），出口位置為（5,6）時，則輸出數(shù)據(jù)為：# # # # # #

3、# # 0 # 0 # 0 0 # 0 # 0 0 0 0 # # # # # # # #(5) 程序執(zhí)行的命令為：1、 輸入迷宮的尺寸；2、創(chuàng)建迷宮；3、輸入迷宮的的出入口位置；4、求解迷宮；輸出迷宮的解。二、 概要設(shè)計2.1.數(shù)據(jù)結(jié)構(gòu)2.1.1、邏輯結(jié)構(gòu)1）棧的定義：限定僅在表尾進(jìn)行插入或刪除操作的線性表；2）操作特性：后進(jìn)先出;3) ADT定義：ADT Stack數(shù)據(jù)對象：D=ai|aiCharSet,i=1,2,n,n>=0數(shù)據(jù)關(guān)系：R1=<ai-1,ai>|ai-1,aiD,i=2,n基本操作：InitStack(&S)操作結(jié)果：構(gòu)造一個空棧S。Destro

4、yStack（&S）初始條件：棧S 已存在。操作結(jié)果：銷毀棧S。ClearStack(&S)初始條件：棧S 已存在。操作結(jié)果：將S 清為空棧。StackLength(&S)初始條件：棧S 已存在。操作結(jié)果：返回棧S 的長度。StackEmpty(&S)初始條件：棧S 已存在。操作結(jié)果：若S 為空棧，則返回TRUE，否則返回FALSE。GetTop(S,&e)初始條件：棧S 已存在。操作結(jié)果：若棧S 不空，則以e 返回棧頂元素。Push(&S,e)初始條件：棧S 已存在。操作結(jié)果：在棧S 的棧頂插入新的棧頂元素e。Pop(&S,&e

5、)初始條件：棧S 已存在。操作結(jié)果：刪除S 的棧頂元素，并以e 返回其值。StackTraverse(S,visit()初始條件：棧S 已存在。操作結(jié)果：從棧底到棧頂依次對S 中的每個元素調(diào)用函數(shù)visit( )。ADT Stack2.1.2、存儲結(jié)構(gòu)1）順序存儲結(jié)構(gòu)：順序棧：是利用一塊地址連續(xù)的存儲單元來存放棧中的元素，同時要利用一個指針top 來指示棧頂元素的位置。注：在本迷宮求解程序設(shè)計中用到的就是棧的順序存儲結(jié)構(gòu)。/- 棧的順序存儲表示 -#define STACK_INIT_SIZE 100; #define STACKINCREMENT 10; typedef structSEle

6、mType*base; SElemType*top;int stacksize;SqStack;2）鏈?zhǔn)酱鎯Y(jié)構(gòu) 鏈?zhǔn)綏＃烘湕Ｊ侵覆捎面準(zhǔn)酱鎯Y(jié)構(gòu)存儲的棧。鏈棧是一種特殊的單鏈表，即限定僅在表頭進(jìn)行插入和刪除操作的單鏈表，因此鏈棧的結(jié)點結(jié)構(gòu)與單鏈表的結(jié)點結(jié)構(gòu)相同。2.2、基本操作2.2.1、迷宮中棧的基本操作：基本操作：InitStack(&S)操作結(jié)果：構(gòu)造一個空棧S。StackEmpty(&S)初始條件：棧S 已存在。操作結(jié)果：若 S 為空棧，則返回TRUE，否則返回FALSE。GetTop(S,&e)初始條件：棧S 已存在。操作結(jié)果：若棧 S 不空，則以e 返回棧

7、頂元素。Push(&S,e)初始條件：棧S 已存在。操作結(jié)果：在棧 S 的棧頂插入新的棧頂元素e。Pop(&S,&e)初始條件：棧S 已存在。操作結(jié)果：刪除 S 的棧頂元素，并以e 返回其值。2.2.2、迷宮的抽象數(shù)據(jù)類型ADT MazeType數(shù)據(jù)對象 : D=ai,j|ai,j,#、*，0<=i<=n+1, 0<=j<=m+1,m,n<=20 數(shù)據(jù)關(guān)系 :R=ROW,LINEROW=<ai-1,j,ai,j>|ai-1,j,ai,jD,i=1,m+1,j=0,n+1LINE=<ai-1,j,ai,j>|ai-1,

8、j,ai,jD,i=1,m+1,j=0,n+1 基本操作 :Status Pass(MazeType &maze,PosType curpos)初始條件: maze 存在迷宮, curpos 保存了當(dāng)前位置的坐標(biāo)操作結(jié)果: 如果可通,返回真,否則為假void FootPrint(MazeType &maze,PosType curpos)初始條件: maze 存在迷宮, curpos 保存了當(dāng)前位置的坐標(biāo)操作結(jié)果: 將當(dāng)前坐標(biāo)curpos處的maze值記為 足跡PosType NextPos(PosType CurPos,int di)初始條件: 各參數(shù)值已經(jīng)定義操作結(jié)果: 求

9、得以當(dāng)前位置為棧頂?shù)南乱粋€方向的元素的坐標(biāo)Status MazePath(SqStack &S, PosType start, PosType end) 初始條件: maze 存在迷宮地圖操作結(jié)果: 為建立的迷宮找到一條路徑ADT maze;2.2.3、本程序包含三個模塊1）主函數(shù)模塊：int main（） 初始化迷宮； 求解迷宮； 輸出迷宮的解；return 0；2）棧實現(xiàn)模塊實現(xiàn)棧的抽象殊絕類型3）迷宮實現(xiàn)模塊實現(xiàn)迷宮的抽象數(shù)據(jù)類型各模塊的調(diào)用關(guān)系如下：主函數(shù)模塊>迷宮模塊>棧模塊4）求解迷宮中一條通路的偽碼算法：設(shè)定當(dāng)前位置的初值為入口位置；do 若當(dāng)前位置可通， 則

10、將當(dāng)前位置插入棧頂； /納入路徑 若該位置是出口位置，則結(jié)束； /求得路徑存放在棧中 否則切換當(dāng)前位置的東鄰方塊為新的當(dāng)前位置；否則 若棧不空且棧位置尚有其他方向未被探索， 則設(shè)定新的當(dāng)前位置為沿順時針方向旋轉(zhuǎn)找到的棧頂位置的下一相鄰塊； 若棧不空但棧頂位置的四周均不可通， 則刪去棧頂位置； /后退一步，從路徑中刪去該通道塊； 若棧不空，則重新測試新的棧頂位置； 直到找到一個可通的相鄰塊或出棧至棧空；while(棧不空)；?？照f明沒有路徑存在三、 詳細(xì)設(shè)計1、 坐標(biāo)位置類型typedef structint row;int line;PosType;2、 迷宮類型Status Pass(Pos

11、Type CurPos)/判定當(dāng)前位置是否可以通過，即是未曾走到過的通道塊void FootPrint(PosType CurPos)/給當(dāng)前可通過的位置標(biāo)記PosType NextPos(PosType CurPos,int di)/探尋下一個位置，并標(biāo)記方向Status MazePath(SqStack &S, PosType start, PosType end)/求解迷宮maze中，從入口start到出口end的一條路徑，/如存在，返回OK，否則返回ERROR3、 棧類型typedef structint ord; /通道塊在路徑上的“序號”int di; /通道塊在迷宮中的“

12、坐標(biāo)位置”PosType seat;/從此通道塊走向下一通道塊的“方向”SElemType; /棧的元素類型typedef structSElemType *base;/在構(gòu)造棧之前和銷毀之后，base的值為NULLSElemType *top; /棧頂指針int stacksize; /當(dāng)前已分配的存儲空間，以元素為單位SqStack;/棧定義棧的基本操作如下：void InitStack(SqStack &S)/初始化棧，設(shè)棧S為空棧（S.top=NULL）void Push(SqStack &S,SElemType e)/若分配空間成功，則在S 的棧頂插入新的棧頂元素e/

13、否則增加棧棧的存儲空間，再插入新的元素int GetTop(SqStack &S,SElemType e)/若棧S不空，則以e帶回棧頂元素并返回TRUE，否則返回FALSEint Pop(SqStack &S,SElemType &e)/若棧不空，則刪除S 的棧頂元素并以e 帶回其值，且返回TRUE/否則返回FALSEint StackEmpty(SqStack S)/若S為空棧（S.top=NULL），則返回TRUE；否則返回FALSE具體部分操作的算法如下：void InitStack(SqStack &S) /初始化棧S為空棧（S.top=NULL）S.b

14、ase=(SElemType *)malloc(STACK_INIT_SIZE *sizeof(SElemType);if(!S.base) exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;/Initstackvoid Push(SqStack &S,SElemType e) /若分配空間成功，則在S 的棧頂插入新的棧頂元素e/否則增加棧棧的存儲空間，再插入新的元素if(S.top-S.base>=S.stacksize)S.base=(SElemType *)realloc(S.base,(S.stacksize+

15、STACKINCREMENT)*sizeof(SElemType);if(!S.base) exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;/Push4、 求解迷宮的偽碼算法：Status MazePath(SqStack &S, PosType start, PosType end) /若迷宮maze中存在從入口start到出口end的通道，則/一條存放在棧中(從棧底到棧頂為從入口到出口的路徑)，并返/回OK，否則返回ERRORPosType curpos;int curste

16、p;SElemType e;InitStack(S);curpos = start;/設(shè)定“當(dāng)前位置”為“初始位置”curstep = 1; /探索第一步do if (Pass(curpos) /當(dāng)前位置可以通過，即是未曾走到過的的通道塊/留下足跡FootPrint(curpos); e.di =1;e.ord = curstep;e.seat= curpos;Push(S,e); /加入路徑if (curpos.row=end.row && curpos.line=end.line) return OK; /到達(dá)出口位置curpos = NextPos(curpos, 1);

17、 curstep+;/探索下一步 else /當(dāng)前位置不能通過if (!StackEmpty(S) Pop(S,e);while (e.di=4 && !StackEmpty(S) FootPrint(e.seat); Pop(S,e); curstep-； if (e.di<4) e.di+; Push(S, e); curpos = NextPos(e.seat, e.di); /if /if while (!StackEmpty(S);return ERROR;/MazePath5、 主函數(shù)和其它函數(shù)的偽碼算法void printpath(SqStack S,int

18、 n,int m)/打印路徑printf("nn通路路徑為:n");/PosType start,end;SElemType * p=S.base;/定義一個指針p指向棧中的元素，設(shè)/定初值為p=S.basewhile(p!=S.top)mazep->seat.rowp->seat.line=2;p+;/將有效路徑的通道塊全部標(biāo)記為2或其他不為1或0的/值int i,flag=0;/打印出路徑，周圍用“#”圍成一圈作圍墻for(i=0;i<m+2;i+)printf("%c ",'#');printf("n&q

19、uot;);for(i=1;i<n+1;i+) printf("%c ",'#');for(int j=1;j<m+1;j+)if(mazeij=2) printf("%c ",'0');else printf(" ");printf("%c",'#');printf("n");for(i=0;i<m+2;i+)printf("%c ",'#');printf("nn");/

20、printpathint main()/主函數(shù)SqStack S;int r,l;while(true)printf("創(chuàng)建一個迷宮，請輸入迷宮長和寬(不得大于20):n");scanf("%d%d",&r,&l);if(r<1 | r>20|l<1|l>20)printf("輸入錯誤!");int i;printf("按行輸入%d*%d數(shù)據(jù)(0代表可通,1代表不可通):n",r,l);for(i=0;i<l+2;i+)maze0i=1;for(i=1;i<r+1

21、;i+)mazei0=1;for(int j=1;j<l+1;j+)scanf("%d",&mazeij);mazeil+1=1;for(i=0;i<l+2;i+)mazer+1i=1;PosType start,end;printf("輸入入口行坐標(biāo)和列坐標(biāo):");scanf("%d",&start.row);scanf("%d",&start.line);printf("輸入出口行坐標(biāo)和列坐標(biāo):");scanf("%d",&en

22、d.row);scanf("%d",&end.line);if(MazePath(S,start,end) printpath(S,r,l);else printf("該迷宮找不到通路!nn");return 0;/main四、 調(diào)試分析1、在本次的程序設(shè)計中，最核心的算法就是MazePath()函數(shù)，其他的算法并沒有出現(xiàn)什么問題。不過在最后輸出的時候本來想輸出路徑的先后順序，即maze12->maze22->maze32->maze33->maze43->maze53->maze54->maze55-&

23、gt;maze56，但是最后發(fā)現(xiàn)這樣只有在入口在左上角，出口在右下角時，才可以正確輸出。但是入口和出口是隨機的，若是入口在右下角，出口在左上角，則也同樣輸出maze12->maze22->maze32->maze33->maze43->maze53->maze54->maze55->maze56，雖然這兩個路徑是一樣的，但是有先后順序，故最后沒有輸出這種形式，將這段代碼注釋了（源程序中有注釋的代碼）；2、本來是想設(shè)計成既可以手動輸入迷宮又可以自動生成迷宮，但是感覺沒有太大的用處，所以最后省略了，只保留了手動輸入。3、在整個編寫的過程中，出現(xiàn)過很多錯誤，包括一些標(biāo)點符號的小錯誤，但是借助DEBUG調(diào)試器和數(shù)據(jù)觀察窗口，很快找出來問題的所在。五、 用戶手冊1、 本程序的運行環(huán)境為 DOS 操作系統(tǒng), 執(zhí)行文件為：迷宮求解.exe.2、 進(jìn)入演示程序后 , 即顯示文本方式的用戶界面:3、 根據(jù)提示輸入迷宮大小及迷宮后,輸入迷宮的行和