1、用C語言解決迷宮設計與尋找通路的問題 摘 要 本課程設計主要解決設計一個迷宮以及在給出一組入口和出口的情況下，求出一條通路的問題。在課程設計中，系統(tǒng)開發(fā)平臺為Windows 2000，程序設計語言采用Visual C+6.0，數(shù)據(jù)結構采用鏈式棧存儲結構，程序運行平臺為Windows 98/2000/XP。對于迷宮設計問題，首先假設了用“0”表示此道路可通，“1”表示不可通，即障礙，然后采用了簡單的以時間產生隨機種子（0，1變量）和人工輸入0-1變量的方法產生迷宮矩陣。對求解迷宮通路問題，采用“窮舉求解”的方法和設計一個“先進后出”的棧來存放當前位置路徑，最后得出一條動態(tài)行走迷宮的通路。在程序設

2、計中，采用了結構化與面向對象兩種解決問題的方法。程序通過調試運行，初步實現(xiàn)了設計目標。 關鍵詞 程序設計；C+6.0；鏈式棧存儲結構；0-1；窮舉求解 1 引 言本課程設計主要解決設計一個迷宮以及在給出入口和出口的情況下求解一條通路的問題。利用“窮舉求解”的方法來判定當前位置是否可通以及利用棧“先進后出”的特點來存放當前位置可通的信息。1.1 課程設計目的在我們對一個具體的問題進行分析時，往往要抽象出一個模型，設計一個算法來實現(xiàn)所需要達到的功能。在此程序中，我們主要是綜合運用所學過的知識，回顧VC+編程的同時，熟悉并掌握數(shù)據(jù)結構中的算法分析與設計。同時，要掌握類C語言的算法轉換成C程序并上機調

3、試的基礎；通過本次課程設計，進一步鞏固C語言和數(shù)據(jù)結構課程所學的知識，特別是加強數(shù)據(jù)結構的理解與運用，熟悉面向對象的程序設計方法；通過此次課程設計的實踐，鍛煉自身程序設計的能力以及用C語言解決實際問題的能力，為以后后續(xù)課程的學習以及走上社會打好基礎。1.2 課程設計內容根據(jù)對題目的分析和設想，首先，設計一個鏈式棧存儲結構，動態(tài)的對迷宮數(shù)據(jù)進行操作（主要為入棧和出棧）；其次，定義一個二維數(shù)組和一個備份數(shù)組，用于存放迷宮數(shù)據(jù)，并在構建迷宮中，要完成對手動建立迷宮和自動建立迷宮方法的設計，并能輸出原始迷宮信息和原始圖形信息；再次，當程序接受外部輸入一組入口、出口數(shù)據(jù)后，能完成對該迷宮矩陣計算出是否存

4、在通路的情況，若存在通路，則分別用坐標通路和圖形通路輸出該通路，否則輸出無通路的信息；最后，設計完成實現(xiàn)多次輸入入口和出口數(shù)據(jù)后，計算出不同結果的情況，并能分別顯示出對應信息。1.3 概要設計計算機解迷宮通常用的是“窮舉求解”方法，即從入口出發(fā)，順著某一個方向進行探索，若能走通，則繼續(xù)往前進；否則沿著原路退回，換一個方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到則未能到達出口，則所設定的迷宮沒有通解1。可以用二維數(shù)組存儲迷宮數(shù)據(jù)，通常設定入口點的下標為（1，1），出口點的下標為（n,n）。為處理方便起見，可以迷宮的四周加一圈障礙。對于迷宮任一位置，均可約定有東、南、西、北

5、四個方向可通。最后，以方陣、坐標和圖形形式輸出迷宮及其通路。 2 程序設計說明2.1 定義抽象數(shù)據(jù)類型1、設定迷宮的抽象數(shù)據(jù)類型為ADT maze 數(shù)據(jù)對象：D= ai，j 、，0<=i<=m+1,0<=j<=n+1,m,n<=50 數(shù)據(jù)關系：R= ROW，COL ROW=<ai-1, j , ai，j >| ai-1, j, ai，jD,i=1,m+1,j=0,n+1 COL=< ai，j-1 , ai，j >| ai，j-1 ,ai，j D,i=1,m+1,j=0,n+1基本操作： create(&mazeN+2,a,b)初始條

