[理學(xué)]表達(dá)式求解迷宮求解

《[理學(xué)]表達(dá)式求解迷宮求解》由會(huì)員分享，可在線閱讀，更多相關(guān)《[理學(xué)]表達(dá)式求解迷宮求解（30頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、 課 程 設(shè) 計(jì) 報(bào) 告 課程名稱 數(shù)據(jù)結(jié)構(gòu) 課題名稱 表達(dá)式求解 迷宮求解 專 業(yè) 信息與計(jì)算科學(xué) 班 級 學(xué) 號 姓 名 指導(dǎo)教師 年 月 日 湖南工程學(xué)院 課 程 設(shè) 計(jì) 任 務(wù) 書 課程名稱 數(shù)據(jù)結(jié)構(gòu) 課 題

2、 表達(dá)式求值 迷宮求解 專業(yè)班級 學(xué)生姓名 學(xué) 號 指導(dǎo)老師 審 批 任務(wù)書下達(dá)日期 2009 年 5 月 15 日 任務(wù)完成日期 年 月 日 一、設(shè)計(jì)內(nèi)容與設(shè)計(jì)要求 課題1表達(dá)式求值 問題描述：設(shè)計(jì)一編譯器，對讀入的表達(dá)式能根據(jù)人們的約定予以正確解釋，并計(jì)算結(jié)果。 設(shè)計(jì)要求：（1

