jt.cpp

交通咨询的事例程序

	if ( k==1 )
		cout << endl 
			 << "不存在列车车次从"
			 << G.vertices[v0].cityname
			 << "到"
			 << G.vertices[v1].cityname
			 << endl << endl;
	else		
		cout << endl 
			 << "不存在飞机航班从"
			 << G.vertices[v0].cityname
			 << "到"
			 << G.vertices[v1].cityname
			 << endl << endl;
}


//两直达城市之间最少旅行时间和相应路径
void MinTime(infolist arcs,int *time,int *route)
{
	int i,t[2];
	time[0]=arcs.stata[0].arrivetime[0]-arcs.stata[0].begintime[0];
	time[1]=arcs.stata[0].arrivetime[1]-arcs.stata[0].begintime[1];
	if ( time[0]<0 ) time[0]=time[0]+24;
	if(time[1]<0)
	{
		time[0]--;
		time[1]=time[1]+60;
	}
	*route=0;
	for(i=1;i<=arcs.last;i++)
	{
		t[0]=arcs.stata[i].arrivetime[0]-arcs.stata[i].begintime[0];  
		t[1]=arcs.stata[i].arrivetime[1]-arcs.stata[i].begintime[1];	 
		if(t[0]<0) t[0]=t[0]+24;
		if(t[1]<0) 
		{
			t[0]--;
			t[1]=t[1]+60;
		}
		if ( t[0]<time[0]||(t[0]==time[0]&&t[1]<time[1]))
		{
			time[0]=t[0];
			time[1]=t[1];
			*route=i;
		}
	}
}


//时间树处理
void TimeTreeDispose(Node *head,infolist (*arcs)[MAX_VERTEX_NUM])
{
	int n,i,j;
	Node *p;
	LinkQueue Q;
	TimeTree root;
	root=(TimeNode *)malloc(sizeof(TimeNode));
	InitQueue(&Q);
	TTime[0]=INFINITY;
	TTime[1]=INFINITY;
	p=head->next;
	while(p!=NULL)
	{
		EnterQueue(&Q,p->adjvex);
		p=p->next;
	}
	DeleteQueue(&Q,&i);
	root->adjvex=i;
	DeleteQueue(&Q,&j);
	CreateTimeTree(root,i,j,&Q,arcs); 
	for(n=0;n<=(*(*(arcs+i)+j)).last;n++)
	{
		time1[0]=0;
		time1[1]=0;
		time2[0]=root->child[n]->begintime[0];
		time2[1]=root->child[n]->begintime[1];
		time[0]=INFINITY;
		time[1]=INFINITY;
		VisitTimeTree(root->child[n]);
		if ( time[0]<TTime[0]||(time[0]==TTime[0]&&time[1]<TTime[1]) )
		{
			TTime[0]=time[0];
			TTime[1]=time[1];
			p=head->next;
			while( p!=NULL )
			{
				p->route=d[p->adjvex];
				p=p->next;
			}
		}
	}
	DestoryTimeTree(root);
}

//创建时间树
void CreateTimeTree(TimeTree p,int i,int j,LinkQueue *Q,infolist (*arcs)[MAX_VERTEX_NUM])
{
	int n,x,y;
	TimeTree q;
	q=(TimeNode *)malloc(sizeof(TimeNode));
	q->adjvex=j;
	q->begintime[0]=(*(*(arcs+i)+j)).stata[0].begintime[0];
	q->begintime[1]=(*(*(arcs+i)+j)).stata[0].begintime[1];
	q->arrivetime[0]=(*(*(arcs+i)+j)).stata[0].arrivetime[0];
	q->arrivetime[1]=(*(*(arcs+i)+j)).stata[0].arrivetime[1];
	q->route=0;
	p->child[0]=q;
	for (n=1;n<=(*(*(arcs+i)+j)).last;n++ )
	{
		q=(TimeNode *)malloc(sizeof(TimeNode));
		q->adjvex=j;
		q->begintime[0]=(*(*(arcs+i)+j)).stata[n].begintime[0];
		q->begintime[1]=(*(*(arcs+i)+j)).stata[n].begintime[1];
		q->arrivetime[0]=(*(*(arcs+i)+j)).stata[n].arrivetime[0];
		q->arrivetime[1]=(*(*(arcs+i)+j)).stata[n].arrivetime[1];
		q->route=n;
		p->child[n]=q;
	}
	while(n<MAX_ROUTE_NUM)
	{
		p->child[n]=NULL;
		n++;
	}
	x=j;
	if(!IsEmpty(Q))
	{
		DeleteQueue(Q,&y);
		CreateTimeTree(p->child[0],x,y,Q,arcs);
		for ( n=1;n<=(*(*(arcs+i)+j)).last;n++ )
			CopyTimeTree(p->child[n],p->child[0]);
	}
	else
	{
		for ( n=0; n<MAX_ROUTE_NUM; n++ ) 
			p->child[0]->child[n]=NULL;
		for ( n=1; n<=(*(*(arcs+i)+j)).last; n++ )
			CopyTimeTree(p->child[n],p->child[0]);
	}
}

