tg.cpp

c语言实现的全国交通咨询模拟系统

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NULL 0
#define MAXVTXNUM 30      //图中顶点数的最大值

/****************************** <Graph Struct>**********************************/
typedef struct 
{
	int  ivex;			    //起始点号	
	int  jvex;			    //终点号
	char Number[10];        // 车次号
	int  Money;             //费用
	int  StratTime;         //起始时间（秒）
	int  EndTime;           //终止时间（秒）
	int  Time;              //中途时间（秒）
}EdgeType;  				//Edge类型

typedef struct EdgeNode
{
		EdgeType  elem;
		EdgeNode *nextEdge;
}EdgeNode, *EdgePtr;		//边的结点类型，指向边的指针


typedef struct 
{
		char cityName[10];
		int cityNumber;
		EdgePtr firstEdge;   //指向的一条依附该顶点的边的指针
}Vnode;                      //City类型


typedef struct 
{
	Vnode Adjlist[MAXVTXNUM];		 //邻接表
	int vexNum, edgeNum;             //图重的顶点数和边数
	int Flag[MAXVTXNUM];             //0表示已经不存在,1表示存在
}GraphType;                          //图类型

/*****************************************************************************/

/**************************** < Path Struct > ********************************/
typedef struct {
	int vx,vy;
	EdgeType p;
}Edge;

typedef struct {
	Edge edges[MAXVTXNUM];         //路径中边的序列 : edges[i]表示从起点到i的最短路径
	int len;                       //路径中边的数目
}PathType;

/*******************************************************************************/

/***************************   <Time 操作>   ***********************************/

int TimeChange(int hour,int minute) //输入的时间转换
{
	if(minute>60)
	{
		hour=hour+minute/60;
		minute=minute%60;
	}

	if(hour>24)
	{
		hour=hour%24;
	}

	int change= hour*60+minute;
	return change;
}

void PrintTime(int m)       //时间输出(包括起始时间,历经时间)
{
	int hour,minute;
	
	if(m>1440)
	{
		m=m%1440;
	}
	
	hour=m/60;
	minute=m%60;

	printf("%4d时%2d分",hour,minute);
}

int TimeSub(int a, int b)
{
	int c;
	if(a-b<0)
	{
		c=a+1440-b;
	}
	else if(a-b>1440)
	{
		c=(a-b)%1440;
	}
	else
		c=a-b;
	return c;
}

/*******************************************************************************/

/***************************************<GraphType 基本操作>**********************/
void GreateGraph (GraphType &G)
{
	//建立空图,初始化
	int i;
	G.edgeNum=0;
	G.vexNum=0;
	for(i=0;i<MAXVTXNUM;i++)
		G.Flag[i]=0;
}

bool LocateVex(GraphType G, char *name , int &i)
{
	//在图中查找其景点名称和name相同的顶点。若存在则以i返回其在邻接表中的位置
	//如果有返回ture,且i为位置，如果没有返回false

	i=0;
	while(i<MAXVTXNUM)
	{
		if(G.Flag[i]==1&&strcmp(G.Adjlist[i].cityName,name)==0)
		{
			return true;
		}
		i++;
	}

	return false;	
}

bool LocateEdge(GraphType G, int st,int sn,char *number)
{
	//在图中查找起点为st,终点为sn,车次号为number是否存在
	//如果有返回ture,如果没有返回false
	EdgeNode *p;
	p=G.Adjlist[st].firstEdge;
	while(p)
	{
		if(p->elem.jvex==sn&&strcmp(p->elem.Number,number)==0)
			break;
		p=p->nextEdge;
	}
	if(p)
		return true;
	else
		return false;
}

void InsertVex (GraphType &G , char *name)
{	
	//	初始条件：图G存在，v和途中顶点有相同特征
	//	操作结果：在图G中添加新顶点v

	int i;
	for(i=0;i<MAXVTXNUM;i++)
	{
		if(G.Flag[i]!=1)
			break;
	}
	G.Adjlist[i].cityNumber=i;
	strcpy(G.Adjlist[i].cityName,name);
	G.Adjlist[i].firstEdge=NULL;
	G.Flag[i]=1;
	G.vexNum++;
}