3、）表達(dá)式中應(yīng)包含數(shù)值常量、四則運(yùn)算符、括號等。 （2）對不合理的解釋應(yīng)有反應(yīng)。 設(shè)計(jì)提示：（1）可用兩個(gè)棧（操作數(shù)棧及運(yùn)算符棧）來存儲原始數(shù)據(jù)及中間結(jié)果。 （2）對表達(dá)式進(jìn)行語法檢查。 （3）用一一維數(shù)組約定運(yùn)算符的位置，用一二維數(shù)組存放運(yùn)算符間的優(yōu)先關(guān)系。 測試數(shù)據(jù)：3+a*9 2+(1*(7-8)*5 7*(5+6-4*2/(2*7))+9/4-5 課題4 迷宮問題 問題描述：用計(jì)算機(jī)模擬解決“迷宮問題”，求出其中一條通道。用數(shù)組MAZE[1...M,1..N]表示迷宮，有的可以通行（0表示），有的是路障（1

4、表示），MAZE[1][1]為迷宮入口,MAZE[M][N]為迷宮出口,用非遞歸算法求出一條通路。 設(shè)計(jì)要求：用“■”標(biāo)示所輸出的路徑(見運(yùn)行示例)否則說明沒有通路,繼續(xù)生成迷宮,直到有通路。 算法提示：實(shí)現(xiàn)這一算法的具體方法很多（如堆棧,隊(duì)列等）,但基本思想一般是回溯法使用MAZE[M][N]表示迷宮（如圖２），為判定過程中是否越界，在其外圍加一圈１作為路障，mark[M][N]作為標(biāo)志數(shù)組，move[8][2]是行列增量數(shù)組（見圖１－２）；建堆棧．約定（i,j）表示I行j列,direction 表示方向, 從入囗開始探索路徑：沿０－１八個(gè)方向依次試探，若某方向可通（為０），則該點(diǎn)連同

5、方向入堆棧，從該點(diǎn)繼續(xù)試探；若八個(gè)方向都不通，則取出堆棧頂點(diǎn)，從其標(biāo)記的方向開始試探其余方向；直至找到出口（有通路）或堆棧為空(沒有通路). 下面是利用一隨機(jī)函數(shù)生成的0/1方陣及運(yùn)行示例: 二、進(jìn)度安排 日 期 上午 下午 15周星期一 課題講解 明確任務(wù)查資料 15周星期二 上機(jī)調(diào)試 上機(jī)調(diào)試 15周星期三 上機(jī)調(diào)試 上機(jī)調(diào)試 16周星期二 上機(jī)調(diào)試 上機(jī)調(diào)試 16周星期五 上機(jī)調(diào)試及答辯 答辯 目錄 1 表達(dá)式求值 1.1問

6、題分析…………………………………………………………… 1.2算法描述…………………………………………………………… 1.3運(yùn)行結(jié)果…………………………………………………………… 1.4設(shè)計(jì)體會(huì)…………………………………………………………… 2 迷宮求解 2.1問題分析…………………………………………………………… 2.2算法描述…………………………………………………………… 2.3運(yùn)行結(jié)果…………………………………………………………… 2.4設(shè)計(jì)體會(huì)……………………………………………………………

7、 1表達(dá)式求值 1.1問題分析 設(shè)計(jì)一個(gè)編譯器，能對一個(gè)含有數(shù)值常量，四則運(yùn)算符，括號的表達(dá)式根據(jù)人們給予約定計(jì)算正確的結(jié)果，并且對于不合理的表達(dá)式有所反應(yīng)。關(guān)于表達(dá)式求值，輸入的數(shù)據(jù)用棧這一數(shù)據(jù)結(jié)構(gòu)儲存，建立一個(gè)數(shù)據(jù)棧（OPND），用來存儲表達(dá)式中的數(shù)據(jù)；一個(gè)運(yùn)算符棧（OPTR），用來存儲表達(dá)式中的四則運(yùn)算符；用一個(gè)二維數(shù)組約定運(yùn)算符之間的優(yōu)先級別。通過對兩個(gè)棧進(jìn)行元素的進(jìn)棧與出棧以及中間結(jié)果的計(jì)算，得到輸入表達(dá)式的值。 1.2算法描述 表達(dá)式求值是棧應(yīng)用的一個(gè)典型列子

8、，我采用的是一種簡單直觀、廣為使用的算法，通常稱為“算符優(yōu)先法”。任何一個(gè)表達(dá)式都是由操作數(shù)、運(yùn)算符和界限符組成的，其中操作數(shù)是是用戶從鍵盤終端輸入的整型變量，運(yùn)算符為‘+’、‘-’，‘*’，‘/’，界限符有左右括號和表達(dá)式結(jié)束符。在本程序中，我把運(yùn)算符和界限符統(tǒng)稱為算符，他們構(gòu)成的集合命名為OP。根據(jù)三條運(yùn)算法則： （1）先乘除，后加減； （2）從左算到右； （3）先括號內(nèi)，后括號外； 在運(yùn)算的每一步，任意兩個(gè)相繼出現(xiàn)的算符@1和@2之間的優(yōu)先關(guān)系至多是下面三種關(guān)系之一： @1<@2 @1的優(yōu)先權(quán)低于@2 @1>@2 @2的優(yōu)先權(quán)高于@2 @1=@2 @1的優(yōu)

9、先權(quán)等于@2 表A定義了算符之間的這種優(yōu)先關(guān)系： （表A） @1 @2 + - * / （ ） # + > > < < < > > - > > < < > * > > > > < < < / > > > > < < < （ < < < <

10、 < = ） > > > > ? > > # < < < <

11、以下的這個(gè)算法描述了這個(gè)過程： OperandType EvaluateExpression(){ //算術(shù)表達(dá)式求值的算符優(yōu)先算法。設(shè)OPTR和OPND分別為運(yùn)算符棧和運(yùn)算數(shù)棧 // OP為運(yùn)算符集合 InitStack(OPTR); Push(OPTR,‘#’)； InitStack(OPND);c=getchar(): do{ if(!In(c,OP) { Push(OPND,c);c=getchar;}//不是運(yùn)算符則進(jìn)棧 else switch(Precede（GetTop(OPTR),c） { case’

12、<’://棧頂元素優(yōu)先權(quán)低 Push(OPTR,c);c=getchar(); Break; Case’=’://脫括號并接收下一字符 Pop(OPTR,x); c=getchar(); Break; Case’>’://退棧并將運(yùn)算結(jié)果入棧 Pop(OPTR,theta); Pop(OPND,b);

13、Pop(OPND,a); Push(OPND,Operate(a,theta,b)); Break; }//switch }while(!OPTR); Return GetTop(OPND); }//EvaluateExpression ? 算法中調(diào)用了兩個(gè)函數(shù)，其中Precede是判定運(yùn)算符棧棧頂?shù)脑谸1與讀入的@2之間優(yōu)先關(guān)系的函數(shù)；Operate為進(jìn)行二元運(yùn)算a @ b的函數(shù)，如果是編譯表達(dá)式，則產(chǎn)生這個(gè)運(yùn)算的一組相應(yīng)指令并返回存放結(jié)果的中間變量名；如果是解釋執(zhí)行表達(dá)式，則直接進(jìn)行運(yùn)算

14、，并返回運(yùn)算的結(jié)果。 流程圖 Main函數(shù)流程圖： 開始 N Y Y N Y 輸入一個(gè)表達(dá)式，存在數(shù)組c[N]中 建立數(shù)據(jù)棧（OPND） 運(yùn)算符棧（OPTR） 將字符‘?！瘔喝? 棧OPTR中 c[i]為?；蛘逴PTR的棧頂元素為

15、＃ i＝0 c[i]為運(yùn)算符 ] C[i]入棧 i++ OPTR的棧頂元素與c[i]優(yōu)先級比較 <：c[i]入棧 i++,break =：脫括號 i++;break >：計(jì)算中間結(jié)果 break 輸出結(jié)果 判斷OPTR是否為空 N i++ 結(jié)束 子函數(shù) Operate(char a,char b,char c) int a1=a-‘0’ int c1=c-‘0’ 將字符型的數(shù)字轉(zhuǎn)化為整型 Switch(b) case ‘+’:result=a1+c1 case ‘-’: result=a1-c1 case ‘*’: result=

