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

1、<p><b>　　目錄</b></p><p>　　第一部分 需求分析</p><p>　　第二部分 詳細設計</p><p>　　第三部分 調試分析</p><p>　　第四部分 用戶手冊</p><p>　　第五部分 測試結果<

2、;/p><p>　　第六部分 附錄</p><p>　　第七部分 參考文獻</p><p><b>　　需求分析</b></p><p>　　1、對于給定的一個迷宮，給出一個出口和入口，找一條從入口到出口的通路，并把這條通路顯示出來；如果沒有找到這樣的通路給出沒有這樣通路的信息。</p>&

3、lt;p>　　2、可以用一個m×n的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設計一個程序，對任意設定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結論。</p><p>　　3、編寫一個求解迷宮的非遞歸程序。求得的通路以三元組(i，j，d)的形式輸出，其中：(i，j)指示迷宮中的一個坐標，d表示走到下一坐標的方向。</p><p>　　4、由于迷宮是任意給定

4、的，所以程序要能夠對給定的迷宮生成對應的矩陣表示，所以程序的輸入包括了矩陣的行數(shù)、列數(shù)、迷宮內墻的個數(shù)、迷宮內墻的坐標、所求的通路的入口坐標、出口坐標。</p><p><b>　　二、詳細設計</b></p><p>　　1、計算機解迷宮通常用的是“窮舉求解“方法，即從人口出發(fā)，順著某一個方向進行探索，若能走通，則繼續(xù)往前進；否則沿著原路退回，換一個方向繼續(xù)探索，直

5、至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達出口，則所設定的迷宮沒有通路。</p><p>　　可以二維數(shù)組存儲迷宮數(shù)據(jù)，通常設定入口點的下標為(1，1)，出口點的下標為(n，n)。為處理方便起見，可在迷宮的四周加一圈障礙。對于迷宮中任一位置，均可約定有東、南、西、北四個方向可通。</p><p>　　2、如果在某個位置上四個方向都走不通的話，就退回到前一個位置，換一個方

6、向再試，如果這個位置已經沒有方向可試了就再退一步，如果所有已經走過的位置的四個方向都試探過了，一直退到起始點都沒有走通，那就說明這個迷宮根本不通。</p><p>　　3、所謂"走不通"不單是指遇到"墻擋路"，還有"已經走過的路不能重復走第二次"，它包括"曾經走過而沒有走通的路"?！　★@然為了保證在任何位置上都能沿原路退回，需要用一

7、個"后進先出"的結構即棧來保存從入口到當前位置的路徑。并且在走出出口之后，棧中保存的正是一條從入口到出口的路徑。</p><p>　　4、若當前位置“可通”，則納入“當前路徑”，并繼續(xù)朝“下一位置”探索；若當前位置“不可通”，則應順著“來的方向”退回到“前一通道塊”，然后朝著除“來向”之外的其他方向繼續(xù)探索；若該通道塊的四周四個方塊均“不可通”，則應從“當前路徑”上刪除該通道塊。</p&

