jt.cpp

交通咨询的事例程序

	cout << endl 
		 << "请输入删除列车车次的信息:"
		 << endl;
	cout << "列车车次的编号:";
	cin >> code;
	
	cout << "起始城市:";
	cin  >> vt;
	cout << "目的城市:";
	cin  >> vh;
	cout << endl
		 << "确认?(Y/N)";
	
	cin >> c;
	if(c=='Y'||c=='y')
	{
		i=LocateVertex(G,vt);
		j=LocateVertex(G,vh);
		if ( i==-1 )
		{ 
			cout << endl
				 << "错误！无法找到起始城市"
				 << endl;
			return;
		}
		if ( j==-1 )
		{
			cout << endl
				 << "错误！无法找到目的城市"
				 << endl;
			return;
		}
		p = G->vertices[i].trainfirstarc;
		q = p;
		while ( p!=NULL )
		{
			if ( p->adjvex==j )
			{
				n = -1;
				for ( k=0;k<=p->info.last;k++ )
				{
					if ( p->info.stata[k].number==code )
					{
						n = k;
						break;
					}
				}
				if ( n!=-1 )
				{
					if ( p->info.last==0 )
					{
						if ( q==p )
							G->vertices[i].trainfirstarc=p->nextarc;
						else
							q->nextarc=p->nextarc;
						free(p);
					}
					else
					{
						for(k=n;k<p->info.last;k++)
						{
							p->info.stata[k].number=p->info.stata[k+1].number;
							p->info.stata[k].expenditure=p->info.stata[k+1].expenditure;
							p->info.stata[k].begintime[0]=p->info.stata[k+1].begintime[0];
							p->info.stata[k].begintime[1]=p->info.stata[k+1].begintime[1];
							p->info.stata[k].arrivetime[0]=p->info.stata[k+1].arrivetime[0];
							p->info.stata[k].arrivetime[1]=p->info.stata[k+1].arrivetime[1];
						}
						p->info.last=p->info.last-1;
					}
				}
				else cout << endl 
						  << "在此两城市之间无法找到No."
						  << code
						  << "列车车次"
						  << endl;
				save(G);
				return;
			}
			q = p;
			p = p->nextarc;
		}
		if ( p==NULL ) cout << endl
							<< "在此两城市之间无列车车次存在"
							<< endl;
	}	
	else return;
}

//用户咨询项目选择界面
void UserDemand(ALGraph G)
{
	char i;
	char q;
	cout << endl 
		 << "请选择咨询项目:"
		 << endl;
	cout << "1=最少旅行费用"		<< endl
		 << "2=最少旅行时间"		<< endl
		 << "3=最少旅行中转次数"	<< endl
		 << "4=返回上一级菜单"		<< endl;
	cout << "选择?";
	cin  >> i;
	
	while(i!='4')
	{
		switch(i)
		{
			case 1: DemandDispose(1,G);	break;
			case 2: DemandDispose(2,G);	break;
			case 3: DemandDispose(3,G);	break;
		}
		
		cout << "按回车继续" << endl;
		cin  >> q;
		cout << "请选择咨询项目:"		<< endl;
		cout << "1=最少旅行费用"		<< endl
			 << "2=最少旅行时间"		<< endl
			 << "3=最少旅行中转次数"	<< endl
			 << "4=返回上一级菜单"		<< endl;
		cout << "选择?";
		cin  >> i;		
	}
}