void DeleteVex (GraphType &G, int ivex)
{

	int i;
	EdgeNode *pt,*p;
	
	//把所有的ivex出度的路径删除
	pt=G.Adjlist[ivex].firstEdge;

	while(pt)
	{	
		p=pt->nextEdge;
		delete pt;
		pt=p;
		G.edgeNum--;
	}
	pt=G.Adjlist[ivex].firstEdge=NULL;

	//把点ivex标记为不使用
	G.Flag[ivex]=0;
	G.vexNum--;

	//把所有的ivex入度的路径删除
	for(i=0;i<MAXVTXNUM ;i++)
	{
		if(G.Flag[i]==1)
		{
			p=G.Adjlist[i].firstEdge;
			pt=p;
			while(p)
			{
				if(p->elem.jvex==ivex)
				{
					if(p==G.Adjlist[i].firstEdge)
					{
						G.Adjlist[i].firstEdge=p->nextEdge;
						pt=G.Adjlist[i].firstEdge;
					}
					else
						pt->nextEdge=p->nextEdge;	
					delete p;
					p=pt;
					G.edgeNum--;
				}
			
				pt=p;
				if(p)
					p=p->nextEdge;
			}
		}
	}
	
}

void InsertEdge (GraphType &G  ,EdgeType q)//起始站，终点站的编号
{
	//初始条件： 图G存在，v和w是G中两个顶点
	//操作结果： 在G中添加边 (v, w)
	
	EdgeNode *p = new EdgeNode;
	
	p->elem.ivex=q.ivex;
	p->elem.jvex=q.jvex;
	strcpy(p->elem.Number,q.Number);
	p->elem.StratTime=q.StratTime;
	p->elem.EndTime=q.EndTime;
	p->elem.Time=q.Time;
	p->elem.Money=q.Money;
    p->nextEdge=G.Adjlist[q.ivex].firstEdge;
	G.Adjlist[q.ivex].firstEdge=p;

	G.edgeNum++;
}

void DeleteEdge(GraphType &G ,EdgeType q)
{	
	EdgeNode *p,*pt;

	p=G.Adjlist[q.ivex].firstEdge;
	pt=p;

	while(p)
	{
		if(p->elem.jvex==q.jvex&&strcmp(p->elem.Number,q.Number)==0)
		{
			break;
		}
		pt=p;
		p=p->nextEdge;
	}
	if(p==G.Adjlist[q.ivex].firstEdge)
		G.Adjlist[q.ivex].firstEdge=p->nextEdge;
	else
		pt->nextEdge=p->nextEdge;
	delete p;
	G.edgeNum--;
}

bool DistoryGraph (GraphType &G)
{
	//销毁图结构
	int i;
	for(i=0;i<MAXVTXNUM;i++)
	{
		if(G.Flag[i]==1)
			DeleteVex(G,i);
	}
	return true;
}

/*********************************************************************************/


/***************************<PathType 基本操作>********************************/
void InitPath (PathType &pa)
{
	//初始化pa为一条空路径（pa.len=0）
	pa.len=0;
}

void copyPath (PathType &p1,PathType &p2)
{
	//复制路径p1=p2
	int i;
	for(i=0;i<p2.len;i++)
	{
		p1.edges[i].vx=p2.edges[i].vx;
		p1.edges[i].vy=p2.edges[i].vy;
		p1.edges[i].p =p2.edges[i].p;
	}
	p1.len=p2.len;
}

void InsertPath (PathType &pa, int v, int w, EdgeType t)
{
	//在路径pa中插入一条边（v, w）
	pa.edges[pa.len].vx=v;
	pa.edges[pa.len].vy=w;
	pa.edges[pa.len].p=t;
	pa.len++;
}

void SetPath(PathType &pa, int v, int w, EdgeType t)
{
	//设置第一条边使用
	pa.edges[0].vx=v;
	pa.edges[0].vy=w;
	pa.edges[0].p=t;
	pa.len=1;

}

/*******************************************************************************/

/******************< 迪杰斯特拉算法 求取最少钱数和最短时间 >********************/

void GetMoneyLeastPath (GraphType G, int st, int nd, PathType &pathA)     
			//st：起点号，nd：终点号，结果存储在pathA中，所有信息，都有可以使用
{
	//利用迪杰斯特拉算法的基本思想求图G中从顶点st到nd的一条
	//最短路径PathInfo,路径长度pathLength
	//设int dist[MAXVTXNUM];PathType path[MAXVTXNUM];
	int i;
	int dist[MAXVTXNUM];
	bool final[MAXVTXNUM]={false}; 
	PathType path[MAXVTXNUM];
	EdgeNode *p,*q;
	EdgeType t;
	bool found;
	int min=9999,min_i,v,w;
	for(i=0;i<MAXVTXNUM;i++)             //初始化
	{
		dist[i]=9999;
		InitPath(path[i]);
	}
	p=G.Adjlist[st].firstEdge;
	while(p)                            //初始化dist数组，检测依附于起始点的每一条边
	{
		q=p->nextEdge;
		if(p->elem.Money<dist[p->elem.jvex])
		{
			dist[p->elem.jvex]=p->elem.Money;
			t=p->elem;
			SetPath(path[p->elem.jvex],st,p->elem.jvex,t);
		}
		p=q;		
	}
	found= false;
	while(!found)
	{
		//在所有未求得最短路径的顶点求使得dist[i]取最小的i
		for(i=0;i<MAXVTXNUM;i++)
		{
			if(final[i]==false && dist[i]<min)
				min_i=i;
		}

		final[min_i]=true;

		if(min_i==nd) 
			found=true;
		else
		{
			v=min_i;
			p=G.Adjlist[v].firstEdge;
			while(p)
			{
				q=p->nextEdge;
				w=p->elem.jvex;
				if(final[w]==false &&((dist[v]+p->elem.Money)<dist[w]))
				{
					dist[w]=dist[v]+p->elem.Money;
					copyPath(path[w],path[v]);
					InsertPath(path[w],v,w,p->elem);
				}
				p=q;
			} //while(p)
		} //else
	}// while(!found)

	copyPath(pathA,path[nd]);
}