8、gt;<p>　　所謂“下一位置”指的是“當前位置”四周四個方向（東、南、西、北）上相鄰的方塊。假設以棧S記錄“當前路徑”，則棧頂中存放的是“當前路徑上最后一個通道塊”。由此，“納入路徑”的操作即為“當前位置入棧”；“從當前路徑上刪除前一通道塊”的操作即為“出?！薄?lt;/p><p>　　5、找通路的程序的關鍵部分可以表示如下：</p><p>　　do{ 若當前位置可通，

9、 則{　　將當前位置插入棧頂； 　　　　　　// 納入路徑 　　若該位置是出口位置，則算法結束； 　　// 此時棧中存放的是一條從入口位置到出口位置的路徑　　否則切換當前位置的東鄰方塊為新的當前位置； }</p><p><b>　　否則</b></p><p>　　{　　若棧不空且棧頂位置尚有其他方向未被探索， 　則設定新的當前位置為: 沿順

10、時針方向旋轉找到的棧頂位置的下一相鄰塊；　 若棧不空但棧頂位置的四周均不可通， 　 則{ 刪去棧頂位置； 　　　　// 從路徑中刪去該通道塊　　　若棧不空，則重新測試新的棧頂位置， 　　直至找到一個可通的相鄰塊或出棧至棧空； 　　} </p><p><b>　　} </b></p><p>　　} while (棧不空)；</p>&

11、lt;p>　　6、程序中用的數(shù)據(jù)結構解析：</p><p>　?、?程序中用了順序棧保存當前找到的路徑，當前位置不可通時，可以出棧，退回到前一個位置再繼續(xù)探索通路，棧的定義如下：</p><p>　　struct SqStack</p><p><b>　　{</b></p><p>　　SElemType *ba

12、se; // 在棧構造之前和銷毀之后，base的值為NULL</p><p>　　SElemType *top; // 棧頂指針</p><p>　　int stacksize; // 當前已分配的存儲空間，以元素為單位</p><p><b>　　}; // 順序棧</b></p><p>　?、?棧中元素的類型結構&

13、lt;/p><p>　　程序中先定義了一個表示坐標的類型結構：</p><p>　　struct PosType // 迷宮坐標位置類型</p><p><b>　　{</b></p><p>　　int x; // 行值</p><p>　　int y; // 列值</p><p

14、><b>　　};</b></p><p>　　棧中元素的類型結構如下：</p><p>　　struct SElemType // 棧的元素類型</p><p><b>　　{</b></p><p>　　int ord; // 通道塊在路徑上的＂序號＂</p><p&g

15、t;　　PosType seat; // 通道塊在迷宮中的＂坐標位置＂</p><p>　　int di; // 從此通道塊走向下一通道塊的＂方向＂(0～3表示東～北)</p><p><b>　　};</b></p><p><b>　　7、主函數(shù)的流程圖</b></p><p><b>

16、;　　調試分析</b></p><p>　　1、對于程序的設計由簡單到復雜，先設計一個整體的輪廓然后再慢慢的增加程序的功能，這樣能夠有效的減少錯誤，功能慢慢的增加，在前一步的程序運行通過之后再繼續(xù)增加功能，這樣在檢查錯誤的時候比較有目的性，提高寫程序的效率。</p><p>　　2、對于程序中的錯誤，如果遇到說變量沒有定義或者數(shù)據(jù)結構沒定義的錯誤，可能是由于你在定義這種數(shù)據(jù)結構

17、的變量時數(shù)據(jù)結構還沒有定義，也就是說在定義此數(shù)據(jù)結構的變量的語句要放在聲明這種結構體之后。</p><p>　　3、在寫程序時要注意printf和scanf語句的格式，格式不對會得不到你想要的結果。</p><p>　　4、寫程序時一定要瞻前顧后，前后一致，包括名稱、數(shù)據(jù)類型等等。</p><p><b>　　四、用戶手冊</b></p&

18、gt;<p>　　在使用程序時嚴格按照程序給出的提示一步一步來，下面給出程序正常執(zhí)行的步驟：</p><p>　　1、程序會提示“請輸入迷宮的行數(shù)，列數(shù)（包括外墻）：”，這時就需要輸入表示迷宮的二維數(shù)組的行數(shù)和列數(shù)，需要注意的是由于我們在迷宮周圍加了一道墻，所以要輸入的行列數(shù)要比實際表示迷宮的行列數(shù)多兩行兩列。</p><p>　　2、程序提示“請輸入迷宮內墻單元數(shù)：”，此時

19、需要輸入迷宮中墻的數(shù)目。</p><p>　　3、程序提示“請依次輸入迷宮內墻每個單元的行數(shù)，列數(shù)：”，此時要輸入迷宮中所有墻的坐標，我們用數(shù)組中的一個元素來表示墻。</p><p>　　4、在輸入了迷宮所有內墻的坐標后，程序會顯示出迷宮的結構，然后程序會提示“請輸入起點的行數(shù)，列數(shù)：”，此時需要輸入所求通路的起點坐標。</p><p>　　5、程序提示“請輸入終點

20、的行數(shù)，列數(shù)：”，此時需要輸入所求通路的終點的坐標。</p><p>　　6、終點坐標輸入完畢之后，程序會顯示出兩種運行的結果，一種是輸出了迷宮的結構，此時迷宮中已包含了所找的通路，用連續(xù)的數(shù)字表示出了通路在迷宮中是如何走的，此時迷宮中的-1表示找通路時走過的單元但是通路不通。</p><p>　　注意：再輸入內墻單元的坐標是一定要細心，不要錯輸，也不要漏輸。否則程序會出錯。</p&

21、gt;<p><b>　　五、測試結果</b></p><p>　　迷宮的測試數(shù)據(jù)如下：左上角(1，1)為入口，右下角(9，8)為出口。</p><p>　　1 2 3 4 5 6 7 8</p><p><b>　　程序的測試結果為：</b></p>

22、<p><b>　　1、程序的開始界面</b></p><p>　　2、輸入迷宮的行數(shù)列數(shù)之后</p><p>　　3、輸入內墻的個數(shù)之后</p><p>　　4、再輸入了所有內墻的坐標后，程序會給出迷宮的結構</p><p>　　5、輸入所求通路的起點坐標</p><p>　　6、輸入

23、所求通路的終點坐標后會得到結果</p><p>　　① 結果以迷宮的形式輸出</p><p>　?、?結果用坐標和下一位值的方向表示</p><p>　　六、附錄（附有完整的源程序）</p><p><b>　　源程序如下：</b></p><p>　　#include"stdio.h&

24、quot;</p><p>　　#include"stdlib.h"</p><p>　　#define TRUE 1</p><p>　　#define FALSE 0</p><p>　　#define OK 1</p><p>　　#define ERROR 0</p><

25、p>　　#define OVERFLOW -2</p><p>　　typedef int Status;</p><p>　　#define STACK_INIT_SIZE 10 // 存儲空間初始分配量</p><p>　　#define STACKINCREMENT 2 // 存儲空間分配增量</p><p>　　struct P

26、osType // 迷宮坐標位置類型</p><p><b>　　{</b></p><p>　　int x; // 行值</p><p>　　int y; // 列值</p><p><b>　　};</b></p><p>　　struct SElemType // 棧的

27、元素類型</p><p><b>　　{</b></p><p>　　int ord; // 通道塊在路徑上的＂序號＂</p><p>　　PosType seat; // 通道塊在迷宮中的＂坐標位置＂</p><p>　　int di; // 從此通道塊走向下一通道塊的＂方向＂(0～3表示東～北)</p>

28、<p><b>　　};</b></p><p>　　struct SqStack</p><p><b>　　{</b></p><p>　　SElemType *base; // 在棧構造之前和銷毀之后，base的值為NULL</p><p>　　SElemType *top; //

29、 棧頂指針</p><p>　　int stacksize; // 當前已分配的存儲空間，以元素為單位</p><p><b>　　}; // 順序棧</b></p><p>　　SqStack S;</p><p>　　#define MAXLENGTH 25 // 設迷宮的最大行列為25</p><

30、;p>　　typedef int MazeType[MAXLENGTH][MAXLENGTH]; // 迷宮數(shù)組[行][列]</p><p><b>　　// 全局變量</b></p><p>　　MazeType m; // 迷宮數(shù)組</p><p>　　int curstep=1; // 當前足跡,初值為1</p>&l

31、t;p>　　Status InitStack(SqStack &S)</p><p>　　{ // 構造一個空棧S</p><p>　　if(!(S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType))))</p><p>　　exit(OVERFLOW); // 存儲分配失敗</

32、p><p>　　S.top=S.base;</p><p>　　S.stacksize=STACK_INIT_SIZE;</p><p>　　return OK;</p><p><b>　　}</b></p><p>　　Status StackEmpty(SqStack S)</p>

33、<p>　　{ // 若棧S為空棧，則返回TRUE，否則返回FALSE</p><p>　　if(S.top==S.base)</p><p>　　return TRUE;</p><p><b>　　else</b></p><p>　　return FALSE;</p><p>&

34、lt;b>　　}</b></p><p>　　Status Push(SqStack &S,SElemType e)</p><p>　　{ // 插入元素e為新的棧頂元素</p><p>　　if(S.top-S.base>=S.stacksize) // 棧滿，追加存儲空間</p><p><b>

35、;　　{</b></p><p>　　S.base=(SElemType*) realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));</p><p>　　if(!S.base)</p><p>　　exit(OVERFLOW); // 存儲分配失敗</p><p&

36、gt;　　S.top=S.base+S.stacksize;</p><p>　　S.stacksize+=STACKINCREMENT;</p><p><b>　　}</b></p><p>　　*(S.top)++=e;</p><p>　　return OK;</p><p><b&

37、gt;　　}</b></p><p>　　Status Pop(SqStack &S,SElemType &e)</p><p>　　{ // 若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR</p><p>　　if(S.top==S.base)</p><p>　　return ERR

38、OR;</p><p>　　e=*--S.top;</p><p>　　return OK;</p><p><b>　　}</b></p><p>　　Status Pass(PosType b)</p><p>　　{ // 當迷宮m的b點的序號為0(可通過路徑)，return OK; 否則，

39、return ERROR。</p><p>　　if(m[b.x][b.y]==0)</p><p>　　return OK;</p><p><b>　　else</b></p><p>　　return ERROR;</p><p><b>　　}</b></p&g

40、t;<p>　　void FootPrint(PosType a)</p><p>　　{ // 使迷宮m的a點的序號變?yōu)樽阚E(curstep)</p><p>　　m[a.x][a.y]=curstep;</p><p><b>　　}</b></p><p>　　PosType NextPos(PosT

41、ype c,int di)</p><p>　　{ // 根據(jù)當前位置及移動方向，返回下一位置</p><p>　　PosType direc[4]={{0,1},{1,0},{0,-1},{-1,0}}; // {行增量,列增量}</p><p>　　// 移動方向,依次為東南西北</p><p>　　c.x+=direc[di].x;&l

42、t;/p><p>　　c.y+=direc[di].y;</p><p><b>　　return c;</b></p><p><b>　　}</b></p><p>　　void MarkPrint(PosType b)</p><p>　　{ // 使迷宮m的b點的序號變?yōu)?/p>

43、-1(不能通過的路徑)</p><p>　　m[b.x][b.y]=-1;</p><p><b>　　}</b></p><p>　　Status MazePath(PosType start,PosType end) // 算法3.3</p><p>　　{ // 若迷宮maze中存在從入口start到出口end的通

44、道，則求得一條</p><p>　　// 存放在棧中(從棧底到棧頂)，并返回TRUE；否則返回FALSE</p><p>　　PosType curpos;</p><p>　　InitStack(S);</p><p>　　SElemType e;</p><p>　　curpos=start;</p>

45、<p><b>　　do</b></p><p><b>　　{</b></p><p>　　if(Pass(curpos))</p><p>　　{ // 當前位置可以通過，即是未曾走到過的通道塊</p><p>　　FootPrint(curpos); // 留下足跡</p&g

46、t;<p>　　e.ord=curstep;</p><p>　　e.seat.x=curpos.x;</p><p>　　e.seat.y=curpos.y;</p><p><b>　　e.di=0;</b></p><p>　　Push(S,e); // 入棧當前位置及狀態(tài)</p>&l

47、t;p>　　curstep++; // 足跡加1</p><p>　　if(curpos.x==end.x&&curpos.y==end.y) // 到達終點(出口)</p><p>　　return TRUE;</p><p>　　curpos=NextPos(curpos,e.di);</p><p><b&g

48、t;　　}</b></p><p><b>　　else</b></p><p>　　{ // 當前位置不能通過</p><p>　　if(!StackEmpty(S))</p><p><b>　　{</b></p><p>　　Pop(S,e); // 退棧到

49、前一位置</p><p>　　curstep--;</p><p>　　while(e.di==3&&!StackEmpty(S)) // 前一位置處于最后一個方向(北)</p><p><b>　　{</b></p><p>　　MarkPrint(e.seat); // 留下不能通過的標記(-1)&l

50、t;/p><p>　　Pop(S,e); // 退回一步</p><p>　　curstep--;</p><p><b>　　}</b></p><p>　　if(e.di<3) // 沒到最后一個方向(北)</p><p><b>　　{</b></p>

51、<p>　　e.di++; // 換下一個方向探索</p><p>　　Push(S,e);</p><p>　　curstep++;</p><p>　　curpos=NextPos(e.seat,e.di); // 設定當前位置是該新方向上的相鄰塊</p><p><b>　　}</b></p>

52、<p><b>　　}</b></p><p><b>　　}</b></p><p>　　}while(!StackEmpty(S));</p><p>　　return FALSE;</p><p><b>　　}</b></p><p&g