//用户咨询选择信息输入界面
void DemandDispose(int n,ALGraph G)
{
	char q;
	ArcNode *plane,*train;
	infolist planearcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM],trainarcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
	int i,j,k,final[MAX_VERTEX_NUM],T[MAX_VERTEX_NUM][2];
	float M[MAX_VERTEX_NUM];
	
	for(i=0;i<G.vexnum;i++)
		for(j=0;j<G.vexnum;j++)
			for(k=0;k<MAX_ROUTE_NUM;k++)
			{
				planearcs[i][j].stata[k].expenditure=INFINITY;
				planearcs[i][j].stata[k].begintime[0]=0;
				planearcs[i][j].stata[k].begintime[1]=0;
				planearcs[i][j].stata[k].arrivetime[0]=INFINITY;
				planearcs[i][j].stata[k].arrivetime[1]=INFINITY;
				planearcs[i][j].last=-1;
				trainarcs[i][j].stata[k].expenditure=INFINITY;
				trainarcs[i][j].stata[k].begintime[0]=0;
				trainarcs[i][j].stata[k].begintime[1]=0;
				trainarcs[i][j].stata[k].arrivetime[0]=INFINITY;
				trainarcs[i][j].stata[k].arrivetime[1]=INFINITY;
				trainarcs[i][j].last=-1;
			}
	for(i=0;i<G.vexnum;i++)
	{
		plane=G.vertices[i].planefirstarc;
		train=G.vertices[i].trainfirstarc;
		while(plane!=NULL)
		{
			planearcs[i][plane->adjvex]=plane->info;
			plane=plane->nextarc;
		}
		while(train!=NULL)
		{
			trainarcs[i][train->adjvex]=train->info;
			train=train->nextarc;
		}
	}
	cout << endl
		 << "请选择旅行起始城市:"
		 << endl;
	for(k=0;k<G.vexnum;k++)
		printf("%d=%s\n",k,G.vertices[k].cityname);
	cout << "选择?";
	cin  >> i;
	cout << endl 
		 << "请选择旅行到达城市:"
		 << endl;
	for(k=0;k<G.vexnum;k++) printf("%d=%s\n",k,G.vertices[k].cityname);
	cout << "选择?";
	cin  >> j;
	cout << endl
		 << "请选择交通工具:"
		 << endl;
	cout << "1=列车" << endl 
		 << "2=飞机" << endl;
	cout << "选择?";
	cin  >> k;
	cout << endl 
		 << "确认? (Y/N)";
	
	cin  >> q;
	if ( q=='Y' || q=='y' )
	{
		if( k==1&&n==1 )
			ExpenditureDispose(1,trainarcs,G,i,j,M,final);
		else if ( k==1&&n==2 )
			TimeDispose(1,trainarcs,G,i,j,T,final);
		else if ( k==1&&n==3 )
			TransferDispose(1,trainarcs,G,i,j);
		else if( k==2&&n==1 )
			ExpenditureDispose(2,planearcs,G,i,j,M,final);
		else if ( k==2&&n==2 )
			TimeDispose(2,planearcs,G,i,j,T,final);
		else if ( k==2&&n==3 )
			TransferDispose(2,planearcs,G,i,j);
	}
	else if ( q=='N'||q=='n' )
		UserDemand(G);
	else
	{
		cout << endl
			 << "选择错误"
			 << endl << endl;
		DemandDispose(n,G);
	}
}

//初始化队列
void InitQueue(LinkQueue *Q)
{
	Q->front=(QNode *)malloc(sizeof(QNode));
	Q->rear=Q->front;
	Q->front->next=NULL;
}

//入队操作
void EnterQueue(LinkQueue *Q,int x)
{
	QNode *newnode;
	newnode=(QNode *)malloc(sizeof(QNode));
	newnode->adjvex=x;
	newnode->next=NULL;
	Q->rear->next=newnode;
	Q->rear=newnode;
}

//出队操作
void DeleteQueue(LinkQueue *Q,int *x)
{
	QNode *p;
	p=Q->front->next;
	Q->front->next=p->next;
	if(Q->rear==p) Q->rear=Q->front;
	*x=p->adjvex;
	free(p);
}

//队列判空操作
int IsEmpty(LinkQueue *Q)
{
	if(Q->front==Q->rear) return(1); else return(0);
}

