c數據結構迷宮問題課程設計

1、<p>　　用C語言解決迷宮設計與尋找通路的問題</p><p>　　摘 要 本課程設計主要解決設計一個迷宮以及在給出一組入口和出口的情況下，求出一條通路的問題。在課程設計中，系統(tǒng)開發(fā)平臺為Windows 2000，程序設計語言采用Visual C++6.0，數據結構采用鏈式棧存儲結構，程序運行平臺為Windows 98/2000/XP。對于迷宮設計問題，首先假設了用“0”表示此道路可通，“1”表示

2、不可通，即障礙，然后采用了簡單的以時間產生隨機種子（0，1變量）和人工輸入0-1變量的方法產生迷宮矩陣。對求解迷宮通路問題，采用“窮舉求解”的方法和設計一個“先進后出”的棧來存放當前位置路徑，最后得出一條動態(tài)行走迷宮的通路。在程序設計中，采用了結構化與面向對象兩種解決問題的方法。程序通過調試運行，初步實現了設計目標。 </p><p>　　關鍵詞 程序設計；C++6.0；鏈式棧存儲結構；0-1；窮舉求解<

3、/p><p><b>　　目錄</b></p><p>　　1 引言 ………………………………………………………1</p><p>　　1.1 課程設計目的………………………………………………….1</p><p>　　1.2 課程設計內容 ………………………………………………....1</p><p&g

4、t;　　1.3 概要設計 ………………………………………………………1</p><p>　　2 程序設計說明 …………………………………………….3</p><p>　　2.1 定義抽象數據類型 …………………………………………...3</p><p>　　2.2定義棧結構體及二維數組 ……………………………………4</p><p>　　2.

5、3 主程序模塊 ……………………………………………………4</p><p>　　3 詳細設計實現 ……………………………………………..6</p><p>　　3.1 流程圖 ..………………………………………………………..6</p><p>　　3.2算法說明 ……………………………………………………….7</p><p>　　3.3主要

6、算法設計 ………………………………………………….8</p><p>　　4 運行環(huán)境與結果 …………………………………………..11</p><p>　　4.1 運行環(huán)境 ………………………………………………………11</p><p>　　4.2運行過程中遇到的問題與處理方法 ………………………….11</p><p>　　4.3運行結果與

7、分析 ……………………………………………….12</p><p>　　5 結束語 ……………………………………………………...18</p><p>　　參考文獻 ……………………………………………………...19</p><p>　　附錄：結構化設計源程序清單…………………………………..20</p><p><b>　　1 引

8、 言</b></p><p>　　本課程設計主要解決設計一個迷宮以及在給出入口和出口的情況下求解一條通路的問題。利用“窮舉求解”的方法來判定當前位置是否可通以及利用?！跋冗M后出”的特點來存放當前位置可通的信息。</p><p><b>　　課程設計目的</b></p><p>　　在我們對一個具體的問題進行分析時，往往要抽象出一個模

9、型，設計一個算法來實現所需要達到的功能。</p><p>　　在此程序中，我們主要是綜合運用所學過的知識，回顧VC++編程的同時，熟悉并掌握數據結構中的算法分析與設計。</p><p>　　同時，要掌握類C語言的算法轉換成C程序并上機調試的基礎；</p><p>　　通過本次課程設計，進一步鞏固《C語言》和《數據結構》課程所學的知識，特別是加強數據結構的理解與運用，

10、熟悉面向對象的程序設計方法；通過此次課程設計的實踐，鍛煉自身程序設計的能力以及用C語言解決實際問題的能力，為以后后續(xù)課程的學習以及走上社會打好基礎。</p><p><b>　　課程設計內容</b></p><p>　　根據對題目的分析和設想，首先，設計一個鏈式棧存儲結構，動態(tài)的對迷宮數據進行操作（主要為入棧和出棧）；其次，定義一個二維數組和一個備份數組，用于存放迷宮

