迷宫设计数据结构课程设计报告

1、成都工业学院课程设计报告课程名称数据结构课程设计专周题目迷宫姓 名班 级学 号指导教师设计时间2014-12-16至2013-12-27成都工业学院计算机工程系成都工业学院课程设计(论文)任务书一、课程设计(论文)题目迷宫游戏设计 二、课程设计(论文)工作自 2013 年 12 月 16 日至 2013 年 12 月 27 日。三、课程设计(论文) 地点: 2307 四、课程设计(论文)内容要求：1本课程设计的目的1) 使学生增进对数据结构各理论知识的熟练程度， 2) 加强算法设计的能力，为以后的数据库原理等课程的学习打下良好基础。， 2课程设计的任务及要求 题目一：表达式求值 题目二：迷宫游

2、戏3）课程设计论文编写要求1）详细清晰地描述个人的课程设计工作；2）要按照本模板的规格打印誊写课程报告；3）课设报告包括目录、内容提要、正文、课程设计体会、参考文献、附录等；4）课程报告装订按学校的统一要求完成4）评分标准： 1）完成原理分析：20分； 2）完成设计过程：40分； 3）完成代码分析：20分。4）个人创新工作：20分。学生签名： 年 月 日课程设计(论文)评审意见（1）原理分析 （20分）：优（）、良（）、中（）、一般（）、差（）； （2）设计分析（20分）：优（）、良（）、中（）、一般（）、差（）； （3）程序流程（20分）：优（）、良（）、中（）、一般（）、差（）；（4）代码

3、分析（20分）：优（）、良（）、中（）、一般（）、差（）；（5）个人创新（20分）：优（）、良（）、中（）、一般（）、差（）；（6）格式规范性及考勤是否降等级：是（）、否（）评阅人： 职称： 年 月 日目 录目 录- 1 -正 文- 1 -一、 需求分析- 1 -二、 个人工作- 1 -三、概要设计- 3 -五、程序结果- 11 -课程设计体会- 16 -正 文一、 需求分析 本人选择课程设计题目:与 “校园导游咨询”类似的“南岳衡山导游咨询”.根据本人的了解,现在许多人只要有时间就去旅行:但哪了一张旅游图不知怎样去游.是啊,我本人就产生了一些想法就是设计了此“南岳衡山导游咨询”.为例.来解决

4、此问题. 就想到以下要解决的问题: 1,一个旅游时间要最少,但景点又不能少. 2,此设计的导游咨询系统能可以随时改变就好呀.如增加景点呀,或线路呀等等. 3,但此系统只为 “南岳衡山”是不行的呀,于是增加了重新创一个旅游图. 4,有时又决得,好多游客并不知道此有什么好的景点看. 5,为了满足用可用性高,增加了删除功能.通过以上提的问题去解决:本人想到了要快速解决问题.就要有个好的开头. 从本系统最大的要求看就是 第一个问题提的要求: 一个旅游时间要最少,但景点又不能少.可知:这就是数据结构原理中的 “每个顶点之间的最短路径”问题.要解决此问题就用到了图有知识.到的是无向图还是有向图了,这肯定是

5、无向图呀,我景点之间可没有什么只能去不能回呀.数据存储结构用数组表法,邻接表还是用邻接多重表呀本人经过自己的经验决得还是用邻接表对我有很大的优势,同时邻接表对无向图更好操作:同时数据结构原理中重点介绍了此问题也好用邻接表.做实验用过它.就选无向图邻接表.其它问题就根据数据存储结构的无向图邻接表进行操作处理.还有一点还要提到是:就是这里用到要随时能查询就需要用到数据库.其它数据还没有学,只学了用记事本做数据库吧二、 个人工作 根据 “南岳衡山导游咨询问题” 需求分析 :我提出以下设计过程,我能给用户是什么呀:1,一个是repeat创一个旅游图: 或者是增加景点和线路 2,是为用户查询线路,有什么

6、条件呀,(输入任意两个景点):输出(最短路径)线路图:起点-终点.和最短路径距离 3,输出所有景点. 4,删除所有景点和路线.,我要干什么呀. 1,读取已经保存的一个旅游图: 或者保存正在输入的旅游图, 2,保存增加的景点和线路. 或者是删除景点和线路, 3,根据条件: 求出最短路径(任意两个景点);和最短路径距离 输出(距离最短的)线路图:起点-终点. 4,输出所有景点.,我的方法: 1,先创一个旅游图: 2,求出最短路径(任意两个景点); 3,输出(距离最短的)线路图:起点-终点. 接着:,最后修改: 1,完成读取和保存任务: 2,创造增加景点和线路输入; 3,设计友好界面:三、概要设计

