C#数据结构课程设计用栈求解迷宫问题.doc

数据结构C#课程设计题 目 用栈求解迷宫问题 班 级 组长姓名学号 组员姓名学号 组员姓名学号 组员姓名学号 指导教师 编写日期 目录摘要2第1节课程设计题目2第2节课程设计内容22.1需求分析22.2实验目的32.3实验要求3第3节求解迷宫过程其原理4第4节课程设计实验步骤5第5节项目测试65.1测试过程出现的错误以及原因65.2测试数据截图7第6节项目代码9第7节课程设计实验小结20摘要数据结构课程设计是学习数据结构课程的一个重要环节。能巩固和加深课堂教学内容，提高学生实际工作能力，培养科学作风，为学习后续课程和今后的系统开发奠定基础。通过课程设计，使学生熟练掌握数据结构课程中所学的理论知识，并实际应用，通过综合运用数据结构的基本知识来解决实际问题，加强学生分析和解决问题的能力。课程设计比教学实验更复杂一些，深度更广并更加接近实际应用。通过课程设计的综合训练，培养我们学生实际分析问题、编程和动手能力，最终帮助我们学生系统把握课程的主要内容，更好地完成教学任务。第1节 课程设计题目题目：用栈求解迷宫问题第2节 课程设计内容2.1 需求分析迷宫问题通常是用“穷举求解”方法解决，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前走；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。栈是一个后进先出的结构，可以用来保存从入口到当前位置的路径。 定义迷宫类型来存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（n,n）。为处理方便起见，在迷宫的四周加一圈障碍2.2 实验目的（）了解回溯法在求解迷宫问题中的应用。（）进一步了解栈的应用2.3 实验要求 设计一个项目求解迷宫问题的所有路径。要求如下：(1) 迷宫最外围一圈都是不可走的(2) 从一个方块出发一步只能走其相邻的上、下、左、右4个方块中的一个可走方块。(3) 根据用户要求设置一个M*N的迷宫（M、N<=10）以及迷宫的入口和出口。(4) 提供“找路径”命令按钮，通过单击显示第一条迷宫路径。(5) 提供“找下一条路径”命令按钮，单击它一次显示一下条迷宫路径，直到所有的迷宫路径显示完毕。(6) 如下图所示是用户设置一个8*8的迷宫，入口为（1,1），出口为（5,5），单击“找回路”命令按钮显示第一条迷宫路径，当单击“找下一条路径”命令按钮显示 第二条迷宫路径，如此操作直到显示出所有的迷宫路径。第3节 求解迷宫过程其原理求解迷宫(xi,yi)到(xe,ye)路径的过程是：先将入口进栈（其初始方位设置为-1），在栈不空时循环：取栈顶方块（不退栈），若该方块是出口，则输出栈中所有方块即为路径。否则，找下一个可走的相邻方块，若不存在这样的方块，说明当前路径不可能走通，则回溯，也就是恢复当前方块为0后退栈。若存在这样的方块，则将其方位保存到栈顶元素中，并将这个可走的相邻方块进栈（其初始方位设置为-1）。第4节 课程设计实验步骤（1）新建一个windows应用项目“迷宫_栈”。（2）设计本项目对应的窗体Form1，其设计界面如下图所示。窗体上首先显示的是一个默认的10*10迷宫图（每个方块用一个命令按钮表示，白色表示可走，蓝色表示不可走），其操作步骤如下：用户输入行数m和列数n（m、n取值在410之间，包含4和10），单击“设置行列确定”吗，命令按钮，迷宫根据用户输入变成一个m*n迷宫图。用户可以点击迷宫图中的方块命令按钮改变其颜色，定制完成后单击“设置迷宫确定”命令按钮。用户设置入口和出口方块位置。单击“找路径”命令按钮，如果存在迷宫路径，则在迷宫图中显示第一条迷宫路径，迷宫路径用浅黄色方块标记，“”表示方块入口，“”表示方块出口，迷宫路径上的方块箭头表示路径走向。如果要下一条迷宫路径，单击“找下一跳路径”命令按钮，如果存在下一条迷宫路径，则在迷宫图中显示该迷宫路径，如果照完了所有迷宫路径，则显示相应的提示信息。第5节 项目测试5.1 测试过程出现的错误以及原因（1）调试过程中出现的错误有编译连接时的一些语法错误，也有由于算法存在问题而导致程序运行没有结果或者不是预期的结果。这里主要说一下自己由于算法而导致的错误：因为没有注意结点不能重复走，所以造成了死循环，程序没有结果。通过分析后把走过的结点变为不可走的结点，这样就避免了重复走到该结点。还有就是判断迷宫是否有通路的这个结果不能如预期的结果那样：有通路就输出所有的通路，没有就输出“未找到迷宫路径”。因为没有通路可走的时候栈是空的，但是输出所有的路径以后栈也是空的。当迷宫有通路的时候，在输出所有路径以后还是会输出“未找到迷宫路径”这句话。当迷宫没有通路的时候，输出“未找到迷宫路径”这句话。因为算法的思想是这样的，所以达不到预期的结果。解决的方法是如果迷宫有通路则输出所有的通路，如果迷宫没有通路，则没有结果输出。（2）迷宫的求解一般采用的是“穷举求解”，利用栈的思想，先将入口位置进栈，判断方向，若其方向可通，则进栈，若不通，则出栈，如此循环下去。5.2 测试数据截图第6节 项目代码using System;using System.Collections.Generic;using System.ComponentModel;using System.Data;using System.Drawing;using System.Text;using System.Windows.Forms;namespace Maze2 public partial class Form1 : Form const int M = 10; const int N = 10; const int MaxSize = 100; struct Box /定义方块结构体类型 public int i;/当前方块的行号 public int j;/当前方块的列号 public int di;/di是下一可走相邻方位的方位号 ; struct StType /定义顺序栈结构体类型 public Box data; public int top;/栈顶指针 ; StType st = new StType();/定义栈st int xi, yi, xe, ye; /迷宫的入口和出口 int count = 1; /路径计数 public Button, mg = new ButtonM, 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; /(x,y)为每个方块左上角坐标 Size s = new Size(30, 30); for (i = 0; i < M; i+) for (j = 0; j < N; 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; else mgi, 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; else btn.BackColor = System.Drawing.Color.Blue; private void button1_Click(object sender, EventArgs e) int i,j; try if (textBox1.Text.ToString() != "") m = int.Parse(textBox1.Text.ToString(); else m = M; if (textBox2.Text.ToString() != "") n = int.Parse(textBox2.Text.ToString(); else n = 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.Color.Blue; for (j = 0; j < n; j+) mgm - 1, j.BackColor = System.Drawing.Color.Blue; button1.Enabled = false; button2.Enabled = true; 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; else ai, j = 0; button2.Enabled = false; button3.Enabled = true; private void button3_Click(object sender, EventArgs e) int i; try if (textBox3.Text.ToString() != "") xi = int.Parse(textBox3.Text.ToString(); else xi = 1; if (textBox4.Text.ToString() != "") yi = int.Parse(textBox4.Text.ToString(); else yi = 1; if (textBox5.Text.ToString() != "") xe = int.Parse(textBox5.Text.ToString(); else xe = m - 2; if (textBox6.Text.ToString() != "") ye = int.Parse(textBox6.Text.ToString(); else ye = 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(); else button4.Enabled = false; infolabel.Text = "所有迷宫路径查找完毕,共"+Convert.ToString(count-1)+"条路径" public bool mgpath()/求解路径为:(xi,yi)->(xe,ye) 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;/找到一条路径后返回true find = 0; while (di < 4 && find = 0)/找下一个可走方块 di+; switch (di) case 0: i = st.datast.top.i - 1; j = st.datast.top.j; break; case 1: i = st.datast.top.i; j = st.datast.top.j + 1; break; case 2: i = st.datast.top.i + 1; j = st.datast.top.j; break; case 3: i = st.datast.top.i; j = st.datast.top.j - 1; 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 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;/找到一条路径后返回true find = 0; while (di < 4 && find = 0)/找下一个可走方块 di+; switch (di) case 0: i = st.datast.top.i - 1; j = st.datast.top.j; break; case 1: i = st.datast.top.i; j = st.datast.top.j + 1; break; case 2: i = st.datast.top.i + 1; j = st.datast.top.j; break; case 3: i = st.datast.top.i; j = st.datast.top.j - 1; 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 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.datai.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 void restore() /清除上一条迷宫路径 int i; for (i = 0; i <= st.top; i+) mgst.datai.i, st.datai.j.BackColor = System.Drawing.Color.White; mgst.datai.i, st.datai.j.Text = "" mgxe, ye.Text = "" 第7节 课程设计实验小结通过这段时间的课程设计，本人对计算机的应用，数据结构的作用以及C#语言的使用都有了更深的了解。尤其是C#语言的进步让我深刻的感受到任何所学的知识都需要实践，没有实践就无法真正理解这些知识以及掌握它们，使其成为自己的财富。在设计此程序时，刚开始感到比较迷茫，然后一步步分析，试着写出基本的算法，思路渐渐清晰，最后完成程序。当然也遇到不少的问题，也正是因为这些问题引发的思考给我带了收获。  在遇到描写迷宫路径的算法时，我感到有些困难，后来经过一步步分析和借鉴书本上的穷举求解的算法，最后把算法写出来。但其要求是要输出迷宫路径的一步步位置，我通过利用两个栈的互相出入栈，达到栈的逆序输出。在利用递归方法求路径时花费了我很长时间，由于本人对递归方面的知识运用较少，导致我不熟悉它的用法，但最终还是通过询问同学、查找书本和上网了解关于递归方面的知识写出来了。  这次课程设计让我更加深入了解很多方面的知识，如链结构的栈类型及其基本操作，数组的运用等等。在程序的编写中不要一味的模仿，要自己去摸索，只有带着问题反复实践，才能熟练地掌握和运用。  在实际的上机操作过程中，不仅是让我们了解数据结构的理论知识，更重要的是培养解决实际问题的能力，所以相信通过此次实习可以提高我们分析设计能力和编程能力，为后续课程的学习及实践打下良好的基础。