迷宮問題——數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)迷宮問題

1、<p>　　*******************</p><p><b>　　實(shí)踐教學(xué)</b></p><p>　　*******************</p><p><b>　　計(jì)算機(jī)與通信學(xué)院</b></p><p><b>　　2012年春季學(xué)期</b>&

2、lt;/p><p>　　算法與數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計(jì)</p><p>　　題 目： 迷宮問題 </p><p>　　專業(yè)班級(jí)：計(jì)算機(jī)科學(xué)與技術(shù)一班 </p><p>　　姓 名： </p><p>　　學(xué) 號(hào)： <

3、/p><p>　　指導(dǎo)教師： </p><p>　　成 績(jī)： </p><p><b>　　目 錄</b></p><p><b>　　摘 要3</b></p><p><b>　

4、　前 言4</b></p><p><b>　　正 文5</b></p><p>　　一、采用c++語言定義相關(guān)的數(shù)據(jù)類型5</p><p>　　二、各模塊的偽碼算法6</p><p>　　三、函數(shù)的調(diào)用關(guān)系圖10</p><p><b>　　四、調(diào)試分析11

5、</b></p><p><b>　　五、測(cè)試結(jié)果11</b></p><p><b>　　1、開始界面12</b></p><p>　　2、自動(dòng)生成迷宮運(yùn)行情況12</p><p>　　3、鍵盤輸入迷宮運(yùn)行情況14</p><p><b>　　

6、總 結(jié)16</b></p><p><b>　　致 謝17</b></p><p><b>　　參考文獻(xiàn)18</b></p><p><b>　　附 錄19</b></p><p>　　源程序（帶注釋）19</p><p>&

7、lt;b>　　摘 要</b></p><p>　　本程序主要是對(duì)任意給定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。使我們基本掌握線性表及棧上基本運(yùn)算的實(shí)現(xiàn)，進(jìn)一步理解和熟練掌握課本中所學(xué)的各種數(shù)據(jù)結(jié)構(gòu)，學(xué)會(huì)如何把學(xué)到的知識(shí)用于解決實(shí)際問題，培養(yǎng)我們的動(dòng)手能力。</p><p>　　1、生成迷宮：根據(jù)提示輸入數(shù)據(jù)，然后生成一個(gè)8行8列的迷宮。</p&

8、gt;<p>　　2、探索迷宮路徑：由輸入的入口位置開始，對(duì)相鄰的（上，下，左，右）四個(gè)方向的方塊進(jìn)行探索，若可通則“納入路徑”，否則順著“來向”退到“前一通道塊”，朝著“來向”之外的其它方向繼續(xù)探索。</p><p>　　3、保存迷宮路徑：若探索到出口則把探索到的路徑壓入另一個(gè)棧中，并最后彈出路徑坐標(biāo)，輸出在屏幕上。</p><p>　　關(guān)鍵字：棧，棧的存儲(chǔ)結(jié)構(gòu)，出棧與入棧

9、</p><p><b>　　前 言</b></p><p>　　求迷宮中從入口到出口的所有路徑是一個(gè)經(jīng)典的程序設(shè)計(jì)問題。由于計(jì)算機(jī)解迷宮時(shí)，通常用的是“窮舉求解”的方法，即從入口出發(fā)，順某一方向向前探索，若能走通，則繼續(xù)往前走；否則沿原路退回，換一個(gè)方向再繼續(xù)探索，直至所有可能的通路都探索到為止。為了保證在任何位置上都能沿原路退回，顯然需要用一個(gè)后進(jìn)先出的結(jié)構(gòu)來保

10、存從入口到當(dāng)前位置的路徑。因此，在求迷宮通路的算法中應(yīng)用“?！币簿褪亲匀欢坏氖?。迷宮問題要求，所求路徑必須是簡(jiǎn)單路徑，即在求得路徑上不能同時(shí)重復(fù)出現(xiàn)同一通道。在迷宮中用1和0分別表示迷宮中的通路和障礙。</p><p>　　首先，輸入迷宮數(shù)據(jù)，在計(jì)算機(jī)的屏幕上顯示一個(gè)8行8列的矩陣表示迷宮。矩陣中的每個(gè)數(shù)據(jù)或?yàn)橥罚ㄒ?表示），或?yàn)閴Γㄒ?表示），所求路徑必須是簡(jiǎn)單路徑，即在求得的路徑上不能重復(fù)出現(xiàn)同一道塊。&

11、lt;/p><p>　　其次，假設(shè)“當(dāng)前位置”指的是“在搜索過程中某一時(shí)刻所在圖中某個(gè)方塊位置”，則求迷宮中一條路徑的算法的基本思想是：若當(dāng)前位置“可通”，則“納入當(dāng)前路徑”，并繼續(xù)朝“下一個(gè)位置”探索，即切換“下一位置”為“當(dāng)前位置”，如此重復(fù)直到到達(dá)出口；若當(dāng)前位置“不可通”，則應(yīng)順著“來向”退回到“前一通道塊”，然后朝著除“來向”，之外的其它方向繼續(xù)探索，若該通道塊的四周四個(gè)方塊均“不可通”，則應(yīng)該從“當(dāng)前路徑

