欢迎来到天天文库
浏览记录
ID:6789284
大小:249.00 KB
页数:12页
时间:2018-01-25
《数据结构课程设计-校园导航系统》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、安徽省巢湖学院计算机与信息工程学院课程设计报告课程名称《数据结构》课题名称校园导航系统专业计算机科学与技术班级10计本2班学号姓名联系方式指导教师2011年12月29日10目录1、数据结构课程设计任务书11.1、题目11.2、要求12、详细设计12.1、程序中所采用的数据结构及存储结构的说明12.2、算法的设计思想23、调试与测试:23.1、调试方法与步骤:23.2、测试结果的分析与讨论:24、时间复杂度的分析:45、源程序清单和执行结果56、C程序设计总结97、致谢108、参考文献10101、数
2、据结构课程设计任务书1.1、题目校园导航问题1.2、要求设计你的学校的平面图,至少包括10个以上的场所,每两个场所间可以有不同的路,且路长也可能不同,找出从任意场所到达另一场所的最佳路径(最短路径)。1)设计校园平面图,在校园景点选10个左右景点。以图中顶点表示校园内各景点,存放景点名称、代号、简介等信息;以边表示路径,存放路径长度等有关信息。2)为来访客人提供图中任意景点相关信息的查询。3)为来访客人提供任意景点的问路查询,即查询任意两个景点之间的一条最短路径。2、详细设计模块功能说明:如函数功
3、能、入口及出口参数说明,函数调用关系描述等;2.1、程序中所采用的数据结构及存储结构的说明(1)图。采用邻接矩阵存储,其中图所用到的结构体为:typedefstruct{SeqListvertices;//表示图中的顶点intEdge[MaxVertices][MaxVertices];//表示图中的边intnumOfEdge;//表示图中边的数目}AdjMGraph;(2)景点。用顺序表存储。所用到的结构体为:typedefstruct{charname[20];//顶点名称intcode;//
4、顶点代号charintroduction[50];//顶点信息简介}DataType;(3)景点之间的连接描述,所用到的结构体为:typedefstruct{introw;intcol;intweight;10}RowColWeight;用图来存放所提供的所有景点,然后用线性表来存放每一个景点的信息,其中包括景点的名称,代号,信息简介,以及其它的一些信息。这样就将对景点的操作,变成对图中各顶点的操作。2.2、算法的设计思想根据题目分析,对于信息查询与修改功能,设计如下:1,输入景点名称2,从线性表
5、头扫描到表尾,if(找到该景点)输出景点结构体信息else输出提示信息找不到该顶点实现查找最短路径,设计如下:1,景点名称2,根据输入的信息找到它们所在的线性表中的位置3,调用Floyd算法找出最短路径4,输出信息3、调试与测试:3.1调试过程中遇到的问题与解决方案:关于最短路径的输出问题。在进行最短路径输出时,我刚开始时只能正序输出,具体的描述为:比如,我要查寻从东区到东湖的最短路径,那么它能正确输出结果,他的形式为:东区——>主楼——>西体育馆——>隧道——>北大门——>东湖。但是,当我逆向输
6、出时,得到的结果却有点问题,经过分析调试后,找到了错误的所在。在找最短路径的时候我用的是Floyd算法,在这个算法中有三重循环,形式均为:for(k=0;k7、作中允许使用者输入一个景点名称,然后再根据景点名称来或取其相关的信息,这个操作要扫描线性表,其时间复杂度为o(n),空间复杂度为o(n);2,最短路径查询。实现这个功能用到了Floyd算法,他用到了一个三重的for()循环,故其时间复杂度为o(n^3),空间复杂度为o(1);5、源程序清单和执行结果(清单中应有足够的注释)school.cpp//程序源文件AdjMGraph.h//图的相关操作头文件AdjMGraphCreat.h//创建图的头文件SeqList.h//线性表操作头文件Floyd.8、h//Floyd算法头文件Operation.h//自己所定义的一些操作的头文件Inquiry.h//查询信息包含的头文件//详细school.cpp程序源文件#include#include#include#defineMaxSize20//线性表的最大数组空间#defineMaxVertices20//景点个数所允许的最大值#defineMaxWeight1000//无穷边权值#include"Floyd.h"#incl
7、作中允许使用者输入一个景点名称,然后再根据景点名称来或取其相关的信息,这个操作要扫描线性表,其时间复杂度为o(n),空间复杂度为o(n);2,最短路径查询。实现这个功能用到了Floyd算法,他用到了一个三重的for()循环,故其时间复杂度为o(n^3),空间复杂度为o(1);5、源程序清单和执行结果(清单中应有足够的注释)school.cpp//程序源文件AdjMGraph.h//图的相关操作头文件AdjMGraphCreat.h//创建图的头文件SeqList.h//线性表操作头文件Floyd.
8、h//Floyd算法头文件Operation.h//自己所定义的一些操作的头文件Inquiry.h//查询信息包含的头文件//详细school.cpp程序源文件#include#include#include#defineMaxSize20//线性表的最大数组空间#defineMaxVertices20//景点个数所允许的最大值#defineMaxWeight1000//无穷边权值#include"Floyd.h"#incl
此文档下载收益归作者所有