11、數據，并在構建迷宮中，要完成對手動建立迷宮和自動建立迷宮方法的設計，并能輸出原始迷宮信息和原始圖形信息；再次，當程序接受外部輸入一組入口、出口數據后，能完成對該迷宮矩陣計算出是否存在通路的情況，若存在通路，則分別用坐標通路和圖形通路輸出該通路，否則輸出無通路的信息；最后，設計完成實現多次輸入入口和出口數據后，計算出不同結果的情況，并能分別顯示出對應信息。</p><p><b>　　概要設計</b

12、></p><p>　　計算機解迷宮通常用的是“窮舉求解”方法，即從入口出發(fā)，順著某一個方向進行探索，若能走通，則繼續(xù)往前進；否則沿著原路退回，換一個方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到則未能到達出口，則所設定的迷宮沒有通解[1]。</p><p>　　可以用二維數組存儲迷宮數據，通常設定入口點的下標為（1，1），出口點的下標為（n,n）。為處理方便起

13、見，可以迷宮的四周加一圈障礙。對于迷宮任一位置，均可約定有東、南、西、北四個方向可通。最后，以方陣、坐標和圖形形式輸出迷宮及其通路。</p><p><b>　　2 程序設計說明</b></p><p>　　2.1 定義抽象數據類型</p><p>　　1、設定迷宮的抽象數據類型為</p><p><b>　

14、　ADT maze</b></p><p>　　{ 數據對象：D={ ai，j ∈{‘□’、‘■’、‘↑’、‘←’、‘→’‘↓’、‘㊣’}，0<=i<=m+1,0<=j<=n+1,m,n<=50}</p><p>　　數據關系：R={ ROW，COL }</p><p>　　ROW={<ai-1, j , ai，j

15、>| ai-1, j, ai，j∈D,i=1,……,m+1,j=0,……n+1 }</p><p>　　COL={< ai，j-1 , ai，j >| ai，j-1 ,ai，j ∈D,i=1,……,m+1,j=0,……n+1}</p><p><b>　　基本操作：</b></p><p>　　create(&maze

16、[][N+2],a,b)</p><p>　　初始條件：二維數組maze[a+2][b+2]已存在，其中自第1行至第a+1行、每行中自第1列至第b+1列的元素已有值，并且以值0表示通路，以值1表示障礙。</p><p>　　操作結果：構造迷宮的0-1數組，以“0”表示通路，以“1”表示障礙，并在迷宮四周加上一圈障礙。</p><p>　　prin(&maze

17、[][N+2],a,b)</p><p>　　初始條件：迷宮maze已被賦值。</p><p>　　操作結果：打印maze迷宮0-1矩陣以及圖形矩陣，‘□’表示通路，‘■’表示障礙。</p><p>　　MazePath( &maze,x1,x2,y1,y2)</p><p>　　初始條件：迷宮maze已被賦值。</p>

18、<p>　　操作結果：從入口（x1,y1）開始，判定當前位置是否可通，可通就入棧并判斷下一個方向是否可通 ，按具體情況做入棧和出棧處理，直到出口（x2,y2）為止。</p><p>　　printonglu1()</p><p>　　初始條件：棧stack不空。</p><p>　　操作結果：出棧，得到一條從入口到出口的通路</p><

19、;p>　　printonglu2(int a,int b)</p><p>　　初始條件：迷宮maze已存在。</p><p>　　操作結果：若迷宮maze中存在一條通路，則按照如下規(guī)定改變迷宮maze的狀態(tài)；以字符‘↑’、‘←’、‘→’‘↓’、表示當前路徑上往下一位置的方向，字符“㊣”表示出口,打印迷宮矩陣。</p><p>　　} ADT maze<

20、/p><p>　　2.2 定義棧結構體及二維數組</p><p><b>　　1、定義堆棧結構</b></p><p>　　typedef struct node //堆棧結構</p><p><b>　　{</b></p><p>　　int row; //行<

21、;/p><p>　　int col; //列</p><p>　　struct node *next;</p><p><b>　　}Mlink;</b></p><p>　　Mlink *stack;//定義一個棧</p><p><b>　　2、定義二維數組</b><