12、”上刪除該通道塊，所謂“下一個(gè)位置”指的是“當(dāng)前位置”四周四個(gè)方向（上，下，左，右）上相鄰的方塊。假設(shè)以棧S記錄“當(dāng)前路徑”，則棧頂中存放的是“當(dāng)前路徑上最后一個(gè)通道塊”。由此，“納入路徑”的操作為“當(dāng)前位置入?！保粡漠?dāng)前路徑刪除前一通道塊的操作為“出?！薄?lt;/p><p>　　最后，若找到出口，則從棧中彈出數(shù)據(jù)，在屏幕上顯示從入口到出口的路徑坐標(biāo)。最后希望通過對(duì)該課題的設(shè)計(jì)，理解和掌握所學(xué)到的各種數(shù)據(jù)結(jié)構(gòu)，學(xué)會(huì)

13、把學(xué)到的知識(shí)應(yīng)用于解決實(shí)際的問題當(dāng)中，培養(yǎng)自己的動(dòng)手能力。</p><p><b>　　正 文</b></p><p>　　一、采用c++語言定義相關(guān)的數(shù)據(jù)類型</p><p>　　1、定義坐標(biāo)（X，Y）:</p><p>　　#include<iostream></p><p>　

14、　#include<fstream></p><p>　　using namespace std;</p><p>　　struct Coor </p><p><b>　　{</b></p><p>　　int row; </p><p>　　int c

15、olumn; </p><p>　　int direction; </p><p><b>　　}; </b></p><p><b>　　2、定義方向：</b></p><p>　　struct Move </p><p><

16、;b>　　{</b></p><p><b>　　int row;</b></p><p>　　int column;</p><p><b>　　};</b></p><p>　　3、定義/鏈表結(jié)點(diǎn)：</p><p>　　struct LinkNode

17、 </p><p><b>　　{</b></p><p>　　Coor data;</p><p>　　LinkNode *next;</p><p><b>　　};</b></p><p><b>　　4、定義棧：</b></p>

18、<p>　　class stack</p><p><b>　　{</b></p><p><b>　　private:</b></p><p>　　LinkNode *top; </p><p><b>　　public:</b></p&

19、gt;<p>　　stack(); </p><p>　　~stack(); </p><p>　　void Push(Coor data); </p><p>　　Coor Pop(); </p><p>　　Coor G

20、etPop(); </p><p>　　void Clear(); </p><p>　　bool IsEmpty(); </p><p><b>　　};</b></p><p>　　5、定義迷宮定義移動(dòng)的4個(gè)方向：</p>&

21、lt;p>　　Move move[4]={{0,1},{1,0},{0,-1},{-1,0}};</p><p>　　6、幾個(gè)函數(shù)功能的描述:</p><p>　　stack(); //構(gòu)造函數(shù)，置空棧</p><p>　　~stack(); //析構(gòu)函數(shù)</p><p>　　void

22、Push(Coor data); //把元素data壓入棧中</p><p>　　Coor Pop(); //使棧頂元素出棧</p><p>　　Coor GetPop(); //取出棧頂元素</p><p>　　void Clear(); //把棧

23、清空</p><p>　　bool IsEmpty(); //判斷棧是否為空</p><p>　　bool Mazepath(int **maze,int m,int n); </p><p>　　//尋找迷宮maze中從（0，0）到（m,n）的路徑</p><p>　　//到則返回true,否則返回false<

24、/p><p>　　void PrintPath(stack p); //輸出迷宮的路徑</p><p>　　void PrintPath2(int m,int n,stack p,int **maze); //輸出路徑</p><p>　　void Restore(int **maze,int m,int n); //恢復(fù)迷宮&

25、lt;/p><p>　　二、各模塊的偽碼算法</p><p>　　1、根據(jù)輸入產(chǎn)生一個(gè)8*8的迷宮：</p><p><b>　　m=a;</b></p><p>　　n=b; </p><p>　　maze=new int *[m+2]; //申請(qǐng)長(zhǎng)度等于行數(shù)加2的二級(jí)指針<

26、;/p><p>　　for(i= 0;i<m+2;i++) //申請(qǐng)每個(gè)二維指針的空間</p><p><b>　　{</b></p><p>　　maze[i]=new int[n+2];</p><p><b>　　}</b></p><p>　　for(i=1;i&

27、lt;=m;i++) </p><p>　　for(j=1;j<=n;j++)</p><p>　　cin>>maze[i][j];</p><p>　　cout<<"是否保存新迷宮？\n";</p><p>　　cout<<"用Y或y表示保存、N或n表示

28、不保存 \n";</p><p>　　char choose;</p><p>　　cin>>choose;</p><p>　　if(choose=='Y'||choose=='y')</p><p><b>　　{</b></p><p>

