数据结构实验报告-交通指南

数据结构课程实验报告班级:计嵌 141姓名:陈志远学号:1413052025交通指南系统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 Graph[n]; void Floyd(Graph G,float A[n][n],int p[n][n]) { int i,j,k; for(i=0;iusing namespace std;struct ArcCell{int adj; //存放弧长 bool *info; //就是否用过该弧};struct _MGraph{ char vexs[20]; //存放站点ArcCell arcs[20][20]; //int vexnum;int arcnum;};typedef int Path[20][20][20]; typedef int Distanc[20][20]; 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;cout<<"请输入站点个数,直接可达线路得条数: ";cin>>mgraph、vexnum>>mgraph、arcnum ;cout<<"\n 请输入各站点名: ";for(i = 0;i>mgraph、vexs[i];}for(i = 0;i