数据结构课程设计(迷宫问题)

第 1 页 共 16 页 大连海洋大学理学院 课程设课程设计实验报告实验报告 第 2 页 共 16 页 迷宫问题程序的设计与实现迷宫问题程序的设计与实现 一 需求分析 1 问题描述 问题描述 本实验是迷宫问题 取自心理学的一个古典实验 在该实验中 把一只老鼠从一个无顶大盒子的门放入 在盒中设置 了许多墙 对行进方向形成了多处阻挡 盒子仅有一个 出口 在出 口处放置一块奶酪 吸引老鼠在迷宫中寻找道路以到达出口 对同 一老鼠重复进行上述实验 一直到老鼠从入口到出口 而不走错一 步 老鼠经多次试验终于得到它学习走该迷宫的路线 设计一个计 算机程序对任意设定的迷宫 求出一条从入口到出口的通路 或得 出没有通路的结论 2 2 基本要求 基本要求 1 一条通路的二元组 i j 数据序列 i j 表示通路上某 一点的坐标 2 用标志 如数字 8 在二维数组中标出该条通路 并在屏幕上 输出二维数组 3 3 实现提示 实现提示 1 以二维数组 maze i j 表示迷宫 其中 0 0 mi nj 数组元素值为 1 表示该位置是墙壁 不能通行 元素值为 0 表示该位置是通路 限定迷宫的大小 m n 9 假定从 mg 0 0 出发 出口位于 mg m n 移动方向为顺时针的 8 个方 向 东 东南 南 西南 西 西北 北 东北 2 以文件的形式输入迷宫的数据 文件中第一行的数据为迷 第 3 页 共 16 页 宫的行数 m 和列数 n 从第 2 行至第 m 1 行为迷宫值 3 若设定的迷宫存在通路 则以方阵形式及其通路路径输出 若设定的迷宫不存在通路 则输出 没有可走路径 4 用一种标志 本题设为 8 在二维数组中显示该条通路 并 在屏幕上输出二维数组 本程序最终要求求出一条成功的 通路 2 概要设计 2 12 1 类型的定义 类型的定义 typedef struct int row 行 int col 列 int dir 方向 element element stack MAX STACK SIZE 存储走过的位置 typedef struct int vert 水平方向增量 int horiz 垂直方向增量 offsets 记录八个方向 东 东南 南 西南 西 西北 北 东北 第 4 页 共 16 页 int maze N 2 N 2 迷宫 int mark N 2 N 2 记录 maze 数组上的元素是否别访问过 int EXIT ROW EXIT COL 定义找到出口时的行和列 2 22 2 关系 关系 下图为下图为 pathpath 函数的流程图 函数的流程图 主函数 path del add 第 5 页 共 16 页 开始 栈不为空且未 找到路径 8个方向为全走 过且未找到路 径 下一位置不为 出口位置 可以走且没走 过 是 否 是 否 找到出路 当前位置和出口位 置入栈 否 返回失败标志 找到路径 是 否 结束 走下一方向 否 当前位置入栈当前 位置为下一位置是 初始位置入栈 读取栈顶元素 使其为当前位置 当前位置移动东到 下一相邻位置 是 输出栈中元 素 路径 第 6 页 共 16 页 三 详细设计 void path int row col next row next col dir found FALSE 分别为 当前位置行 列号 下 一位置行 列号 遍历方向 element position int top 0 mark 1 1 1 标记初始位置 stack 0 row 1 初始位置行号 stack 0 col 1 初始位置列号 stack 0 dir 0 定义初始位置遍历方向 move 0 vert 1 move 0 horiz 1 八个方向具体设置 move 1 vert 0 move 1 horiz 1 move 2 vert 1 move 2 horiz 0 move 3 vert 1 move 3 horiz 1 move 4 vert 1 move 4 horiz 1 move 5 vert 1 move 5 horiz 0 move 6 vert 0 move 6 horiz 1 move 7 vert 1 move 7 horiz 1 while 栈不为空且没找到路径 position del 栈顶元素出栈 第 7 页 共 16 页 将出栈元素作为当前位置 row position row col position col dir position dir while 八个方向没走完且没找到出路 next row row move dir vert 下一位置行号 next col col move dir horiz 下一位置列号 if 下一位置为终点 found TRUE 当前位置入栈 终点入栈 else if 下一位置非墙且没走过 标记 下一位置 当前位置 入栈 当前位置 改为 下一位置 初始方向设为第一方向即 dir 0 else 遍历下一方向即 dir 第 8 页 共 16 页 if found int count 0 记录节点为输出路径上的第几个节 点 输出 找到路径 路径坐标如下 for int i 0 i top i count 计数 输出该节点坐标 if count 5 0 printf n printf n n n int flag 记录最后遍历方向的下一方向 printf 具体路径为 n for i 1 i N 1 i for int j 1 j N 1 j flag 1 初值 if 栈中有该点坐标 flag 1 if flag 1 printf 2d maze i j 该点不在路径上 第 9 页 共 16 页 输出 else 输出栈中存储的上一方向 printf n printf n n else printf 未找到路径 n n n n printf n 四 使用说明 调试分析及结果 1 使用说明 依次按照文字提示输入 输入迷宫的方式 手动 自动随机产 生 手动输入 0 或 1 分别代表通路和墙壁 输入完成 即可生成结果 2 测试结果与分析 错误测试结果 矩阵输 入数值 不当 3 调试过程中遇到的问题是如何解决提以及对设计与实现的回顾讨论和分析 4 运行界面 第 10 页 共 16 页 没有找到路径 找到路径 第 11 页 共 16 页 5 课程设计总结 通过这一周的数据结构课程设计 过程曲折可谓一语难尽 整天都是对着电脑 不然就是翻阅资料 在此期间我失落过 也曾一度热情高涨 点点滴滴令我回味无 长 这次课程设计使我体会到只有做到细心耐心 恒心才能做好事情 这次的课程设计 加强了我们动手 思考和解决问题的能力 巩固和加深了对 数据结构的理解 提高综合运用本课程所学知识的能力 培养了我选用参考书 查 阅手册及文献资料的能力 培养独立思考 深入研究 分析问题 解决问题的能力 通过实际编译系统的分析设计 编程调试 掌握应用软件的分析方法和工程设计方 法 通过课程设计 培养了我严肃认真的工作作风 逐步建立正确的生产观念 经 济观念和全局观念 而且做课程设计同时也是对课本知识的巩固和加强 平时看课 本时 有些问题就不是很能理解 做完课程设计 那些问题就迎刃而解了 而且还 可以记住很多东西 认识来源于实践 实践是认识的动力和最终目的 实践是检验 真理的唯一标准 所以这个期末测试之后的课程设计对我们的作用是非常大的 这次的课程设计使我懂得了理论与实际相结合是很非常重要的 只有理论知识 是远远不够的 只有把所学的理论知识与实践相结合起来 从理论中得出结论 才 能真正为社会服务 从而提高自己的实际动手能力和独立思考的能力 在整个设计 过程中 构思是很花费时间的 调试时经常会遇到这样那样的错误 有的是因为粗 心造成的语法错误 当然 很多也时用错了方法 总是实现不了 同时在设计的过 程中发现了自己的不足之处 对以前所学过的知识理解得不够深刻 掌握得不够牢 固 第 12 页 共 16 页 根据我在课程设计中遇到得问题 我将在以后的学习过程中注意以下几点 1 认真上好专业实验课 多在实践中锻炼自己 2 写程序的过程中要考虑周到 严密 3 在做设计的时候要有信心 有耐心 切勿浮躁 4 认真的学习课本知识 掌握课本中的知识点 并在此基础上学会灵活运用 5 在课余时间里多写程序 熟练掌握在调试程序的过程中所遇到的常见错误 以便能节省调试程序的时间 每个实验通常都要花费很久的时间才能理清一个程序的思路 而且要不断的调 试程序才能把程序调试正确 这次课程设计终于顺利完成了 在设计中遇到了很多 专业知识问题 最后在老师的辛勤指导下 也完成了课程设计 通过这次的课程设计 让我更加了解到数据结构的重要性 以及它对我们专业 的发展发挥的作用 对我们而言 知识上的收获很重要 但精神上的丰收更加可喜 让我知道了学无止境的道理 我们每一个人永远不能满足于现有的成就 人生就像 在爬山 一座山峰的后面还有更高的山峰在等着你 挫折是一份财富 经历是一份 拥有 这次课程设计必将成为我人生旅途上一个非常美好的回忆 同时在做课程设 计时要能够从多方面去考虑 去研究 用多种算法去实现要求 此次课程设计 学 到了很多课内学不到的东西 比如独立思考解决问题 出现差错的随机应变 这些 都让我受益非浅 今后的制作应该能够更轻松 自己也都能够解决并高质量的完成 项目 第 13 页 共 16 页 6 附录 源程序清单 void path int row col next row next col dir found FALSE 分别为 当前位置行 列号 下 一位置行 列号 遍历方向 element position int top 0 mark 1 1 1 标记初始位置 stack 0 row 1 初始位置行号 stack 0 col 1 初始位置列号 stack 0 dir 0 定义初始位置遍历方向 move 0 vert 1 move 0 horiz 1 八个方向具体设置 move 1 vert 0 move 1 horiz 1 move 2 vert 1 move 2 horiz 0 move 3 vert 1 move 3 horiz 1 move 4 vert 1 move 4 horiz 1 move 5 vert 1 move 5 horiz 0 move 6 vert 0 move 6 horiz 1 move 7 vert 1 move 7 horiz 1 while 栈不为空且没找到路径 position del 栈顶元素出栈 第 14 页 共 16 页 将出栈元素作为当前位置 row position row col position col dir position dir while 八个方向没走完且没找到出路 next row row move dir vert 下一位置行号 next col col move dir horiz 下一位置列号 if 下一位置为终点 found TRUE 当前位置入栈 终点入栈 else if 下一位置非墙且没走过 标记 下一位置 当前位置 入栈 当前位置 改为 下一位置 初始方向设为第一方向即 dir 0 else 遍历下一方向即 dir 第 15 页 共 16 页 if found int count 0 记录节点为输出路径上的第几个节 点 输出 找到路径 路径坐标如下 for int i 0 i top i count 计数 输出该节点坐标 if count 5