迷宫与栈问题.doc

目录目录 一 一 系统开发的背景系统开发的背景 1 1 二 二 系统分析与设计系统分析与设计 1 1 一一 系统功能要求系统功能要求 1 二二 系统模块结构设计系统模块结构设计 1 三 三 系统的设计与实现系统的设计与实现 2 2 一一 栈的基本操作栈的基本操作 2 二二 迷宫算法 迷宫算法 PATHPATH S SEQEQS STACKTACK S S 4 三三 迷宫路径输出算法 迷宫路径输出算法 PRINTPATHPRINTPATH S SEQEQS STACKTACK S S 6 四四 主函数主函数 7 四 四 系统测试系统测试 8 8 一一 测试主函数迷宫的输入输出测试主函数迷宫的输入输出 8 二二 测试迷宫函数和迷宫路径输出函数测试迷宫函数和迷宫路径输出函数 8 五 五 总结总结 9 9 六 六 附件 代码 附件 代码 9 9 1 迷宫与栈问题迷宫与栈问题 一 一 系统开发的系统开发的背景背景 迷宫问题是心理学中的一个经典问题 一直以来人们乐都此不彼的研 究它 同样利用栈的思想也可以解决迷宫问题 二 二 系统分析与设计系统分析与设计 一一 系统功能要求系统功能要求 以一个mXn的长方阵表示迷宫 0和1分别表示迷宫中的通路和障碍 设计一个程序 对任意设定的迷宫 求出一条从入口到出口的通路 或得 出没有通路的结论 首先实现一个以链表作存储结构的栈类型 然后编写 一个求解迷宫的非递归程序 求得的通路以三元组 i j d 的形式输出 其中 i j 指示迷宫中的一个坐标 d表示走到下一坐标的方向 二二 系统模块结构设计系统模块结构设计 通过对系统功能的分析 系统功能如图 1 所示 迷宫与栈问题迷宫与栈问题 栈栈 的的 基基 本本 操操 作作 迷迷 宫宫 算算 法法 主主 函函 数数 迷迷 宫宫 路路 径径 输输 出出 2 图 1 迷宫与栈问题系统功能图 通过上图的功能分析 把整个系统划分为 4 个模块 1 栈的基本操作 该模块主要包括栈的初始化 栈空判别算法 入栈 算法 出栈算法 主要通过函数 SeqStack Init SeqStack Empty SeqStack SeqStack s Push SeqStack SeqStack s DateType x pop SeqStack SeqStack s DateType x 实现 2 迷宫算法 该模块主要通过函数 path SeqStack s 实现 3 迷宫路径输出算法 该模块主要通过函数 printpath SeqStack s 实现 4 主函数 该模块主要是迷宫的输入 打印 以及对以上函数的调 用 三 三 系统的设计系统的设计与实现与实现 一一 栈的基本操作栈的基本操作 分析 栈的初始化算法也可理解为置空栈算法 首先建立栈空间 然 后初始化栈顶指针 利用 if 来判断是否申请到足够大的储存空间 然后 返回空指针或栈空间地址 栈空判别算法 当栈顶指针指向栈底时 栈为 空 入栈算法 入栈时 首先借助 if 语句判断栈是否满了 栈满时 不 能入栈 返回错误代码 0 相反 栈顶指针向上移动 将 x 置于新的栈顶 入栈成功返回成功代码 1 出栈算法 出栈时 首先判断栈是否为空 借 助于 if 语句 栈空不能出栈 返回错误代码 0 相反 保存栈顶元素值 栈顶指针向下移动 栈顶元素存入 x 返回成功代码 1 该模块如图 2 所 示 3 图 2 栈的基本操作 该模块的具体代码如下所示 栈的初始化算法 SeqStack Init SeqStack SeqStack s s SeqStack malloc sizeof SeqStack s top 0 return s 栈空判别算法 int Empty SeqStack SeqStack s if s top 0 判断空栈 return 1 else return 0 入栈算法 int Push SeqStack SeqStack s DateType x if s top Maxsize 1 判断栈满 return 0 else s top s data s top x return 1 出栈算法 int pop SeqStack SeqStack s DateType x if Empty SeqStack s 栈的基本操作栈的基本操作 栈栈 的的 初初 始始 化化 栈栈 空空 判判 别别 算算 法法 入入 栈栈 操操 作作 出出 栈栈 操操 作作 4 return 0 else x s data s top s top return 1 二二 迷宫算法 迷宫算法 path SeqStackpath SeqStack s s 分析 从迷宫入口出发 按照一定的顺序 在本程序中顺序依次为右 右下 下 左下 左 左上 上 右上 对周围的墙 路进行判断 若周 围的位置都为 1 即没有通路 则沿原路返回前一点 换下一个方向继续 试探 直到所有通路都试探到 或找到一条通路 或无路可走又返回到入 口点 在求解过程中 为了保证在到达某一点后不能向前继续行走时 能 正确返回前一点 以便继续从下一个方向向前试探 则需要用一个栈保存 所能到达的没一点的下标及从该点前进的方向 栈是由行 列 方向组成 的三元组 迷宫求解算法思想如下 1 栈初始化 2 将入口坐标及到达该点的方向 设为 1 入栈 3 伪代码入下 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 5 else d 该模块的具体代码如下所示 迷宫算法 int path SeqStack s DateType temp int x y d i j temp x 1 temp y 1 temp d 1 初始化入口坐标及方向 Push SeqStack s temp while Empty SeqStack s pop SeqStack s x temp x y temp y d temp d 1 while d 8 i x move d x j y move d y if maze i j 0 该点可达 temp x x temp y y temp d d 坐标及方向 Push SeqStack s temp 坐标及方向入栈 x i y j maze x y 1 到达新点 if x m 到出口 迷宫有路 成功返回 1 else d 0 重新初始化方向 else d 改变方向 return 0 迷宫无路 失败返回 0 6 三三 迷宫路径输出算法 迷宫路径输出算法 printpath SeqStackprintpath SeqStack s s 分析 利用 for 循环输出栈中保存的路径 该算法的流程图如图 3 所 示 图 3 迷宫路径输出流程图 该模块的具体代码如下所示 void printpath SeqStack s int i for i 1 itop i printf d d d s data i x s data i y s data i d if itop printf if i 3 0 printf n printf n itop i 1 s data i x s data i s data i d y s data i d i N Y 7 四四 主函数主函数 分析 迷宫的输入输出借助于 for 循环实现 为了迷宫算法查找方 便 用 maze m 2 m 2 来表示迷宫 在四周加上一圈 哨兵 即迷宫四周 的值全部为 1 标识迷宫入口和出口即将 maze 1 1 maze m n 置为 0 该模块的具体代码如下所示 void main SeqStack s int i j k printf n printf 迷宫与栈问题 n printf n printf 请按行输入迷宫 d d n m n printf 提示 0 表示通路 1 表示阻碍 n for i 1 i m i for j 1 j n j scanf ld maze 1 1 0 maze m n 0 for i 0 i m 2 i maze i 0 1 maze i n 1 1 for j 0 j n 2 j maze 0 j 1 maze m 1 j 1 printf n 输入的迷宫如图所示 n for i 0 i m 2 i for j 0 j n 2 j printf 2d maze i j 8 printf n s Init SeqStack k path s if k 1 printf n 输出路径如下 n printpath s else printf 失败 n n getchar 四 四 系统测试系统测试 一一 测试主函数迷宫的输入输出测试主函数迷宫的输入输出 图 4 迷宫的输入及打印 二二 测试迷宫函数和迷宫路径输出函数测试迷宫函数和迷宫路径输出函数 9 图 5 迷宫路径的输出 五 五 总结总结 系统完成了迷宫的输入输出及查找路径并输出了路径的功能 系统不能输出迷宫所有的路径 统过这段时间的课程设计 我对计算机的应用 数据结构的作用 以及 C 语言的使用都有了更深的了解 尤其是 C 语言的进步让我深刻 的感受到任何所学的知识都需要实践 没有实践就无法真正理解这些 知识以及掌握它们 在设计此程序时 刚开始感到比较迷茫 然后一步 步分析 试着写出基本的算法 思路渐渐清晰 最后完成程序 当然也遇 到不少的问题 也正是因为这些问题引发的思考给我带了收获 这次课程 设计让我更加深入了解很多方面的知识 如顺序结构的栈类型及其基本操 作 数组的运用等等 在实际的上机操作过程中 不仅是让我们了解数据 结构的理论知识 更重要的是培养解决实际问题的能力 所以相信通过此 次课程设计可以提高我们分析设计能力和编程能力 为后续课程的学习及 实践打下良好的基础 六 六 附件 代码 附件 代码 include include define m 10 迷宫的行 define n 10 迷宫的列 顺序栈的类型描述 define Maxsize 50 10 int maze m 2 n 2 Move 数组定义 typedef struct int x y item item move 8 0 1 1 1 1 0 1 1 0 1 1 1 1 0 1 1 栈中元素的设计 typedef struct int x y d DateType 横坐标及方向 typedef struct DateType data Maxsize int top SeqStack SeqStack s 定义一个指向顺序栈的指针变量 栈的初始化算法 SeqStack Init SeqStack SeqStack s s SeqStack malloc sizeof SeqStack s top 0 return s 栈空判别算法 int Empty SeqStack SeqStack s if s top 0 判断空栈 return 1 else return 0 入栈算法 int Push SeqStack SeqStack s DateType x if s top Maxsize 1 判断栈满 return 0 else s top s data s top x return 1 出栈算法 int pop SeqStack SeqStack s DateType x if Empty SeqStack s return 0 else 11 x s data s top s top return 1 迷宫算法 int path SeqStack s DateType temp int x y d i j temp x 1 temp y 1 temp d 1 初始化入口坐标及方向 Push SeqStack s temp while Empty SeqStack s pop SeqStack s x temp x y temp y d temp d 1 while d 8 i x move d x j y move d y if maze i j 0 该点可达 temp x x temp y y temp d d 坐标及方向 Push SeqStack s temp 坐标及方向入栈 x i y j maze x y 1 到达新点 if x m 到出口 迷宫有路 成功返回 1 else d 0 重新初始化方向 else d 改变方向 return 0 迷宫无路 失败返回 0 12 打印迷宫路径函数 void printpath SeqStack s int i for i 1 itop i printf d d d s data i x s data i y s data i d if itop printf if i 3 0 printf n printf n void main SeqStack s int i j k printf n printf 迷宫与栈问题 n printf n printf 请按行输入迷宫 d d n m n printf 提示 0 表示通路 1 表示阻碍 n for i 1 i m i for j 1