29、<b>　　char ch;</b></p><p>　　ofstream fop("Newtest.txt"); </p><p>　　for(i=1;i<=m;i++)</p><p><b>　　{</b></p><p>　　for(j=1;j<=n;j

30、++)</p><p><b>　　{</b></p><p>　　ch='0'+maze[i][j];</p><p><b>　　fop<<ch;</b></p><p><b>　　}</b></p><p>　　fop

31、<<endl;</p><p>　　flush(cout);</p><p><b>　　}</b></p><p>　　fop.close();</p><p><b>　　}</b></p><p><b>　　} </b></p&

32、gt;<p>　　//給迷宮的四周加一堵墻，即把迷宮四周定義為1</p><p>　　for(i=0;i<m+2;i++) </p><p>　　maze[i][0]=maze[i][n+1]=1;</p><p>　　for(i=0;i<n+2;i++)</p><p>　　maze[0]

33、[i]=maze[m+1][i]=1;</p><p>　　for(int p=0;p<m+2;++p)</p><p><b>　　{</b></p><p>　　for(int q=0;q<=n+2;++q)</p><p><b>　　{</b></p><p&

34、gt;　　if(maze[p][q]==0)</p><p>　　cout<<"■";</p><p>　　if(maze[p][q]>=1)</p><p>　　cout<<"□";</p><p><b>　　}</b></p>&l

35、t;p>　　cout<<endl;</p><p><b>　　}</b></p><p>　　return maze; //返回存貯迷宮的二維指針maze</p><p><b>　　2、探索路徑函數(shù)：</b></p><p>　　bool Mazepa

36、th(int **maze,int m,int n)</p><p>　　//尋找迷宮maze中從（0，0）到（m,n）的路徑</p><p>　　//到則返回true,否則返回false</p><p><b>　　{</b></p><p>　　stack q,p; //定義棧p、q,分別存探索迷宮的存儲(chǔ)

37、和路徑過程</p><p>　　Coor Temp1,Temp2; </p><p>　　int row,column,loop;</p><p>　　Temp1.row=1;</p><p>　　Temp1.column=1;</p><p>　　q.Push(Temp1); //將入口

38、位置入棧</p><p>　　p.Push(Temp1);</p><p>　　maze[1][1]=8; //標(biāo)志入口位置已到達(dá)過</p><p>　　while(!q.IsEmpty()) //棧q非空，則反復(fù)探索</p><p><b>　　{</b></p><p&

39、gt;　　Temp2=q.GetPop(); //獲取棧頂元素</p><p>　　if(!(p.GetPop().row==q.GetPop().row&&p.GetPop().column==q.GetPop().column)) </p><p>　　p.Push(Temp2); </p><p>　　//如果有新位置

40、入棧，則把上一個(gè)探索的位置存入棧p</p><p>　　for(loop=0;loop<4;loop++) //探索當(dāng)前位置的4個(gè)相鄰位置</p><p><b>　　{</b></p><p>　　row=Temp2.row+move[loop].row; //計(jì)算出新位置x位置值</p><p>　

41、　column=Temp2.column+move[loop].column; //計(jì)算出新位置y位置值</p><p>　　if(maze[row][column]==0) //判斷新位置是否可達(dá)</p><p><b>　　{</b></p><p>　　Temp1.row=row;</p><

42、p>　　Temp1.column=column;</p><p>　　maze[row][column]=8; //標(biāo)志新位置已到達(dá)過</p><p>　　q.Push(Temp1); //新位置入棧</p><p><b>　　}</b></p><p>　　if((row==(

43、m))&&(column==(n))) //成功到達(dá)出口</p><p><b>　　{</b></p><p>　　Temp1.row=m;</p><p>　　Temp1.column=n;</p><p>　　Temp1.direction=0;</p><p>　　p

44、.Push(Temp1); //把最后一個(gè)位置入棧</p><p>　　char choose;</p><p>　　cout<<"請(qǐng)選擇以坐標(biāo)形式（row，column，direction）輸出迷宮選(1)或以方陣形式輸出迷宮選(2):";</p><p>　　cin>>choose; &l

45、t;/p><p>　　if(choose=='1') </p><p><b>　　{</b></p><p>　　PrintPath(p); //坐標(biāo)顯示輸出 </p><p>　　Restore(maze,m,n); </p><p><b>　

46、　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　PrintPath2(m,n,p,maze); //矩陣顯示輸出 </p><p>　　Restore(maze,m,n); </p>

47、<p><b>　　}</b></p><p>　　return 1; //表示成功找到路徑</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　if(p.GetPop().row==q.GetP

48、op().row&&p.GetPop().column==q.GetPop().column)</p><p>　　//如果沒有新位置入棧，則返回到上一個(gè)位置</p><p><b>　　{</b></p><p><b>　　p.Pop();</b></p><p><b&g

49、t;　　q.Pop();</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　return 0; //表示查找失敗，即迷宮無路經(jīng)</p><p><b>　　}</b></p>

50、<p><b>　　3、輸出迷宮</b></p><p>　　void PrintPath(stack p) //輸出路徑</p><p><b>　　{</b></p><p>　　cout<<"迷宮的路徑為\n";</p><p>　　c