//复制时间树
void CopyTimeTree(TimeTree p,TimeTree q)
{
	TimeTree r;
	int n=0;
	while(q->child[n]!=NULL)
	{
		r=(TimeNode *)malloc(sizeof(TimeNode));
		r->adjvex=q->child[n]->adjvex;
		r->begintime[0]=q->child[n]->begintime[0];
		r->begintime[1]=q->child[n]->begintime[1];
		r->arrivetime[0]=q->child[n]->arrivetime[0];
		r->arrivetime[1]=q->child[n]->arrivetime[1];
		r->route=q->child[n]->route;
		p->child[n]=r;
		CopyTimeTree(p->child[n],q->child[n]);
		n++;
	}
	while(n<MAX_ROUTE_NUM)
	{
		p->child[n]=NULL;
		n++;
	}
}

//访问时间树界面
void VisitTimeTree(TimeTree p)
{
	int n,x[2],y[2];
	x[0] = time1[0];
	x[1] = time1[1];
	y[0] = time2[0];
	y[1] = time2[1];
	if (p->begintime[0]>time2[0]||(p->begintime[0]==time2[0]&&p->begintime[1]>=time2[1]))
	{
		time1[0] = time1[0]+p->begintime[0]-time2[0];
		time1[1] = time1[1]+p->begintime[1]-time2[1];
		if(time1[1]<0)
		{
			time1[1] = time1[1]+60;
			time1[0]--;
		}
		if ( time1[1]>=60 )
		{
			time1[1] = time1[1]-60;
			time1[0]++;
		}
	}
	else if ( p->begintime[0]<time2[0]||(p->begintime[0]==time2[0]&&p->begintime[1]<time2[1]) )
	{
		time1[0]=time1[0]+p->begintime[0]-time2[0]+24;
		time1[1]=time1[1]+p->begintime[1]-time2[1];
		if ( time1[1]<0 )
		{
			time1[1] = time1[1]+60;
			time1[0]--;
		}
		if ( time1[1]>=60 )
		{
			time1[1] = time1[1]-60;
			time1[0]++;
		}
	}
	if ( p->arrivetime[0]>p->begintime[0]||(p->arrivetime[0]==p->begintime[0]&&p->arrivetime[1]>=p->begintime[1]) )
	{
		time1[0]=time1[0]+p->arrivetime[0]-p->begintime[0];
		time1[1]=time1[1]+p->arrivetime[1]-p->begintime[1];
		if ( time1[1]<0 )
		{
			time1[1]=time1[1]+60;
			time1[0]--;
		}
		if ( time1[1]>=60 )
		{
			time1[1] = time1[1]-60;
			time1[0]++;
		}
	}
	else if ( p->arrivetime[0]<p->begintime[0]||(p->arrivetime[0]==p->begintime[0]&&p->arrivetime[1]<p->begintime[1]) )
	{
		time1[0] = time1[0]+p->arrivetime[0]-p->begintime[0]+24;
		time1[1] = time1[1]+p->arrivetime[1]-p->begintime[1];
		if( time1[1]<0 )
		{
			time1[1] = time1[1]+60;
			time1[0]--;
		}
		if ( time1[1]>=60 )
		{
			time1[1] = time1[1]-60;
			time1[0]++;
		}
	}
	time2[0] = p->arrivetime[0];
	time2[1] = p->arrivetime[1];
	c[p->adjvex] = p->route;
	if( p->child[0]==NULL )
	{
		if( time1[0]<time[0]||(time1[0]==time[0]&&time1[1]<time[1]) )
		{
			time[0] = time1[0];
			time[1] = time1[1];
			for ( n=0;n<MAX_VERTEX_NUM;n++ ) 
				d[n] = c[n];
		}
	}
	else
	{
		n = 0;
		while ( p->child[n]!=NULL )
		{
			VisitTimeTree( p->child[n] );
			n++;
		}
	}
	time1[0] = x[0];
	time1[1] = x[1];
	time2[0] = y[0];
	time2[1] = y[1];
}

