欢迎来到天天文库
浏览记录
ID:6636513
大小:248.00 KB
页数:18页
时间:2018-01-20
《数据结构课程设计-求解迷宫问题》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
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
此文档下载收益归作者所有