16、a1*c1 case ‘/’: result=a1/c1 將計(jì)算結(jié)果轉(zhuǎn)化為字符型，作為返回值 開始 結(jié)束 取兩個(gè)運(yùn)算數(shù)a,c; 取一個(gè)四則運(yùn)算符b 子函數(shù) Precede(char a,char b) 開始 結(jié)束 用變量i，j 分別找到字符a，b的下標(biāo) 用一維數(shù)aa[7]組約定字符的位置 用二維數(shù)組bb[7][7]約定兩字符的優(yōu)先級別 把bb[i][j]作為字符型的返回值 得到需要優(yōu)先級比較的字符a,b 1.3運(yùn)行結(jié)果 在tc中輸入代碼中，不斷的編譯調(diào)試，不斷的發(fā)現(xiàn)問題，然后再找解決的辦法。我在調(diào)試

17、中主要遇到的問題如下： 1) 在剛看到課題的時(shí)候，不知道應(yīng)該如何用一個(gè)二維數(shù)組約定運(yùn)算符間的優(yōu)先級別，于是，翻閱了教科書，也試圖從圖書館中找到相應(yīng)的資料，但是，失敗了，后來，在看書的時(shí)候，教科書中的表格，讓我突然的明白過來，于是，在上機(jī)的時(shí)候，用一維數(shù)組約定非運(yùn)算數(shù)的位置，利用相應(yīng)的下標(biāo)在二維數(shù)組中得到優(yōu)先級別，并把它作為子函數(shù)Precede（char a,char b）的返回值。調(diào)試的時(shí)候，當(dāng)我輸入‘+’，‘*’時(shí)，得到了預(yù)期中的結(jié)果‘<’。 2) 在一個(gè)一個(gè)子函數(shù)的代碼編寫中，當(dāng)我遇到要計(jì)算中間結(jié)果的時(shí)候，不知道怎樣把從字符型棧中出棧的字符型的運(yùn)算數(shù)，轉(zhuǎn)換為相應(yīng)的整型，進(jìn)而進(jìn)行四則運(yùn)算

18、。向老師請教，老師說是字符型的字符減去一個(gè)‘0’，就可以轉(zhuǎn)換成數(shù)字了，比如說 char a=’3’,做相應(yīng)的處理：a1=a-‘0’；就得到了數(shù)字3。還有，怎樣把字符型的運(yùn)算能，能進(jìn)行運(yùn)算呢，通過和同學(xué)的討論，可以選用switch 語句，根據(jù)運(yùn)算的類型，做相應(yīng)的代數(shù)運(yùn)算，并把得到的結(jié)果返回。比如說，我要計(jì)算的是 ‘3’‘+’‘2’；先a1=‘3’-‘0’=3;c1=‘2’-‘0’=2；b==‘+’；result=3+2=5。又解決了一個(gè)問題。后來在與同學(xué)互相交流的時(shí)候，他們還告訴我一個(gè)方法，強(qiáng)制轉(zhuǎn)換成int 型再加上48就可以得到相應(yīng)的整型值了。 3) 經(jīng)過一段時(shí)間的努力后，程序代碼總算是完