51、out<<"括號(hào)內(nèi)的內(nèi)容分別表示為(行坐標(biāo),列坐標(biāo),數(shù)字化方向,方向)\n";</p><p>　　stack t; //定義一個(gè)棧，按從入口到出口存取路徑</p><p><b>　　int a,b;</b></p><p>　　Coor data;</p><p>

52、;　　LinkNode *temp;</p><p>　　temp=new LinkNode; //申請(qǐng)空間</p><p>　　temp->data=p.Pop(); //取棧p的頂點(diǎn)元素，即第一個(gè)位置</p><p>　　t.Push(temp->data); //第一個(gè)位置入棧t</p><p&g

53、t;　　delete temp; //釋放空間</p><p>　　while(!p.IsEmpty()) //棧p非空，則反復(fù)轉(zhuǎn)移</p><p><b>　　{</b></p><p>　　temp=new LinkNode;</p><p>　　temp->data=p.Pop();

54、 //獲取下一個(gè)位置</p><p><b>　　//得到行走方向</b></p><p>　　a=t.GetPop().row-temp->data.row; //行坐標(biāo)方向</p><p>　　b=t.GetPop().column-temp->data.column; //列坐標(biāo)方向</p>

55、<p>　　if(a==1) temp->data.direction=1; //方向向下，用1表示</p><p>　　else if(b==1) temp->data.direction=2; //方向向右，用2表示</p><p>　　else if(a==-1) temp->data.direction=3; //方向向上，用3表示</p

56、><p>　　else if(b==-1) temp->data.direction=4; //方向向左，用4表示</p><p>　　t.Push(temp->data); //把新位置入棧</p><p>　　delete temp;</p><p><b>　　}</b></p

57、><p>　　cout<<"坐標(biāo)（row,column,direction）中x在指向當(dāng)前位置所在的行數(shù)，y指向當(dāng)前位置所在的列數(shù)，";</p><p>　　cout<<"direction表示下一位置走向。"<<endl;</p><p>　　//輸出路徑，包括行坐標(biāo)，列坐標(biāo)，下一個(gè)位置方向&

58、lt;/p><p>　　while(!t.IsEmpty()) //棧非空，繼續(xù)輸出</p><p><b>　　{</b></p><p>　　data=t.Pop();</p><p>　　cout<<'('<<data.row<<','

59、<<data.column<<','<<data.direction<<","; //輸出行坐標(biāo)，列坐標(biāo)</p><p>　　switch(data.direction) //輸出相應(yīng)的方向 </p><p><b>　　{</b></p><p>　　c

60、ase 1:cout<<"↓)\n";break;</p><p>　　case 2:cout<<"→)\n";break;</p><p>　　case 3:cout<<"↑)\n";break;</p><p>　　case 4:cout<<"←

61、)\n";break;</p><p>　　case 0:cout<<")\n";break;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p>

62、<p>　　void PrintPath2(int m,int n,stack p,int **maze) //輸出路徑</p><p><b>　　{</b></p><p>　　cout<<"迷宮的路徑為\n";</p><p>　　for (int i = 0; i < m+