7、1-重创一个旅游图 (流程图1)2-增加旅游景点或线路 (流程图-2)3-查询此旅游图有什么好景点 (流程图-3)4-数据的保存和读取(流程图-4)4-查询你要去的景点 (流程图-5)以下:南岳衡山旅游导图是根据真实图改来的(南岳衡山旅游导图) 四、源程序（关键代码分析） 本人想其它的算法实现很简单,现在本人简要介绍一下本人是怎样实现:查询你要去的景点 查询你要去的景点系统中最重要的算法是求最路径;本人运用Dijkstra提出来的算法,它解决了 “从某个源点到其顶点的最短路径”问题,而现是有于可以很方便的知道这某个源点,所以可以用Dijkstra算法解决求任意两景点之间的距离.算法如下: 以下

8、为Dijkstra算法:void ShortesPath_DIJ(int v)for(int i=0;iG.vexnum;i+) Di=10000;/保存最短距离(两路径之距离不能超过此值) for(i=0;iG.vexnum;i+) Prei=-1;/标志保存被访问的顺序for(i=0;i=0;w=NextAdjVex(v,w)if(!visitedv)Dw=TwoVexPath(v,w);/保存所有的两景点之间的距离Prew=v;/标志所有的Prew为源点/进行初始化Dv=0;visitedv=true;Prev=0;/标志着源点为被访问,到自己的距离为0for(i=1;iG.vexnum

9、;i+)int min=;/假设一个为最小的为初值for(w=0;wG.vexnum;w+)/找最小的距离if(!visitedw)if(Dwmin) v=w;min=Dw;/保存景点和改变min值visitedv=true;/标志被访问的景点/从V出发找到其它没有被访问的距离同是标志其它的景点为Vfor(w=0;wG.vexnum;+w)if(!visitedw&(TwoVexPath(v,w)!=-1)&(min+TwoVexPath(v,w)Dw)Dw=min+TwoVexPath(v,w);Prew=v;/for/for void ShowHengShanLine(int a,int

10、b) int v=a; int mid=b;if(-1=Prea|-1=Premid) couttta旅客注意呀:没有线路去那里endl; return;visit_v(v);cout; SqStack Q;int e; InitStack(Q);while (v!=Premid) e=Premid; Push(Q,e); mid=e;/对b到源点访问路径进行进栈if(!StackEmpty(Q) while(Pop(Q,e) ) visit_v(e); cout;/输出a到b访问的路径 visit_v(b);/ifelse visit_v(b); coutendl;cout最短路径长度为:;

11、coutDbendl;void SeekHengShanPath()if(G.vexnum=0)coutttt 对不起:系统还没有设计旅游图endl;coutendl;coutendl;coutendl; return ;int a,b;VertexType Po1,Po2;cout请输入你要查找的开始景点和终止景点:Po1;cinPo2;a=LocateVex(Po1);b=LocateVex(Po2);if(-1=a|b=-1)/对不存在进行处理 couttt 对不起:系统还没有设计到此景点线路endl; return;coutendl; cout从源点到其余各顶点的最短路径:endl;

12、coutendl;ShortesPath_DIJ(a);ShowHengShanLine(a,b);五、程序结果 看一下数据库存有什么内容呀 1,友好开始界面:可以任意选择所要求的功能:(还有现此时用的时间哦)2,任意的查询要去南岳衡山的景点:如: 神秘山洞 到 水濂洞 轻松一按可以少走数几十里3,可以知道有什么好景点: 轻松一按全知景点:4,用户可以轻松改变本此导游图.5,查询一下是否增加成功呀;哦成功了.6,还有一个最大功能就是实现了任意旅游区处理;你可能不相信这也能成功吧.哪咋就试一下就知道了哦出现了好玩的景点了,你可能还不信吧:这你应该信了吧,好了成功了.哦!刚我们输入景点的可没有什么

13、用呀呀,怎么办, 不要急,不是还有删除功能吗?老方法测试一下: 总算完了吧忘记了还有呀退出呀. 还有呀.看下存取的数据库的记事本:怎么数据库全部为空了呀 哦重设此系统的导游图全部删除了六、参考文献1. 数据结构C+版（第2版） 作者：王红梅，出版社：清华大学出版社 2012年2. 数据结构 作者：严蔚敏，出版社：清华大学出版社 2000 年3. 数据结构实验题集作者：严蔚敏，出版社：清华大学出版社 2000 年课程设计体会在课程设计过程中的个人感想，字数不多于200。（包括 : 课程设计 过程的收获、遇到问题、遇到问题解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在课程设计过程中对数据结构课程的认识等内容） 通过此数据结构课程设计题目为: 南岳衡山导游咨询没有想到此数据结构利用这么广大呀,刚开始时,以为又像高数一样,好多算法不能用到日常生活中,可以解决帮助我们人类所做的事情.而且用方便处理这些问题呀,只要好好学学好数据结构.就可以帮助我们解决常见问题. 在此课程设计过程中遇到好多问题呀,可能还没有学好