交通系统设计说明书.doc

文档介绍：中北大学
数据结构
课程设计说明书
 
 
 
学生姓名:
苏国伟 
学号:
1021011826 
学院:
软件学院
专业:
软件开发与测试 
题目:
交通咨询系统设计
指导教师
何志英
 
 
 
 2011年12月20日
(包括系统总体框图及功能描述)
设计内容:
设计一个交通咨询系统,能让旅客咨询从任一个城市定点到另一个城市定点之间的最短路径或最低花费或最少时间等问题。对于不同的咨询要求、可输入城市间的路程或所需时间或所需花费。
设计要求:
。
。
。
。
总体框图:
打印交通图
获得最短路径
查询最短路径
获得最佳路径
查询最短路径
两个城市之间
一个城市到其他城市
交通咨询系统
存储交通图

本设计所采用的数据结构(如:链表、栈、树、图等)
要实现设计要求,首先要定义交通图的存储结构。邻接矩阵是表示图形中顶点之间相邻关系的矩阵。一个图的领接矩阵表示是唯一的。图的邻接矩阵表示,除了需要用一个二维数组存储顶点之间的邻接关系外,通常还需要使用一个具有n个元素的一维数组来存储顶点信息,起中下标为i的元素存储顶点vi的信息。因此,图的邻接矩阵的存储结构可定义如下:
typedef struct{
char vexs[MVNum];//顶点数组,类型假定为char型
int arcs[MVNum][MVNum];//链接矩阵,假定为int型
}MGraph;
功能模块详细设计

由于有向图的邻接矩阵是不对称的,所以只要输入所有有向边及其权值即可,因此,建立一个有向图的算法可设计如下:
void CreateMGraph(MGraph *G,int n,int e)
{//采用邻接矩阵表示法构造有向图G,n,e表示图的当前结点数和边数
int i,j,k,w;
for(i=1;i<=n;i++)//输入顶点信息
G->vexs[i]=(char)i;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
G->arcs[i][j]=Maxint;//初始化邻接矩阵,权值为无限大
printf("输入%d条边的i,j及w: \n",e);
for(k=1;k<=e;k++){//读入e条边,建立邻接矩阵
scanf("%d %d %d",&i,&j,&w);//////////////////顶点i到顶点j的权值w
G->arcs[i][j]=w;//将i和j两点之间的权值赋给arcs[i][j]
}
printf("有向图的存储结构建立完毕!\n");
}

void Dijkstra(MGraph *G,int v1,int n)
{
//用Dijkstra算法求有向图G的v1顶点到其他顶点v的最短路径P[v]及其权D[v]
//设G是有向图的邻接矩阵,若边<i,j>不存在,则G[i][j]=Maxint、*菡枫*
//S[v]为真,当且仅当v∈s,即已求得从v1到v的最短路径
int D2[MVNum],P2[MVNum];
int v,i,w,min;
enum boolean S[MVNum];
for (v=1;v<=n;v++){//初始化S和D
S[v]=FALSE;//置空最短路径终点集
D2[v]=G->arcs[v1][v];//置初始的最短路径值
if(D2[v]<Maxint)
P2[v]=v1;//v1是v的前趋(双亲)
else
P2[v]=0;//v无前趋
}
D2[v1]=0;
S[v1]=TRUE;//S集初始只有源点,源点到源点的距离为0
//开始循环,每次球得v1到某个v顶点的最短路径,并加v到S集中
for(i=2;i<n;i++){//其余n-1个顶点*菡枫*
min=Maxint;
for(w=1;w<=n;w++)
if(!S[w]&&D2[w]<min){
v=w;
min=D2[w];
}//更新当前最短路径及距离
S[v]=TRUE;
for(w=1;w<=n;w++)
if(!S[w]&&(D2[v]+G->arcs[v][w]<D2[w])){
D2[w]=D2[v]+G->arcs[v][w];
P2[w]=v;
}
}
printf("路径长度: 路径\n");
for(i=1;i<=n;i++){
prin