控制台编程

开发平台：
C/C++

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[]=".\trainGraph.dat";
	if((f=fopen(filename,"r"))==NULL)
	{
		printf("can not open file to read(fscanf):%sn",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));
		if(pa.length >0)	insert_path(l,pa);
	}
	fclose(f);
	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,%dn",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 =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]='';
	}
}
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 nd)
{
	//将路径转换为城市名称的序列
	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("%sn",city_name);
	}
	PR("%sn",l.adj_list [nd].city_name);	
	get_city(l,pa.path[pa.len-1].vy ,city_name);
	strcpy(citys->citys[m] ,city_name);
	citys->num =m;
}
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]=='')
		{
			if(temp>dist[i])
			{
				min=i;
				temp=dist[i];
			}
		}
	}//end for
	if(min!=-1)
	{
//		PR("求dist[]中的最小边 min:%dn",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]=='')&&((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("从 %s 到 %s 的最短路径是:n",g.adj_list [st].city_name ,g.adj_list [nd].city_name );
	out_path(g,path[nd],&ss,nd);
	PR("总路径长度 :%d 公里n",dist[nd]);
}

						