数据结构与算法课程设计 城市公共交通最短线路.docx

《数据结构与算法课程设计 城市公共交通最短线路.docx》由会员分享，可在线阅读，更多相关《数据结构与算法课程设计 城市公共交通最短线路.docx（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构与算法课程设计 城市公共交通最短线路 数据结构与算法 课程设计 一、问题描述及设计目的 城市公共交通最短线路，利用邻接矩阵来构建交通节点，邻接矩阵的行列编号即为交通中的节点，有行列决定的数据即为权值 基本的输入信息和条件： 1. 输入总的节点个数，即为交通中的站点数目 本程序中，站点的数目最大值为100。 2. 输入存在的通路，即为弧两个站点之间是联通的 弧的数目是有限制的，数目小于站点数目n*(n-1)/2 3. 输入存在通路的两点，即为两站点 站点编号要小于站点总数目 二、应具备的功能 1. 确定起点的最短路径问题，即已知起始结点，求最短路径的问题。 2. 确定终点的最短路径问题，

2、与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。 3. 确定起点终点的最短路径问题，即已知起点和终点，求两结点之间的最短路径。 三、设计思想、主要算法的实现、基本操作、子程序调用关系 1Dijkstra算法的基本思想 按路径长度递增顺序求最短路径算法。 2Dijkstra 算法的基本步骤 设V0是起始源点，S是已求得最短路径的终点集合。 V-S = 未确定最短路径的顶点的集合，初始时S=V0，长度最短的路径是边数为1且权值最小的路径。 下一条长度最短的路径： V i V - S ，

3、先求出V0到V i中间只经S 中顶点的最短路径； 上述路径中长度最小者即为下一条长度最短的路径； 将所求最短路径的终点加入S 中； 重复直到求出所有终点的最短路径。 3存储结构设计 本系统采用图结构类型（mgraph）存储抽象交通图的信息。其中：各站点间的邻接关系用图的邻接矩阵类型存储；图的顶点个数及边的个数由分量n、e表示，它们是整型数据。 数据结构如下： typedef struct int no; /顶点编号 InfoType info; /顶点其他信息，这里用于存放边的权值 VertexType; /顶点类型 typedef struct /图的定义 int edgesMAXVMAXV

4、; /邻接矩阵 int n,e; /顶点数，弧数 VertexType vexsMAXV; /存放顶点信息 MGraph; /图的邻接矩阵类型 查询站点间的最短路程距离和路径 该功能是查询站点的最短路径，包括距离和线路，有Floyd( )函数实现。 输出邻接矩阵 该功能即输出图的邻接矩阵的值，由函数DispMat(g)实现 4算法设计 分析实现功能的几个主要函数的代码构成和实现方式 （1）.输出邻接矩阵 通过循环嵌套，即双重循环，打印矩阵数据 时间复杂度由站点数n确定T=O(n2) void DispMat(MGraph g) /输出邻接矩阵g int i,j; for (i=0;i(Aik+

5、Akj) Aij=Aik+Akj; pathij=k; printf(n输出需要查找的两个站点:n); printf(起点:);scanf(%3d,&f); while(f=n) printf(该点不存在，请重新输入！n); printf(起点:);scanf(%3d,&f); ; printf(终点:);scanf(%3d,&r); while(r=n) printf(该点不存在，请重新输入！n); printf(终点:);scanf(%3d,&r); ; while(r=f) printf(不能等于起点，请重新输入！n); printf(终点:);scanf(%3d,&r); ; prin

6、tf(n输出最短路径:n); if (Afr=INF) if(f!=r)printf(从%3d到%3d没有路径n,f,r); else printf(从%3d到%3d路径为:,f,r); printf(%3d,f); ppath(path,f,r); printf(%3d,r); printf(t路径长度为:%3dn,Afr); 四、环境和工具、用户手册 1.环境与工具 vc+6.0 2.用户手册 本程序只能对程序原有的结点进行输入查找最短距离等基础功能，不能用于对其它的邻接矩阵的查找操作。 五、详细设计（源程序清单） #include #defineMAXV 100 /最大顶点个数 #def

7、ine INF 32767 /用32767表示 typedef int InfoType; /假设InfoType为int类型 /以下定义邻接矩阵类型 typedef struct i nt no; /顶点编号 InfoType info; /顶点其他信息，这里用于存放边的权值 VertexType; /顶点类型 typedef struct /图的定义 i nt edgesMAXVMAXV; /邻接矩阵 int n,e; /顶点数，弧数 VertexType vexsMAXV; /存放顶点信息 MGraph; /图的邻接矩阵类型 void DispMat(MGraph g) /输出邻接矩阵g

8、 int i,j; for (i=0;i(Aik+Akj) Aij=Aik+Akj; pathij=k; printf(n输出需要查找的两个站点(站点编号为0-13):n); printf(起点:);scanf(%3d,&f); while(f=n) printf(该点不存在，请重新输入！n); printf(起点:);scanf(%3d,&f); ; printf(终点:);scanf(%3d,&r); while(r=n) printf(该点不存在，请重新输入！n); printf(终点:);scanf(%3d,&r); ; while(r=f) printf(不能等于起点，请重新输入！n); printf(终点:);scanf(%3d,&r); printf(n输出最短路径:n);