19、成了，編譯后沒有錯(cuò)誤，沒有警告，但是就是得不到正確的計(jì)算結(jié)果，可以運(yùn)行，但是進(jìn)入了死循環(huán)，經(jīng)過一步步的調(diào)試，發(fā)現(xiàn)了問題是出在元素進(jìn)棧的時(shí)候，運(yùn)行結(jié)果總是打印“”The stack is full”,后來，知道了在main函數(shù)中的一個(gè)循環(huán)中應(yīng)該把break該成continue，該了之后，再運(yùn)行，可以得到一個(gè)結(jié)果了，但是不是正確的結(jié)果，而且無論我輸入的表達(dá)式是怎樣的，都得到結(jié)果49。后來，還是找了同學(xué)幫忙，他發(fā)現(xiàn)了我邏輯上的一個(gè)錯(cuò)誤，在我的while循環(huán)中，我的第一個(gè)運(yùn)算符不會(huì)入棧，所以中間結(jié)果沒有計(jì)算，直接就結(jié)束了，而把while語句改成do…while的時(shí)候，就可以把第一個(gè)運(yùn)算符入棧了。 4

20、) 問題是一個(gè)接一個(gè)的解決了，但是，我的編譯器還是沒成功，后來，意識到了一個(gè)問題，那就是，我原先是用一個(gè)一維數(shù)組接收的求值表達(dá)式，如果我輸入的是一個(gè)2位數(shù)的數(shù)字，它就會(huì)成為2個(gè)字符儲存，出棧的時(shí)候，就會(huì)發(fā)生錯(cuò)誤，導(dǎo)致得不到正確的結(jié)果。可，我輸入的是一位數(shù)的表達(dá)式時(shí)，很遺憾，還是出錯(cuò)了。已經(jīng)自己發(fā)現(xiàn)不了錯(cuò)誤，于是，去找老師請教，老師很耐心的給我的程序一步步的測試，一會(huì)之后，就發(fā)現(xiàn)了問題的所在，我的Operate的函數(shù)的返回值是int型的，然而，入棧的時(shí)候我直接用了Push（OPND，Operate（m，theta，n）），把一個(gè)int型的數(shù)據(jù)放進(jìn)了一個(gè)字符型的棧，從而導(dǎo)致了其他的邏輯錯(cuò)誤，應(yīng)改成

21、Push（OPND，Operate（m，theta，n）+‘0’）；同時(shí)，在最后得到的表達(dá)式的計(jì)算結(jié)果時(shí)，也應(yīng)將字符型的改回int型，即:printf(“\nthe result is:%d”,GetTop(OPND)-‘0’)。做了這樣了修改之后，程序終于能成功運(yùn)行出正確的結(jié)果了。測試了一下8-2*（7-6）, 運(yùn)行結(jié)果是 the result is:6 。 1.4設(shè)計(jì)體會(huì) 通過一星期的努力，終于把課題“表達(dá)式求值”完成了，

22、雖然做出來的編譯器之能進(jìn)行一位數(shù)的四則運(yùn)算，但是，我自己已經(jīng)很高興了。 這一星期的學(xué)習(xí)，我頗有感觸體會(huì)： (一) 因?yàn)橹R的需要，報(bào)課本細(xì)致的看了一些，重新溫習(xí)了書本，對于之前的學(xué)習(xí)起了很大的補(bǔ)充作用，也對原有的知識進(jìn)行了鞏固。 (二) 一個(gè)大的收獲應(yīng)該是學(xué)以致用吧。把所學(xué)的知識用到了實(shí)處，不再是停留在理論的程度上，把所學(xué)進(jìn)行組合，然后實(shí)實(shí)在在的做出了一點(diǎn)東西，有了信心，也有了小小的成就感，同時(shí)也產(chǎn)生了學(xué)習(xí)的興趣與樂趣。 (三) 在和同學(xué)老師的交流中學(xué)會(huì)了很多，認(rèn)識到了自己的差距與不足，從優(yōu)秀的同學(xué)那里學(xué)到了很多的知識，也看了他們學(xué)習(xí)的認(rèn)真和效果，從老師那里再一次深刻的體會(huì)到了學(xué)海無涯