6、件：二維數(shù)組mazea+2b+2已存在，其中自第1行至第a+1行、每行中自第1列至第b+1列的元素已有值，并且以值0表示通路，以值1表示障礙。操作結果：構造迷宮的0-1數(shù)組，以“0”表示通路，以“1”表示障礙，并在迷宮四周加上一圈障礙。prin(&mazeN+2,a,b) 初始條件：迷宮maze已被賦值。 操作結果：打印maze迷宮0-1矩陣以及圖形矩陣，表示通路，表示障礙。 MazePath( &maze,x1,x2,y1,y2)初始條件：迷宮maze已被賦值。操作結果：從入口（x1,y1）開始，判定當前位置是否可通，可通就入棧并判斷下一個方向是否可通 ，按具體情況做入棧和出

7、棧處理，直到出口（x2,y2）為止。printonglu1() 初始條件：棧stack不空。 操作結果：出棧，得到一條從入口到出口的通路printonglu2(int a,int b)初始條件：迷宮maze已存在。操作結果：若迷宮maze中存在一條通路，則按照如下規(guī)定改變迷宮maze的狀態(tài)；以字符、表示當前路徑上往下一位置的方向，字符“”表示出口,打印迷宮矩陣。 ADT maze2.2 定義棧結構體及二維數(shù)組1、定義堆棧結構typedef struct node /堆棧結構int row; /行int col; /列struct node *next;Mlink;Mlink *stack;/定

8、義一個棧 2、定義二維數(shù)組 int mazeM+2N+2;int backupM+2N+2; /備份數(shù)組2.3 主程序模塊 main() 設置背景顏色； 輸入矩陣的大小a,b; 建立矩陣； 備份矩陣； While(k!=0) 打印原始矩陣以及圖形矩陣； 輸入入口和出口位置； 判定有無通路； 輸出結果； 輸入k值，判定下一步的操作； 3 詳細實現(xiàn)3.1 流程圖 （1）主要設計思想流程如下3.1圖所示：開始 設計棧結構體創(chuàng)建迷宮矩陣設計各種所需的函數(shù)設計main函數(shù)結束 圖3.1 主要設計思想流程圖 （2）詳細設計流程圖通過對本問題的分析與概括和程序的分析，可得出如下3.2圖的詳細設計程序流程圖：

9、 開始輸入數(shù)組行列值建立迷宮矩陣并備份迷宮信息判斷變量k是否為0打印迷宮矩陣原始信息輸入入口和出口坐標信息判定MazePath值是否為1NY結束輸出坐標通路以及圖形通路輸出無通路NY用局部備份數(shù)組信息還原迷宮矩陣和全局備份數(shù)組 圖3.2 程序流程圖3.2 算法說明該程序用于解決設計一個迷宮，并在此基礎上給出一組入口和出口數(shù)據(jù)后能判定從該入口位置起是否有通路達到出口位置，有通路則輸出坐標通路和圖形通路兩種方式，否則輸出無通路的信息。本程序分兩大模塊，迷宮模塊和主程序模塊，迷宮模塊又包括建立迷宮矩陣函數(shù)、輸出迷宮矩陣原始信息函數(shù)、判斷通路函數(shù)和輸出最終信息函數(shù)（包括輸出坐標通路函數(shù)和輸出圖形通路函