53、t;　　void Print(int x,int y)</p><p>　　{ // 輸出迷宮的解</p><p><b>　　int i,j;</b></p><p>　　for(i=0;i<x;i++)</p><p><b>　　{</b></p><p>　　f

54、or(j=0;j<y;j++)</p><p>　　printf("%3d",m[i][j]);</p><p>　　printf("\n");</p><p><b>　　}</b></p><p><b>　　}</b></p><

55、;p>　　void main()</p><p><b>　　{</b></p><p>　　PosType begin,end;</p><p>　　int i,j,x,y,x1,y1;</p><p>　　SElemType a;</p><p>　　SqStack T;</p&g

56、t;<p>　　InitStack(T);</p><p>　　printf("請輸入迷宮的行數(shù),列數(shù)(包括外墻)：");</p><p>　　scanf("%d%d",&x,&y);</p><p>　　for(i=0;i<y;i++) // 定義周邊值為0(同墻)</p>

57、<p><b>　　{</b></p><p>　　m[0][i]=1; // 行周邊</p><p>　　m[x-1][i]=1;</p><p><b>　　}</b></p><p>　　for(j=1;j<x-1;j++)</p><p><b&

58、gt;　　{</b></p><p>　　m[j][0]=1; // 列周邊</p><p>　　m[j][y-1]=1;</p><p><b>　　}</b></p><p>　　for(i=1;i<x-1;i++)</p><p>　　for(j=1;j<y-1;j+

59、+)</p><p>　　m[i][j]=0; // 定義通道初值為0</p><p>　　printf("請輸入迷宮內墻單元數(shù)：");</p><p>　　scanf("%d",&j);</p><p>　　printf("請依次輸入迷宮內墻每個單元的行數(shù),列數(shù)：\n");

60、</p><p>　　for(i=1;i<=j;i++)</p><p><b>　　{</b></p><p>　　scanf("%d%d",&x1,&y1);</p><p>　　m[x1][y1]=1; // 定義墻的值為1</p><p><

61、b>　　}</b></p><p>　　printf("迷宮結構如下:\n");</p><p>　　Print(x,y);</p><p>　　printf("請輸入起點的行數(shù),列數(shù)：");</p><p>　　scanf("%d%d",&begin.x,

62、&begin.y);</p><p>　　printf("請輸入終點的行數(shù),列數(shù)：");</p><p>　　scanf("%d%d",&end.x,&end.y);</p><p>　　if(MazePath(begin,end)) // 求得一條通路</p><p><

63、b>　　{</b></p><p>　　printf("此迷宮從入口到出口的一條路徑如下:\n");</p><p>　　Print(x,y); // 輸出此通路</p><p>　　while(!StackEmpty(S))</p><p><b>　　{</b></p>

64、;<p><b>　　Pop(S,a);</b></p><p>　　Push(T,a);</p><p><b>　　}</b></p><p>　　printf("找到的路徑用坐標表示如下:\n");</p><p>　　while(!StackEmpty(T)

65、)</p><p><b>　　{</b></p><p><b>　　Pop(T,a);</b></p><p>　　printf("%d%3d%3d\n",a.seat.x,a.seat.y,a.di);</p><p><b>　　}</b></

66、p><p><b>　　}</b></p><p><b>　　else</b></p><p>　　printf("此迷宮沒有從入口到出口的路徑\n");</p><p><b>　　}</b></p><p><b>　　七