23、，我們還有很多的東西尚需虛心學(xué)習(xí)。我要繼續(xù)努力，好好學(xué)習(xí)，天天向上。 (四) 一段時(shí)間的學(xué)習(xí)，發(fā)現(xiàn)了學(xué)好一樣?xùn)|西并不難，只要有恒心，有堅(jiān)持，有學(xué)習(xí)的情緒，或許，這并不是我最新的體會(huì)，可是，這次的學(xué)習(xí)，有體會(huì)到了它的真實(shí)性，好好的學(xué)，即便是理論上的東西，現(xiàn)在可能我們用不上，但，對于以后，誰能夠下定論呢，時(shí)間擺在我的眼前，與其虛度光影不如好好的學(xué)，不至于以后落得個(gè)數(shù)到用時(shí)方恨少。 (五) 做表達(dá)式求值這個(gè)課題，應(yīng)該就算是做一個(gè)簡單的計(jì)算器吧，以前用計(jì)算器的時(shí)候，總覺得很神奇，輕輕一按，就可以得到計(jì)算結(jié)果，現(xiàn)在明白了一些原理，也對當(dāng)前的科技對了幾分的敬佩。同時(shí)，也知道了有些東西，其實(shí)我們自己也可

24、以做到，只是我們目前的知識有限。應(yīng)該說，這次的程序設(shè)計(jì)，激發(fā)了我對學(xué)習(xí)的部分熱情吧，對我所不知的世界、領(lǐng)域產(chǎn)生了想去探究的想法。 (六) 通過這段時(shí)間的共同學(xué)習(xí)，和同學(xué)們之間的友情加深了。一起談?wù)搶W(xué)習(xí)，共同探討問題的答案，互相幫助，歡聲笑語也夾雜其中，很高興，能有愉快的學(xué)習(xí)氛圍。 完成了課程設(shè)計(jì)表達(dá)式求值，我覺得我的收獲真的很大，總結(jié)之后，更是發(fā)現(xiàn)了自己學(xué)會(huì)了很多，得到了很多，無論是學(xué)習(xí)還是思想上的一些東西。 2迷宮求解 2.1問題分析 三、報(bào)告要求 1 課程設(shè)

25、計(jì)說明書裝訂順序：封面、任務(wù)書、目錄、正文、評分、附件（A4大小的圖紙及程序清單）。 2 每課題應(yīng)包含：問題分析、算法描述、運(yùn)行結(jié)果、設(shè)計(jì)體會(huì)等。 正文 宋體5號 一 附錄 1 表達(dá)式求值 # include # include # define N 100 # define TRUE 1 # define FALSE 0 typedef struct { char stack[N]; int top; } SeqStack; SeqStack

26、 *InitStack() { SeqStack *s; s=malloc(sizeof(SeqStack)); if(!s) {printf("do not have enoughf space");return NULL; } else s->top=-1; return s; } char GetTop(SeqStack *s) { if(s->top==-1) {printf("\nthis is a empty stack!");return FALSE;} else return (s->stack[s->top]); } SeqSta

27、ck *Push(SeqStack *s,char x) { if(s->top==N-1) {printf("\n the stack is full!"); return NULL;} else { s->top++; s->stack[s->top]=x; return s; } } char Pop(SeqStack *s) { if(s->top==-1) { printf("\nThe sequence stack is empty!"); return FALSE; } (s->top)--; return (s->stack[s-

28、>top+1]); } int StackEmpty(SeqStack *s) { if(s->top==-1) return TRUE; else return FALSE; } int match(char *c) { int i=0; SeqStack *s; s=InitStack(); while(c[i]!='#') { switch(c[i]){ case '(':Push(s,c[i]);break; case ')':if(!StackEmpty(s)&&GetTop(s)=='(') { Pop(s);break;

29、} /* end if */ else return FALSE; } /* end switch */ i++; } /* end while */ return (StackEmpty(s)); } char Precede(char a,char b) { int i,j; char aa[7]={'+','-','*','/','(',')','#'}; char bb[7][7]={{'>','>','<','<','<','>','>'},{'>','>','<','<','<','>'

30、,'>'}, {'>','>','>','>','<','>','>'},{'>','>','>','>','<','>','>'}, {'<','<','<','<','<','=','@'},{'>','>','>','>','@','>','>'}, {'<','<','<','<','<','@','='}}; for(i=0;i<7;i++){ if(a==aa[i]) break; } for(j=0;j<7;j++) { if(b==aa[j]) break; } return bb[i][j]; }

