交通咨询系统设计 数据结构

#include
#include
#define MVNum 100 //最大顶点数
#define Maxint 65535 //定义一个最大数，其意义为无穷大
enum boolean{FALSE,TRUE};
typedef char Vertextype;
typedef int Adjmatrix;
typedef struct
{
Vertextype vexs[MVNum]; //顶点数组 类型假定为char型
Adjmatrix arcs[MVNum] [MVNum]; // 邻接矩阵 假定为int型
}MGraph;
typedef struct
{
Vertextype vexs[MVNum]; //顶点数组 类型假定为char型
Adjmatrix arcs[MVNum] [MVNum]; // 邻接矩阵 假定为int型
}HGraph;
typedef struct
{
Vertextype vexs[MVNum]; //顶点数组 类型假定为char型
Adjmatrix arcs[MVNum] [MVNum]; // 邻接矩阵 假定为int型
}GGraph;
int D1[MVNum], p1[MVNum];
int D[MVNum][MVNum],p[MVNum][MVNum];
void pr(int i)
{
switch(i)
{
case 1:printf("北京 ");
break;
case 2:printf("天津 ");
break;
case 3:printf("郑州 ");
break;
case 4:printf("徐州 ");
break;
case 5:printf("西安 ");
break;
case 6:printf("成都 ");
break;
case 7:printf("武汉 ");
break;
case 8:printf("上海 ");
break;
case 9:printf("福州 ");
break;
case 10:printf("南昌 ");
break;
case 11:printf("株洲 ");
break;
case 12:printf("贵阳 ");
break;
case 13:printf("昆明 ");
break;
case 14:printf("广州 ");
break;


}

}
void pri()
{
int i;

printf("城市代号对照表\n");

printf("********************************************************************************");

for(i=1;i<=14;i++)
{
printf("%d.",i);
pr(i);
}
pr(i);
printf("\n");
printf("********************************************************************************");
}
void CreateMGraph(MGraph *G)
{ //采用邻接矩阵表示法构造有向图G，此图为带权距离图
int i,j;
for(i=1;i<=14;i++) //输入顶点信息
G->vexs[i]=(char)i;
for(i=1;i<=14;i++)
{
for(j=1;j<=14;j++)
{
G->arcs[i][j]=Maxint; // 初始化邻接矩阵
}
}
G->arcs[1][2]=G->arcs[2][1]=137;
G->arcs[2][4]=G->arcs[4][2]=674;
G->arcs[1][3]=G->arcs[3][1]=695;
G->arcs[3][4]=G->arcs[4][3]=349;
G->arcs[3][5]=G->arcs[5][3]=511;
G->arcs[5][6]=G->arcs[6][5]=842;
G->arcs[3][7]=G->arcs[7][3]=534;
G->arcs[4][8]=G->arcs[8][4]=651;
G->arcs[6][13]=G->arcs[13][6]=1100;
G->arcs[6][12]=G->arcs[12][6]=967;
G->arcs[7][11]=G->arcs[11][7]=409;
G->arcs[8][10]=G->arcs[10][8]=825;
G->arcs[9][10]=G->arcs[10][9]=622;
G->arcs[10][11]=G->arcs[11][10]=367;
G->arcs[11][12]=G->arcs[12][11]=902;
G->arcs[12][13]=G->arcs[13][12]=639;
G->arcs[11][14]=G->arcs[14][11]=675;
}
void CreateHGraph(HGraph *H)
{ //采用邻接矩阵表示法构造有向图H,此图为带权花费图
int i,j;
for(

i=1;i<=14;i++) //输入顶点信息
H->vexs[i]=(char)i;
for(i=1;i<=14;i++)
{
for(j=1;j<=14;j++)
{
H->arcs[i][j]=Maxint; // 初始化邻接矩阵
}
}
H->arcs[1][2]=H->arcs[2][1]=20;
H->arcs[2][4]=H->arcs[4][2]=93;
H->arcs[1][3]=H->arcs[3][1]=93;
H->arcs[3][4]=H->arcs[4][3]=51;
H->arcs[3][5]=H->arcs[5][3]=72;
H->arcs[5][6]=H->arcs[6][5]=112;
H->arcs[3][7]=H->arcs[7][3]=75;
H->arcs[4][8]=H->arcs[8][4]=91;
H->arcs[6][13]=H->arcs[13][6]=141;
H->arcs[6][12]=H->arcs[12][6]=128;
H->arcs[7][11]=H->arcs[11][7]=62;
H->arcs[8][10]=H->arcs[10][8]=105;
H->arcs[9][10]=H->arcs[10][9]=86;
H->arcs[10][11]=H->arcs[11][10]=53;
H->arcs[11][12]=H->arcs[12][11]=115;
H->arcs[12][13]=H->arcs[13][12]=86;
H->arcs[11][14]=H->arcs[14][11]=91;
}
void CreateGGraph(GGraph *M)
{ //采用邻接矩阵表示法构造有向图M,此图为带权花费图
int i,j;
for(i=1;i<=14;i++) //输入顶点信息
M->vexs[i]=(char)i;
for(i=1;i<=14;i++)
{
for(j=1;j<=14;j++)
{
M->arcs[i][j]=Maxint; // 初始化邻接矩阵
}
}
M->arcs[1][2]=M->arcs[2][1]=1;
M->arcs[2][4]=M->arcs[4][2]=2;
M->arcs[1][3]=M->arcs[3][1]=3;
M->arcs[3][4]=M->arcs[4][3]=4;
M->arcs[3][5]=M->arcs[5][3]=5;
M->arcs[5][6]=M->arcs[6][5]=6;
M->arcs[3][7]=M->arcs[7][3]=7;
M->arcs[4][8]=M->arcs[8][4]=8;
M->arcs[6][13]=M->arcs[13][6]=9;
M->arcs[6][12]=M->arcs[12][6]=10;
M->arcs[7][11]=M->arcs[11][7]=11;
M->arcs[8][10]=M->arcs[10][8]=12;
M->arcs[9][10]=M->arcs[10][9]=13;
M->arcs[10][11]=M->arcs[11][10]=14;
M->arcs[11][12]=M->arcs[12][11]=15;
M->arcs[12][13]=M->arcs[13][12]=16;
M->arcs[11][14]=M->arcs[14][11]=17;
}
//以下是迪杰斯特拉算法
void Dijkstra(MGraph *G, int v1,int n)
{ //用Dijkstra算法求有向网G的v1顶点到其他顶点v的最短路径P[v]及其权D[v]
//设G是有向图的邻接矩阵，若边不存在则G[i][j]=Maxint
//S[v]为真当且仅当v属于S,即已经求得从v1到v的最短路径
int D[MVNum], P2[MVNum];
int v,i,w,min;
enum boolean S[MVNum];
for(v=1;v<=n;v++)
{ // 初始化S和D
S[v]=FALSE; //置空最短路径终点集
D[v]=G->arcs[v1][v]; //置初始的最短路径值
if(D[v]< Maxint)
P2[v]=v1; //v1是前趋双亲
else
P2[v]=0; //v 无前趋
} // End_for
D[v1]=0;S[v1]=TRUE; //S集初始时只有源点 源点到源点的距离为0
//开始循环每次求的V1到某个V顶点的最短路径并加V到S集中
for(i=2;i<=n;i++)//其余n-1个顶点
{
min=Maxint; // 当前所知离v1顶点的最近距离设初值为∞
for(w=1;w<=n;w++) //对所有顶点检查
if(!S[w] && D[w]

{ //找离v1最近的顶点w并将其赋给v距离赋给min
v=w; //在S集之外的离v1最近的顶点序号
min=D[w]; //最近的距离
} //W顶点距离V1顶点更近
S[v]=TRUE; //将v并入S集
for(w=1;w<=n;w++) //更新当前最短路径及距离
if(!S[w]&&(D[v]+G->arcs[v][w]{ //修改D2[w]和p2[w] w 属于 V-S
D[w]=D[v]+G->arcs[v][w]; //更新D2[w]
P2[w]=v;
} //End_if
} //End_for
printf ("路径长度（单位：km） 最短路径\n");
for(i=1;i<=n;i++)
{
printf ("%10d", D[i]);
printf ("%13d", i);v=P2[i];
while(v!=0) {
printf ("<-%d", v);
v=P2[v];
}
printf("\n");
}
printf("\n\n");
}
//以下是弗洛伊德求最短路径算法

void Floyd(MGraph *G, int n)
{
//用Floyd算法求有向网G中各对顶点i和j之间的最短路径
int i, j, k;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(G->arcs[i][j]!=Maxint)
p[i][j]=j; //j是i的后继
else
p[i][j]=0;
D[i][j]=G->arcs[i][j];
}
for(k=1;k<=n;k++) {
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(D[i][k]+D[k][j]{
D[i][j]=D[i][k]+D[k][j]; //修改长度
p[i][j]=p[i][k];
}
}
}
}

}

void Floyd1(HGraph *H, int n)
{
//用Floyd算法求有向网H中各对顶点i和j之间的最小花费
int i, j, k;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(H->arcs[i][j]!=Maxint)
p[i][j]=j; //j是i的后继
else
p[i][j]=0;
D[i][j]=H->arcs[i][j];
}
for(k=1;k<=n;k++) {
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(D[i][k]+D[k][j]{
D[i][j]=D[i][k]+D[k][j]; //修改长度
p[i][j]=p[i][k];
}
}
}
}
}
void Floy2(GGraph *M, int n)
{
//用Floy2算法求有向网G中各对顶点i和j之间的最短时间
int i, j, k;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(M->arcs[i][j]!=Maxint)
p[i][j]=j; //j是i的后继
else
p[i][j]=0;
D[i][j]=M->arcs[i][j];
}
for(k=1;k<=n;k++) {
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(D[i][k]+D[k][j]{
D[i][j]=D[i][k]+D[k][j]; //修改长度
p[i][j]=p[i][k];
}
}
}
}

}
void main()
{
MGraph * G;
HGraph * H;
GGraph * M;
int v, w, k;
int xz=1;
G=(MGraph *)malloc(sizeof(MGraph));
H=(HGraph *)malloc(sizeof(HGraph));
M=(GGraph *)malloc(sizeof(GGraph));
CreateMGraph(G); //建立图的存储结构
CreateHGraph(H);
CreateGGraph(M);
printf("**********************************\n");
printf("* 姓名： *\n");
printf("* 学号： *\n");
printf("**********************************\n\n\n");

whi

le(xz!=0)
{
printf("******求城市之间的最短路径********\n");
printf("**********************************\n");
printf("0.退出\n");
printf("1.求一个城市到所有城市的最短路径\n");
printf("2.求任意的两个城市之间的最短路径\n");
printf("3.求任意的两个城市之间的最小花费\n");
printf("3.求任意的两个城市之间的最小花费时间\n");
printf("**********************************\n");
scanf("%d",&xz);

switch(xz)
{
case 1:
{
pri();
printf("请输入城市起点代号：");
scanf("%d", &v);
Dijkstra(G,v,14); //调用迪杰斯特拉算法
}
break;


case 2:
{
pri();
Floyd(G,14); //调用费洛伊德求最短路径算法
printf("输入城市起点代号和终点代号：");
scanf("%d%d",&v,&w );
k=p[v][w]; //k为起点v的后继顶点
if(k==0)
printf("顶点%d 到 %d 无路径! \n",v,w);
else
{
printf("从顶点%d到%d的最短路径是: %d",v,w,v);
}
while(k!=w)
{
printf("->%d",k); //输出后继顶点
k=p[k][w]; //继续找下一个后继顶点
}
printf("->%d",w); // 输出终点w
printf(" 路径长度:%d\n\n\n",D[v][w]);
} break;


case 3:
{
pri();
Floyd1(H,14); //调用费洛伊德求最小花费算法
printf("输入城市起点代号和终点代号：");
scanf("%d%d",&v,&w );
k=p[v][w]; //k为起点v的后继顶点
if(k==0)
printf("顶点%d 到 %d 无路径! \n",v,w);
else
{
printf("从顶点%d到%d的路径是: %d",v,w,v);
}
while(k!=w)
{
printf("->%d",k); //输出后继顶点
k=p[k][w]; //继续找下一个后继顶点
}
printf("->%d",w); // 输出终点w
printf("\n最小花费（单位：元）：%d\n\n\n",D[v][w]);
}
break;


case 4:
{
pri();
Floy2(M,14); //调用费洛伊德求最时间算法
printf("输入城市起点代号和终点代号：");
scanf("%d%d",&v,&w );
k=p[v][w]; //k为起点v的后继顶点
if(k==0)
printf("顶点%d 到 %d 无路径! \n",v,w);
else
{
printf("从顶点%d到%d的最短时间是: %d",v,w,v);
}
while(k!=w)
{
printf("->%d",k); //输出后继顶点
k=p[k][w]; //继续找下一个后继顶点
}
printf("->%d",w); // 输出终点w
printf(" 最短时间:%d\n\n\n",D[v][w]);
}
break;
}

}

}