//销毁时间树
void DestoryTimeTree(TimeTree p)
{
	if(p!=NULL)
	{
		DestoryTimeTree(p->child[0]);
		DestoryTimeTree(p->child[1]);
		DestoryTimeTree(p->child[2]);
		DestoryTimeTree(p->child[3]);
		DestoryTimeTree(p->child[4]);
		p->child[0] = NULL;
		p->child[1] = NULL;
		p->child[2] = NULL;
		p->child[3] = NULL;
		p->child[4] = NULL;
		free(p);
	}
}

//最少旅行时间处理
void TimeDispose(int k,infolist (*arcs)[MAX_VERTEX_NUM],ALGraph G,int v0,int v1,int (*T)[2],int *final)
{
	int v,w,i,route,m[2];
	Node *p,*q,*r,*s,*t;
	p=(Node *)malloc(G.vexnum*sizeof(Node));
	for(v=0;v<G.vexnum;v++)
	{
		*(final+v)=False;
		MinTime(*(*(arcs+v0)+v),*(T+v),&route);
		p[v].next=NULL;
		if(*(*(T+v)+0)<INFINITY&&*(*(T+v)+1)<INFINITY)
		{
			q=(Node *)malloc(sizeof(Node));
			s=(Node *)malloc(sizeof(Node));
			q->adjvex=v0;
			s->adjvex=v;
			s->route=route;
			p[v].next=q;
			q->next=s;
			s->next=NULL;
		}
	}
	*(*(T+v0)+0)=0;
	*(*(T+v0)+1)=0;
	*(final+v0)=True;
	for(i=1;i<G.vexnum;i++)
	{
		m[0]=INFINITY;
		m[1]=INFINITY;
		v=-1;
		for (w=0;w<G.vexnum;w++)
			if (*(final+w)==False)
				if (*(*(T+w)+0)<m[0]||(*(*(T+w)+0)==m[0]&&*(*(T+w)+1)<m[1]))
				{ 
					v=w;
					m[0]=*(*(T+w)+0);
					m[1]=*(*(T+w)+1);
				}
		if (v==v1)
		{
			q=p[v].next;
			r=q->next;
			cout << endl 
				 << "旅行路线是:"
				 << endl;
			while(r!=NULL)
			{
				if (k==1)
					cout << "乘坐No."
						 << (*(*(arcs+q->adjvex)+r->adjvex)).stata[r->route].number
						 << "列车车次在"
						 << (*(*(arcs+q->adjvex)+r->adjvex)).stata[r->route].begintime[0]
						 << ":"
						 << (*(*(arcs+q->adjvex)+r->adjvex)).stata[r->route].begintime[1]
						 << "从"
						 << G.vertices[q->adjvex].cityname
						 << "到"
						 << G.vertices[r->adjvex].cityname
						 << endl;
				else					
					cout << "乘坐No."
						 << (*(*(arcs+q->adjvex)+r->adjvex)).stata[r->route].number
						 << "飞机航班在"
						 << (*(*(arcs+q->adjvex)+r->adjvex)).stata[r->route].begintime[0]
						 << ":"
						 << (*(*(arcs+q->adjvex)+r->adjvex)).stata[r->route].begintime[1]
						 << "从"
						 << G.vertices[q->adjvex].cityname
						 << "到"
						 << G.vertices[r->adjvex].cityname
						 << endl;
				q = r;
				r = r->next;
			}
			cout << "最少旅行时间是"
				 << m[0] 
				 << ":" 
				 << m[1] 
				 << endl << endl;
			for ( v=0; v<G.vexnum; v++ )
			{
				q = p[v].next;
				while ( q!=NULL )
				{ 
					s = q;
					q = q->next;
					free(s);
				}
				p[v].next = NULL;
			}
			free(p);
			return;
		}
		else if (v!=-1 )
		{
			*(final+v)=True;
			for ( w=0;w<G.vexnum;w++)
				if ( *(final+w)==False&&(*(*(arcs+v)+w)).last>-1 )
				{
					t = p[w].next;
					q = &p[w];
					s = p[v].next;
					while ( s!=NULL )
					{
						r = (Node *)malloc(sizeof(Node));
						r->adjvex = s->adjvex;
						r->route = s->route;
						q->next = r;
						q = r;
						s = s->next;
					}
					r = (Node *)malloc(sizeof(Node));
					r->adjvex = w;
					r->route = route;
					r->next = NULL;
					q->next = r;
					TimeTreeDispose(&p[w],arcs);
					if (*(*(T+w)+0)>TTime[0]||(*(*(T+w)+0)==TTime[0]&&*(*(T+w)+1)>TTime[1]))
					{
						*(*(T+w)+0) = TTime[0];
						*(*(T+w)+1) = TTime[1];
						while ( t!=NULL )
						{
							q = t;
							t = t->next;
							free(q);
						}
					}
					else 
					{
						q = p[w].next;
						while ( q!=NULL )
						{
							r = q;
							q=q->next;
							free(r);
						}
						p[w].next = t;
					}
				}
		}
	}
	for ( v=0; v<G.vexnum; v++ )
	{
		q = p[v].next;
		while ( q!=NULL )
		{
			s = q;
			q = q->next;
			free(s);
		}
		p[v].next = NULL;
	}
	free(p);
	if ( k==1 )
		cout << endl 
			 << "不存在列车车次从" 
			 << G.vertices[v0].cityname 
			 << "到" << G.vertices[v1].cityname
			 << endl << endl;
	else
		cout << endl
			 << "不存在飞机航班从"
			 << G.vertices[v0].cityname
			 << "到"
			 << G.vertices[v1].cityname
			 << endl << endl;
}

