DOC《一.引言 ：》

一.

引言 : 校园导游咨询 任务:设计一个校园导游程序,为来访的客人提供各种信息查询服务. 要求: 1设计华东交通大学的校园平面图,所含景点不少于10个.以图中顶点表示校内各景点,存放景点名称、代号、简介等信息;

以边表示路径,存放路径长度等相关信息. 2为来访客人提供图中任意景点相关信息的查询. 3为来访客人提供图中任意景点的问路查询,即查询任意两个景点之间的一条最短的简单路径. . 二.内容简介 1.目的 为配合《数据结构》课程的教学,实现各种算法,使学生能更深刻地领会《数据结构》这门课程的重要性,并可练习程序设计, 特开设此课程设计. 2.结构设计 【课程描述】 本程序是华东交通大学的校园导游问路程序,是为来访的客人提供景点查询服务,找出景点之间的最短路径. 选取华东交通大学11个具有代表性的景点,抽象成一个无向带权图.以图中顶点表示景点,边上的权值表示两景点之间的距离. 程序根据客人输入的景点代号,找出景点之间最短路径. 【数据结构】 构造一个无向图G并用邻接矩阵来存储. 利用迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径用二维数组p[i][]来记录,最短路径长度就用一维数组d[i]存放;

i的范围:0~20. 一维数组have[]是用来记录最短路径出现顶点的顺序. 根据起点和终点输出最短路径和路径长度. 【时间复杂度】因为主要用迪杰斯特拉算法设计,所以总的时间复杂度为O(N?) 3.流程图 4.源程序 /*求任意两点间距离的源程序*/ #include #include #define INFINITY

1000 #define MAX_V

20 typedef struct ArcCell{ int adj;

}ArcCell,AdjMtrix[MAX_V][MAX_V];

typedef struct{ int vexs[MAX_V];

AdjMtrix arcs;

int vexnum,arcnum;

}MGraph;

int have[20];

void Create(MGraph &G)构造无向图*/ int i,j,k,v1[15]={1,2,3,3,7,7,9,8,1,4,4,10,5,5,6},v2[15]={2,3,5,7,9,6,8,11,4,5,10,11,10,6,11}, w[15]={20,50,32,60,33,60,88,150,52,70,210,90,30,35,200};

G.vexnum=11;

G.arcnum=15;

for(i=0;

i