31、int YSF(char y) { if(y=='+'||y=='-'||y=='*'||y=='/'||y=='('||y==')') return TRUE; else return FALSE; } int Operate(char a,char b,char c) { int a1,c1,result; a1=a-'0'; c1=c-'0'; switch(b){ case '+':result=a1+c1;break; case '-':result=a1-c1;break; case '*':result=a1*c1;break; case '/'

32、:result=a1/c1;break; } return result; } void main() { char c[N]; int i,j; char m,n,theta; SeqStack *OPTR; /* yunsanfu */ SeqStack *OPND; /* yunsanshu */ OPTR=InitStack(); Push(OPTR,'#'); OPND=InitStack(); i=0; do { c[i]=getchar(); i++; }while(c[i-1]!='#'); print

33、f("\nthe equation you input is below:\n"); for(j=0;j

34、 switch(Precede(GetTop(OPTR),c[i])) { case '<':Push(OPTR,c[i]);i++;break; case '=':Pop(OPTR);i++;break; case '>':{ theta=Pop(OPTR); n=Pop(OPND); m=Pop(OPND); Push(OPND,Operate(m,theta,n)+'0'); } break; } /* end swtich */ } while(c[i]!='#'||GetTop(OPTR)!='#');

35、 /*end while */ printf("the result of the equation is: %d", GetTop(OPND)-'0'); getchar(); } /* end main() */ 2迷宮求解： #include #include /************************************************************** 數(shù)據(jù)定義 *************************

36、*************************************/ typedef enum { ERROR, OK } Status; typedef struct { int row; //row表示“行”號 int line; //line表示“列”號 }PosType; //位置的元素類型 typedef struct { int ord; //該通道在路徑上的“序號” PosType seat; /

37、/通道塊在迷宮中的“坐標(biāo)位置” int di; //從此通道走向下以通道塊的“方向” }SElemType; //棧的元素類型 typedef struct { SElemType * base; SElemType * top; int stacksize; }SqStack; /************************************************************** 函數(shù)原型說明 ********************

38、******************************************/ Status InitStack(SqStack &S); //創(chuàng)建一個(gè)空棧S Status Push(SqStack &S,SElemType &a); //插入新元素a Status Pop(SqStack &S,SElemType &a); //刪除棧頂元素，a返回其值 Status StackEmpty(SqStack S); //檢查是否

39、空棧 Status MazePath(int maze[12][12],SqStack &S, PosType start, PosType end); //找通路 void Initmaze(int maze[12][12],int size); //初始化迷宮 void printmaze(int maze[12][12],int size); //顯示迷宮 Status Pass(int maze[12][12],PosType CurPos); //判斷當(dāng)前位置是否可通 void Markfoot(int maz

40、e[12][12], PosType CurPos); //標(biāo)記當(dāng)前位置不可通 PosType NextPos(PosType CurPos, int Dir); //進(jìn)入下一位置 void printpath(int maze[12][12],SqStack S,int size); //顯示通路 /************************************************************** 主函數(shù) **********************************

41、****************************/ void main (void) { SqStack S; int size,maze[12][12]; for(int n=0;n<10;n++) { printf("創(chuàng)建一個(gè)正方形迷宮，請輸入迷宮尺寸(注意不要大于10):\n"); //設(shè)置迷宮大小 scanf("%d",&size);if(size<1 || size>10){printf("輸入錯(cuò)誤!");return;} Initmaze(maze,size); //初始化迷宮

42、printmaze(maze,size); //顯示所創(chuàng)建的迷宮 PosType start,end; //設(shè)置入口和出口 printf("輸入入口行坐標(biāo)和列坐標(biāo):");scanf("%d",&start.row);scanf("%d",&start.line); printf("輸入出口行坐標(biāo)和列坐標(biāo):");scanf("%d",&end.row);scanf("%d",&end.line); if(MazePath(maze,S,start,end)) //若有通路，顯示通路

43、 printpath(maze,S,size); else printf("找不到通路!\n\n"); } } /************************************************************** 若迷宮maze中從入口 start到出口 end的通道，則求得一條存放在棧中 **************************************************************/ Status MazePath(int maze[12][12],SqStack &S, P

44、osType start, PosType end) { PosType curpos; int curstep; SElemType e; InitStack(S); curpos = start; // 設(shè)定"當(dāng)前位置"為"入口位置 curstep = 1; // 探索第一步 do { if (Pass(maze,curpos)) // 當(dāng)前位置可通過，即是未曾走到過的通道塊 { Markfoot(

45、maze,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á)終點(diǎn)（出口） curpo