22、/p><p>　　int maze[M+2][N+2];</p><p>　　int backup[M+2][N+2]; //備份數組</p><p>　　2.3 主程序模塊</p><p><b>　　main()</b></p><p><b>　　{</b></p

23、><p><b>　　設置背景顏色；</b></p><p>　　輸入矩陣的大小a,b;</p><p><b>　　建立矩陣；</b></p><p><b>　　備份矩陣；</b></p><p>　　While(k!=0)</p><

24、;p>　　{ 打印原始矩陣以及圖形矩陣；</p><p>　　輸入入口和出口位置；</p><p><b>　　判定有無通路；</b></p><p><b>　　輸出結果；</b></p><p>　　輸入k值，判定下一步的操作；</p><p><b>　

25、　}</b></p><p><b>　　}</b></p><p><b>　　3 詳細實現</b></p><p><b>　　3.1 流程圖</b></p><p>　　（1）主要設計思想流程如下3.1圖所示：</p><p>　　圖

26、3.1 主要設計思想流程圖</p><p>　　（2）詳細設計流程圖</p><p>　　通過對本問題的分析與概括和程序的分析，可得出如下3.2圖的詳細設計程序流程圖：</p><p>　　圖3.2 程序流程圖</p><p><b>　　3.2 算法說明</b></p><p>　　該程序用于

27、解決設計一個迷宮，并在此基礎上給出一組入口和出口數據后能判定從該入口位置起是否有通路達到出口位置，有通路則輸出坐標通路和圖形通路兩種方式，否則輸出無通路的信息。本程序分兩大模塊，迷宮模塊和主程序模塊，迷宮模塊又包括建立迷宮矩陣函數、輸出迷宮矩陣原始信息函數、判斷通路函數和輸出最終信息函數（包括輸出坐標通路函數和輸出圖形通路函數兩種）五大函數，主程序模塊主要為調用函數和while語句來判定是否重復執(zhí)行操作。其中建立迷宮矩陣函數包括手動建立

28、和自動建立兩種功能，手動建立即人為的輸入0-1數據，直至達到二維數組大小的要求，自動建立是利用時間來產生隨機種子，從而建立滿足大小的二維數組矩陣；輸出迷宮矩陣原始信息函數的功能是首先輸出帶有行列號的0-1矩陣，再輸出以‘□’表示通路，‘■’表示障礙的圖形矩陣；判斷通路函數首先判定由實參傳遞過來的入口坐標位置是否可通，然后再決定是否將其入棧，之后再執(zhí)行后續(xù)操作，即若入口可通，則入棧，然后判定該位置的四方相鄰的方向，若有一個方向的相鄰位置可

29、通，則將該相鄰位置入棧，依次方法窮舉求解下去，若能到達出口位置，最后將出口位置入棧并返回函數值“1”，否則返回</p><p>　　在主程序中，首先調用建立迷宮矩陣函數建立一個迷宮，然后用while語句來選擇是否重復執(zhí)行來求取不同通路。</p><p><b>　　主要算法設計</b></p><p>　?。?）、結構體的定義</p>

30、;<p>　　typedef struct node //堆棧結構</p><p><b>　　{</b></p><p>　　int row; //行</p><p>　　int col; //列</p><p>　　struct node *next;</p><p>

31、;<b>　　}Mlink;</b></p><p>　　Mlink *stack;//定義一個棧</p><p>　?。?）、主要函數聲明</p><p>　　void create(int maze[][N+2],int a,int b)//建立迷宮</p><p>　　void prin(int maze[][N+

32、2],int a,int b) //打印迷宮矩陣</p><p>　　int Mazepath(int maze[][N+2],int x1,int x2,int y1,int y2)</p><p><b>　　//判定迷宮通路</b></p><p>　　void printonglu1() //輸出坐標通路</p><

33、;p>　　void printonglu2(int a,int b) //輸出圖形通路</p><p>　　void main() //主函數</p><p><b>　　{</b></p><p>　　system("color f0"); //背景為白色</p><p>

