实训报告—迷宫问题

1、 迷宫问题 实训报告数据结构 题 目： 迷宫问题 院 系： 信息科技学院 专 业： 计算机科学与技术 姓 名： 黄经伟 学 号： 1151210213 指导教师： 梁海 日 期： 2013年1月6日 桂林电子科技大学信息科技学院 目 录 迷宫问题- 3 -一、设计需求- 3 -二、概要设计- 3 -1、系统设计- 3 -11 总体设计- 3 -12 详细设计- 4 -1.2.1执行流程- 4 -3、系统实现- 5 -31 编码- 5 -3.1.1 类和结构体的代码- 5 -3.1.2 初始界面及行列数输入的代码- 5 -3.1.3 手动设计迷宫的代码- 5 -3.1.4自动设置迷宫的代码- 6

2、 -3.1.5 显示迷宫的代码- 7 -3.1.6 搜索通路的代码- 7 -32 测试与调试- 9 -3.2.1 概述- 9 -3.2.2 程序测试- 10 -4、系统维护- 14 -5、归纳总结- 14 -51 开发经验- 14 -52 实训中遇到的问题及解决方法- 14 -53感想和心得体会- 14 -迷宫问题【摘要】随着信息科技的发展，我们可以在计算机上设计一些系统来计算一些比较复杂的问题，例如：迷宫问题。迷宫问题指的是在一个迷宫内寻找一条可以走出迷宫的路径，我们可以通过计算机来的高速运算来快速求出路径，这就是本次实训的目的。【关键字】迷宫 寻找路径 快速 一、 设计需求本次实训我选择了

3、迷宫问题，迷宫问题是数据结构课程的一个经典问题。迷宫问题要求寻找一条从入口到出口的路径。为了保证在任何位置上都能原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求解迷宫的通路的算法中要应用“栈”的思想。对于栈的内容在整个学期学习中我也有了一定的了解，所以选择迷宫这一经典的问题来作为实训。二、 概要设计1、系统设计11 总体设计采用模块化的程序设计方法，即将较大的任务按照一定的原则分为一个个较小的任务，然后分别设计各个小任务。需要注意的是划分出来的模块应该相对独立但又相关，且容易理解。可以用模块化层次结构图（即模块图）来分析其任务的划分，一般从上到下进行，最上面一层是

4、主模块，下面各层是其上一层模块的逐步细化描述。结束迷宫问题迷宫生成随机生成手动生成输出迷宫和迷宫路径手动编辑迷宫输出迷宫和迷宫路径图2.1 功能结构图本迷宫问题设计如图2.1所示，它由两个部分组成：l 随机生成：电脑随机生成迷宫，可以快速画出迷宫，并求出迷宫是否有通路。l 手动生成：通过自己手动来设计出迷宫，设计好后，系统通过计算，画出迷宫并求出迷宫是否有通路。12 详细设计 图2.2 执行流程图开始进到初始界面选择迷宫的行数和列数选择手动绘制或者电脑绘制电脑绘制手动绘制编辑迷宫显示迷宫，并输出路径结束1.2.1执行流程本迷宫系统执行主流程如图2.2所示。它首先进入初始界面，然后用户可以对功能

5、进行选择进行相应的操作，可以查看手动和自动生成迷宫，并求出路径。3、系统实现31 编码3.1.1 类和结构体的代码class CLabyrinth int X,Y; /迷宫的大小 int MapMaxXMaxY; /迷宫结构 Point Result255; /存放正确的路径(栈) int top; /栈顶（指针） public: CLabyrinth(); /得到迷宫尺寸 void SetMap(); /手工设置迷宫结构 void AutoSetMap(); /自动设置迷宫结构 void ShowMap(); /显示迷宫 void SearchWay(); /搜索通路 void ShowRe

6、sult(); /显示通路 ;3.1.2 初始界面及行列数输入的代码CLabyrinth:CLabyrinth() /主界面 cout<<"tt 欢迎进入迷宫ttn" <<" 输入迷宫的大小X*Y(最大为50*50):n" <<"【不建议超过8列，因为绘出的地图将不会显示】n" int x,y; cout<<" 请输入行数:"<<endl; cin>>x; cout<<" 请输入列数:"<<endl;

7、 cin>>y; X = (x>48) ? 50 : x+2; /多两个单位是存放迷宫外壁 Y = (y>48) ? 50 : y+2; top=-1; 3.1.3 手动设计迷宫的代码void CLabyrinth:SetMap() /手工设置迷宫结构 cout<<"n依次输入迷宫的结构(1为有障碍，0为无障碍):n" <<"前进方向有4个,分别是上、下、左、右n" for(int i=0,j,t;i<X;i+) for(j=0;j<Y;j+) if(i=0 | j=0 | i=X-1 | j=

8、Y-1) /在迷宫周围包上一圈1，防止搜索通路时越界 Mapij=1; continue; cin>>t; Mapij = (t!=0) ? 1 : 0; 3.1.4自动设置迷宫的代码void CLabyrinth:AutoSetMap() /自动设置迷宫结构 cout<<"n前进方向有4个,分别是上、下、左、右、n" int a(39),b(72); for(int i=0,j;i<X;i+) srand(unsigned)time(NULL); for(j=0;j<Y;j+) if(i=0 | j=0 | i=X-1 | j=Y-1)

9、 Mapij=1; continue; srand(rand()*(a+)+(b+)%65536); /随机生成点Mapij=rand()%2; 3.1.5 显示迷宫的代码void CLabyrinth:ShowMap() /显示迷宫 if(Y>10) return; cout<<"n迷宫示意图为:n" for(int i=1,j;i<X-1;i+) for(j=1;j<Y-1;j+) if(i=1&&j=1) /cout<<"nt入口->" cout<<"入口->

