数据结构课程实验报告班级：计嵌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 Graph[n];void Floyd(Graph G，float A[n][n]，int p[n][n]){ int i，j，k;for(i=0;i<n;i++)fot(j=0;j<n;j++){ A[i][j]=G[i][j];P[i][j]=-1;}for(k=0;k<n;k++)for(i=0;i<n;i++)for(j=0;j<n;j++)if(A[i][k]+A[k][j]<A[i][j]){ p[i][j]=k;A[i][j]=A[i][k]+A[k][j];}}（2）算法提示采用任意两点最短路径的相关算法。
4.源代码#include <iostream>using namespace std;struct ArcCell{int adj; //存放弧长bool *info; //是否用过该弧};struct _MGraph{char vexs[20]; //存放站点ArcCell arcs[20][20]; //<i,j>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.vexnum;i++)//构造顶点向量{cin>>mgraph.vexs[i];}for(i = 0;i<mgraph.vexnum;i++) //初始化邻接矩阵{for(j = 0;j<mgraph.vexnum;j++){if(i==j)mgraph.arcs[i][j].adj = 0;elsemgraph.arcs[i][j].adj = 20000; //infinity;mgraph.arcs[i][j].info = false;}}for(i = 0;i<mgraph.arcnum;i++) //构造邻接矩阵{cout<<"\n请输入其中一条线路的起点站点名,终点站点名,需要时间（分钟）: ";cin>>v1>>v2>>w;int m = LocateVex(v1);int n = LocateVex(v2);mgraph.arcs[m][n].adj = w; // <v1, v2>的权值}return true;}void MGraph::DestroyGraph(){for(int i = 0 ;i<mgraph.vexnum;i++)for(int j = 0;j<mgraph.vexnum;j++){if(mgraph.arcs[i][j].info){delete []mgraph.arcs[i][j].info;mgraph.arcs[i][j].info = false;}}mgraph.vexnum = 0;mgraph.arcnum = 0;}int MGraph::LocateVex(char u){for(int i = 0 ;i<20;i++){if(u == mgraph.vexs[i]){return i;}}return -1;}void MGraph::ShortestPath_FLOYD(Path &P,Distanc &D)//求每对顶点间的最短路径// 用Floyd算法求有向网G中各对顶点v和w之间的最短路径P[v][w]及其带权长度D[v][w]// 若P[v][w][u]为TRUE，则u是从v到w当前求得最短路径上的顶点。
{int u,v,w,i;for(v = 0;v<mgraph.vexnum;v++){for(w = 0;w<mgraph.vexnum;w++){D[v][w] = mgraph.arcs[v][w].adj;// 顶点v到顶点w的直接距离for(u = 0;u<mgraph.vexnum;u++)P[v][w][u] = false; //路径矩阵初值if(D[v][w]<20000) //从v到w有直接路径P[v][w][v] = P[v][w][w] = true;//由v到w的路径经过v和w两点}}for(u = 0;u<mgraph.vexnum;u++){for(v = 0;v<mgraph.vexnum;v++){for(w = 0;w<mgraph.vexnum;w++){if(D[v][u]+D[u][w]<D[v][w])//从v经u到w的一条路径更短{D[v][w] = D[v][u]+D[u][w];// 更新最短距离for(i = 0;i<mgraph.vexnum;i++)P[v][w][i] = P[v][u][i]||P[u][w][i];//从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;cout<<"\n***************欢迎使用交通指南系统**************\n"<<endl;g.CreateDN();cout<<"\n请依次输入您的出发站和目的站站点名称：";cin>>v1>>v2;s=g.LocateVex (v1);t=g.LocateVex (v2);g.ShortestPath_FLOYD(p,d);if(s!=t){int a=s;cout<<"\n由站点"<<g.mgraph.vexs[s]<<"到站点"<<g.mgraph.vexs[t]<<"途中经过站点：";for(k = 0;k<g.mgraph.vexnum;k++)if(p[s][t][k] == 1){ cout<<g.mgraph.vexs[k]<<" ";sum=sum+g.mgraph.arcs[a][k].adj;a=k;}}cout<<"最短时间："<<sum<<"分钟";cout<<"\n\n***************感谢您的使用！*****************"<<endl;cout<<"\n\n***************祝您旅途愉快！*****************"<<endl;g.DestroyGraph();}5.实现（注：文档可能无法思考全面，请浏览后下载，供参考。
可复制、编制，期待你的好评与关注）。