63、2; ++i )</p><p><b>　　{</b></p><p>　　for (int j = 0; j < n+2; ++j)</p><p>　　cout << maze[i][j]<<" ";</p><p>　　cout << endl;&

64、lt;/p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　三、函數(shù)的調(diào)用關(guān)系圖</p><p><b>　　四、調(diào)試分析</b></p><p>　　1、調(diào)試中遇到的問題及對(duì)問題的解決方法</p>

65、<p>　　在調(diào)試過程中，自己定義不可通取值從ch>='0'&&ch<='9'都可以執(zhí)行，但是在執(zhí)行過程中顯示迷宮時(shí)有“吃墻”現(xiàn)象，如圖：</p><p>　　經(jīng)過反復(fù)調(diào)試程序，最后發(fā)現(xiàn)在定義 出錯(cuò)，后來改為后，吃圖現(xiàn)象在沒有發(fā)生，如圖；</p><p>　　2、算法的時(shí)間復(fù)雜度和空間復(fù)雜度</p><

66、;p>　　空間復(fù)雜度：O（1）；</p><p><b>　　時(shí)間復(fù)雜度</b></p><p>　　隨機(jī)生成迷宮：O（n*n）；</p><p>　　探尋出口：O（n*n）；</p><p>　　輸出迷宮：O（n*n）；</p><p>　　判斷當(dāng)前位置可通：O（1）。</p>

67、<p><b>　　五、測(cè)試結(jié)果</b></p><p><b>　　1、開始界面</b></p><p>　　2、自動(dòng)生成迷宮運(yùn)行情況</p><p>　　選擇生成迷宮輸入1如下圖所示</p><p>　　選擇以坐標(biāo)形式輸出迷宮：輸入1如下圖所示</p><p&g

68、t;　　選擇以方陣形式輸出迷宮：輸入2如下圖所示（其中8代表路徑，1代表墻）</p><p>　　3、鍵盤輸入迷宮運(yùn)行情況</p><p>　　選擇鍵盤輸入輸入2如下圖所示</p><p>　　鍵盤輸入10*10的迷宮，運(yùn)行結(jié)果及通路結(jié)果如下圖所示</p><p><b>　　總 結(jié)</b></p>&l

69、t;p>　　我的課設(shè)題目為迷宮問題，通過該題目的設(shè)計(jì)過程,我加深了對(duì)棧的邏輯結(jié)構(gòu),存儲(chǔ)結(jié)構(gòu)及入棧出棧過程的理解,對(duì)棧的基本運(yùn)算的實(shí)現(xiàn)有所掌握,對(duì)課本中所學(xué)的各種數(shù)據(jù)結(jié)構(gòu)進(jìn)一步理解和掌握,學(xué)會(huì)了如何把學(xué)到的知識(shí)用于解決實(shí)際問題,鍛煉了自己動(dòng)手的能力。</p><p>　　本次課程設(shè)計(jì)，使我對(duì)數(shù)據(jù)結(jié)構(gòu)線性表的設(shè)計(jì)方法、步驟、思路，有一定的了解和認(rèn)識(shí)，它相當(dāng)于實(shí)際設(shè)計(jì)工作的模擬。在課程設(shè)計(jì)過程中，基本能按照規(guī)定的

70、程序進(jìn)行，先針對(duì)表達(dá)式算法為背景，建立系統(tǒng)模型：收集、調(diào)查有關(guān)資料，共同與老師和同學(xué)進(jìn)行幾次討論、修改、再討論、再修改，最后確定方案。</p><p>　　通過此次課程設(shè)計(jì)，我了解了編寫應(yīng)用軟件的一般步驟，獲得了很多寶貴的經(jīng)驗(yàn)，特別是怎么樣通過理論與實(shí)踐相結(jié)合，把書本上的內(nèi)容應(yīng)用到我們做的程序上去。怎樣使各個(gè)子模塊實(shí)施其的詳細(xì)功能，特別是各個(gè)子模塊之間的接口，一定要相當(dāng)清晰，達(dá)到相互協(xié)調(diào)的作用。其次，我熟悉了數(shù)據(jù)

71、結(jié)構(gòu)知識(shí)，學(xué)會(huì)了很多關(guān)于程序設(shè)計(jì)的經(jīng)驗(yàn)和技巧，明白了程序的使用性和通用性是程序生存周期長(zhǎng)短的關(guān)鍵。學(xué)會(huì)了調(diào)試程序的一般方法，知道了如何在困難重重中一步一步發(fā)現(xiàn)問題，解決問題。</p><p>　　一個(gè)人要完成所有的工作是非常困難和耗時(shí)的。在以后的學(xué)習(xí)中我會(huì)更加注意各個(gè)方面的能力的協(xié)調(diào)發(fā)展。在課程設(shè)計(jì)時(shí)遇到了很多的問題，在老師的幫助，和對(duì)各種資料的查閱中，將問題解決，培養(yǎng)了我自主動(dòng)手，獨(dú)立研究的能力，為今后在學(xué)習(xí)工

72、作中能更好的發(fā)展打下了堅(jiān)實(shí)的基礎(chǔ)。</p><p>　　三周的課程設(shè)計(jì)很短暫，但其間的內(nèi)容是很充實(shí)的，在其中我學(xué)習(xí)到了很多平時(shí)書本中無法學(xué)到的東西，積累了經(jīng)驗(yàn)，鍛煉了自己分析問題，解決問題的能力，并學(xué)會(huì)了如何將所學(xué)的各課知識(shí)融會(huì)，組織，來配合學(xué)習(xí)，三周中我收益很大，學(xué)到很多。</p><p><b>　　致 謝</b></p><p>　　在

73、此次課程設(shè)計(jì)的撰寫過程中，我得到了許多人的幫助和支持。</p><p>　　首先，我要感謝張永老師在課程設(shè)計(jì)上給予我的指導(dǎo)、提供給我的支持和幫助，這是我能順利完成這次報(bào)告的主要原因，更重要的是張老師的幫助使我解決了許多技術(shù)上的難題，讓我能把系統(tǒng)做得更加完善。在此期間，我不僅學(xué)到了許多新的知識(shí)，而且也開闊了視野，提高了自己的設(shè)計(jì)能力和實(shí)踐能力。其次，我要感謝本班同學(xué)和幫助過我的同學(xué)，是他們的幫助和支持使我順利的完成

74、了本次課程設(shè)計(jì)，他們也為我解決了不少我不太明白的設(shè)計(jì)上的難題。同時(shí)也感謝學(xué)院為我提供良好的做課程設(shè)計(jì)的環(huán)境。</p><p>　　最后，再一次感謝所有在課程設(shè)計(jì)中曾經(jīng)幫助過我的良師益友和同學(xué)。</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1] 嚴(yán)蔚敏，吳偉民.《數(shù)據(jù)結(jié)構(gòu)（C語言版）》.清華大學(xué)出版社.</p>

75、<p>　　[2] 嚴(yán)蔚敏，吳偉民.《數(shù)據(jù)結(jié)構(gòu)題集（C語言版）》.清華大學(xué)出版社.</p><p>　　[3] 《DATA STRUCTURE WITH C++》. William Ford,William Topp .清華大學(xué)出版社（影印版）. </p><p>　　[4] 譚浩強(qiáng).《c語言程序設(shè)計(jì)》. 清華大學(xué)出版社. </p><p>　　[5]