46、s = NextPos(curpos, 1); // 下一位置是當(dāng)前位置的東鄰 curstep++; // 探索下一步 } else // 當(dāng)前位置不能通過 { if (!StackEmpty(S)) { Pop(S,e); while (e.di==8 && !StackEmpty(S)) {

47、 Markfoot(maze,e.seat); // 留下不能通過的標(biāo)記，并退回一步 Pop(S,e); } if (e.di<8) { e.di++; // 換下一個(gè)方向探索 Push(S, e); curpos = NextPos(e.seat, e.di); // 當(dāng)前位置設(shè)為新方向的相鄰塊

48、 } } } } while (!StackEmpty(S)); return ERROR; } /************************************************************** 初始化迷宮 **************************************************************/ void Initmaze(int maze[12][12],int size) { for(int i

49、=0;i

50、* 顯示迷宮 **************************************************************/ void printmaze(int maze[12][12],int size) { printf("\n\n"); printf("顯示所建的迷宮(#表示外面的墻):\n"); for(int i=0;i

51、,'#'); for(int j=1;j

52、*****************************************************/ void printpath(int maze[12][12],SqStack S,int size) { printf("\n\n通路路徑為:\n"); SElemType * p=S.base; while(p!=S.top) { maze[p->seat.row][p->seat.line]=2; //標(biāo)記為路徑中的點(diǎn) p++; } for(int i=0;i

53、printf("\n"); for(i=1;i

54、 /************************************************************** 判斷當(dāng)前位置是否可通 **************************************************************/ Status Pass(int maze[12][12],PosType CurPos) { if (maze[CurPos.row][CurPos.line]==0) return OK; //

55、如果當(dāng)前位置是可以通過，返回1 else return ERROR; // 其它情況返回0 } /************************************************************** 標(biāo)記當(dāng)前位置不可通 **************************************************************/ void Markfoot(int maze[12][12],PosType CurPos) { maze[Cur

56、Pos.row][CurPos.line]=1; } /************************************************************** 進(jìn)入下一位置 **************************************************************/ PosType NextPos(PosType CurPos, int Dir) //進(jìn)入下一位置 { PosType ReturnPos; switch (Dir) { case 1:

57、 ReturnPos.row=CurPos.row+1; ReturnPos.line=CurPos.line; break; case 2: ReturnPos.row=CurPos.row+1; ReturnPos.line=CurPos.line+1; break; case 3: ReturnPos.row=CurPos.row; ReturnPos.line=CurPos.line+1; break;

58、 case 4: ReturnPos.row=CurPos.row-1; ReturnPos.line=CurPos.line+1; break; case 5: ReturnPos.row=CurPos.row-1; ReturnPos.line=CurPos.line; break; case 6: ReturnPos.row=CurPos.row-1; ReturnPos.line=CurPos.line-1;

59、 break; case 7: ReturnPos.row=CurPos.row; ReturnPos.line=CurPos.line-1; break; case 8: ReturnPos.row=CurPos.row+1; ReturnPos.line=CurPos.line-1; break; } return ReturnPos; } /**********************************************************

60、**** 創(chuàng)建一個(gè)空棧S **************************************************************/ Status InitStack(SqStack &S) { S.base=(SElemType *)malloc(100*sizeof(SElemType)); if(!S.base)return ERROR; S.top=S.base; S.stacksize=100; return OK; } /***********************************

61、*************************** 插入新元素a **************************************************************/ Status Push(SqStack &S,SElemType &a) { *S.top++=a; return OK; } /************************************************************** 刪除棧頂元素，a返回其值

62、 **************************************************************/ Status Pop(SqStack &S,SElemType &a) { if(S.top==S.base)return ERROR; a=*--S.top; return OK; } /************************************************************** 檢查是否空棧 **************************************************************/ Status StackEmpty(SqStack S) { if(S.top==S.base)return OK; return ERROR; }