嘉兴学院数据结构C课程设计概要.doc

目录 问题描述....................................1 问题分析....................................1 数据结构描述............................1 算法设计....................................1 主程序代码................................4 程序运行结果..........................14 七．实验小结..................................151.问题描述： 给定一个M*N的迷宫图，求一条从指定入口到出口的路径。假设迷宫图如图M=10，N=1 ，其中的方块图表示迷宫。对于途中的每个方块，用空格表示通道，用阴影表示墙。要求所求路径必须是简单路径，即在求得的路径上不能重复出现同一通道块。 2.问题分析： 为了表示迷宫，设置一个数组a，其中每个元素表示一个方块的状态，为0时表示对应方块是通道，为1时表示对应方块不可走。 3.数据结构描述： 在算法中用到的栈采用顺序栈存储结构，将栈定义如下： Struct Box { Public int i; Public int j; Public int di; }; Struct StType { Public 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 Box[MaxSize]; st.top=-1; //初始化栈顶指针 st.top++; //初始入口方块进栈 st.data[st.top].i=xi;st.data[st.top].j=yi; st.data[st.top].di=-1;a[xi,yi]=-1; while (st.top -1) //栈不空时循环 { i = st.data[st.top].i; j = st.data[st.top].j;