数据结构与算法----迷宫求解课程设计

《数据结构与算法----迷宫求解课程设计》由会员分享，可在线阅读，更多相关《数据结构与算法----迷宫求解课程设计（14页珍藏版）》请在毕设资料网上搜索。

1、 课课 程程 设设 计计 课程设计名称：课程设计名称： 迷宫求解 专专 业业 班班 级级 ： 学学 生生 姓姓 名名 ： 学学 号号 ： 指指 导导 教教 师师 ： 课程设计时间：课程设计时间： 专业课程设计任务书专业课程设计任务书 学生姓名学生姓名 专业班级专业班级 学号学号 题题 目目 迷宫求解迷宫求解 课题性质课题性质 其它其它 课题来源课题来源 自拟课题自拟课题 指导教师指导教师 同组姓名同组姓名 主要内容主要内容 建立迷宫，在迷宫中寻找任意两坐标间是否存在路径，并显示出该路径。 为了保证在任何位置上都能沿远路退回，需要用一个后进先出的结构来保存从 入口到当前位置的路径。因此，在求迷宫

2、通路的算法中要应用“栈”的思想。 任务要求任务要求 1应用数据结构基础知识进行实际问题求解与分析； 2编程实现算法 3具有良好的界面，操作方便灵活、简洁高效。 4按要求撰写课程设计报告和设计总结。 参考文献参考文献 1数据结构，严蔚敏，吴伟民，清华大学出版社， 2C 程序设计（第二版），谭浩强，北京，清华大学出版社，1999. 3C+实用教程（第一版），杨明军、董亚卓、汪黎，人民邮电出版社， 2002. 4. Visual C+实用教程（第一版），张荣梅、梁晓林，冶金工业出版社， 2004 审查意见审查意见 指导教师签字：指导教师签字： 教研室主任教研室主任签字：签字： 年年 月月 日日 说明

3、：本表由指导教师填写，由教研室主任审核后下达给选题学生，装订在设计（论文）首页 1 1 需求分析 本课程设计内容是解决迷宫问题。 迷宫是一个矩形区域， 有一个入口和出口。 在迷宫内部不能穿越墙或障碍。输入一个 m*n 大小的方阵表示迷宫，0 和 1 分别 表示迷宫中的通路和障碍。迷宫问题要求寻找一条从入口到出口的路径。由于计 算解迷宫时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前 探索，若能走通，则继续往前进：否则沿原路退回，换一个方向再继续探索；直 至所有可能的通路都探索为止。为了保证在任何位置上都能沿远路退回，显然需 要用一个后进先出的结构来保存从入口到当前位置的路径。因此

4、，在求迷宫通路 的算法中要应用“栈”的思想。 首先，在计算机中可以用 0、1 图表示迷宫。所求路径必须是简单路径，即 在求得的路径上不能重复出现同一通道。 假设“当前位置”指的是“在搜索过程 中的某一时刻所在图中某个位置”，则求迷宫中一条路径的算法的基本思想是： 若当前位置“可通”，则纳入“当前路径”，并继续朝“下一位置”探索，即切 换“下一位置”为“当前位置”，如此重复直至到达出口；若当前位置“不可 通”，则应顺着“来向”退回到“前一通道”，然后朝着除“来向”之外的其他 方向继续探索；若该通道块的四周 4 个方向均“不可通”，则应从“当前路径” 上删除该通道。所谓“下一位置”指的是当前位置四周 4 个方向（东、南、西、 北） “1” 。假设以栈 S 记录“当前路径”，则栈顶中存放的是“当前路径上最后 一个通道”。由此，“纳入路径”的操作即为“当前