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

数据结构与算法课程设计一、问题描述及设计目的城市公共交通最短线路，利用邻接矩阵来构建交通节点，邻接矩 阵的行列编号即为交通中的节点，有行列决定的数据即为权值 基本的输入信息和条件：1. 输入总的节点个数，即为交通中的站点数目本程序中，站点的数目最大值为100。2. 输入存在的通路，即为弧两个站点之间是联通的弧的数目是有限制的，数目小于站点数目n*(n-1)/23. 输入存在通路的两点，即为两站点站点编号要小于站点总数目二、应具备的功能1. 确定起点的最短路径问题，即已知起始结点，求最短路径的问题。2. 确定终点的最短路径问题，与确定起点的问题相反，该问题是已 知终结结点，求最短路径的问题。在无向图中该问题与确定起点的 问题完全等同，在有向图中该问题等同于把所有路径方向反转的确 定起点的问题。3. 确定起点终点的最短路径问题，即已知起点和终点，求两结点之 间的最短路径。二、设计思想、主要算法的实现、基本操作、子程序调 用关系1. Dijkstra算法的基本思想按路径长度递增顺序求最短路径算法。2. Dijkstra算法的基本步骤设V0是起始源点，S是已求得最短路径的终点集合。V-S =未确定最短路径的顶点的集合，初始时S=V0,长度最短的路径是边数为1且权值最小的路径。下一条长度最短的路径： V V - S，先求出V0到V.中间只经S中顶点的最短路径；i0i 上述路径中长度最小者即为下一条长度最短的路径;将所求最短路径的终点加入S中；重复直到求出所有终点的最短路径。3 存储结构设计本系统采用图结构类型（mgraph）存储抽象交通图的信息。其中: 各站点间的邻接关系用图的邻接矩阵类型存储；图的顶点个数及边的 个数由分量n、e表示，它们是整型数据。数据结构如下：typedef struetint no;/顶点编号InfoType info;/顶点其他信息，这里用于存放边的权值 VertexType;/顶点类型typedef struet/图的定义 int edgesMAXVMAXV; /邻接矩阵int n,e;/顶点数，弧数Ver texType vexsMAXV;/存放顶点信息 MGraph;/图的邻接矩阵类型查询站点间的最短路程距离和路径该功能是查询站点的最短路径，包括距离和线路，有Floyd()函数 实现。输出邻接矩阵该功能即输出图的邻接矩阵的值，由函数DispMa t(g)实现4. 算法设计分析实现功能的几个主要函数的代码构成和实现方式(1) .输出邻接矩阵通过循环嵌套，即双重循环，打印矩阵数据时间复杂度由站点数n确定T=0(f2)void DispMat(MGraph g)/输出邻接矩阵 gint i,j;for (i=0;ig.n;i+)for (j=0;jg.n;j+)if (g.edgesij=INF)prin tf(%3s,g);/表示两站点间不可达elsepri ntf (%3d,g.edgesij);printf (n)；(2) .求最短路线通过自递归，逐个输出最短路径所经过的站点编号Ppath()函数在path中递归输出从站点i到站点j的最短路径void ppa th(in t pat hMAXV,in t i,int j) / 输入各条最短路 经int k;k二pa thij;if (k=T) retu rn;ppa th(pa th,i,k);/递归prin tf (%3d,k);/输出站点编号ppa th(pa th,k,j);(3) .求最短路线的距离Path二维数组保存最短路径，它与当前的迭代的次数有关。求Aij时，pathij存放从顶点i到j的中间编号大于k的最 短路径上前一个结点的编号。在算法结束时，有二维数组path的值追溯，可以得到从i到j的最短路径，若pat hij=-l.则没有中间站 点。void Floyd(MGraph g)/弗洛伊德算法从每对顶点之间的最短路径int AMAXVMAXV,pa thMAXVMAXV;int i,j,k,f,r,n二g.n;for (i=0;in;i+)/给 A 数组置初值for (j=0;jn;j+)Aij二g.edgesij;pat hij=T;for (k=0;kn;k+)/计算 Akfor (i=0;in;i+)for (j=0;jn;j+)if (Aij(Aik+Akj)Aij二Aik+Akj;pat hij=k;printf （n输出需要查找的两个站点：n）;pri ntf（起点:）；scanf（%3d，&f）; while（f=n）printf （该点不存在，请重新输入！ n）;pri ntf（起点:）;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）;if （Afr=INF） if（f!=r）printf（从3d 到3d 没有路径n,f,r）;elseprintf（从34 至到%3d 路径为：，f,r）;pri ntf （%3d,f）;ppa th（pa th,f,r）;pri ntf （%3d,r）;printf（t 路径长度为:3dn,Afr）;四、环境和工具、用户手册1环境与工具vc+6.02.用户手册本程序只能对程序原有的结点进行输入查找最短距离等基础功能, 不能用于对其它的邻接矩阵的查找操作。五、详细设计（源程序清单）#include #defineMAXV 100最大顶点个数#define INF 32767/用32767表示8typedef int InfoType;以下定义邻接矩阵类型假设InfoType为int类型typedef struct int no;顶点编号InfoType info;顶点其他信息，这里用于存放边的权值 VertexType;顶点类型typedef struct图的定义 int edgesMAXVMAXV;邻接矩阵int n,e;顶点数，弧数VertexType vexsMAXV;存放顶点信息 MGraph;图的邻接矩阵类型void DispMat(MGraph g)输出邻接矩阵gint i,j;for (i=0;i14;i+)for (j=0;j14;j+)if (g.edgesij=INF)printf(%3s,Q)；else printf(%3d,g.edgesij);printf(n); void ppath(int pathMAXV,int i,int j) 输入各条最短路经 int k;k=pathij;if (k=-1) return;ppath(path,i,k);printf(%3d,k);ppath(path,k,j);void Floyd(MGraph g)弗洛伊德算法从每对顶点之间的最短路径int AMAXVMAXV,pathMAXVMAXV;int i,j,k,f,r,n=14;for (i=0;in;i+)给A数组置初值for (j=0;jn;j+) Aij=g.edgesij;pathij=-1;for (k=0;kn;k+)计算Akfor (i=0;in;i+)for (j=0;j(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);if (Afr=INF) if(f!=r)printf(从3小到%3d 没有路径n,f,r);elseprintf(从3小到%3d 路径为:,f,r);printf(%3d,f);ppath(path,f,r);printf(%3d,r);printf(t 路径长度为:3dn,Afr);void main()printf(交通网路的邻接矩阵为n);int i,j;MGraph g;intA1414=32767,32767,32767,32767,32767,32767,32767,8,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,6,32767,8,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,7,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,5,32767,7,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,6,32767,32767,9,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,6,32767,8,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,6,32767,32767,6,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,8,32767,32767,5,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,8,7,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,7,6,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,32767,6,32767,32767,32767,32767,32767,32767,1,32767,32767,32767,32767,32767,32767,32767,6,32767,32767,32767,32767,1,32767,32767,32767,32767,32767,32767,9,8,32767,32767,32767,32767,32767,32767,32767,32767;for (i=0;i14;i+)for (j=0;j14;j+)g.edgesij=Aij;DispMat(g);Floyd(g);六、结果分析及算法评价程序主界面及输入起点：& D:vc6.0MSDev98MyProjectssafDebugsaf.exe 交通网路的邻接矩阵为coOOcocoOOOOCO8OOOOcocoOOOOoococoODOOcoco6OO8coODOOcocoOOcocoOOOOcoCOOO7cocoOOOOoococoODOOcocoOD5CO7ODOOcocoOOcoCOOOOOcoCOOOOO6coOO9oococoODOOcocoODOOcoCO6OO8coOOcoCOOOOOcoCOOOOOcoCO6OOoo6coODOOcocoODOOcocoODOOco8OOco5OOOOcoCOOOOOcoCOOOOOoo87OOcocoODOOcocoODOOcocoOOCO76OOcoCOOOOOcoCOOOOOoococoODOO6coODOOcocoOD1cocoOOcoCOOOOO6COOOOOco1OOOOoococoOD98COODOOcocoODOOco输出需要查找的两个詁点（站点编号为T3）: 总点：输入起点终点输出最短路径:总结分析此次算法的编辑过程，使我熟练的掌握了邻接矩阵存储结构的使 用，从另一面了解到迪克斯拉算法，更深刻的意识到清晰的思路能够 使程序简单明了。经过多次的调试与编译，最终程序的运行结果达到 自己的要求。通过课程设计的练习，强化自己对所学知识的掌握及对 问题分析和任务定义的理解，对每到题目作出了相应的逻辑分析和数 据结构的选择，通过对任务的分析，为操作对象定义相应的数据结构, 以过程化程序设计的思想方法为原则划分各个模块，定义数据的抽象 数据类型。通过程序的编译掌握对程序的调试方法及思想，并且让自 己学会使用一些编程技巧。