10、數(shù)兩種）五大函數(shù)，主程序模塊主要為調用函數(shù)和while語句來判定是否重復執(zhí)行操作。其中建立迷宮矩陣函數(shù)包括手動建立和自動建立兩種功能，手動建立即人為的輸入0-1數(shù)據(jù)，直至達到二維數(shù)組大小的要求，自動建立是利用時間來產生隨機種子，從而建立滿足大小的二維數(shù)組矩陣；輸出迷宮矩陣原始信息函數(shù)的功能是首先輸出帶有行列號的0-1矩陣，再輸出以表示通路，表示障礙的圖形矩陣；判斷通路函數(shù)首先判定由實參傳遞過來的入口坐標位置是否可通，然后再決定是否將其入棧，之后再執(zhí)行后續(xù)操作，即若入口可通，則入棧，然后判定該位置的四方相鄰的方向，若有一個方向的相鄰位置可通，則將該相鄰位置入棧，依次方法窮舉求解下去，若能到達出口

11、位置，最后將出口位置入棧并返回函數(shù)值“1”，否則返回函數(shù)值“0”；輸出坐標通路函數(shù)的功能是若存在通路，則利用棧“先進后出”的特點輸出從入口到出口的一條通路；輸出圖形通路函數(shù)的功能是若存在通路，利用棧中元素作比較，將棧中元素的信息和二維數(shù)組作比較，將二維數(shù)組對應位置上的圖形改為、并輸出。在主程序中，首先調用建立迷宮矩陣函數(shù)建立一個迷宮，然后用while語句來選擇是否重復執(zhí)行來求取不同通路。 3.3 主要算法設計（1）、結構體的定義 typedef struct node /堆棧結構int row; /行int col; /列struct node *next;Mlink;Mlink *stack

12、;/定義一個棧 （2）、主要函數(shù)聲明 void create(int mazeN+2,int a,int b)/建立迷宮 void prin(int mazeN+2,int a,int b) /打印迷宮矩陣int Mazepath(int mazeN+2,int x1,int x2,int y1,int y2)/判定迷宮通路void printonglu1() /輸出坐標通路void printonglu2(int a,int b) /輸出圖形通路void main() /主函數(shù) system("color f0"); /背景為白色 int k=1,a,b; int maz

13、eM+2N+2;/迷宮矩陣 int abcM+2N+2,p,q; /備份數(shù)組以重復使用迷宮 printf("建立迷宮!n"); printf("輸入迷宮矩陣的行列數(shù)M,N!n"); scanf("%d%d",&a,&b); create(maze,a,b); /建立迷宮 for(p=0;p<=a+2;p+) for(q=0;q<=b+2;q+) abcpq=mazepq; while(k!=0) （3）、主要變量說明 M、N：預定義M和N的值，表示二維數(shù)組的大小； a、b：用于接收外部輸入的值，按操作者意愿

14、建立一定大小的迷宮； p:：棧指針，動態(tài)分配地址值； row、col：二維數(shù)組的行列值，分別接收變量a、b的值，使二維數(shù)組大小為mazeab； next：指向下一節(jié)點指針。4 運行環(huán)境與結果4.1 運行環(huán)境Microsoft Visual C+6.0。Visual C+(簡稱VC)是Microsoft公司推出的目前使用極為廣泛的基于Windows平臺的C+可視化開發(fā)環(huán)境。Visual C+6.0提出的控制臺應用程序對學習和掌握標準的C/C+內容非常有利。“可視”的資源編輯器與MFC類以及應用程序向導，為快速高效的開發(fā)出功能強大的Windows應用程序提供了極大的方便。利用Visual C+6.

