嘉兴学院数据结构C课程设计资料

目录一问题描述1二问题分析1三数据结构描述 .1四算法设计1五主程序代码 .4六程序运行结果14七实验小结151.问题描述：给定一个 M*N 的迷宫图，求一条从指定入口到出口的路径。假设迷宫图如图M=10 ，N=1 ，其中的方块图表示迷宫。对于途中的每个方块，用空格表示通道，用阴影表示墙。要求所求路径必须是简单路径，即在求得的路径上不能重复出现同一通道块。2.问题分析：为了表示迷宫，设置一个数组a，其中每个元素表示一个方块的状态，为0时表示对应方块是通道，为1时表示对应方块不可走。3. 数据结构描述：在算法中用到的栈采用顺序栈存储结构，将栈定义如下：Struct BoxPublic int i;Public int j;Public int di;Struct StTypePublic Box data;Public int top;StType st=new StType();4. 算法设计：求迷宫问题就是在一个指定的迷宫中求出入口到出口的路径。求解时，通常用的是 “穷举求解”的方法。即从入口出发，顺某一方向向前试探，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续试探，直到所有可能的通路都试探完为止。为了保证在任何位置上都能沿原路退回（称为回溯），需要用一个后进先出的栈来保存从入口到当前位置的路径。对于迷宫中的每个方块，有上、下、左、右4个方块相邻，第 i 行第 j 列的方块的位置记为（ i ， j ），规定上方方块为方位0，并按顺时针方向递增编号。在试探过程中，假设从方位0到方位 3的方向查找下一个可走的方块。为了便于回溯 , 对于可走的方块都要进栈， 并试探它的下一可走的方位， 将这个可走的方位保存到栈中。求解迷宫（ xi ， yi ）到（ xe， ye）路径的过程是：先将入口进栈，在栈不空时循环：取栈顶方块（不退栈），若该方块是出口，则输出栈中所有方块即为路径。否则，找下一个可走的相邻方块，若不存在这样的方块， 说明当前路径不可能走通，则回溯，也就是恢复当前方块为 0后退栈。若存在这样的方块，则将其方位保存到栈顶元素中，并将这个可走的相邻方块进栈（其初始方位设置为 -1 ）。求迷宫路径的回溯过程中，从前一方块找到一个可走相邻方块即当前方块后，再从当前方块找相邻可走方块，若没有这样的方块，说明当前方块不可能是从入口到出口路径上的一个方块，则从当前方块回溯到前一方块，继续从前一方块找另一个可走的相邻方块。为了保证试探的可走相邻方块不是已走路径上的方块，如（i ，j ）已进栈，在试探（i+1 ，j ）的下一可走方块时，又试探到（i ，j ），这样可能会引起死循环。为此，在一个方块进栈后，将对应的a数组元素值改为-1 （变为不可走的相邻方块），当退栈时（表示该栈顶方块没有可走相邻方块），将其恢复为0。求解一条从入口（xi ， yi ）到出口（ xe， ye）的迷宫路径的算法如下：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)/ 栈不空时循环i = st.datast.top.i;j = st.datast.top.j;di = st.datast.top.di;/ 取栈顶方块if (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; 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;/让该位置变为其他路径可走方案st.top-;/将该方块退栈return false;/ 表示没有可走路径，返回false当采用上述过程找到出口时，栈中从栈底到栈顶恰好是一条从入口到出口的迷宫路径，输出栈底到栈顶的所有方块即为一条从入口到出口的迷宫路径。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;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,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 = 0; j < M;j+ )mgi, j = new Button ();mgi, j.Left = x;mgi, j.Top = y;mgi, j.Size = s;if (ai, j = 1)mgi, j.BackColor = System.Drawing.Color .Blue;elsemgi, j.BackColor = System.Drawing.Color .White;mgi, j.Visible =true;mgi, j.Click +=new System.EventHandler (this .button_Click);this.Controls.Add(mgi,j);x = x + 30;if (x >= 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. 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.Parse(textBox2.Text.ToString();elsen = N;catch (Exception err )infolabel.Text = " 操作提示：输入的迷宫大小是错误的，需要重新输入"return;if (m<4 | m>10 | n<4 | n>10)infolabel.Text = " 迷宫行数或列数输入错误，请重新输入 " 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; 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 = Convert.ToString(m-2);textBox6.Text = Convert.ToString(n-2);for (i = 0; i < m; i+)for (j = 0; j < n; j+)if (mgi, j.BackColor = System.Drawing.Color .Blue)ai, j = 1;elseai, j = 0;button2.Enabled = false;button3.Enabled = true;private void button3_Click( object sender, EventArgs e)int i;tryif (textBox3.Text.ToString() !="" )xi = int .Parse(textBox3.Text.ToString();elsexi = 1;if (textBox4.Text.ToString() !="" )yi = int .Parse(textBox4.Text.ToString();elseyi = 1;if (textBox5.Text.ToString() !="" )xe = int.Parse(textBox5.Text.ToString();elsexe = m - 2;if (textBox6.Text.ToString() !="" )ye = int.Parse(textBox6.Text.ToString();elseye = n - 2;catch (Exception err)infolabel.Text = " 操作提示：输入的迷宫入口和出口位置是错误的，请重新输入 "return;if (mgpath()display();button4.Enabled = true;else infolabel.Text = "未找到迷宫路径"button3.Enabled = false;private void button4_Click( object sender, EventArgs e)if (nextpath ()display ();elsebutton4.Enabled = false;infolabel.Text = " 所有迷宫路径查找完毕，共" + Convert.ToString(count - 1)+ "条路径 "public bool mgpath()int i, j, 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)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 <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) find = 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 bool nextpath()int i, j, di, find;restore();ast.datast.top.i, st.datast.top.j = 0;st.top-;while (st.top >-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 < 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) find = 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 .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 ="出口 "6. 程序运行结果：7. 实验小结：在这为期一个星期的时间内，通过我们小组各成员之间的相互讨论和合作，我们完成了栈迷宫的程序设计，更值得高兴的是我们的程序得到了大家的认可。这次设计， 不仅巩固了我以前所学的知识，还让我对C#有了更深一步的了解，掌握了更多的技巧和技能。在我们小组有解决不了的问题时，我们会主动查阅相关的资料，或向其他同学询问，这不仅丰富了我们的知识， 还增进了我们同学之间的合作能力。在参考书上， 我们不仅参考了所学的李春葆主编的数据结构教程C#语言描述，还通过上网搜索与本次课程实验设计相关的文献进行参考。我先将书本认认真真地看了一遍，又做了一下课后习题来完善和增进自己的理解，终于， 经过我们的不懈努力，我们小组的程序设计有了突破，成功地实现了通过栈制作迷宫的程序。 在这次课程设计中，我们首先对程序的整体功能进行了构思，然后用结构化分析方法进行分析， 将整个系统清楚的划分为几个模块，再根据每个模块的功能编写代码。而且尽可能的将模块细分，最后在进行修改和完善。由于我们是分工编写代码，最后需要将每个人的代码放到一起进行调试。因为我们每个人写的函数的思想不都一样，所以在调试的过程中也遇到了少许困难，但经过我们耐心的修改，终于功夫不负有心人，我们成功了!一周的短学期即将结束，时间虽短，但是我收获了很多。最后，谢谢老师和同学们的指导，更要感谢我们小组成员之间的合作与交流。 完2016/7/4.数据结构 C#课程设计题目栈迷宫班 级组长姓名学号组员姓名学号组员姓名学号组员姓名学号指导教师编写日期