数据结构--迷宫求解()

实验报告实验报告 题目题目 迷宫求解 一 需求分析一 需求分析 1 本演示程序运用栈的结构求解迷宫 2 实现一个以顺序表或链表做存储结构的栈类型 编写一个求解迷宫的非递归程序 求得 的通路以三元组 i j d 的形式输出 3 程序执行的命令是 对任意设定的迷宫 求出一条从入口到出口的通路 或得出没有通 路的结论 4 迷宫的测试数据如下 左上角 1 1 为入口 右下角 3 4 为出口 二 编码实现二 编码实现 1 存储类型 存储类型 typedef struct zuobiao base zuobiao top Sqstack 2 部分函数的伪码算法 部分函数的伪码算法 构造一个栈构造一个栈 void Initstack Sqstack s top s base 入栈操作入栈操作 void push Sqstack s top y e y s top 出栈出栈 111111 1 1 1 1 1 1 1 11111 11 11 0 0 0 0 000 012345 void pop Sqstack e x s top x e y s top y 取栈顶元素取栈顶元素 void gettop Sqstack s zuobiao e x s top x e y s top y 迷宫求解迷宫求解 int mgqj int mg 6 6 Sqstack zj 1 1 东 zi 2 1 zj 2 0 南 zi 3 0 zj 3 1 西 zi 4 1 zj 4 0 北 i 1 j 1 e x 1 e y 1 push s e mg 1 1 1 do for v 1 v 4 v m i zi v n j zj v if mg m n 0 mg m n 1 i m j n e x m e y n push s e break else continue if v 5 gettop s e i e x j e y while s top s base if i 4 else return 0 三 调试分析三 调试分析 1 由于忽略算法和程序的区别 首次运行存在许多错误 2 本次作业题目虽然算法较长 但要求清晰 易形成思路 3 经验体会 在程序中适当加以注释 将使程序调试变得非常简便 可以加快找到程序中 的疵点 编制程序时应先建立大体框架 再将各部分细化 掌握从算法到程序的转换得方 法 四 测试结果四 测试结果 除输出整个迷宫外 还输出 1 1 1 2 2 2 3 2 3 3 3 4 五 附录五 附录 带注释的源程序如下带注释的源程序如下 include include typedef struct int x int y zuobiao typedef struct zuobiao base zuobiao top Sqstack void Initstack Sqstack s top s base void push Sqstack s top y e y s top void pop Sqstack e x s top x e y s top y void gettop Sqstack s zuobiao e x s top x e y s top y int mgqj int mg 6 6 Sqstack zuobiao e zi 1 0 zj 1 1 zi 2 1 zj 2 0 zi 3 0 zj 3 1 zi 4 1 zj 4 0 i 1 j 1 e x 1 e y 1 push s e mg 1 1 1 do for v 1 v 4 v m i zi v n j zj v if mg m n 0 mg m n 1 i m j n e x m e y n push s e break else continue if v 5 gettop s e i e x j e y while s top s base if i 4 else return 0 void main zuobiao e Sqstack s Initstack s int i j mg 6 6 for i 1 i 4 i 输入迷宫数据 0 或 1 for j 1 j 4 j scanf d for i 0 i 5 i 添加外围封闭墙 mg i 0 1 mg i 5 1 for j 0 j 5 j mg 0 j 1 mg 5 j 1 if mgqj mg s printf 此路可通 printf n for i 0 i 6 i for j