34、　　int k=1,a,b;</p><p>　　int maze[M+2][N+2];//迷宮矩陣</p><p>　　int abc[M+2][N+2],p,q; //備份數組以重復使用迷宮</p><p>　　printf("建立迷宮!!!\n");</p><p>　　printf("輸入迷宮矩陣的行列

35、數M,N!!!\n");</p><p>　　scanf("%d%d",&a,&b);</p><p>　　create(maze,a,b); //建立迷宮</p><p>　　for(p=0;p<=a+2;p++)</p><p>　　for(q=0;q<=b+2;q++)<

36、;/p><p>　　abc[p][q]=maze[p][q];</p><p>　　while(k!=0)</p><p><b>　　{ …………</b></p><p><b>　　}</b></p><p><b>　　}</b></p>

37、<p>　?。?）、主要變量說明</p><p>　　M、N：預定義M和N的值，表示二維數組的大??；</p><p>　　a、b：用于接收外部輸入的值，按操作者意愿建立一定大小的迷宮；</p><p>　　p:：棧指針，動態(tài)分配地址值；</p><p>　　row、col：二維數組的行列值，分別接收變量a、b的值，使二維數組大小為

38、maze[a][b]；</p><p>　　next：指向下一節(jié)點指針。</p><p><b>　　4 運行環(huán)境與結果</b></p><p><b>　　4.1 運行環(huán)境</b></p><p>　　Microsoft Visual C++6.0。Visual C++(簡稱VC)是Micros

39、oft公司推出的目前使用極為廣泛的基于Windows平臺的C++可視化開發(fā)環(huán)境。Visual C++6.0提出的控制臺應用程序對學習和掌握標準的C/C++內容非常有利?！翱梢暋钡馁Y源編輯器與MFC類以及應用程序向導，為快速高效的開發(fā)出功能強大的Windows應用程序提供了極大的方便。利用Visual C++6.0進行Internet、數據庫及多媒體等多方面的程序開發(fā)也很容易[2]。</p><p>　　4.2

40、運行過程中遇到的問題與處理方法</p><p>　　在設計本程序之初，本人遇到的第一個問題就是如何建立一個迷宮矩陣，難道要手動的一個個輸入數據嗎？如果建立10階以上的矩陣不是要輸入100個以上的元素，這對現實來說是不可行的。經過翻查資料后，我才知道能利用時間產生隨機種子，所用函數為srand(time())，再用i1=(int)(rand()%a)+1；j1=(int)(rand()%b)+1；maze[i1][

41、j1]=(int)(rand()%2)語句產生0-1變量，并且這種方法是經過驗證的產生0元素較多的方法，即通過這種方法產生的迷宮矩陣有多條通路?；谶@種方法和我們慣常的想法，我在編算法時提供了“手動建立”和“自動建立”兩種方法來創(chuàng)建迷宮矩陣。</p><p>　　隨著程序設計的深入，我便遇到了第二個問題，與其說是問題，不如說是選擇。在判定迷宮中是否存在通路時，要設計一個棧來存放數據，在選擇用鏈式棧還是順序棧之間我

42、徘徊了很久，因為在網上我看到的類似算法中都是用順序棧來實現迷宮通路的判定，進而構建了一些關于棧的相關算法，程序不僅顯得冗長而且多了些不必要的操作，如判定棧是否空或滿，而用鏈棧不僅不需要判定棧滿，也只是涉及棧的入棧和出棧操作，程序簡潔明了，因此我就廢棄前人的成果自己另寫了個算法，這對我來說確實是個挑戰(zhàn)。</p><p>　　之后雖然又遇到了幾個問題，但都是小問題，一下就解決了，所以在此不再說明。</p>

43、<p>　　4.3 運行結果與分析</p><p>　?。?）、自動建立迷宮矩陣情形</p><p>　　對程序進行編譯運行后，窗口彈出如圖4.1的信息：</p><p>　　圖4.1 自動建立20*20迷宮矩陣</p><p>　　這是在操作者輸入矩陣的行列數M、N并選擇功能鍵“2（自動建立）”后所顯示的界面。當我們再按下鍵

