数据结构课程设计-求解迷宫问题

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

1、课程设计(论文)题目名称迷宫求解课程名称数据结构课程设计学生姓名学号系、专业信息工程系、电气信息类（信息类）指导教师申寿云2010年1月3日摘要设计一个简单迷宫程序，从入口出发找到一条通路到达出口。编制程序给出一条通过迷宫的路径或报告一个“无法通过”的信息。首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。用“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。可以用二维数组存储迷宫

2、数据，通常设定入口点的下标为（1，1），出口点的下标为（n，n）。为处理方便起见，可在迷宫的四周加一障碍。对于迷宫任一位置，均可约定有东、南、西、北四个方向可通。关键词：迷宫；栈；链表；二维数组目录1问题描述12需求分析13概要设计13．1抽象数据类型定义13．2模块划分24详细设计24．1数据类型的定义24．2主要模块的算法描述35测试分析66课程设计总结7参考文献8附录（源程序清单）91问题描述迷宫是一个M行N列的0-1矩阵，其中0表示无障碍，1表示有障碍。设入口为(1，1)出口为(M，N)每次移动只能从一个无障碍的单元移到其周围8个方向上任一无障碍的单元

3、，编制程序给出一条通过迷宫的路径或报告一个“无法通过”的信息。2需求分析（1）首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i，j，d）的形式输出，其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。否则报告一个无法通过的信息。（2）建立InitStack函数，用于构造一个空栈。（3）建立DestroyStack函数，用于销毁栈。（4）建立Pop函数，用于删除栈顶元素，返回栈顶元素的值。（5）建立Push函数，用于插入新的栈顶元素。（6）建立NextPos函数，用于定位下一个位置。3概要设计3．1抽象数

4、据类型定义（1）栈的抽象数据类型定义InitStack(LStack*S)操作结果：构造一个空栈S。DestroyStack(LStack*S)操作结果：栈S被销毁。Pop(LStack*S，ElemType*e)操作结果：删除S的栈顶元素。用e返回栈顶元素的值。若栈为空则返回0。Push(LStack*S，ElemTypee)操作结果：在栈顶之上插入元素e为新的栈顶元素。若栈S为空栈，则返回0。（2）迷宫的抽象数据类型定义NextPos(unsigned*x，unsigned*y，shortdi)操作结果：找到下一个位置。153．2模块划分本程序包括三个模块

5、：（1）主程序模块voidmain(){初始化；构造迷宫；迷宫求解；迷宫输出；}（2）栈模块——实现栈的抽象数据类型（3）迷宫模块——实现迷宫的抽象数据类型4详细设计4．1数据类型的定义（1）迷宫类型typedefstruct{unsignedord,x,y；shortdi；}ElemType；unsignedx,y,curstep,i=0；charmaze[10][10]；（2）栈类型typedefstructNode{ElemTypedata；structNode*next；}Node,*LinkList；typedefstruct{LinkListtop

6、；unsignedlength；15}LStack；LinkListq；LStackS,T；ElemTypee；4．2主要模块的算法描述4.1函数寻找下一个位置流程图此函数的功能是寻找下一个位置。首先判断di的值，如果di=1，指针x++，退出。如果di=2，指针y++，退出。如果di=3，指针x--，退出。如果di=4，指针y--，退出。如果di为其它值，则直接退出。见图4.1。YNYNYYNNdi=1di=2di=3di=4Break；指针x自增；Break；指针y自增；Break；指针x自减；Break；指针y自减；Break；开始结束图4.1函数寻找下

7、一个位置流程图154.2函数销毁栈流程图此函数的功能是销毁栈，首先建立单链表q，判断top指针是否为空，若为空则释放s的空间，否则出栈，直到top指针为空，释放s的空间。见图4.2。YNLinkListq；判断栈的top释放栈s的空间；出栈；开始结束图4.2函数销毁栈流程图4.3函数出栈流程图此函数的功能是出栈。首先建立单链表q，如果栈s为空则返回0，若栈s不为空，则出栈，修改指针。返回1。见图4.3。YNLinkListq；栈s为空出栈；Return1；Return0；开始结束图4.3函数出栈流程图154.4函数入栈流程图此函数的功能是入栈。首先在链表中生成

8、结点p，判断p是否为空。若为空则返回0