15、0進行Internet、數(shù)據(jù)庫及多媒體等多方面的程序開發(fā)也很容易2。4.2 運行過程中遇到的問題與處理方法在設計本程序之初，本人遇到的第一個問題就是如何建立一個迷宮矩陣，難道要手動的一個個輸入數(shù)據(jù)嗎？如果建立10階以上的矩陣不是要輸入100個以上的元素，這對現(xiàn)實來說是不可行的。經過翻查資料后，我才知道能利用時間產生隨機種子，所用函數(shù)為srand(time()，再用i1=(int)(rand()%a)+1；j1=(int)(rand()%b)+1；mazei1j1=(int)(rand()%2)語句產生0-1變量，并且這種方法是經過驗證的產生0元素較多的方法，即通過這種方法產生的迷宮矩陣有多條通

16、路。基于這種方法和我們慣常的想法，我在編算法時提供了“手動建立”和“自動建立”兩種方法來創(chuàng)建迷宮矩陣。隨著程序設計的深入，我便遇到了第二個問題，與其說是問題，不如說是選擇。在判定迷宮中是否存在通路時，要設計一個棧來存放數(shù)據(jù)，在選擇用鏈式棧還是順序棧之間我徘徊了很久，因為在網上我看到的類似算法中都是用順序棧來實現(xiàn)迷宮通路的判定，進而構建了一些關于棧的相關算法，程序不僅顯得冗長而且多了些不必要的操作，如判定棧是否空或滿，而用鏈棧不僅不需要判定棧滿，也只是涉及棧的入棧和出棧操作，程序簡潔明了，因此我就廢棄前人的成果自己另寫了個算法，這對我來說確實是個挑戰(zhàn)。之后雖然又遇到了幾個問題，但都是小問題，一下

17、就解決了，所以在此不再說明。4.3 運行結果與分析（1）、自動建立迷宮矩陣情形對程序進行編譯運行后，窗口彈出如圖4.1的信息： 圖4.1 自動建立20*20迷宮矩陣這是在操作者輸入矩陣的行列數(shù)M、N并選擇功能鍵“2（自動建立）”后所顯示的界面。當我們再按下鍵盤上的任意鍵后，界面就會顯示如圖4.2圖4.3中的信息： 圖4.2 自動建立20階矩陣后的迷宮數(shù)字信息 圖4.3自動建立20階矩陣后的迷宮圖形信息界面中在顯示上示信息后并立刻彈出如下信息，如圖4.4： 圖4.4 等待輸入入口和出口的運行界面在本次輸入中，輸入的一組數(shù)據(jù)如上圖所示為入口（1/1）、出口（20/20），當輸入完成后，按回車鍵，程

18、序就進入到基于前面輸入的數(shù)據(jù)判定迷宮中是否存在一條從入口到出口的通路，并在判定完成后顯示如圖4.5、4.6中的信息： 圖4.5 存在通路時的坐標通路 圖4.6 存在通路時的圖形通路其中“輸入0結束”表示在完成上述操作后，如果你從鍵盤上輸入數(shù)字“0”，則此程序就會結束，相反，如果輸入的是非0，則程序會跳轉到如下圖界面，對同一迷宮矩陣進行不同的判定。 圖4.7 重新確定入口和出口數(shù)據(jù)界面此圖中的信息不僅包含已經重新輸入了迷宮入口（1、1）出口（17、4）的信息，更包含了在重新輸入數(shù)據(jù)后完成對該迷宮矩陣的判定，次時判定為“無通路！” (2) 手動建立迷宮矩陣情形 當我們要建立的迷宮矩陣的階數(shù)小于等于

19、10時，我們可選擇手動建立它，如圖4.8就是其中的情形： 圖4.8 選擇手動建立迷宮的界面 如上圖在我們選擇了功能鍵“1”后，我們就要手動輸入0或者1來建立迷宮矩陣，建立的迷宮矩陣信息如圖4.9所示： 圖4.9 手動建立迷宮的情形 輸入完數(shù)據(jù)后，按回車鍵，就會顯示如下相關信息，如圖4.10所示 圖4.10 手動建立后的迷宮的數(shù)字和圖形矩陣 在顯示完上示信息后，界面又會彈出如下信息給你輸入入口和出口數(shù)據(jù)，如圖4.11所示： 圖4.11 等待輸入入口和出口數(shù)據(jù)的運行界面 在上示界面中，當我們輸入如上信息，入口（1、1），出口（10、8）后，程序立刻判定出結果“無通路”，之后“在輸入0結束”的提示下

20、，我輸入“1”后，顯示如下信息，如圖4.12所示： 圖4.12 再次進入等待輸入入口和出口數(shù)據(jù)的界面 在這界面中，當輸入入口（3、1）出口（10、8）數(shù)據(jù)后，經判定后顯示如下信息，如圖4.13、4.14所示： 圖4.13 存在通路時的坐標通路 圖4.14 存在通路時的圖形通路 在顯示上示信息后，根據(jù)“輸入0結束”語句，我們可重復判定該迷宮的在不同入口，出口情形下的通路情況。在這我選擇了“0”結束了程序的運行。5 結束語  通過本次課程設計使我意識到自身許多方面的不足以及讓我學到了以前沒有學過的知識，使我對課程設計有了更深層次的認識和理解，懂得了靈活運用；也讓我意識到理論和實踐想結合的

21、重要性。在課程設計中，困難遇到過，也徘徊過，可是最終都被我一一解決了，我想說只要我們肯努力，愿意付出勞動，就能夠得到屬于我們自己所期望的東西，只要自己認真，敢于拼搏，勇于實踐，我們就會有收獲。 在此，我由衷的向我的指導老師 老師表示忠心的感謝，是她的悉心指導、嚴格要求和多次為我們細心的解疑和矯正，才使我的課程設計有了較為完善的一面，才使我有了能力的提高，并使我得到了充分的鍛煉。參考文獻1 嚴蔚敏，吳偉民數(shù)據(jù)結構（C語言版）. 北京：清華大學出版社，19972 鄭阿奇，丁有和，鄭進，周怡君Visual C+實用教程北京：電子工業(yè)出版社，2005，63第五版.北京：北京郵電大學，20044 太平洋

22、網站，/：2010-5-5附錄：結構化設計源程序清單/程序名稱：迷宮設計問題.cpp/程序功能：應用數(shù)據(jù)結構，采用C語言設計程序，實現(xiàn)迷宮的設計與判定通路/程序作者： /最后修改日期：2010/7/2#include<malloc.h>#include<time.h>#include<iostream>#include<stdlib.h>#include<stdio.h>#define M 50#define N 50typedef struct node /堆棧結構int row; /行int col; /列struct node

23、*next;Mlink;Mlink *stack;/定義一個棧int backupM+2N+2; /備份數(shù)組/*建立迷宮矩陣*/void create(int mazeN+2,int a,int b)/建立迷宮int i,j,flag;srand(unsigned)time(NULL); /以時間產生隨機種子for(i=0;i<=a+1;i+)for(j=0;j<=b+1;j+)mazeij=1;/將四周置為for(i=1;i<=a;i+)for(j=1;j<=b;j+)mazeij=0;/初始化矩陣backupij=0;/初始化備份矩陣printf("建立迷

24、宮矩陣(選擇或者)：n1,手動建立n2,自動建立n請輸入您的選擇：n");scanf("%d",&flag);if(flag=1)/手動建立迷宮printf("手動建立迷宮矩陣(0表示可通表示障礙):n");for(i=1;i<=a;i+)for(j=1;j<=b;j+)scanf("%d",&mazeij);if(flag=2) /自動建立迷宮int c,i1,j1;for(c=1;c<=a*b;c+) /矩陣初始為“”，隨機選擇位置賦予一個隨機的或， i1=(int)(rand()%a)

25、+1;j1=(int)(rand()%b)+1;mazei1j1=(int)(rand()%2); /隨機矩陣這樣可以產生更多的“”即通路printf("自動生成中n");system ("pause");for(i=1;i<=a;i+)for(j=1;j<=a;j+)backupij=mazeij;/備份數(shù)組矩陣/*打印迷宮矩陣*void prin(int mazeN+2,int a,int b)int i,j,z;printf("迷宮矩陣如下(0可通)：n ");for(z=1;z<=b;z+) /在矩陣上方標明

26、列號if(z<10) printf("%d ",z); else printf("%d ",z);for(i=1;i<=a;i+)printf("n"); if(i<10) printf("%d ",i); /矩陣左方標明行號else printf("%d ",i);for(j=1;j<=b;j+)printf("%d ",mazeij);printf("n迷宮圖形如下(白色可通)：n");printf(" ")

27、;for(z=1;z<=b;z+) /在圖形上方標明列號if(z<10) printf("%d ",z); else printf("%d",z);for(i=1;i<=a;i+)printf("n");if(i<10) printf("%d ",i); /矩陣左方標明行號else printf("%d",i);for(j=1;j<=b;j+)if(mazeij=0) printf("");if(mazeij=1) printf("&q

28、uot;);/*分割線*/int Mazepath(int mazeN+2,int x1,int x2,int y1,int y2)Mlink *p;if(mazex1y1=0) p=(Mlink *)malloc(sizeof(Mlink); p->row=x1; p->col=y1; p->next=NULL; stack=p; /將入口放入堆棧 mazestack->rowstack->col=1;/標志入口已訪問while(!(stack->row=NULL&&stack->col=NULL)&&(!(stack

29、->row=x2&&stack->col=y2)/未找到出口并且堆棧不空if(mazestack->row+1stack->col=0) /下面可通p=(Mlink *)malloc(sizeof(Mlink);p->row=stack->row+1;p->col=stack->col;p->next=stack; /入棧stack=p;mazestack->rowstack->col=1; /標記已訪問else if(mazestack->rowstack->col+1=0) /右面位置可通p=(M

30、link *)malloc(sizeof(Mlink);p->row=stack->row;p->col=stack->col+1;p->next=stack; /入棧stack=p;mazestack->rowstack->col=1;/標記已訪問else if(mazestack->row-1stack->col=0) /左面可通p=(Mlink *)malloc(sizeof(Mlink);p->row=stack->row-1;p->col=stack->col;p->next=stack; /入棧st

31、ack=p;mazestack->rowstack->col=1;/標記已訪問else if(mazestack->rowstack->col-1=0)/上面可通p=(Mlink *)malloc(sizeof(Mlink);p->row=stack->row;p->col=stack->col-1;p->next=stack; /入棧stack=p;mazestack->rowstack->col=1;/標記已訪問else /不可通返回上一點if (stack->next!=NULL) /堆棧里布置一個頂點則出棧并返回循

32、環(huán) p=stack; stack=stack->next; /出棧 free(p); /釋放空間else /堆棧里只有一個頂點即入口，此時若釋放空間出棧會使循環(huán) /控制語句無法比較（因為stack->col,stack->row都已不存在，) stack->row=NULL; stack->col=NULL; stack->next=NULL;if (stack->row=x2&&stack->col=y2) return (1);else return (0);else return(0);/*輸出坐標通路*/void prin

33、tonglu1()Mlink *q;int i=1;printf("其中的一條通道為：n"); q=stack; printf(" 出口<-"); while (q!=NULL) if(i%5=0) printf("n"); printf("%d%3d<-",q->row,q->col); q=q->next; i+; printf("入口n");/*分割線*/*輸出圖形通路*/2時輸出，時輸出，時輸出，時輸出void printonglu2(int a,int b

34、)printf("圖形通路如下：n");int z;printf(" ");for(z=1;z<=b;z+) /圖形上方標明列號if(z<10)printf("%d ",z); else printf("%d",z);int i,j;Mlink *p;p=stack;backupp->rowp->col=6;while (p->next!=NULL)if(p->next->col!=NULL)if( p->row > p->next->row ) b

35、ackupp->next->rowp->next->col=5;/下一節(jié)點在下else if(p->row<p->next->row) backupp->next->rowp->next->col=2;/下一節(jié)點在上else if(p->col>p->next->col) backupp->next->rowp->next->col=4;/下一節(jié)點在右else backupp->next->rowp->next->col=3;/下一節(jié)點在左else ;p=p->next;for(i