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