嘉興學院數(shù)據(jù)結(jié)構(gòu)C課程設計資料

1、目錄一問題描述1二問題分析1三數(shù)據(jù)結(jié)構(gòu)描述 .1四算法設計1五主程序代碼 .4六程序運行結(jié)果14七實驗小結(jié)151.問題描述：給定一個 M*N 的迷宮圖，求一條從指定入口到出口的路徑。假設迷宮圖如圖M=10 ，N=1 ，其中的方塊圖表示迷宮。對于途中的每個方塊，用空格表示通道，用陰影表示墻。要求所求路徑必須是簡單路徑，即在求得的路徑上不能重復出現(xiàn)同一通道塊。2.問題分析：為了表示迷宮，設置一個數(shù)組a，其中每個元素表示一個方塊的狀態(tài)，為0時表示對應方塊是通道，為1時表示對應方塊不可走。數(shù)據(jù)結(jié)構(gòu)描述：在算法中用到的棧采用順序棧存儲結(jié)構(gòu)，將棧定義如下：Struct BoxPublic int i;Pu

2、blic int j;Public int di;Struct StTypePublic Box data;Public int top;StType st=new StType();算法設計：求迷宮問題就是在一個指定的迷宮中求出入口到出口的路徑。求解時，通常用的是 “窮舉求解”的方法。即從入口出發(fā)，順某一方向向前試探，若能走通，則繼續(xù)往前走；否則沿原路退回，換一個方向再繼續(xù)試探，直到所有可能的通路都試探完為止。為了保證在任何位置上都能沿原路退回（稱為回溯），需要用一個后進先出的棧來保存從入口到當前位置的路徑。對于迷宮中的每個方塊，有上、下、左、右4個方塊相鄰，第 i 行第 j 列的方塊的位置

3、記為（ i ， j ），規(guī)定上方方塊為方位0，并按順時針方向遞增編號。在試探過程中，假設從方位0到方位 3的方向查找下一個可走的方塊。為了便于回溯 , 對于可走的方塊都要進棧， 并試探它的下一可走的方位， 將這個可走的方位保存到棧中。求解迷宮（ xi ， yi ）到（ xe， ye）路徑的過程是：先將入口進棧，在棧不空時循環(huán)：取棧頂方塊（不退棧），若該方塊是出口，則輸出棧中所有方塊即為路徑。否則，找下一個可走的相鄰方塊，若不存在這樣的方塊， 說明當前路徑不可能走通，則回溯，也就是恢復當前方塊為 0后退棧。若存在這樣的方塊，則將其方位保存到棧頂元素中，并將這個可走的相鄰方塊進棧（其初始方位設置為

4、 -1 ）。求迷宮路徑的回溯過程中，從前一方塊找到一個可走相鄰方塊即當前方塊后，再從當前方塊找相鄰可走方塊，若沒有這樣的方塊，說明當前方塊不可能是從入口到出口路徑上的一個方塊，則從當前方塊回溯到前一方塊，繼續(xù)從前一方塊找另一個可走的相鄰方塊。為了保證試探的可走相鄰方塊不是已走路徑上的方塊，如（i ，j ）已進棧，在試探（i+1 ，j ）的下一可走方塊時，又試探到（i ，j ），這樣可能會引起死循環(huán)。為此，在一個方塊進棧后，將對應的a數(shù)組元素值改為-1 （變?yōu)椴豢勺叩南噜彿綁K），當退棧時（表示該棧頂方塊沒有可走相鄰方塊），將其恢復為0。求解一條從入口（xi ， yi ）到出口（ xe， ye）的

5、迷宮路徑的算法如下：Public bool mgpath(int xi,int yi,int xe,int ye)Int I,j,k,di,find;st.data=new BoxMaxSize;st.top=-1;/ 初始化棧頂指針st.top+;/初始入口方塊進棧st.datast.top.i=xi;st.datast.top.j=yi;st.datast.top.di=-1;axi,yi=-1;while (st.top -1)/ 棧不空時循環(huán)i = st.datast.top.i;j = st.datast.top.j;di = st.datast.top.di;/ 取棧頂方塊if (

6、i = xe & j = ye)/ 找到了出口， 輸出路徑return true;/ 找到一條路徑后返回truefind = 0;while (di 4 & find= 0)/ 找到下一個可走方塊di+;switch(di)case 0: i = st.datast.top.i - 1; j = st.datast.top.j;case 1: i = st.datast.top.i; j = st.datast.top.j + 1;case 2: i = st.datast.top.i + 1; j = st.datast.top.j;case 3: i = st.datast.top.i;

7、j = st.datast.top.j - 1;break;break;break;break;if (ai, j = 0) find = 1;/ 找到下一個可走相鄰方塊if (find = 1)/找到了下一個可走方塊st.datast.top.di = di;/ 修改原棧頂元素的di值st.top+;st.datast.top.i = i;st.datast.top.j = j;st.datast.top.di = -1;/ 下一個可走方塊進棧ai, j = -1;/ 避免重復走到該方塊else/沒有路徑可走，則退棧ast.datast.top.i, st.datast.top.j = 0;