44、盤上的任意鍵后，界面就會顯示如圖4.2圖4.3中的信息：</p><p>　　圖4.2 自動建立20階矩陣后的迷宮數字信息</p><p>　　圖4.3自動建立20階矩陣后的迷宮圖形信息</p><p>　　界面中在顯示上示信息后并立刻彈出如下信息，如圖4.4：</p><p>　　圖4.4 等待輸入入口和出口的運行界面</p>

45、<p>　　在本次輸入中，輸入的一組數據如上圖所示為入口（1/1）、出口（20/20），當輸入完成后，按回車鍵，程序就進入到基于前面輸入的數據判定迷宮中是否存在一條從入口到出口的通路，并在判定完成后顯示如圖4.5、4.6中的信息：</p><p>　　圖4.5 存在通路時的坐標通路</p><p>　　圖4.6 存在通路時的圖形通路</p><p>　　

46、其中“輸入0結束”表示在完成上述操作后，如果你從鍵盤上輸入數字“0”，則此程序就會結束，相反，如果輸入的是非0，則程序會跳轉到如下圖界面，對同一迷宮矩陣進行不同的判定。</p><p>　　圖4.7 重新確定入口和出口數據界面</p><p>　　此圖中的信息不僅包含已經重新輸入了迷宮入口（1、1）出口（17、4）的信息，更包含了在重新輸入數據后完成對該迷宮矩陣的判定，次時判定為“無通路！

47、”</p><p>　　(2) 手動建立迷宮矩陣情形</p><p>　　當我們要建立的迷宮矩陣的階數小于等于10時，我們可選擇手動建立它，如圖4.8就是其中的情形：</p><p>　　圖4.8 選擇手動建立迷宮的界面</p><p>　　如上圖在我們選擇了功能鍵“1”后，我們就要手動輸入0或者1來建立迷宮矩陣，建立的迷宮矩陣信息如圖4.9

48、所示：</p><p>　　圖4.9 手動建立迷宮的情形</p><p>　　輸入完數據后，按回車鍵，就會顯示如下相關信息，如圖4.10所示</p><p>　　圖4.10 手動建立后的迷宮的數字和圖形矩陣</p><p>　　在顯示完上示信息后，界面又會彈出如下信息給你輸入入口和出口數據，如圖4.11所示：</p><p

49、>　　圖4.11 等待輸入入口和出口數據的運行界面</p><p>　　在上示界面中，當我們輸入如上信息，入口（1、1），出口（10、8）后，程序立刻判定出結果“無通路”，之后“在輸入0結束”的提示下，我輸入“1”后，顯示如下信息，如圖4.12所示：</p><p>　　圖4.12 再次進入等待輸入入口和出口數據的界面</p><p>　　在這界面中，當輸入入

50、口（3、1）出口（10、8）數據后，經判定后顯示如下信息，如圖4.13、4.14所示：</p><p>　　圖4.13 存在通路時的坐標通路</p><p>　　圖4.14 存在通路時的圖形通路</p><p>　　在顯示上示信息后，根據“輸入0結束”語句，我們可重復判定該迷宮的在不同入口，出口情形下的通路情況。在這我選擇了“0”結束了程序的運行。</p>

51、;<p><b>　　5 結束語 </b></p><p>　　通過本次課程設計使我意識到自身許多方面的不足以及讓我學到了以前沒有學過的知識，使我對課程設計有了更深層次的認識和理解，懂得了靈活運用；也讓我意識到理論和實踐想結合的重要性。在課程設計中，困難遇到過，也徘徊過，可是最終都被我一一解決了，我想說只要我們肯努力，愿意付出勞動，就能夠得到屬于我們自己所期望的東西，

52、只要自己認真，敢于拼搏，勇于實踐，我們就會有收獲。</p><p>　　在此，我由衷的向我的指導老師xx老師表示忠心的感謝，是她的悉心指導、嚴格要求和多次為我們細心的解疑和矯正，才使我的課程設計有了較為完善的一面，才使我有了能力的提高，并使我得到了充分的鍛煉。</p><p><b>　　參考文獻</b></p><p>　　[1] 嚴蔚敏，吳