void GetTimeShortestPath (GraphType G, int st, int nd, int n ,PathType &pathA)
{
				//st：起点号，nd：终点号，n：当前时间（秒），结果存储在pathA中，所有信息，都有可以使用
	
	//利用迪杰斯特拉算法的基本思想求图G中从顶点st到nd的一条
	//最短路径PathInfo,路径长度pathLength
	//设int dist[MAXVTXNUM];PathType path[MAXVTXNUM];
	int i;
	int dist[MAXVTXNUM];
	bool final[MAXVTXNUM]={false}; 
	int now[MAXVTXNUM];
	PathType path[MAXVTXNUM];
	EdgeNode *p,*q;
	EdgeType t;
	bool found;
	int min=99999,min_i,v,w,time;
	for(i=0;i<MAXVTXNUM;i++)             //初始化
	{
		dist[i]=99999;
		InitPath(path[i]);
		now[i]=0;
	}
	now[st]=n;

	p=G.Adjlist[st].firstEdge;
	while(p)                            //初始化dist数组，检测依附于起始点的每一条边
	{
		q=p->nextEdge;
		if(p->elem.StratTime<now[st]&&p->elem.EndTime>=now[st])
		{
			time= 1440-TimeSub(p->elem.EndTime,now[st]);
		}
		else
			time= TimeSub(p->elem.EndTime,now[st]);
			

		if(time<dist[p->elem.jvex])
		{
			dist[p->elem.jvex]=time;
			t=p->elem;
			SetPath(path[p->elem.jvex],st,p->elem.jvex,t);
			now[p->elem.jvex]=p->elem.EndTime;
		}
		p=q;		
	}
	found= false;
	while(!found)
	{
		//在所有未求得最短路径的顶点求使得dist[i]取最小的i
		for(i=0;i<MAXVTXNUM;i++)
		{
			if(final[i]==false && dist[i]<min)
				min_i=i;
		}

		final[min_i]=true;

		if(min_i==nd) 
			found=true;
		else
		{
			v=min_i;
			p=G.Adjlist[v].firstEdge;
			while(p)
			{
				q=p->nextEdge;
				w=p->elem.jvex;

				if(final[w]==false &&(dist[v]+TimeSub(p->elem.EndTime,now[v])<dist[w]))
				{
					dist[w]=dist[v]+TimeSub(p->elem.EndTime,now[v]);
					copyPath(path[w],path[v]);
					InsertPath(path[w],v,w,p->elem);
				}
				p=q;
			} //while(p)
		} //else
	}// while(!found)
	copyPath(pathA,path[nd]);
}

/*********************************************************************************/

/******************************* < 数据存取 >*************************************/


bool SaveGraph_T(GraphType G)    //保存火车图信息
{
	FILE *fp;
	int i,j=0;
	char c = '\n';
	EdgeNode *p;
	
	if((fp = fopen("Train.txt","w")) == NULL)
	{
		printf("不能建立文件：data.txt");
		return false;
	}
	fprintf(fp,"%d\n",G.vexNum);
    fprintf(fp,"%d\n",G.edgeNum);
	j=0;
	i=0;
	while(j<G.vexNum)
	{
		fprintf(fp,"%d,%d,%s%c",i,G.Flag[i],G.Adjlist[i].cityName,c);
		if(G.Flag[i]==1)
			j++;
		i++;
	}
	i=0;
	j=0;
	while(j<G.vexNum)
	{
		p = G.Adjlist[i].firstEdge;
		while(p !=NULL)
		{
				fprintf(fp,"%d,%d\n",i,p->elem.jvex);
				fprintf(fp,"%d,%d,%d,%d\n",p->elem.Money,p->elem.StratTime,p->elem.EndTime,p->elem.Time);
				fprintf(fp,"%s%c",p->elem.Number,c);
			p = p->nextEdge;
		}
		if(G.Flag[i]==1)
			j++;
		i++;

	}
	fclose(fp);
	return true;
	
}