//最少旅行中转次数处理
void TransferDispose(int k,infolist (*arcs)[MAX_VERTEX_NUM],ALGraph G,int v0,int v1)
{
	int visited[MAX_VERTEX_NUM],v,w,n=1;
	LinkQueue Q;
	ArcNode *t;
	Node *p,*q,*r,*s;
	p = (Node *)malloc(G.vexnum*sizeof(Node));
	for(v=0;v<G.vexnum;v++)
	{
		visited[v]=0;
		p[v].next=NULL;
	}
	InitQueue(&Q);
	visited[v0]=1;
	q=(Node *)malloc(sizeof(Node));
	q->adjvex=v0;
	q->next=NULL;
	p[v0].next=q;
	EnterQueue(&Q,v0);
	while(!IsEmpty(&Q))
	{
		DeleteQueue(&Q,&v);
		if(k==1)
			t=G.vertices[v].trainfirstarc;
		else
			t=G.vertices[v].planefirstarc;
		while(t!=NULL)
		{
			w=t->adjvex;
			if ( !visited[w] )
			{
				visited[w]=1;
				q=&p[w];
				s=p[v].next;
				while(s!=NULL)
				{
					r=(Node *)malloc(sizeof(Node));
					r->adjvex=s->adjvex;
					q->next=r;
					q=r;
					s=s->next;
				}
				r=(Node *)malloc(sizeof(Node));
				r->adjvex=w;
				r->next=NULL;
				q->next=r;
				if(w==v1)
				{
					q=p[w].next;
					r=q->next;
					
					cout << endl
						 << "旅行路线是:"
						 << endl;
					
					while(r!=NULL)
					{
						if ( k==1 )
							cout << "乘坐No."
								 << (*(*(arcs+q->adjvex)+r->adjvex)).stata[0].number
								 << "列车车次在"
								 << (*(*(arcs+q->adjvex)+r->adjvex)).stata[0].begintime[0]
								 << ":"
								 << (*(*(arcs+q->adjvex)+r->adjvex)).stata[0].begintime[1]
								 <<	"从"
								 <<	G.vertices[q->adjvex].cityname
								 << "到"
								 <<	G.vertices[r->adjvex].cityname
								 <<	endl;								 
						else
							cout << "乘坐No."
								 << (*(*(arcs+q->adjvex)+r->adjvex)).stata[0].number
								 << "飞机航班在"
								 << (*(*(arcs+q->adjvex)+r->adjvex)).stata[0].begintime[0]
								 << ":"
								 << (*(*(arcs+q->adjvex)+r->adjvex)).stata[0].begintime[1]
								 << "从" 
								 << G.vertices[q->adjvex].cityname
								 << "到"
								 << G.vertices[r->adjvex].cityname
								 << endl;								 
						q=r;
						r=r->next;
						n++;
					}
					
					cout << "最少中转次数是"
						 << n-2
						 << "次"
						 << 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;	
				}
				EnterQueue(&Q,w);
			}
			t=t->nextarc;
		}
	}
	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 MinExpenditure(infolist arcs,float *expenditure,int *route)
{
	int i;
	*expenditure=arcs.stata[0].expenditure;
	if ( *expenditure<INFINITY ) *route = 0; else *route = -1;
	for ( i=1;i<=arcs.last;i++ )
		if( arcs.stata[i].expenditure<*expenditure )
		{
			*expenditure=arcs.stata[i].expenditure;
			*route=i;
		}
}


//最少旅行费用处理	
void ExpenditureDispose(int k,infolist (*arcs)[MAX_VERTEX_NUM],ALGraph G,int v0,int v1,float *M,int *final)
{
	int v=-1,w,i,route;
	float m,expenditure;
	Node *p,*q,*r,*s;
	p=(Node *)malloc(G.vexnum*sizeof(Node));
	for(v=0;v<G.vexnum;v++)
	{
		*(final+v)=False;
		MinExpenditure(*(*(arcs+v0)+v),M+v,&route);
		p[v].next=NULL;
		if(*(M+v)<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;
		}
	}
	*(M+v0)=0;
	*(final+v0)=True;
	for(i=0;i<G.vexnum;i++)
	{
		m=INFINITY;
		v=-1;
		for(w=0;w<G.vexnum;w++)
			if(*(final+w)==False)
				if(*(M+w)<m)
				{
					v=w;
					m=*(M+w);
				}
		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 
				 << "元"
				 << 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)
				{
					MinExpenditure(*(*(arcs+v)+w),&expenditure,&route);
					if(*(M+w)>m+expenditure)
					{
						*(M+w)=m+expenditure;
						q=p[w].next;
						while(q!=NULL)
						{
							s=q;
							q=q->next;
							free(s);
						}
						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;
					}
				}
		}
	}
	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);