用C語言解決迷宮設(shè)計(jì)與尋找通路的問題

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

2、計(jì)中，采用了結(jié)構(gòu)化與面向?qū)ο髢煞N解決問題的方法。程序通過調(diào)試運(yùn)行，初步實(shí)現(xiàn)了設(shè)計(jì)目標(biāo)。 關(guān)鍵詞 程序設(shè)計(jì)；C+6.0；鏈?zhǔn)綏４鎯Y(jié)構(gòu)；0-1；窮舉求解 1 引 言本課程設(shè)計(jì)主要解決設(shè)計(jì)一個(gè)迷宮以及在給出入口和出口的情況下求解一條通路的問題。利用“窮舉求解”的方法來判定當(dāng)前位置是否可通以及利用棧“先進(jìn)后出”的特點(diǎn)來存放當(dāng)前位置可通的信息。1.1 課程設(shè)計(jì)目的在我們對一個(gè)具體的問題進(jìn)行分析時(shí)，往往要抽象出一個(gè)模型，設(shè)計(jì)一個(gè)算法來實(shí)現(xiàn)所需要達(dá)到的功能。在此程序中，我們主要是綜合運(yùn)用所學(xué)過的知識，回顧VC+編程的同時(shí)，熟悉并掌握數(shù)據(jù)結(jié)構(gòu)中的算法分析與設(shè)計(jì)。同時(shí)，要掌握類C語言的算法轉(zhuǎn)換成C程序并上機(jī)調(diào)

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

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

5、四個(gè)方向可通。最后，以方陣、坐標(biāo)和圖形形式輸出迷宮及其通路。 2 程序設(shè)計(jì)說明2.1 定義抽象數(shù)據(jù)類型1、設(shè)定迷宮的抽象數(shù)據(jù)類型為ADT maze 數(shù)據(jù)對象：D= ai，j 、，0<=i<=m+1,0<=j<=n+1,m,n<=50 數(shù)據(jù)關(guān)系：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表示障礙。操作結(jié)果：構(gòu)造迷宮的0-1數(shù)組，以“0”表示通路，以“1”表示障礙，并在迷宮四周加上一圈障礙。prin(&mazeN+2,a,b) 初始條件：迷宮maze已被賦值。 操作結(jié)果：打印maze迷宮0-1矩陣以及圖形矩陣，表示通路，表示障礙。 MazePath( &maze,x1,x2,y1,y2)初始條件：迷宮maze已被賦值。操作結(jié)果：從入口（x1,y1）開始，判定當(dāng)前位置是否可通，可通就入棧并判斷下一個(gè)方向是否可通 ，按具體情況做入棧和出

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

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

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

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

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

12、;/定義一個(gè)棧 （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() /輸出坐標(biāo)通路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ù)組以重復(fù)使用迷宮 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：預(yù)定義M和N的值，表示二維數(shù)組的大??； a、b：用于接收外部輸入的值，按操作者意愿

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

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

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

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

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

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

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

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

22、網(wǎng)站，/：2010-5-5附錄：結(jié)構(gòu)化設(shè)計(jì)源程序清單/程序名稱：迷宮設(shè)計(jì)問題.cpp/程序功能：應(yīng)用數(shù)據(jù)結(jié)構(gòu)，采用C語言設(shè)計(jì)程序，實(shí)現(xiàn)迷宮的設(shè)計(jì)與判定通路/程序作者： /最后修改日期：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 /堆棧結(jié)構(gòu)int row; /行int col; /列struct node

23、*next;Mlink;Mlink *stack;/定義一個(gè)棧int backupM+2N+2; /備份數(shù)組/*建立迷宮矩陣*/void create(int mazeN+2,int a,int b)/建立迷宮int i,j,flag;srand(unsigned)time(NULL); /以時(shí)間產(chǎn)生隨機(jī)種子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+) /矩陣初始為“”，隨機(jī)選擇位置賦予一個(gè)隨機(jī)的或， i1=(int)(rand()%a)

25、+1;j1=(int)(rand()%b)+1;mazei1j1=(int)(rand()%2); /隨機(jī)矩陣這樣可以產(chǎn)生更多的“”即通路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+) /在矩陣上方標(biāo)明

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); /矩陣左方標(biāo)明行號else printf("%d ",i);for(j=1;j<=b;j+)printf("%d ",mazeij);printf("n迷宮圖形如下(白色可通)：n");printf(" ")

27、;for(z=1;z<=b;z+) /在圖形上方標(biāo)明列號if(z<10) printf("%d ",z); else printf("%d",z);for(i=1;i<=a;i+)printf("n");if(i<10) printf("%d ",i); /矩陣左方標(biāo)明行號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;/標(biāo)志入口已訪問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; /標(biāo)記已訪問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;/標(biāo)記已訪問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;/標(biāo)記已訪問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;/標(biāo)記已訪問else /不可通返回上一點(diǎn)if (stack->next!=NULL) /堆棧里布置一個(gè)頂點(diǎn)則出棧并返回循

32、環(huán) p=stack; stack=stack->next; /出棧 free(p); /釋放空間else /堆棧里只有一個(gè)頂點(diǎn)即入口，此時(shí)若釋放空間出棧會使循環(huán) /控制語句無法比較（因?yàn)閟tack->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);/*輸出坐標(biāo)通路*/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時(shí)輸出，時(shí)輸出，時(shí)輸出，時(shí)輸出void printonglu2(int a,int b

34、)printf("圖形通路如下：n");int z;printf(" ");for(z=1;z<=b;z+) /圖形上方標(biāo)明列號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é)點(diǎn)在下else if(p->row<p->next->row) backupp->next->rowp->next->col=2;/下一節(jié)點(diǎn)在上else if(p->col>p->next->col) backupp->next->rowp->next->col=4;/下一節(jié)點(diǎn)在右else backupp->next->rowp->next->col=3;/下一節(jié)點(diǎn)在左else ;p=p->next;for(i