数据结构课程设计迷宫程序

《数据结构课程设计迷宫程序》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、目录课程设计目的功能说明三.详细设计3.1.功能模块设计3.1.1.主函数main()执行流程图3.1.2.创建模块3.1.3.操作模块3.1.4.显示模块3.1.5.其他模块3.2.数据结构设计3.3.函数功能描述四.程序实现4.1.源码分析4.2.调试结果4.3.遇到的问题及解决4.4.时间复杂度分析4.5.算法的改进思想五.结束语六.参考文献课程设计目的1.理解和掌握双向链表的数据结构。2.了解迷宫问题的提出背景、机器穷举法求解思路。3.使用机器穷举法和双向链表结构实现迷宫路径的查找。4.

2、设计实现一个完整的迷宫求解程序。二.功能说明整个实验将实现迷宫路径的查找，并图形化输出其中最短的路径。木实验脚步的存放使用双向链表实现，迷宫使用二维数组存放。机器通过穷举法解出迷宫的最短路径，储存在双向链表中，最后输岀。整个实验分为以下几个模块：1.创建模块。本实验的创建包含两方面，迷宫的定义和脚步的初始化。迷宫的定义通过修改二维数组实现，最终创建一个确定的迷宫。脚步的初始化由程序自行完成，最终建立一个双向链表的附加头结点。2.路径查找模块。路径查找核心分为两个部分：路径查找、更优解替换。路径查

3、找包括可通性检查、脚步前进、脚步后退三个模块。可通性检查会检查当前脚步的四个方向是否有通路。脚步前进可以在有通路的情况下抵达下一个点，并记录在脚步双向链表中。脚步后退使在当前脚步无路的情况下后退一步，并转向其他方向，同时删除链表中最后一个脚步。当求出的路径比上一次求出的路径更短时，更优解替换将更优解替换进路线存储链表。3.输岀模块。实现迷宫解的图形化显示和路径的坐标输岀。4.其他模块。格式化模块，用于迷宫求解后的处理。迷宫数组改写模块，按照求解的结果改写迷宫二维数组，以满足最终输岀需要。迷宫路径

4、查找程序其他模块输出模块创建模块迷宫数组改写格式化模块路径坐标输出迷宫解图形化显示路径查找模块LV迷宫定义图1功能模块图二.详细设计3.1・功能模块设计3.1.1.主函数main()执行流程图程序启动时，执行mainO函数输出菜单。用户根据菜单的提示输入要执行的功能，程序会根据用户的选择执行不同的功能。程序详细功能如下：1.自动演示：命令1,由程序自动生成一个迷宫，并进行路径求解的演示。2.手动迷宫：命令2,由用户自行创建一个迷宫，定义迷宫的大小、形状等，程序将对用户指定的迷宫进行求解。3.程序

5、帮助：命令3,显示程序帮助和必要信息。4.退岀：命令4,退岀程序。执行流程如下图:开始图2主函数main()执行流程图3.1.2.创建模块本模块将进行待解迷宫的创建。1.在〈自动演示〉中，机器会调用autocrcat()函数自动创建一个10*10的迷宫。2.在〈手动迷宫〉中，程序会使用creatO函数，用户可以通过指定迷宫大小ni*n,输入迷宫每一行的数据来自行创建迷宫。3.1.3.路径查找模块1•路径查找。本模块实现了路径的查找和脚步的移动。思路是依次判断上右下左四个方向，若可以通过则前进，不

6、可通过则转向下一个方向，四个方向都不可通过则后退。＜1＞可通性检查。可通性检查用来判断指定的方向是否可以通过。需要判断两方面内容，即下一点是否有障碍(通过chk()函数完成)和下一点是否已包含在了已有路径Z中。若同时满足无障碍和无包含条件，则可以通过。否则不能通过。〈2＞脚步前进。下一点若经过检查可以通过，则通过move()函数完成前进。“前进”的实现有两方面，第一方面，将新脚步纳入双向链表中，另一方面，在迷宫数组中将本步坐标所指标记为“己走”。〈3＞脚步后退。若木步四个方向都不能行走，则通过b

7、ack()函数退后。退后包括两方面，一方面把链表中最后一个节点抛弃，当前脚步指向倒数第二个节点。另一方面，将迷宫数组中已抛弃节点指向的元素重新标记为“未走”，以便进行其他路径的寻路操作时可以顺利通过。2•更优解替换。本模块完成了更优解的替换。当程序查找到比己存解更短的解时，将会销毁己存解，并将新解作为优解。直到最后所有的路径都搜索完毕，优解所存的路径即为最短路径。3.1.2.输出模块输岀模块调用outlinO函数，根据不同的参数值，输出不同的内容。主要功能是输出迷宫的图形化路径，并输岀此路径的坐

8、标顺序表示。3.1.4.其他模块1・格式化模块。调用formatmaze()函数，初始化存储迷宫的二维数组、各变量值，销毁上次求解时产生的双向链表，释放内存空间。2.迷宫数组改写模块，调用revise0函数，按照最终生成的最短双向链表记录的结果改写迷宫二维数组，以满足最终输岀需要。2.2.数据结构设计存储脚步的双向链表定义如下：typedefstructInode{structInode*next;structInode*pre;intx;inty；intstepsum;//表示当前脚步为第儿步