数据结构课程设计.doc

数据结构课程设计模板-交通咨询题目：全国交通咨询 日期：2012.12.12年级：2011 班级：电科2班姓名：左志鹏 学号：110802223 一实习目的 通过实习，了解并初步掌握设计、实现较大系统的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。2 问题描述 在交通网络非常发达的今天，人们出差、旅游或做其他出行时，不仅关心节省交通费用，而且对里程和所需时间等问题也很感兴趣。对于这样一个人们关心的问题，可用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。图中顶点表示城市，边表示城市之间的交通关系。设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到达另外一个城市顶点之间的最短路径（里程）的问题。三功能要求1.交通资讯系统提供用户三种决策方案：一是建立交通网络图的存储结构。二是某个城市到达其余各城市的最短路径。三是实现两个城市之间最短路径的问题。主要目的是给用户提供路径咨询。 2.本系统规定：(1)在程序中输入城市名称时，需输入0到5的城市代号(2)在选择功能是，应输入与所选功能对应的一个整形数据。(3)程序的输出信息主要是：城市代号，某城市到达其余各城市的最短路径，两城市之间最短路径。四各模块的功能void main() 主函数void Dijkstr() 采用迪杰斯特拉算法求从顶点v到其余个顶点的最短路径void DisPath() 由path计算最短路径void Ppath() 输出各条最短路径void Floyd() 采用弗洛伊德算法求所有顶点之间的最短路径void DisPath2() 由path计算最短路径void Ppath2() 输出各条最短路径五各函数算法 迪杰斯特拉算法 void Dijkstra(MGraph g,int v) /求网g的顶点v到其余顶点的最短路径pathv及其带权长度distv for(i=0;ig.n;i+) disti=g.edgesvi; si=0;/初始化s if(g.edgesviINF) pathi=v; else pathi=-1; sv=1;pathv=0; for(i=0;ig.n;i+) / mindis=INF; for(j=0;jg.n;j+) /寻找到dist中最小值以及j值 if(sj=0&distjmindis) u=j; mindis=distj; su=1;for(j=0;jg.n;j+)if(sj=0)if(g.edgesujINF&distu+g.edgesujdistj) /当经过U点的路径与U点到j点的路径之和小于直接从起点到 /达J点的权值时，将U存入path，distj赋予最小值 distj=distu+g.edgesuj;pathj=u; Dispath函数有path函数计算最短路径，搜索最短路径的所有边，输出路径上的起点， 输 出路径上的中间点， 输出路径上的终点。 void Dispath(int dist,int path,int s,int n,int v) for(i=0;in;i+) if(si=1&disti!=INF) printf(从%d到%d的最短路径长度为：%dt路径为： ,v,i,disti); printf(%d,v); Ppath(path,i,v);/调用Ppath函数输出路径上的点 printf(%dn,i); else printf(从%d到%d不存在路径n,v,i); Ppath函数 前向递归查找路径上的顶点，找到起点则返回，找顶点k的前一个顶点，输出 顶点k。 void Ppath(int path,int i,int v) k=pathi; if(k=v) return; Ppath(path,k,v); printf(%d,k); 弗洛伊德函数 设置路径长度A和路径path初值。做k次迭代，每次均试图将顶点K扩充到点钱球得的从i到j的最短路径Pij上，修开路径长度，输出最短路径。void Floyd(MGraph g) int pathMAXVMAXV,AMAXVMAXV; int i,j,k; for(i=0;ig.n;i+) for(j=0;jg.n;j+) Aij=g.edgesij; pathij=-1; for(k=0;kg.n;k+) for(i=0;ig.n;i+) for(j=0;jAik+Akj) Aij=Aik+Akj; pathij=k; Ppath2函数 向前递归查找路径上的顶点，找到了起点则返回，找顶点i的前一个顶点k，找顶点k的前一个顶点j。在path中递归输出从顶点i到顶点j的最短路径void Ppath2(int pathMAXV,int i,int j) int k;k=pathij; if(k=-1)return;Ppath2(path,i,k);printf(%d,k);Ppath2(path,k,j);DisPath2函数 由path计算最短路径，若顶点i和顶点j之间没有边，则输出i到j没有路径，若有边则输出路劲上的起点、中间点和终点。void Dispath2(int AMAXV,int pathMAXV,int n) int i,j; printf(请输入起点和终点(i,j)：); scanf(%d,%d,&i,&j); if(Aij=INF) if(i!=j) printf(从%d到%d没有路径n,i,j);elseprintf(从%d到%d路径为：,i,j); printf(%d,i); Ppath2(path,i,j); printf(%d,j); printf(t路径长度为：%dn,Aij);Main函数 void main()int i,j,z,x;MGraph g;int AMAXV=, ,;/图的信息for(i=0;ig.n;i+)for(j=0;jg.n;j+)g.edgesij=Aij; printf(交通咨询系统n); printf(1-查看系统中的城市代号n); printf(2-一个城市到所有城市的最短路径n); printf(3-任意的两个城市之间的最短路径n); printf(0-退出n); printf(n); printf(请选择：);scanf(%d,&z); while(z!=0) switch(z) case 1: printf(n); printf(n); main(); scanf(%d,&z); break; case 2: printf(请输入城市代号:); scanf(%d,&x); switch(x) case 0: printf(以下是最短路径：n);Dijkstra(g,x);break; case 1: printf(以下是最短路径：n);Dijkstra(g,x);break; case 2: printf(以下是最短路径：n);Dijkstra(g,x);break; case 3: printf(以下是最短路径：n);Dijkstra(g,x);break; case 4: printf(以下是最短路径：n);Dijkstra(g,x);break; case 5: printf(以下是最短路径：n);Dijkstra(g,x);break; default : printf(输入有误，请重新输入n); printf(n); main();/循环查询 printf(n);main(); scanf(%d,&z);break; case 3: Floyd(g);printf(请选择：);printf(n);main(); scanf(%d,&z);break; case 0: exit(-1);break; default: printf(输入有误，请重新输入n); printf(n); main(); 六源代码#include#include#include string.h#define INF 32767#define MAXV 10typedef int InfoType;typedef structchar cityname; int no; InfoType info;VertexType;typedef structint edgesMAXVMAXV;int n,e;VertexType vxsMAXV;MGraph;void Ppath(int path,int i,int v)int k;k=pathi;if(k=v) return;Ppath(path,k,v);printf(%d,k);void Dispath(int dist,int path,int s,int n,int v)int i;for(i=0;in;i+) if(si=1&disti!=INF) printf(从%d到%d的最短路径长度为：%dt路径为：,v,i,disti); printf(%d,v); Ppath(path,i,v); printf(%dn,i);else printf(从%d到%d不存在路径n,v,i);void Dijkstra(MGraph g,int v) int distMAXV,pathMAXV;int sMAXV;int mindis,i,j,u;for(i=0;ig.n;i+) disti=g.edgesvi; si=0; if(g.edgesviINF) pathi=v; else pathi=-1;sv=1;pathv=0;for(i=0;ig.n;i+) mindis=INF; for(j=0;jg.n;j+) if(sj=0&distjmindis) u=j; mindis=distj; su=1;for(j=0;jg.n;j+)if(sj=0)if(g.edgesujINF&distu+g.edgesujdistj)distj=distu+g.edgesuj;pathj=u; Dispath(dist,path,s,g.n,v);void Ppath2(int pathMAXV,int i,int j) int k;k=pathij; if(k=-1)return;Ppath2(path,i,k);printf(%d,k);Ppath2(path,k,j);void Dispath2(int AMAXV,int pathMAXV,int n) int i,j; printf(请输入起点和终点(i,j)：); scanf(%d,%d,&i,&j); if(Aij=INF) if(i!=j) printf(从%d到%d没有路径n,i,j);elseprintf(从%d到%d路径为：,i,j); printf(%d,i); Ppath2(path,i,j); printf(%d,j); printf(t路径长度为：%dn,Aij);void Floyd(MGraph g) int pathMAXVMAXV,AMAXVMAXV; int i,j,k; for(i=0;ig.n;i+) for(j=0;jg.n;j+) Aij=g.edgesij; pathij=-1; for(k=0;kg.n;k+) for(i=0;ig.n;i+) for(j=0;jAik+Akj) Aij=Aik+Akj; pathij=k; Dispath2(A,path,g.n); void main()int i,j,z,x;MGraph g;int AMAXV=INF,5,8,7,INF,3,2,5,INF,4,INF,INF,INF,0,8,4,INF,5,INF,9,0,7,INF,5,INF,5,6,0,INF,INF,INF,5,INF,1,4,3,INF,9,6,1,INF,6,2,INF,INF,INF,4,6,INF;g.n=7;g.e=10;for(i=0;ig.n;i+)for(j=0;jg.n;j+)g.edgesij=Aij; printf( 交通咨询系统n); printf(1-查看系统中的城市代号n); printf( 2-一个城市到所有城市的最短路径n); printf(-任意的两个城市之间的最短路径n); printf( 0-退出 n); printf(n); printf(请选择：);scanf(%d,&z); while(z!=0) switch(z) case 1: printf(0北京,1天津,2上海,3广州,4南京,5厦门,6-成都n); printf(n); main(); scanf(%d,&z); break; case 2: printf(请输入城市代号:); scanf(%d,&x); switch(x) case 0: printf(以下是最短路径：n);Dijkstra(g,x);break; case 1: printf(以下是最短路径：n);Dijkstra(g,x);break; case 2: printf(以下是最短路径：n);Dijkstra(g,x);break; case 3: printf(以下是最短路径：n);Dijkstra(g,x);brea