bool SaveGraph_P(GraphType G)         //保存飞机图信息
{
	FILE *fp;
	int i,j=0;
	char c = '\n';
	EdgeNode *p;
	
	if((fp = fopen("Plane.txt","w")) == NULL)
	{
		printf("不能建立文件：data.txt");
		return false;
	}
	fprintf(fp,"%d\n",G.vexNum);
    fprintf(fp,"%d\n",G.edgeNum);
	j=0;
	i=0;
	while(j<G.vexNum)
	{
		fprintf(fp,"%d,%d,%s%c",i,G.Flag[i],G.Adjlist[i].cityName,c);
		if(G.Flag[i]==1)
			j++;
		i++;
	}
	i=0;
	j=0;
	while(j<G.vexNum)
	{
		p = G.Adjlist[i].firstEdge;
		while(p !=NULL)
		{
				fprintf(fp,"%d,%d\n",i,p->elem.jvex);
				fprintf(fp,"%d,%d,%d,%d\n",p->elem.Money,p->elem.StratTime,p->elem.EndTime,p->elem.Time);
				fprintf(fp,"%s%c",p->elem.Number,c);
			p = p->nextEdge;
		}
		if(G.Flag[i]==1)
			j++;
		i++;

	}
	fclose(fp);
	return true;
	
}

bool OpenGraph_T(GraphType &G)          //打开火车图
{
	FILE *fp;
	char c='\n';
	int i=0,j=0;
	if((fp = fopen("Train.txt","r")) == NULL)
	{
		return false;
	}
   fscanf(fp,"%d",&G.vexNum);
   fscanf(fp,"%d",&G.edgeNum);

	while(j<G.vexNum) 
	{
		 fscanf(fp,"%d,%d,%s",&G.Adjlist[i].cityNumber,&G.Flag[i],&G.Adjlist[i].cityName);
		 G.Adjlist[i].firstEdge = NULL;
		 if(G.Flag[i]==1)
			 j++;
		 i++;
	 }

	 for(i = 0;i<G.edgeNum;i++)
	 {
		 EdgeNode *p = new EdgeNode ;
		 
		 fscanf(fp,"%d,%d",&p->elem.ivex,&p->elem.jvex);
		 fscanf(fp,"%d,%d,%d,%d",&p->elem.Money,&p->elem.StratTime,&p->elem.EndTime,&p->elem.Time);
		 fscanf(fp,"%s",&p->elem.Number);

		 p->nextEdge=G.Adjlist[p->elem.ivex].firstEdge;
		 G.Adjlist[p->elem.ivex].firstEdge=p;
	 }
	 fclose(fp);
	 return true;
}

bool OpenGraph_P(GraphType &G)     //打开飞机图
{
	FILE *fp;
	char c='\n';
	int i=0,j=0;
	if((fp = fopen("Plane.txt","r")) == NULL)
	{
		return false;
	}
   fscanf(fp,"%d",&G.vexNum);
   fscanf(fp,"%d",&G.edgeNum);

	while(j<G.vexNum) 
	{
		 fscanf(fp,"%d,%d,%s",&G.Adjlist[i].cityNumber,&G.Flag[i],&G.Adjlist[i].cityName);
		 G.Adjlist[i].firstEdge = NULL;
		 if(G.Flag[i]==1)
			 j++;
		 i++;
	 }

	 for(i = 0;i<G.edgeNum;i++)
	 {
		 EdgeNode *p = new EdgeNode ;
		 
		 fscanf(fp,"%d,%d",&p->elem.ivex,&p->elem.jvex);
		 fscanf(fp,"%d,%d,%d,%d",&p->elem.Money,&p->elem.StratTime,&p->elem.EndTime,&p->elem.Time);
		 fscanf(fp,"%s",&p->elem.Number);

		 p->nextEdge=G.Adjlist[p->elem.ivex].firstEdge;
		 G.Adjlist[p->elem.ivex].firstEdge=p;
	 }
	 fclose(fp);
	 return true;
}

/*********************************************************************************/

/*************************<用户录入函数>******************************************/

bool scanf_Vex(GraphType G,int &i)
{
	char name[10];
	scanf("%s",name);
	fflush(stdin);
	if(LocateVex(G,name,i)==true)
		return true;
	else
	{
		printf("该城市不存在！\n");
		return false;
	}
}

bool scanf_Number(GraphType G, int st,int sn,char *number)
{
	scanf("%s",number);
	if(LocateEdge(G,st,sn,number)==true)
		return true;
	else
	{