交通运输系统.doc

上传人:豆**** 文档编号:33514675 上传时间:2022-08-11 格式:DOC 页数:4 大小:61.50KB
返回 下载 相关 举报
交通运输系统.doc_第1页
第1页 / 共4页
交通运输系统.doc_第2页
第2页 / 共4页
点击查看更多>>
资源描述

《交通运输系统.doc》由会员分享,可在线阅读,更多相关《交通运输系统.doc(4页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、如有侵权,请联系网站删除,仅供学习与交流交通运输系统【精品文档】第 4 页数据结构实验报告交通指南系统题目:假设以一个带权有向图表示某一区域的公交线路网,图中顶点代表一些区域中的重要站点,弧长代表已有的公交线路,弧上的权表示该线路上的票价(或搭乘所需时间),试设计一个交通指南系统,指导前来咨询者以最低的票价或最少的时间从区域中的某一站点到达另一站点。#include using namespace std;struct ArcCellint adj; /存放弧长 bool *info; /是否用过该弧struct _MGraph char vexs20; /存放站点ArcCell arcs20

2、20; /int vexnum;int arcnum;typedef int Path202020; typedef int Distanc2020; class MGraph /没用私有成员public:_MGraph mgraph;/void DestroyGraph(); /析构函数销毁图int LocateVex (char u); / 返回顶点在图中的位置bool CreateDN(); /构造有向网void ShortestPath_FLOYD(Path &P,Distanc &D);bool MGraph:CreateDN()/构造有向网int i,j ,w;char v1, v

3、2;coutmgraph.vexnummgraph.arcnum ;coutn请输入各站点名: ;for(i = 0;imgraph.vexsi;for(i = 0;imgraph.vexnum;i+)/初始化邻接矩阵for(j = 0;jmgraph.vexnum;j+)if(i=j)mgraph.arcsij.adj = 0;elsemgraph.arcsij.adj = 20000; /infinity; mgraph.arcsij.info = false;for(i = 0;imgraph.arcnum;i+) /构造邻接矩阵coutv1v2w;int m = LocateVex(v

4、1);int n = LocateVex(v2);mgraph.arcsmn.adj = w; / 的权值return true; void MGraph:DestroyGraph()for(int i = 0 ;imgraph.vexnum;i+)for(int j = 0;jmgraph.vexnum;j+)if(mgraph.arcsij.info)delete mgraph.arcsij.info;mgraph.arcsij.info = false;mgraph.vexnum = 0;mgraph.arcnum = 0;int MGraph:LocateVex(char u)for(

5、int i = 0 ;i20;i+)if(u = mgraph.vexsi)return i;return -1;void MGraph:ShortestPath_FLOYD(Path &P,Distanc &D)/求每对顶点间的最短路径/ 用Floyd算法求有向网G中各对顶点v和w之间的最短路径Pvw及其带权长度Dvw/ 若Pvwu为TRUE,则u是从v到w当前求得最短路径上的顶点。int u,v,w,i;for(v = 0;vmgraph.vexnum;v+)for(w = 0;wmgraph.vexnum;w+)Dvw = mgraph.arcsvw.adj;/ 顶点v到顶点w的直接距离

6、for(u = 0;umgraph.vexnum;u+)Pvwu = false; /路径矩阵初值if(Dvw20000) /从v到w有直接路径Pvwv = Pvww = true;/由v到w的路径经过v和w两点for(u = 0;umgraph.vexnum;u+)for(v = 0;vmgraph.vexnum;v+)for(w = 0;wmgraph.vexnum;w+)if(Dvu+DuwDvw)/从v经u到w的一条路径更短Dvw = Dvu+Duw;/ 更新最短距离for(i = 0;imgraph.vexnum;i+) Pvwi = Pvui|Puwi;/从v到w的路径经过从v到u

7、和从u到w的所有路径void main()MGraph g;Path p; / 3维数组Distanc d; / 2维数组int s,t,k;char v1,v2;float sum=0;coutn*欢迎使用交通查询系统*nendl;g.CreateDN();coutv1v2;s=g.LocateVex (v1);t=g.LocateVex (v2); g.ShortestPath_FLOYD(p,d); if(s!=t) int a=s;coutn由g.mgraph.vexss到g.mgraph.vexst途中经过:;for(k = 0;kg.mgraph.vexnum;k+)if(pstk = 1)coutg.mgraph.vexsk ;sum=sum+g.mgraph.arcsak.adj;a=k;cout最短线路总长:sum公里;coutnn*祝您旅途愉快!*endl;g.DestroyGraph();

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 教育专区 > 高考资料

本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知淘文阁网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

工信部备案号:黑ICP备15003705号© 2020-2023 www.taowenge.com 淘文阁