76、 數(shù)據(jù)結(jié)構(gòu)與算法分析（Java版） , A Practical Introduction to Data Structures and Algorithm Analysis Java Edition Clifford A. Shaffer , 張銘,劉曉丹譯 電子工業(yè)出版社 2001 年1月</p><p><b>　　附 錄</b></p><p>　　

77、源程序（帶注釋） </p><p>　　#include<iostream></p><p>　　#include<fstream></p><p>　　using namespace std;</p><p>　　struct Coor //定義描當(dāng)前位置的結(jié)構(gòu)類型</p><p

78、><b>　　{</b></p><p>　　int row; </p><p>　　int column; </p><p>　　int direction; </p><p><b>　　};</b></p><p>　

79、　struct Move //定義下一個(gè)位置的方向</p><p><b>　　{</b></p><p><b>　　int row;</b></p><p>　　int column;</p><p><b>　　};</b></p><

80、p>　　struct LinkNode //鏈表結(jié)點(diǎn)</p><p><b>　　{</b></p><p>　　Coor data;</p><p>　　LinkNode *next;</p><p><b>　　};</b></p><p><b&g

81、t;　　//定義棧</b></p><p>　　class stack</p><p><b>　　{</b></p><p><b>　　private:</b></p><p>　　LinkNode *top; </p><p><b

82、>　　public:</b></p><p>　　stack(); //構(gòu)造函數(shù)，置空棧</p><p>　　~stack(); //析構(gòu)函數(shù)</p><p>　　void Push(Coor data); //把元素data壓入棧中</p><p>　　

83、Coor Pop(); //使棧頂元素出棧</p><p>　　Coor GetPop(); //取出棧頂元素</p><p>　　void Clear(); //把棧清空</p><p>　　bool IsEmpty(); //判斷棧是否為空</p

84、><p><b>　　};</b></p><p>　　stack::stack() //構(gòu)造函數(shù)，置空棧</p><p><b>　　{</b></p><p><b>　　top=NULL;</b></p><p><b>　

85、　}</b></p><p>　　stack::~stack() //析構(gòu)函數(shù)</p><p><b>　　{</b></p><p><b>　　}</b></p><p>　　void stack::Push(Coor x) //把元素data壓入棧

86、中</p><p><b>　　{</b></p><p>　　LinkNode *TempNode;</p><p>　　TempNode=new LinkNode;</p><p>　　TempNode->data=x;</p><p>　　TempNode->next=top;&

87、lt;/p><p>　　top=TempNode;</p><p><b>　　}</b></p><p>　　Coor stack::Pop() //使棧頂元素出棧</p><p><b>　　{</b></p><p>　　Coor Temp;

88、</p><p>　　LinkNode *TempNode;</p><p>　　TempNode=top;</p><p>　　top=top->next;</p><p>　　Temp=TempNode->data;</p><p>　　delete TempNode;</p><p

89、>　　return Temp;</p><p><b>　　}</b></p><p>　　Coor stack::GetPop() //取出棧頂元素</p><p><b>　　{</b></p><p>　　return top->data;</p&

90、gt;<p><b>　　}</b></p><p>　　void stack::Clear() //把棧清空</p><p><b>　　{</b></p><p><b>　　top=NULL;</b></p><p>&

91、lt;b>　　}</b></p><p>　　bool stack::IsEmpty() </p><p><b>　　{</b></p><p>　　if(top==NULL) </p><p>　　return true;</p><p><b>　　

92、else </b></p><p>　　return false;</p><p><b>　　}</b></p><p>　　Move move[4]={{0,1},{1,0},{0,-1},{-1,0}}; //定義移動(dòng)的4個(gè)方向</p><p>　　bool Mazepath(int **maze,

93、int m,int n); </p><p>　　//尋找迷宮maze中從（0，0）到（m,n）的路徑</p><p>　　//到則返回true,否則返回false</p><p>　　void PrintPath(stack p); //輸出迷宮的路徑</p><p>　　void PrintPath2(int m,

94、int n,stack p,int **maze); //輸出路徑</p><p>　　void Restore(int **maze,int m,int n); //恢復(fù)迷宮</p><p>　　int** GetMaze(int &m,int &n); //獲取迷宮（可從文件中讀取，也可輸入）</p><p&g

95、t;　　//返回存取迷宮的二維指針</p><p>　　int main()</p><p><b>　　{</b></p><p>　　system("color f5");</p><p>　　int m=0,n=0; </p><p>　　int **maze

96、; //定義二維指針存取迷宮</p><p>　　cout << "\n\t\t****************歡迎使用迷宮模擬程序*************" << endl;</p><p>　　cout << " \t\t 10級(jí)計(jì)算機(jī)一班

97、" << endl;</p><p>　　cout << " \t\t 程文鑫 " << endl;</p><p>　　cout << " \t\t 學(xué)號(hào)：10240

