c++ 数据结构 迷宫问题

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

1、课程设计（论文）任务书软件学院软件工程+电子商务2009专业2班一、课程设计(论文)题目迷宫问题二、课程设计(论文)工作自2010年12月27日起至2011年1月2日止三、课程设计(论文)地点:创新大楼实训中心四、课程设计(论文)内容要求：1．本课程设计的目的（1）巩固和加深对数据结构基本知识的理解，提高综合运用课程知识的能力。（2）使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。（3）使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。2．课程设计的任务及要求1）基本要求：（1）对系统进行功能模块分析

2、、控制模块分析；（2）系统设计要能完成题目所要求的功能；（3）编程简练，可用，尽可能的使系统的功能更加完善和全面；（4）说明书、流程图要清楚；（5）提高学生的论文写作能力；（6）特别要求自己独立完成；2）创新要求：在基本要求达到后，可进行创新设计，如改善算法性能、友好的人机界面。3）课程设计论文编写要求（1）要按照书稿的规格打印与写课程设计论文（2）论文包括目录、正文、小结、参考文献、附录等（3）课程设计论文装订按学校的统一要求完成4）课程设计进度安排内容天数地点构思及收集资料1图书馆编码与调试3实验室撰写论文1图书馆、实验室学生签名：20011年1月3

3、日课程设计(论文)评审意见（1）基本算法（20分）：优（　）、良（　）、中（　）、一般（　）、差（　）；（2）设计分析　（20分）：优（　）、良（　）、中（　）、一般（　）、差（　）；（3）调试分析　（20分）：优（　）、良（　）、中（　）、一般（　）、差（　）；（4）论文内容　（20分）：优（　）、良（　）、中（　）、一般（　）、差（　）；（5）答辩分析　（20分）：优（　）、良（　）、中（　）、一般（　）、差（　）；（6）格式规范性及考勤是否降等级：是（）、否（　）评阅人：职称：讲师2011年1月4日目录一、需求分析1二、概要设计2三、详细设计5四、

4、调试分析及测试15五、个人工作及创新18六、小结19参考文献20数据结构课程设计一、需求分析1.选题理由本次课设我选择了迷宫问题，迷宫求解是数据结构课程的一个经典问题，迷宫问题要求寻找一条从入口到出口的路径。通常用的是“穷举求解”的方法。为了保证在任何位置上都能原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求解迷宫通路的算法中要应用“栈”的思想。对于栈的内容在整个学期的学习中我也有了一定的了解，所以选择了迷宫这一经典问题作为本次课设的内容。2.基本原理分析迷宫问题通常是用“穷举求解”方法解决，即从入口出发，顺着某一个方向进行

5、探索，若能走通，则继续往前走；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。栈是一个后进先出的结构，可以用来保存从入口到当前位置的路径。以二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（n,n）。为处理方便起见，在迷宫的四周加一圈障碍。对于迷宫任何一个位置，均约定东、南、西、北四个方向可通。3.功能要求（1）以一个二维数组Maze[m+2][n+2]表示迷宫，其中：Maze[0][j]和Maze[m+1][j](0<=j<=n+1)及Maze[i

6、][0]和Maze[i][n+1](0<=i<=m+1)为做外层的一圈障碍。数组中以0表示通路，1表示障碍，限定迷宫的大小为：m,n<=10。（2）用户需用文件的形式输入迷宫的数据：文件中第一行的数据为迷宫的行数m和列数n；从第2行至第m+1行（每行n个数）为迷宫值，用0，1输入，同行中的两个数字之间用空白字符相隔。（3）迷宫的入口位置和出口位置可由用户随时设定。（4）若设定的迷宫存在通路，则以长方阵形式将迷宫及其通路输出到标准输出文件上，其中字符“#”表示障碍，“*”表示路径，“@”表示曾途经该位置但不能到达出口，其余位置用空格符表示。若设定迷宫不存在

7、通路则报告相应信息（5）本程序只求出一条成功的通路。（6）程序执行的命令为：1，创建迷宫；2，求解迷宫；3，输出迷宫的解。19数据结构课程设计一、概要设计1、数据结构及其抽象数据类型的定义。（1）栈的抽象数据类型ADTStack{数据对象：D={ai

8、ai∈CharSet,i=1,2…n,n>=0}数据关系：R1={

9、ai-1,ai∈D,i=2,…n}基本操作：InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。操作结果：销毁栈S。ClearStack(&S)初始条件：栈S已存在。操

10、作结果：将S清为空栈。StackLength(S)初始条件：栈S已存在。操作结果