




已阅读5页,还剩5页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
.数据结构课程实验报告班级:计嵌141姓名:陈志远学号:1413052023交通指南系统1. 问题描述 假设以一个带权有向图表示某一区域的公交线路图,图中顶点代表一些区域中的重要站点,弧代表已有的公交线路,弧上的权表示该线路上的票价(或搭乘所需时间),试设计一个交通指南系统,指导前来咨询者以最低的票价或最少的时间从区域中的某一站点到达另一站点。 2. 基本要求 (1)设计结点和图的存储结构; (2)设计任意两点最短路径方法; (3)输入:图的相关信息以建立公交线路网,以及公交线路网咨询的任意两个站点; (4)输出:两个站点间一条最短的简单路径。 3. 实现提示 (1) 结点和图的存储结构 typedef struct node int no; float wgt; struct node*next; edgenode; typedef struct char vtx; edgenode*link; vexnode; typedef vexnode Graphn; void Floyd(Graph G,float Ann,int pnn) int i,j,k; for(i=0;in;i+) fot(j=0;jn;j+) Aij=Gij; Pij=-1; for(k=0;kn;k+) for(i=0;in;i+) for(j=0;jn;j+) if(Aik+AkjAij) pij=k; Aij=Aik+Akj; (2)算法提示 采用任意两点最短路径的相关算法。 4.源代码#include using namespace std;struct ArcCellint adj; /存放弧长 bool *info; /是否用过该弧;struct _MGraph char vexs20; /存放站点ArcCell arcs2020; /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, v2;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; = false;for(i = 0;imgraph.arcnum;i+) /构造邻接矩阵coutv1v2w;int m = LocateVex(v1);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()delete ; = false;mgraph.vexnum = 0;mgraph.arcnum = 0;int MGraph:LocateVex(char u)for(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的直接距离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和从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
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 阳泉市人民医院嗜铬细胞瘤手术麻醉考核
- 通辽市人民医院神经介入医师资格认证
- 吕梁市中医院临时修复体制作考核
- 2025年热电蒸汽项目节能评估报告(节能专)
- 太原市中医院肾脏病理诊断组长竞聘考核
- 运城市中医院针灸推拿科年度综合能力评估
- 2025儿童医院医疗安全事件分析考核
- 2025年养老产业布局优化可行性研究报告
- 黑河市课件教学课件
- 单立柱广告牌建设合同5篇
- 2025年九省联考新高考 物理试卷(含答案解析)
- 《情感表达》课件 2024-2025七年级艺术美术上册人民教育出版社
- 二次结构阶段危险源清单(房建)
- 山东电力系统调度规程
- Python极客项目编程
- 《无人机航迹规划》课程标准(高职)
- 画法几何及机械制图习题册参考答案完整课件
- 藏文五年级上册课件
- 小学二年级数学奥数植树问题(锯木头剪绳子)课件
- 职业生涯规划书模具设计
- 新生儿亚低温治疗
评论
0/150
提交评论