8、/讓該位置變?yōu)槠渌窂娇勺叻桨竤t.top-;/將該方塊退棧return false;/ 表示沒有可走路徑，返回false當采用上述過程找到出口時，棧中從棧底到棧頂恰好是一條從入口到出口的迷宮路徑，輸出棧底到棧頂?shù)乃蟹綁K即為一條從入口到出口的迷宮路徑。5.主程序代碼：using System;using System.Drawing;using System.Windows.Forms;namespace 用棧求迷宮public partial classForm1 : Formconst int M = 10;const int N = 10;const int MaxSize = 100

9、;struct Boxpublic int i;public int j;public int di;struct StTypepublic Box data;public int top;StType st = new StType();int xi, yi, xe, ye;int count = 1;public Button , mg = new Button M, N;public int m = M, n = N;int, a = new int ,1,1,1,1,1,1,1,1,1,1,1,0,0,1,0,0,0,1,0,1,1,0,0,1,0,0,0,1,0,1,1,0,0,0,

10、0,1,1,0,0,1,1,0,1,1,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,1,1,0,1,0,0,0,1,0,0,1,1,0,1,1,1,0,1,1,0,1,1,1,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,;public Form1()InitializeComponent();private void Form1_Load( object sender, EventArgs e)int i, j;int x = 40, y =120;Size s = new Size(30,30);for (i = 0; i M; i+)for (j

11、 = 0; j = 40 + M * 30)x = 40;y += 30;textBox1.Text = Convert.ToString(M);textBox2.Text = Convert.ToString(N);button2.Enabled = false;button3.Enabled = false;button4.Enabled = false;private void button_Click( object sender, EventArgs e)Button btn =( Button )sender;if (btn.BackColor = System.Drawing.

12、Color .Blue)btn.BackColor = System.Drawing. Color .White;elsebtn.BackColor = System.Drawing. Color .Blue;private void button1_Click( object sender, EventArgs e)int i, j;tryif (textBox1.Text.ToString() != )m = int .Parse(textBox1.Text.ToString();elsem = M;if (textBox2.Text.ToString() != )n = int.Pars

13、e(textBox2.Text.ToString();elsen = N;catch (Exception err )infolabel.Text = 操作提示：輸入的迷宮大小是錯誤的，需要重新輸入;return;if (m10 | n10)infolabel.Text = 迷宮行數(shù)或列數(shù)輸入錯誤，請重新輸入 ; return;for (i = 0; i M; i+)for (j = n; j N; j+)mgi, j.Visible =false;for (i = m; i M; i+)for (j = 0; j N; j+)mgi, j.Visible =false;for (i = 0;

14、 i m; i+)mgi, n - 1.BackColor = System.Drawing.for (j = 0; j n; j+)mgm - 1, j.BackColor = System.Drawing.button1.Enabled = false;button2.Enabled = true ;Color .Blue;Color .Blue;private void button2_Click( object sender, EventArgs e)int i, j;textBox3.Text = 1 ;textBox4.Text = 1 ;textBox5.Text = Conve

15、rt.ToString(m-2);textBox6.Text = Convert.ToString(n-2);for (i = 0; i m; i+)for (j = 0; j -1)i = st.datast.top.i;j = st.datast.top.j;di = st.datast.top.di;if (i = xe & j = ye)return true;find = 0;while (di -1)i = st.datast.top.i;j = st.datast.top.j ;di = st.datast.top.di;if (i = xe & j = ye)return tr

16、ue;find = 0;while (di 4 & find = 0)di+;switch(di)case 0: i = st.datast.top.i - 1; j = st.datast.top.j;case 1: i = st.datast.top.i; j = st.datast.top.j + 1;case 2: i = st.datast.top.i + 1; j = st.datast.top.j;case 3: i = st.datast.top.i; j = st.datast.top.j - 1;break;break;break;break;if(ai, j = 0) f

17、ind = 1;if (find = 1)st.datast.top.di = di;st.top+;st.datast.top.i = i;st.datast.top.j = j;st.datast.top.di = -1;ai, j = -1;elseast.datast.top.i, st.datast.top.j = 0;st.top-;return false;private void display()int i;for (i = 0; i = st.top;i+ )mgst.datai.i, st.datai.j.BackColor =System.Drawing. Color

18、.AntiqueWhite;switch (st.data i.di )case 0: mgst.datai.i, st.datai.j.Text = ;break;case 1: mgst.datai.i, st.datai.j.Text = ; break;case 2: mgst.datai.i, st.datai.j.Text = ;break;case 3: mgst.datai.i, st.datai.j.Text = ; break;mgxi, yi.Text = 入口 ;mgxe, ye.Text =出口 ;infolabel.Text =成功找到第 + count.ToString() + 條迷宮路徑 ;count + ;private voidrestore()int i;for (i = 0; i = st.top;i+ )mgst.datai.i, st.datai.j.BackColor = System.Drawing.mgst.datai.i, st.datai.j.Text = ;Color .White;mgxe, ye.Text =出口 ;程序運行結(jié)果：實驗小結(jié)：在這為期一個星期的時間內(nèi)，通過我