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

3

4、时间复杂度的分析：

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

4

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 #include #include

#define MaxSize 20 //线性表的最大数组空间 #define MaxVertices 20 //景点个数所允许的最大值 #define MaxWeight 1000 //无穷边权值

#include \

#include \#include \

AdjMGraph G;

#include \

void main() {

//初始景点信息 DataType a[]={{“学生第二食堂\学生的主要就餐点\男生宿舍\一共有

八栋\操场\最新的塑胶跑道和人工草坪\,{\物理楼\拥有各种实验器材\博学楼\学生上课集中地\草地\休闲娱乐的好地方\老教\学校最早的教学楼\女生宿舍\一共七栋\小门\可以通往半汤镇\图书馆\藏书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); //构造图

5

menu(); }

// 详细Floyd.h头文件

void Floyd(int cost[][MaxVertices],int n,int weight[][MaxVertices],int path[][MaxVertices]) { //初始化 int i,j,k; for(i=0;iweight[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

6