10、; " else cout<<" t" cout<<Mapij; if(i=X-2&&j=Y-1) cout<<" ->出口" cout<<endl; 3.1.6 搜索通路的代码void CLabyrinth:SearchWay() /搜索通路 if(MapX-2Y-2) return; /如果出口不通直接返回 int i(X-2),j(Y-2); /出口的坐标 从出口向入口找路 int pow; /检查方向的计数器 do if(!Mapij) Result+top.x =

11、i; /将要可通行的坐标入栈 Resulttop.y = j; if(Resulttop.x=1&&Resulttop.y=1) break; /如果找到了入口退出循环 i = i-1; /下一个要检查的坐标 左斜上方 j = j-1; pow=0; /计数器清零 else pow+; i = Resulttop.x; /取出栈顶元素 上一次的可通行坐标 j = Resulttop.y; switch(pow) case 1: i-; break; /上 case 2: j-; break; /左 case 3: i-;j+; if(i=Resulttop-1.x &&

12、amp; j=Resulttop-1.y) /若是来路 pow+; else break; case 4: i+;j-; if(i=Resulttop-1.x && j=Resulttop-1.y) pow+; else break; default: Mapij = 1;i = Result-top.x;j = Resulttop.y; /将该坐标设为不可通行 再回到上一次可通行坐标 while(top!=-1); /栈不为空继续循环 void CLabyrinth:ShowResult() /显示通路 if(top=-1) cout<<"n此迷宫没有通

13、路!n" return; cout<<"n此迷宫的其中一条通路为:n入口" for(;top!=-1;top-) cout<<"->("<<Resulttop.x<<','<<Resulttop.y<<')' cout<<"->出口n" 将各类的代码相应的加到程序中，然后进行测试与调试。 32 测试与调试3.2.1 概述一般情况下，为解决一个问题所编写的程序代码较长，可能包括几百条甚至成千上万条语句

14、。在检查并排除所有语法错误后，还会有不易发现的逻辑错误，因此要对程序进行认真仔细的测试与调试。测试是通过运行程序发现错误的过程，常见的错误有数据溢出、数组越界、进入死循环、语句顺序颠倒、多加“；”或少加“”等等。调试则是确定测试中找到的错误性质并改正错误的过程。测试与调试通常交替进行，即测试调试再测试再调试。能检查出尚未发现的、各种不同类型错误的测试才是成功的测试。测试程序需要测试用例，测试用例可用如下公式表示：测试用例测试数据预期结果。好的测试用例应该是用尽可能少的测试数据发现尽可能多的错误，即发现错误的概率要大。要选择合适的测试数据，使系统在运行时尽量能执行到每条语句，以测试各指令是否正确

15、。还应分别测试输入合法数据与非法数据时，程序的运行情况，。对于合法数据，还要考虑数据的一般性与特殊性，如求最大值的问题，应测试最大值在最前面、最后面、中间某一位置的情况。测试可按模块测试、组装测试和确认测试的步骤进行。（1）模块测试就是分别对各模块进行测试的过程。在编写一个模块后应立即对其进行测试，因为这时对模块记忆深刻，而且单个模块相对较小，所以容易构造测试数据，能方便地检查和改正错误。（2）组装测试就是把所有模块（应该是通过模块测试的模块）按预先制定的计划逐步组装和测试的过程。一般情况下，各模块之间要相互传递数据和控制信息，因此组装测试的主要任务是发现模块接口中的错误。（3）确认测试是最后

16、一个步骤，一般在将软件交付用户之前，应确认软件是否确实满足用户的要求，通常使用接近实际的用例进行测试。测试程序时，用监视窗口可以随时查看变量或表达式的值，有时还可以将部分程序代码用注释符暂时括起来，缩短程序，以便压缩出错代码的范围。3.2.2 程序测试l 运行程序进入界面后就说明程序没有错误现在开始进行各种功能的测试！ 图3.1 进入迷宫系统l 输入迷宫大小依次输入迷宫的行数和列数 图3.2 输入迷宫大小l 选择手工绘制迷宫图3.3 选择手工绘制迷宫l 编辑迷宫编辑好迷宫按回车键后，系统就生成迷宫，并将迷宫路径求出，打印出来。图3.4 手动编辑迷宫后l 再次编辑刚刚设计好大小的迷宫选择y后，回

17、到选择手工或者电脑绘制迷宫的界面。图3.5 返回迷宫选择绘制界面l 选择电脑绘制迷宫 因为迷宫没用通路所以会输出“此迷宫没用通路的字样”图3.6 选择电脑绘制迷宫l 选择任意值返回初始界面 选择一个任意的值，则会回到初始界面。图3.6 回到初始界面4、系统维护经测试与调试确认软件无错时，开发就告一段落，这时可以交付软件供用户使用，但是在软件的使用过程中还会面临更加漫长的工作，即软件维护。一般维护的工作有：更改使用中发现的错误；为适应实际环境而对程序进行修改；为满足新的需求而对程序作必要的改进等等。5、归纳总结51 开发经验通过对本题目的开发，体会到要掌握以下几点内容。l 要学会先做好模块，从大到小，进行细化。l 编写好函数，并进行测试与调试。Vc工具提供丰富的库函数，编程序时要善于使用库函数，可以提高效率。l 定义函数时，应选好参数的个数和数据类型。52 实训中遇到的问题及解决方法在这次的实训中，主要遇到的问题是编译环境的不同对程序也不同。所遇到的问题主要是对书本中的知识不太理解，没有将课本上的定义理解完全，后来在经过同学和老师的帮助与指导下，成功的编写出了一套关于成绩管理系统，并且