数据结构—交通指南系统

南通大学数据结构实验课

实验报告

学 生 姓 名 所 在 院 系 专 业 学 号 指 导 教 师

2013年 12 南通大学月 11 日

交通指南系统

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

for(k=0;k

if(A[i][k]+A[k][j]

A[i][j]=A[i][k]+A[k][j]; } }

（2）算法提示

采用任意两点最短路径的相关算法。

4.算法设计

（1）结点类型： struct ArcCell {

int adj; //存放弧长

bool *info; //是否用过该弧 };

struct _MGraph {

char vexs[20]; //存放站点 ArcCell arcs[20][20]; // int vexnum; int arcnum; };

（2）类定义：

class MGraph //没用私有成员 {

public:

_MGraph mgraph;//

void DestroyGraph(); //析构函数销毁图

int LocateVex (char u); // 返回顶点在图中的位置 bool CreateDN(); //构造有向网 void ShortestPath_FLOYD(Path &P,Distanc &D); };

（3）构造有向网：

bool MGraph::CreateDN()//构造有向网 {

int i,j ,w; char v1, v2;

cout<<\请输入站点个数，直接线路的条数: \

cin>>mgraph.vexnum>>mgraph.arcnum ; cout<<\请输入各站点名: \

for(i = 0;i>mgraph.vexs[i]; }

for(i = 0;i

for(i = 0;i>v1>>v2>>w; int m = LocateVex(v1); int n = LocateVex(v2); mgraph.arcs[m][n].adj = w; // 的权值 }

return true; }

（4）销毁有向图：

void MGraph::DestroyGraph() {

for(int i = 0 ;i

（5）定位点：

int MGraph::LocateVex(char u) {

for(int i = 0 ;i<20;i++) { if(u == mgraph.vexs[i]) {return i;} }

return -1; }

（6）最短路径

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

} }

for(u = 0;u

P[v][w][i] = P[v][u][i]||P[u][w][i];//从v到w的路径经过从v到u和从u到w的所有路径