98、127" << endl;</p><p>　　maze=GetMaze(m,n); //調(diào)用GetMaze(int &m,int &n)函數(shù)，得到迷宮</p><p>　　if(Mazepath(maze,m,n)) //調(diào)用Mazepath(int **maze,int m,int n)函數(shù)獲取路徑</p><p>　　c

99、out<<"迷宮路徑探索成功!\n";</p><p>　　else cout<<"路徑不存在!\n";</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　int** G

100、etMaze(int &m,int &n)</p><p>　　//獲取迷宮（可從文件中讀取，也可輸入）</p><p>　　//返回存取迷宮的二維指針</p><p><b>　　{</b></p><p>　　int **maze; </p><p>　

101、　int i=0,j=0;</p><p>　　char Choose; //定義一個(gè)標(biāo)志，選擇讀取文件或直接輸入，獲取迷宮</p><p>　　cout<<"請(qǐng)選擇生成(1)或鍵盤輸入(2):";</p><p>　　cin>>Choose; </p><p&

102、gt;　　if(Choose=='1') //當(dāng)標(biāo)志Choose為‘1’時(shí)，讀取文件</p><p><b>　　{</b></p><p>　　cout<<"生成迷宮如下:\n";</p><p>　　char ch; //定義一個(gè)字符，讀取文件中的內(nèi)容&

103、lt;/p><p><b>　　i=0,j=0;</b></p><p>　　//首先得到文件中數(shù)字字符的數(shù)目，并得到迷宮的長(zhǎng)和寬</p><p>　　ifstream fip("test.txt"); </p><p>　　//定義一個(gè)文件對(duì)象，并打開文件“test.txt”</p>

104、<p>　　while(fip.get(ch)) //從讀取文件中內(nèi)容（一個(gè)個(gè)字符）</p><p><b>　　{</b></p><p>　　if(ch>='0'&&ch<='9') //獲取文件中的數(shù)字字符</p><p><b>　　{&l

105、t;/b></p><p>　　j++; //如果是字符，列就加1</p><p><b>　　}</b></p><p>　　if(ch=='\n') </p><p><b>　　{</b></p><p>

106、　　i++; //如果是換行，就行加1</p><p>　　n=j; //得到寬，即列數(shù)</p><p>　　j=0; </p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　f

107、ip.close(); //讀取文件結(jié)束</p><p>　　m=i; //得到長(zhǎng)即行數(shù)</p><p>　　maze=new int *[m+2]; //申請(qǐng)長(zhǎng)度等于行數(shù)加2的二級(jí)指針</p><p>　　for(i= 0;i<m+2;i++) //申請(qǐng)每個(gè)二維指針的空間</p><p><

108、b>　　{</b></p><p>　　maze[i]=new int[n+2];</p><p><b>　　}</b></p><p><b>　　i=j=1;</b></p><p>　　ifstream fip2("test.txt");//重新讀取文件

109、，以得到內(nèi)容</p><p>　　while(fip2.get(ch))</p><p><b>　　{</b></p><p>　　if(ch>='0'&&ch<='9')</p><p><b>　　{</b></p>&

110、lt;p>　　maze[i][j]=ch-'0'; //把數(shù)字字符轉(zhuǎn)化為數(shù)字，并存到指針里</p><p>　　cout<<maze[i][j]<<" "; //在屏幕中顯示迷宮</p><p><b>　　j++;</b></p><p><b>　　}

111、</b></p><p>　　if(ch=='\n') //遇到換行，指針也相應(yīng)換行</p><p><b>　　{</b></p><p>　　cout<<endl;</p><p><b>　　i++;</b></p><

112、;p><b>　　j=1;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　fip2.close(); //讀取結(jié)束</p><p>　　cout<<endl;</p><p&g

113、t;<b>　　}</b></p><p>　　else //Choose=2 ,輸入迷宮</p><p><b>　　{</b></p><p>　　cout<<"請(qǐng)輸入迷宮的行數(shù)和列數(shù):(中間用空格鍵分開)";</p><p><b&g

114、t;　　int a,b;</b></p><p>　　cin>>a>>b; </p><p>　　cout<<"請(qǐng)輸入迷宮內(nèi)容:(0表示通路,1表示不連通。中間用空格鍵分開)\n";</p><p><b>　　m=a;</b></p>&

115、lt;p>　　n=b; </p><p>　　maze=new int *[m+2]; //申請(qǐng)長(zhǎng)度等于行數(shù)加2的二級(jí)指針</p><p>　　for(i= 0;i<m+2;i++) //申請(qǐng)每個(gè)二維指針的空間</p><p><b>　　{</b></p><p>　　maze[i]=

116、new int[n+2];</p><p><b>　　}</b></p><p>　　for(i=1;i<=m;i++) </p><p>　　for(j=1;j<=n;j++)</p><p>　　cin>>maze[i][j];</p><p>　　c

