数据结构课程设计---迷宫问题.doc

目 录 1．功能描述（或设计目标） 4 2．总体设计（或概要设计） 6 2．1数据结构描述与定义 8 2．2模块设计 9 3．测试结果与分析 10 4．课程设计总结 12 参考文献: 13 附录： 14 功能描述（或设计目标） 课程设计选题的目的 为大家解决一些生活中实际的问题，在这个过程中，自身的能力也在不断地提高。此次程序设计综合运用所学知识解决实际问题，将课堂的书本知识有效的在程序中体现出来，让学生更理解C++功能之强大，进一步让学生对面向对象的方法以及C++的编程思想有较好的了解和认识。此外，此次设计培养独立开发、设计、调试、运行程序的能力，激发学生较强的自学兴趣，锻炼学生之间以及学生与老师的沟通能力，培养学生之间的合作精神，让彼此更好的认识到合作的重要性，使学生在今后的学习中加强对合作精神的培养。 课程设计选题的背景和意义 课程设计的背景 儿童智力游戏的一种，同时也锻炼人的思维能力。当我们在一个迷宫中时怎样避免重复的走一些路，避免怎样走投无路，无路可走，什么样的迷宫可走，怎样就知道迷宫无出口了，通过回溯法帮我们解答，动脑子想办法，看看计算机是怎么实现以最快的方式走出你设的迷宫的。 课程设计的意义 一般来说，课程设计要比教学实验复杂一些，涉及的深度深，而且更加实用些。其目的是通过课程设计的综合训练，培养学生分析解决实际问题和编程等动手能力，最终目标是想通过这种形式，帮助学生系统掌握C++这门课程的主要内容，使老师更好的完成教学任务。 结合实际应用的要求，使课程设计既覆盖教学所要求的知识点，又接近工程的实际需要，训练自己实际分析问题和解决问题以及编程的能力。 通过详细的实例分析，循环渐进的描述，启发学生顺利的完成设计。课程设计将设计要求、需求分析、算法设计、编程和实例测试运行分开，为学生创造分析问题、独立思考的条件。只要学生在吃透要求和算法的前提下，完全可以不按书中提示的参考程序，自己设计出更具有特色的程序。 2．总体设计（或概要设计） 设计思想 迷宫中用回溯法从八个方向向前试探，用队列保存探测到的通路，建立一个数组模拟迷宫，将各个函数结合在一起。 迷宫中定义move数组，从东顺时针探测；进队出队完成探测；自己创建maze数组，并输入入口点和出口点，再进行计算。 详细的设计过程 实现定义操作伪代码算法 求一般路径伪代码： while(栈不空) { 栈顶元素=(x,y,d) 出栈; 求出下一个要试探的方向d++; while(还有剩余试探方向) { if(d方向可走) { (x,y,d)入栈; 求新点坐标(i,j); 将新点(i,j)切换成当前点(x,y); if((x,y)==(m,n)) 结束; else 重置 d=0; } else d++; } } 求解最短路径伪代码： (x,y)入队; while(队列不为空) { 队首元素出队; for(方向为0;方向总方向数;改变方向) { 到达点坐标; if(此坐标点为通路) 入队; if(到达出口点) { 输出路径; 恢复迷宫; } } 当前点有哪些信誉好的足球投注网站完，取下一点有哪些信誉好的足球投注网站; } 2．1数据结构描述与定义 实现定义的数据类型 （1）迷宫数组定义为结构体包含两个整型数据，迷宫出口和入口的值定义为整型。 （2）迷宫内部的设计时各坐标点设置成栈内整型。 （3）迷宫中求最短路径时定义结构体类型表示队列，包含整型坐标点，和整型下标；又有整型的队首尾指针。 结构体定义 typedef struct { int x,y; }item; typedef struct { int x,y,d; }Datetype; typedef struct{ int x,y; //所到点的坐标； int pre; //前驱点的下标； }SqType; //队列； 2．2模块设计 程序流程图 设计思路 在程序设计过程中，大约是按照几个步骤进行的，主要包括：方向设置，路径存储，迷宫图的存储，路径的求解，出口入口的设置。 迷宫问题中，主要依据c++语言和数据结构的相关知识进行设计的，采用move数组存储方向，采用二维数组存储迷宫图，采用栈存储路径，采用队列算出最短路径，参数传递出口入口和迷宫的大小。 迷宫问题中，突出优点为采用了时间随机函数，系统自动生成迷宫，节约用户时间。此外，用两种不同的存储方式（栈和队列）对迷宫进行探究。界面清晰、通俗易懂、操作简便、结构严谨、逻辑习惯强。 3．测试结果与分析 按系统功能描述（设计目标）测试软件运行是否正确，测试数据的选择要代表性，列出所有测试用的输入数据和相应的输出数据以及测试结果。 课程设计总结 程序中的不足 对于迷宫问题，输入迷宫内部结构时，输入形式为0、1空格或回车，输入形式有误时，会使程序无法运行下去，有时还会进入死循环。输入入口坐