traingraph.c

全国旅游交通查询

#include"train.h"

status creat_graph(graph_country *l)
{
	FILE *f;
	int n;
	int i=0,k=0;
//	path_node *no;
	path pa;
	char filename[]="f:\\trainGraph.txt";
	if((f=fopen(filename,"r"))==NULL)
	{
		printf("can not open file to read(fscanf):%s\n",filename);
		return ERROR;
	}
//	init_graph(l);
//	fscanf(f,"%d%d",&(l->city_num),&(l->path_num ));
	for (i=0;i<l->city_num ;i++)
	{
		fscanf(f,"%s",l->adj_list[i].city_name );
		insert_city(l,l->adj_list[i].city_name,i );
	}
	for (k=0;k<l->path_num ;k++)
	{
		n=fscanf(f,"%d%d%d",&(pa.ivex),&(pa.jvex) ,&(pa.length));
//		PR("pa.length :%d\n",pa.length);

		if(pa.length >0)	insert_path(l,pa);
	}
	fclose(f);
	/*for (i=0;i<MAXSIZE;i++)
	{
		for (no=l->adj_list [i].firsh_path ->i_link ;no->i_link !=NULL;no=no->i_link )
			PR("%s",l->adj_list [no->pa.ivex ].city_name );
		PR("\n");
	
	}*/
	return OK;
}
status init_graph(graph_country *l)
{
	int i=0;
/*	l=(graph_country*)malloc(sizeof(graph_country));
	if(l==NULL)
	{
		exit(0);
	}*/
	for (i=0;i<MAXSIZE;i++)
	{
		l->adj_list [i].firsh_path=NULL;
//		l->adj_list [i].firsh_path->i_link  =NULL;
//		l->adj_list [i].firsh_path->j_link =NULL;
	}
	l->city_num =25;
	l->path_num =30;
	return OK;
}

status insert_city(graph_country *l,char *city_name,int i)
{
	strcpy(l->adj_list[i].city_name ,city_name);
//	PR("insert %s,%d\n",city_name,i);
	return OK;
}

status insert_path(graph_country *l,path pa)
{
	path_node_p q;
	q=(path_node_p)malloc(sizeof(path_node));
	if(q==NULL)
	{
		exit(0);
	}
	q->pa .ivex =pa.ivex ;
	q->pa .jvex =pa.jvex ;
	q->pa .length =pa.length ;
/*	q->i_link=NULL;
//	q->j_link =NULL;
	q->i_link =l->adj_list [pa.ivex ].firsh_path  ;
	l->adj_list [pa.ivex ].firsh_path  =q;
	q->j_link =l->adj_list [pa.jvex ].firsh_path  ;
	l->adj_list [pa.jvex ].firsh_path  =q;*/
	q->i_link =l->adj_list [pa.ivex ].firsh_path ;
	q->j_link =l->adj_list [pa.jvex ].firsh_path  ;
	l->adj_list [pa.ivex ].firsh_path =l->adj_list [pa.jvex ].firsh_path =q;
	return OK;
}

void init_p(path_city *pa)
{
	//初始化为一条空路径
	pa->len =0;
}

void init_set(p_city *p)
{
	int i;
	p->num =0;
	for(i=0;i<MAXSIZE;i++)
	{
		p->citys[i][0]='\0';
	}
}

void copy_path(path_city *pa1,path_city *pa2)
{
	//复制路径
	int i;
	for (i=0;i<pa2->len ;i++)
	{
		pa1->path [i].vx =pa2->path [i].vx ;
		pa1->path [i].vy =pa2->path [i].vy ;
	}
	pa1->len =pa2->len ;
}

void insert_p(path_city *pa,int v,int w)
{
	//在pa中插入一条边(v,w)
	pa->path [pa->len ].vx =v;
	pa->path [pa->len ].vy =w;
	pa->len ++;
//	PR("insert (%d,%d)\n",v,w);
}