117、out<<"是否保存新迷宮？\n";</p><p>　　cout<<"用Y或y表示保存、N或n表示不保存 \n";</p><p>　　char choose;</p><p>　　cin>>choose;</p><p>　　if(choose=='Y&#

118、39;||choose=='y')</p><p><b>　　{</b></p><p><b>　　char ch;</b></p><p>　　ofstream fop("Newtest.txt"); </p><p>　　for(i=1;i<=

119、m;i++)</p><p><b>　　{</b></p><p>　　for(j=1;j<=n;j++)</p><p><b>　　{</b></p><p>　　ch='0'+maze[i][j];</p><p><b>　　fop&

120、lt;<ch;</b></p><p><b>　　}</b></p><p>　　fop<<endl;</p><p>　　flush(cout);</p><p><b>　　}</b></p><p>　　fop.close();</

121、p><p><b>　　}</b></p><p><b>　　} </b></p><p>　　//給迷宮的四周加一堵墻，即把迷宮四周定義為1</p><p>　　for(i=0;i<m+2;i++) </p><p>　　maze[i][0]=

122、maze[i][n+1]=1;</p><p>　　for(i=0;i<n+2;i++)</p><p>　　maze[0][i]=maze[m+1][i]=1;</p><p>　　for(int p=0;p<m+2;++p)</p><p><b>　　{</b></p><p>

123、　　for(int q=0;q<=n+2;++q)</p><p><b>　　{</b></p><p>　　if(maze[p][q]==0)</p><p>　　cout<<"■";</p><p>　　if(maze[p][q]>=1)</p><p

124、>　　cout<<"□";</p><p><b>　　}</b></p><p>　　cout<<endl;</p><p><b>　　}</b></p><p>　　return maze; //返回存貯迷宮的二維指針

125、maze</p><p><b>　　}</b></p><p>　　bool Mazepath(int **maze,int m,int n)</p><p>　　//尋找迷宮maze中從（0，0）到（m,n）的路徑</p><p>　　//到則返回true,否則返回false</p><p>

126、<b>　　{</b></p><p>　　stack q,p; //定義棧p、q,分別存探索迷宮的存儲(chǔ)和路徑過程</p><p>　　Coor Temp1,Temp2; </p><p>　　int row,column,loop;</p><p>　　Temp1.row=1;</p>

127、<p>　　Temp1.column=1;</p><p>　　q.Push(Temp1); //將入口位置入棧</p><p>　　p.Push(Temp1);</p><p>　　maze[1][1]=8; //標(biāo)志入口位置已到達(dá)過</p><p>　　while(!q.IsEmpty(

128、)) //棧q非空，則反復(fù)探索</p><p><b>　　{</b></p><p>　　Temp2=q.GetPop(); //獲取棧頂元素</p><p>　　if(!(p.GetPop().row==q.GetPop().row&&p.GetPop().column==q.GetPop().colum

129、n)) </p><p>　　p.Push(Temp2); </p><p>　　//如果有新位置入棧，則把上一個(gè)探索的位置存入棧p</p><p>　　for(loop=0;loop<4;loop++) //探索當(dāng)前位置的4個(gè)相鄰位置</p><p><b>　　{</b></p>

130、<p>　　row=Temp2.row+move[loop].row; //計(jì)算出新位置x位置值</p><p>　　column=Temp2.column+move[loop].column; //計(jì)算出新位置y位置值</p><p>　　if(maze[row][column]==0) //判斷新位置是否可達(dá)</p><

131、;p><b>　　{</b></p><p>　　Temp1.row=row;</p><p>　　Temp1.column=column;</p><p>　　maze[row][column]=8; //標(biāo)志新位置已到達(dá)過</p><p>　　q.Push(Temp1); //

132、新位置入棧</p><p><b>　　}</b></p><p>　　if((row==(m))&&(column==(n))) //成功到達(dá)出口</p><p><b>　　{</b></p><p>　　Temp1.row=m;</p><p>　

133、　Temp1.column=n;</p><p>　　Temp1.direction=0;</p><p>　　p.Push(Temp1); //把最后一個(gè)位置入棧</p><p>　　char choose;</p><p>　　cout<<"請(qǐng)選擇以坐標(biāo)形式（row，column，direction）輸出

134、迷宮選(1)或以方陣形式輸出迷宮選(2):";</p><p>　　cin>>choose; </p><p>　　if(choose=='1') </p><p><b>　　{</b></p><p>　　PrintPath(p); //坐標(biāo)顯示輸出

135、 </p><p>　　Restore(maze,m,n); </p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　PrintPath2(m,n,

136、p,maze); //矩陣顯示輸出 </p><p>　　Restore(maze,m,n); </p><p><b>　　}</b></p><p>　　return 1; //表示成功找到路徑</p><p><b>　　}</b></p>

137、<p><b>　　}</b></p><p>　　if(p.GetPop().row==q.GetPop().row&&p.GetPop().column==q.GetPop().column)</p><p>　　//如果沒有新位置入棧，則返回到上一個(gè)位置</p><p><b>　　{</b&

138、gt;</p><p><b>　　p.Pop();</b></p><p><b>　　q.Pop();</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　return 0

139、; //表示查找失敗，即迷宮無路經(jīng)</p><p><b>　　}</b></p><p>　　void PrintPath(stack p) //輸出路徑</p><p><b>　　{</b></p><p>　　cout<<"迷宮的路徑為