exp5.c

利用邻接矩阵构造一张欧洲交通图

#include<stdio.h>
#include<string.h>
#define INFINITY 2147483647
#define VNUM 21
typedef struct Arccell
	{
		int stickprice;
		int length;
	}AdjMatrix[VNUM][VNUM];

typedef struct
{
	char Vertex[VNUM][20];
	AdjMatrix arcs;
	int vexnum,arcnum;
}MGraph;
/****************************** 确定结点位置函数 *****************************************/
int LocateVex(char t[],MGraph *G)
{
	int i;
	for(i=0;i<VNUM;i++)
	{
		if(!(strcmp(t,G->Vertex[i])))
			return i;
	}//for
	printf("ERROR\n");return 0;
}//
/******************************** 打印用户所需信息的函数 *************************************/
void print(int Distance[][VNUM],int Path[][VNUM],char T,char name1[],char name2[],MGraph*G)
{
	int i,j,I,J;
	int p=0,temppath[VNUM]={'\0'};
	i=I=LocateVex(name1,G);
	j=J=LocateVex(name2,G);
/*	if(T=='p')
		printf("最优价格是%d\n价格最优路线为:\n",Distance[I][J]);
	else
		printf("最优里程是%d\n里程最优路线为:\n",Distance[I][J]);*/
	printf("%s--->",name1);
	if(Path[I][J]==-1)
		printf("%s\n",name2);
	else if(Path[I][J]==-2)
		printf("这两个城市不可达\n");
	else
	{
		while(Path[i][j]!=-1)
		{
			while(Path[i][j]!=-1)
			{
				j=Path[i][j];
				temppath[p++]=j;
			}
			p--;
			while(p!=-1)
			{
				j=temppath[p];
				printf("%s--->",G->Vertex[j]);
				p--;
			}
			i=j;j=J;p=0;
		}//while
		printf("%s",name2);
		printf("\n");
	}//else

}//print
/*********************************** 初始化网络图 *****************************************/
void InitGraph(MGraph* City)
{
	int i,j;
	City->vexnum=VNUM;
	City->arcnum=0;
	for(i=0;i<VNUM;i++)
		for(j=0;j<20;j++)
			City->Vertex[i][j]='\0';
	for(i=0;i<VNUM;i++)
		for(j=0;j<VNUM;j++)
		{
			if(i==j)
			{
				City->arcs[i][j].stickprice=0;
				City->arcs[i][j].length=0;
			}
			else
			{
				City->arcs[i][j].stickprice=INFINITY;
				City->arcs[i][j].length=INFINITY;

			}
		}
}//InitGraph
/*********************************** 创建城市交通网络图 *************************************/
void CreatGraph(MGraph *G)
{
	FILE *fp1,*fp2;
	int i,j,I,J;
	char temp1[20]={'\0'},temp2[20]={'\0'},c;//临时存储读取的城市名称

	fp1=fopen("text1.txt","r");//judge error
	for(i=0;i<VNUM&&!feof(fp1);i++)
	{
		fgets(G->Vertex[i],20,fp1);
		for(j=0;j<20;j++)
		{
			if(G->Vertex[i][j]=='\n')
				G->Vertex[i][j]='\0';
		}
	}
	fclose(fp1);
	fp2=fopen("text2.txt","r");//judge error 
	while(!feof(fp2))
	{
		c=fgetc(fp2);
		fgets(temp1,20,fp2);
		fgets(temp2,20,fp2);//读取两个城市的名称
		for(i=0;i<20;i++)
		{
			if(temp1[i]=='\n')
				temp1[i]='\0';
			if(temp2[i]=='\n')
				temp2[i]='\0';
		}//消除城市名称最后的回车符
		I=LocateVex(temp1,G);
		J=LocateVex(temp2,G);//确定两个城市在结点向量中的位置
		G->arcnum++;//弧加1
		fscanf(fp2,"%d",&G->arcs[I][J].stickprice);
		fscanf(fp2,"%d",&G->arcs[I][J].length);//读取两个城市间的票价信息和里程信息
	}//while
		fclose(fp2);
}//CreatGraph
/********************************* 弗洛伊德算法 ****************************************/
void ShortestPath_FLOYD(MGraph G,int Path[][VNUM],int Distance[][VNUM],char T)
{
	int u,v,w;//循环控制变量
	switch(T)//根据不同类型作出分支初始化处理
	{
		case 'p':	for(v=0;v<G.vexnum;v++)
						for(w=0;w<G.vexnum;w++)
						{
							Distance[v][w]=G.arcs[v][w].stickprice;
							if(Distance[v][w]<INFINITY)
								Path[v][w]=-1;//
						}//for
						break;
		case 'l':	for(v=0;v<G.vexnum;v++)
						for(w=0;w<G.vexnum;w++)
						{
							Distance[v][w]=G.arcs[v][w].length;
							if(Distance[v][w]<INFINITY)
								Path[v][w]=-1;//
						}//for
						break;
	}//switch  初始化完成
		for(u=0;u<G.vexnum;u++)
			for(v=0;v<G.vexnum;v++)
				for(w=0;w<G.vexnum;w++)
					if((Distance[v][u]!=INFINITY)&&(Distance[u][w]!=INFINITY)&&Distance[v][u]+Distance[u][w]<Distance[v][w])
					{
						Distance[v][w]=Distance[v][u]+Distance[u][w];
						Path[v][w]=u;
					}//if
}//ShortestPath_FLOYD
/************************************* main函数 *******************************************/
void main()
{
	MGraph  City;//定义城市交通网络图
	int i,j;
	char type;//区分最优路径的类型（价格最优型p和里程最优型l）
	int D[VNUM][VNUM]={0};//存储各城市之间的弧信息
	int Path[VNUM][VNUM]={0};//存储各城市间的最优路径信息
	char name1[20]={'\0'}, name2[20]={'\0'};//分别存储始末两个城市的名称
	for(i=0;i<VNUM;i++)
		for(j=0;j<VNUM;j++)
		{
			if(i==j)
			{
				D[i][j]=0;
				Path[i][j]=-1;
			}
			else
			{
				D[i][j]=INFINITY;
				Path[i][j]=-2;
			}
		}//初始化“弧信息”和“最优路径信息”
	InitGraph(&City);//初始化城市交通网络图
	CreatGraph(&City);//构造城市交通网络图
	printf("请你选择最优方式:\n1、按票价最优输入输入p       2、按路程最优输入l\n");
	scanf("%c",&type);//根据用户输入的类型程序作出相应处理
	ShortestPath_FLOYD(City,Path,D,type);//根据“弗洛伊德算法”算出各个城市的最优路径
	getchar();
	printf("输入初始城市\n");//输入初始城市名称
	gets(name1);
	printf("输入目的城市\n");//输入目的城市名称
	gets(name2);
	printf("最优路径是:\n");
	print(D,Path,type,name1,name2,&City);//打印出用户需要的信息
}//main