数据结构课程设计校园导航系统

安徽省巢湖学院计算机与信息工程学院课程设计报告课程名称 数据结构 课题名称 校园导航系统 专业 计算机科学与技术 班级 10计本2班 学号10012097 姓名 联系方式 指导教师20 11 年 12 月 29 日10目 录1、数据结构课程设计任务书11.1、题目11.2、要求12、详细设计12.1、程序中所采用的数据结构及存储结构的说明12.2、算法的设计思想23、调试与测试：23.1、调试方法与步骤：23.2、测试结果的分析与讨论：24、时间复杂度的分析：45、源程序清单和执行结果56、C程序设计总结97、致谢108、参考文献101、数据结构课程设计任务书1.1、题目校园导航问题1.2、要求设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。1）设计校园平面图，在校园景点选10个左右景点。以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。2）为来访客人提供图中任意景点相关信息的查询。3）为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条最短路径。2、详细设计模块功能说明：如函数功能、入口及出口参数说明，函数调用关系描述等；2.1、程序中所采用的数据结构及存储结构的说明（1）图。采用邻接矩阵存储，其中图所用到的结构体为：typedef struct SeqList vertices; /表示图中的顶点int EdgeMaxVerticesMaxVertices; /表示图中的边int numOfEdge; /表示图中边的数目AdjMGraph;（2）景点。用顺序表存储。所用到的结构体为： typedef struct char name20; /顶点名称 int code; /顶点代号 char introduction50; /顶点信息简介DataType; （3）景点之间的连接描述，所用到的结构体为： typedef struct int row; int col; int weight;RowColWeight;用图来存放所提供的所有景点，然后用线性表来存放每一个景点的信息，其中包括景点的名称，代号，信息简介，以及其它的一些信息。这样就将对景点的操作，变成对图中各顶点的操作 。 2.2、算法的设计思想根据题目分析，对于信息查询与修改功能，设计如下：1，输入景点名称2，从线性表头扫描到表尾，if(找到该景点) 输出景点结构体信息else 输出提示信息找不到该顶点实现查找最短路径，设计如下：1， 景点名称2，根据输入的信息找到它们所在的线性表中的位置3，调用Floyd算法找出最短路径4，输出信息3、调试与测试：3.1调试过程中遇到的问题与解决方案： 关于最短路径的输出问题。在进行最短路径输出时，我刚开始时只能正序输出，具体的描述为：比如，我要查寻从东区到东湖的最短路径，那么它能正确输出结果，他的形式为：东区 主楼 西体育馆 隧道 北大门 东湖。但是，当我逆向输出时，得到的结果却有点问题，经过分析调试后，找到了错误的所在。在找最短路径的时候我用的是Floyd算法，在这个算法中有三重循环，形式均为：for(k=0;kn;k+)，它们都是从零开始的，所以在顺序输出时没问题，但是逆序的时候就需要进行一个判断，正序与逆序循环输出是相反的。另外，在做这个题时也还出现过一些其他的小问题，不过都比较容易解决，这里我就不再列出了3.2、测试结果的分析与讨论：（测试要写出测试用例及每个用例结果的的截图） 4、时间复杂度的分析：1，相关信息的查询。在这个操作中允许使用者输入一个景点名称，然后再根据景点名称来或取其相关的信息，这个操作要扫描线性表，其时间复杂度为o(n)，空间复杂度为o(n)；2，最短路径查询。实现这个功能用到了Floyd算法，他用到了一个三重的for()循环，故其时间复杂度为o(n3)，空间复杂度为o(1)；5、源程序清单和执行结果(清单中应有足够的注释)school.cpp /程序源文件AdjMGraph.h /图的相关操作头文件AdjMGraphCreat.h /创建图的头文件SeqList.h /线性表操作头文件Floyd.h /Floyd算法头文件Operation.h /自己所定义的一些操作的头文件Inquiry.h /查询信息包含的头文件/ 详细school.cpp 程序源文件#include #include #include #define MaxSize 20 /线性表的最大数组空间#define MaxVertices 20 /景点个数所允许的最大值#define MaxWeight 1000 /无穷边权值#include Floyd.h #include AdjMGraphCreat.h#include Inquiry.hAdjMGraph G;#include Operation.hvoid main() /初始景点信息 DataType a=“学生第二食堂,10,学生的主要就餐点,男生宿舍,11,一共有八栋,操场,12,最新的塑胶跑道和人工草坪 ,物理楼,13,拥有各种实验器材,博学楼,14,学生上课集中地,草地,15,休闲娱乐的好地方,老教,16,学校最早的教学楼,女生宿舍,17,一共七栋,小门,18,可以通往半汤镇,图书馆,19,藏书50万册; /邻接矩阵的表示RowColWeightrcw=0,1,20,0,2,30,0,3,35,1,0,20,1,3,20,2,0,30,2,3,15,2,4,30,3,0,35,3,1,20,3,2,15,3,4,30,4,2,30,4,3,30,4,5,10,5,4,10,5,6,35,5,8,8,6,5,35,6,7,20,6,8,25,6,9,5,7,6,20,7,8,10,8,5,8,8,6,25,8,7,10,9,6,5;int n=10,e=28; /景点数与边数 Creat(&G,a,rcw,n,e); /构造图 menu();/ 详细Floyd.h头文件void Floyd(int costMaxVertices,int n,int weightMaxVertices,int pathMaxVertices)/初始化int i,j,k;for(i=0;in;i+)for(j=0;jn;j+)weightij=costij;pathij=-1;/n次递推for(k=0;kn;k+)for(i=0;in;i+)for(j=0;jweightik+weightkj)weightij=weightik+weightkj;pathij=k;/详细Inquiry.h 头文件void Information(AdjMGraph G, char scenery)int i;for(i=0;iG.vertices.size;i+)if(strcmp(G.vertices.listi.name,scenery)=0)printf(您输入的景点的名称是： %sn,G.vertices.listi.name);printf(您输入的景点的代码为： %dn,G.vertices.listi.code);printf(您输入的景点的相关信息有： %snn,G.vertices.listi.introduction);break;if(i=G.vertices.size)printf(您所查询的景点不在我们所提供的范围内！nn);void Path(AdjMGraph G,char sceneryname, char sceneryname1)int i,j,k,n,m,count=0;n=G.vertices.size;int weightMaxVerticesMaxVertices,pathMaxVerticesMaxVertices;int valueMaxVertices;for(i=0;i%sn,sceneryname,sceneryname1); else while(m!=-1) valuecount=m;if(j,sceneryname);if(j=0;i-) printf(%s,G.vertices.listvaluei.name); printf(%sn,sceneryname1);else for(i=0;i,G.vertices.listvaluei.name); printf(%sn,sceneryname1);/详细Operation.h头文件void menu();/查询景点信息的函数void Information1()char sceneryname20; printf(请输入您所想要查询的景点的名称： ); scanf(%s,sceneryname); Information(G ,sceneryname);menu();/查询最短路径的函数void Path1()char sceneryname20,sceneryname120;printf(请输入你要查询的两景点的名称： );scanf(%s%s,sceneryname,sceneryname1); Path(G,sceneryname,sceneryname1);menu();printf(n);/菜单void menu()int n;puts(tt*菜单*n);puts(ttt1,相关信息查询);puts(ttt2,最短路径查询);puts(tt*n);printf(请选择您想进行的操作： );scanf(%d,&n);switch(n) case 1: Information1(); break; case 2: Path1();break;另外，还有AdjMGraphCreat.h ，AdjMGraph.h和SeqList.h 由于他们在书上已经出现过了，这里我就不再把他们的源程序清单打印出来了 。6、C程序设计总结本程序在刚开始调试时有许多错误，但在我的努力及同学的帮助下都被一一克服，现在在操作本程序时可根据提示进行相关操作，能正确输出结果。在刚开始的几次调试中曾经出现过不能运行、不能产生十以内随机数字、不能随机出现加减、不会正确输出结果、不能进行循环练习等等问题。经过我的努力及同学的帮助，这些问题得到克服，并且使程序的功能也得到了一定的完善。现在它能对出错的题目发出报警声，并且给出正确答案。最后还能分别输出对错的题数及所得分数。在这次设计过程中，不仅复习课本上所学知识，还通过查资料、问同学学到了课本上没有的知识。从而启发我，要想写好程序，在写好课本知识的同时还需要多读和专业有关的一些书籍，同时还需要多动脑子，尽量把所学的知识综合起来应用，力争写出完美的程序。除此之外，我还得到了一些有用的教训：写程序时必须要细心，不能输错一个字符标点，就连全角半角也得注意。在修改时要有耐心，编译出错后必须逐个错误去改正，绝不能心急浮躁，否则修改之后还会有新的错误。7、致谢能够完成这次课程设计必须感谢C+语言课程老师徐荣泉、袁洪军同学（他帮我修改了几处重要错误，同时启发我完善了该程序的功能）。8、参考文献1.数据结构（C语言版）清华大学出版社，严蔚敏 吴伟民 编著2.C+语言程序设计（第四版）清华大学出版社，郑莉 何江舟 编著3.http: