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

安徽省巢湖学院计算机与信息工程学院课程设计报告课程名称《数据结构》课题名称校园导航系统专业计算机科学与技术班级10计本2班学号********姓名吴宗林联系方式152****6478指导教师江家宝20 11 年12 月29 日目录1、数据结构课程设计任务书 (1)1.1、题目 (1)1.2、要求 (1)2、详细设计 (1)2.1、程序中所采用的数据结构及存储结构的说明 (1)2.2、算法的设计思想 (2)3、调试与测试： (2)3.1、调试方法与步骤： (2)3.2、测试结果的分析与讨论： (2)4、时间复杂度的分析： (4)5、源程序清单和执行结果 (5)6、C程序设计总结 (9)7、致谢 (10)8、参考文献 (10)1、数据结构课程设计任务书1.1、题目校园导航问题1.2、要求设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。

1）设计校园平面图，在校园景点选10个左右景点。

以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。

2）为来访客人提供图中任意景点相关信息的查询。

3）为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条最短路径。

2、详细设计模块功能说明：如函数功能、入口及出口参数说明，函数调用关系描述等；2.1、程序中所采用的数据结构及存储结构的说明（1）图。

采用邻接矩阵存储，其中图所用到的结构体为：typedef struct{SeqList vertices; //表示图中的顶点int Edge[MaxVertices][MaxVertices]; //表示图中的边int numOfEdge; //表示图中边的数目}AdjMGraph;（2）景点。

用顺序表存储。

所用到的结构体为：typedef struct{char name[20]; //顶点名称int code; //顶点代号char introduction[50]; //顶点信息简介}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;k<n;k++)，它们都是从零开始的，所以在顺序输出时没问题，但是逆序的时候就需要进行一个判断，正序与逆序循环输出是相反的。

另外，在做这个题时也还出现过一些其他的小问题，不过都比较容易解决，这里我就不再列出了……3.2、测试结果的分析与讨论：（测试要写出测试用例及每个用例结果的的截图）4、时间复杂度的分析：1，相关信息的查询。

在这个操作中允许使用者输入一个景点名称，然后再根据景点名称来或取其相关的信息，这个操作要扫描线性表，其时间复杂度为o(n)，空间复杂度为o(n)；2，最短路径查询。

实现这个功能用到了Floyd算法，他用到了一个三重的for()循环，故其时间复杂度为o(n^3)，空间复杂度为o(1)；5、源程序清单和执行结果(清单中应有足够的注释)school.cpp //程序源文件AdjMGraph.h //图的相关操作头文件AdjMGraphCreat.h //创建图的头文件SeqList.h //线性表操作头文件Floyd.h //Floyd算法头文件Operation.h //自己所定义的一些操作的头文件Inquiry.h //查询信息包含的头文件// 详细school.cpp 程序源文件#include <stdio.h>#include <string.h>#include <malloc.h>#define MaxSize 20 //线性表的最大数组空间#define MaxVertices 20 //景点个数所允许的最大值#define MaxWeight 1000 //无穷边权值#include "Floyd.h"#include "AdjMGraphCreat.h"#include "Inquiry.h"AdjMGraph G;#include "Operation.h"void 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 cost[][MaxVertices],int n,int weight[][MaxVertices],int path[][MaxVertices]) {//初始化int i,j,k;for(i=0;i<n;i++){for(j=0;j<n;j++){weight[i][j]=cost[i][j];path[i][j]=-1;}}//n次递推for(k=0;k<n;k++){for(i=0;i<n;i++){for(j=0;j<n;j++){if(weight[i][j]>weight[i][k]+weight[k][j]){weight[i][j]=weight[i][k]+weight[k][j];path[i][j]=k;}}}}}//详细Inquiry.h 头文件void Information(AdjMGraph G, char scenery[]){int i;for(i=0;i<G.vertices.size;i++){if(strcmp(G.vertices.list[i].name,scenery)==0){printf("您输入的景点的名称是：%s\n",G.vertices.list[i].name);printf("您输入的景点的代码为：%d\n",G.vertices.list[i].code);printf("您输入的景点的相关信息有：%s\n\n",G.vertices.list[i].introduction);break;}}if(i==G.vertices.size){printf("您所查询的景点不在我们所提供的范围内！\n\n");}}void Path(AdjMGraph G,char sceneryname[], char sceneryname1[]){int i,j,k,n,m,count=0;n=G.vertices.size;int weight[MaxVertices][MaxVertices],path[MaxVertices][MaxVertices];int value[MaxVertices];for(i=0;i<G.vertices.size;i++){if(strcmp(G.vertices.list[i].name,sceneryname)==0){j=i;}if(strcmp(G.vertices.list[i].name,sceneryname1)==0){k=i;}}Floyd(G.Edge,n,weight,path);m=path[j][k];printf("最短路径为：%d\n",weight[j][k]);if(m==-1){printf("从%s 点到%s 景点的最短路径为：\n",sceneryname,sceneryname1);printf("%s ——>%s\n",sceneryname,sceneryname1);}else{while(m!=-1){value[count]=m;if(j<k) k=m;else j=m;m=path[j][k];count++;}printf("从%s 点到%s 景点的最短路径为：\n",sceneryname,sceneryname1);printf("%s——>",sceneryname);if(j<k){for(i=count-1;i>=0;i--){printf("%s——>",G.vertices.list[value[i]].name);}printf("%s\n",sceneryname1);}else{for(i=0;i<count;i++){printf("%s——>",G.vertices.list[value[i]].name);}printf("%s\n",sceneryname1);}}}//详细Operation.h头文件void menu();//查询景点信息的函数void Information1(){char sceneryname[20];printf("请输入您所想要查询的景点的名称：");scanf("%s",sceneryname);Information(G ,sceneryname);menu();}//查询最短路径的函数void Path1(){char sceneryname[20],sceneryname1[20];printf("请输入你要查询的两景点的名称：");scanf("%s%s",sceneryname,sceneryname1);Path(G,sceneryname,sceneryname1);menu();printf("\n");}//菜单void menu(){int n;puts("\t\t****************菜单**********************\n");puts("\t\t\t1,相关信息查询");puts("\t\t\t2,最短路径查询");puts("\t\t*******************************************\n");printf("请选择您想进行的操作：");scanf("%d",&n);switch(n){case 1:{Information1();break;}case 2:{Path1();break;}}}另外，还有AdjMGraphCreat.h ，AdjMGraph.h和SeqList.h 由于他们在书上已经出现过了，这里我就不再把他们的源程序清单打印出来了。