数据结构迷宫

《数据结构迷宫》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构课程设计报告迷宫问题班级:姓名:学号:1.设计题目：迷宫问题2.设计内容：在一个mxn的矩形方阵表示一个迷宫，每一个格代表一个房间，相邻房间可以相通，也可以不通。找出一个由左上角进入迷宫由右下角出迷宫的路径。3・概要设计:迷宫问题是栈应用的一个典型例子，求解过程可采用回溯法。回溯法是一种不断试探且及吋纠正错误的搜索方法。从入口出发，按某一方向向前探索，若能走通即某处可到达，则到达新点，否则试探下一方向；若所有的方向均没有通路，换下一个方向继续试探，直到所有可能的通路都探索到，或找一条通路，或无路可走乂返回到入口点。在求解过程中为了保证在到达某一点后不能向前继续行走吋，能正确

2、返回前一点一边继续从下一个方向向前试探，则需要用一个栈保存所能够到达的每一点的下标及从该点前进的方向，栈中保存的就是一条迷宫的通路。为了确保程序能够终止，调整时，必须保证曾被放弃过的填数序列不被再次试验，即要求按某种有序模型生成填数序列。给解的候选者设定一个被检验的程序，按这个顺序逐一生成候选者并检验。4各模块之间的调用关系如下:5.测试结果及分析:caMC:DOCUIENTSANDSETTINGSSTUDEHT桌面Debugaigong.exeTheway40is:><2,2>—><3,2>—><3,1>—><4,1>—><5,1>—><5,2>—><5,3>—><6,

3、3>—><6,4>—><6,5>—><5.5>—><5,6>—><5.7>—><6,7>~><5,7>—><5,8>—><5,9>—>*><■)(・)(・)(KKM-M-MbooXXMMM000*決兴o務*杓00*00000**[m*0***快0MM**0**M*000*00000X*000*0*Ij——2y匸-M-Miheway41is:K1,0>—><2.2>—><3,2>—><4,1>—><5,1>—><5,2>—><5,3>—>〈6,3〉一-X6,4〉-一X6,5〉--X5.5〉-一><5,6>--X5,?〉一-X6.7〉-一>〈5.7〉一-X5.8〉-一X6,8〉--〉<

4、5,8〉--》<5,9〉-->1）本程序可以求解任何一个行和列均小于100的迷宫的通路，其中用来表示迷宫中的数据只可以用0或是1来表示，其中0代表可以通过，1则代表障碍；2）在上机过程中因为程序的逻辑性要求很高，在做迷宫通路求解的函数时因为忽略了一旦找到通路就结束循环，所以导致整个程序不能显示出正确的结果，后来在调试程序中使用了组建中的单步调试，通过来对比逻辑值与运行值来解决问题3）在输入的迷宫矩阵中，只有提示只可以用0或1,但是一旦输入了其它的字符也会接受，而且不能显示输入有错误4）可以扩充的功能有：可以将建好的迷宫以矩阵的形式输出来；可以找出迷宫中所有的通路并显示岀来6.心得体

5、会：课设中感受到自己知识的匮乏，需要学习的东西很多，不能总是局限于书本,在课设期间养成了经常去图书馆查阅的习惯，这个习惯应该继续保持下去，此外，当出现问题吋，应该及吋与周围同学交流，多交流才能使学到的东西更深入到心里，总之，这是一次不错的锻炼，专业水平不说能提高什么，但在过程中学到的学习方法应该是能受益终生的！在课设过程中，由于自己时间安排不当与专业基础知识的不扎实，课程设计的吋间总是感觉不够，在课设中也遇到了很多困难，好多吋候都止步不前，以致自己很是焦急，还好有同学和老师的帮助，使得自己克服困难，很感激他们，同吋也为学到东西而开心。迷宫程序源代码:#include

6、>#include#definen110#definen210typedefstructnode{intx;〃存x坐标inty;〃存y坐标intc;//存该点可能的下点所在的方向，表示向1表示向右，2上，3向左，4向右}linkstack;linkstacktopflOO];〃迷宫矩阵intmaze[nl][n2]={1,1,1,1,1,1,1,1,1,1,0,0,0,1,0,0,0,1,0,1,1,1,0,1,0,0,0,1,0,1,1,0,0,0,0,1,1,0,0,1,1,0丄0,0,0丄0,0丄1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,

7、0,1,0,0,1,1,0,1,1,1,0,1,1,0,1,1丄0,0,0,0,0,0,0,1,1丄1丄1丄1丄1丄};intij,k,m=0;main(){//初始化top[],置所有方向字为左for(i=0;i