void out_path(graph_country l,path_city pa,p_city *citys)
{
	//将路径转换为城市名称的序列
	int m=0,i;
	char city_name[9];

	for(i=0;i<pa.len ;i++)
	{
		get_city(l,pa.path [i].vx ,city_name);
		strcpy(citys->citys[m++], city_name);
		PR("%s\n",city_name);
	}
//	PR("%s\n",city_name);
	
	get_city(l,pa.path[pa.len-1].vy ,city_name);
//	PR("pa.len:%d\n",pa.len );
	strcpy(citys->citys[m] ,city_name);
	citys->num =m;
//	PR("//将路径转换为城市名称的序列完成\n");
}

void get_city(graph_country l,int i, char *city_name)
{
	//以city_name返回邻接多重表中序号为i顶点的城市名(l.adj_list [i].city_name )
	strcpy(city_name,l.adj_list [i].city_name );
}

void putin_set(char *city_name,p_city *p,int st)
{
	strcpy(p->citys [st],city_name);
	p->num ++;
}
	
path_node *first_path(graph_country l,int vi)
{
	//返回图中依附于顶点的第一条这的指针:l.adj_list [vi].firsh_path
	path_node *p;
	p=l.adj_list [vi].firsh_path ;
	return p;
}

path_node *next_path(graph_country g,int vi,path_node p,int *vj,path_node *q)
{
	//以vj返回图g中依附于顶点vi的一条边(由指针p所指)的另一端点;
	//以q返回图中依附于顶点vi且相对于指针p所指边的下一条边
	if(p.pa.ivex ==vi)
	{
		q=p.i_link ;
		*vj=p.pa .jvex ;
	}
	else 
	{
		q=p.j_link ;
		*vj=p.pa .ivex ;
	}
	return q;
}

int minnal(int *dist,p_city ss)
{
	//求dist[]中的最小边
	int min=-1,i,temp;
	temp =maxint;
	for(i=0;i<MAXSIZE;i++)
	{
		if(ss.citys [i][0]=='\0')
		{
			if(temp>dist[i])
			{
				min=i;
				temp=dist[i];
			}
		}
	}//end for
	if(min!=-1)
	{
//		PR("求dist[]中的最小边 min:%d\n",min);
		return min;
	}
	else	
	{
		PR("求最小边时发生错误!\n");
		return -1;
	}
}

void shortest_path(graph_country g,int st,int nd,int *pathlength,p_city *path_info)
{
	//利用迪杰斯特拉算法的基本思想求图g中从顶点st到顶点nd的一条最短路径
	//最短路径path_info及其路径长度path_lenth
	int dist[MAXSIZE];
	int i=0,v,w;
	path_node  q;
	int found,min;
	p_city ss;
	int adjvex;
	path_node *p,*qq;
	path_city path[MAXSIZE];
	for (i=0;i<g.city_num ;i++)
	{
		dist[i]=maxint;
		init_p(&path[i]);
	}
	p=first_path(g,st);
	while(p!=NULL)//初始化dist数组,检测依附于起始边的每一条边
	{
		qq=next_path(g,st,*p,&adjvex,&q);
		dist[adjvex]=p->pa.length ;
		insert_p(&path[adjvex],st,adjvex);
		p=qq;
	}
	found =FALSE;
	init_set(&ss);
	putin_set(g.adj_list[st].city_name ,&ss,st);
	while(!found)
	{
		min=minnal(dist,ss);
			//在所有尚未求得最短路径的顶点中求使dist[i]取小值的i值
		if(min==nd)		found= TRUE;
		else 
		{
			v=min;
			putin_set(g.adj_list[v].city_name,&ss,v);
			p=first_path(g,v);
			while(p!=NULL)//检测依附于v的每一条尚未访问的边
			{
				qq=next_path(g,v,*p,&w,qq);
				if((ss.citys [w][0]=='\0')&&((dist[v]+p->pa .length )<dist[w]))
				{
					dist[w]=dist[v]+p->pa.length ;
					copy_path(&path[w],&path[v]);
					insert_p(&path[w],v,w);
				}
				p=qq;
			}//while(p!=NULL)
		}//else
	}//while(!found)
	pathlength=&dist[nd];
	PR("总路径长度 :%d\n",dist[nd]);
	out_path(g,path[nd],&ss);
}