//显示城市交通系统
void PrintGraph(ALGraph *G)
{   char i;
	int j,k;
	ArcNode *q;

	cout << endl
		 << "请选择显示项目:"
		 << endl;
	cout << "0=显示城市"		<< endl
		 << "1=显示飞机航班"	<< endl
		 << "2=显示列车车次"	<< endl
		 << "3=返回上一级菜单"	<< endl;
	cout <<"选择?";
	cin  >> i;
	
	while(i!='3')
	{
		switch(i)
		{
			case '0': cout << endl << "城市:" << endl;
					for (j=0;j<G->vexnum;j++)
						cout << G->vertices[j].cityname << "  ";
					cout << endl;
					break;
			case '1': cout << endl << "飞机航班:" << endl;
					for (j=0;j<G->vexnum;j++)
					{
						q=G->vertices[j].planefirstarc;
						while(q!=NULL)	
						{
							cout << G->vertices[j].cityname
								 << "---->"
								 << G->vertices[q->adjvex].cityname
								 << endl;
							for (k=0;k<=q->info.last;k++)
								cout << "    number: "
									 << q->info.stata[k].number
									 << "  expenditure: "
									 << q->info.stata[k].expenditure
									 << "  begintime: "
									 << q->info.stata[k].begintime[0]
									 << ":"
									 << q->info.stata[k].begintime[1]
									 << "  arrivetime: "
									 << q->info.stata[k].arrivetime[0]
									 << ":"
									 << q->info.stata[k].arrivetime[1]
									 << endl;
							q=q->nextarc;
						}
					}
					break;
			case '2': cout << endl << "列车车次:" << endl;
					for (j=0;j<G->vexnum;j++)
					{
						q=G->vertices[j].trainfirstarc;
						while(q!=NULL)
						{
							cout << G->vertices[j].cityname
								 << "---->"
								 << G->vertices[q->adjvex].cityname
								 << endl;
							for (k=0;k<=q->info.last;k++)
								cout << "    number:"
									 << q->info.stata[k].number
									 << "  expenditure:"
									 << q->info.stata[k].expenditure
									 << "  begintime:"
									 << q->info.stata[k].begintime[0]
                                     << ":"
									 << q->info.stata[k].begintime[1]
									 << "  arrivetime:"
									 << q->info.stata[k].arrivetime[0]
                                     << ":"
									 << q->info.stata[k].arrivetime[1]
									 << endl;
							q=q->nextarc;
						}
					}
					break;
		}
		cout << endl 
			 << "请选择显示项目:" 
			 << endl;
		cout << "0=显示城市"		<< endl
			 << "1=显示飞机航班"	<< endl
			 << "2=显示列车车次"	<< endl
			 << "3=返回上一级菜单"  << endl;
		cout << "选择?";
		cin  >> i;		
	}
}