adjgraph.cpp

数据结构中交通信息查询系统的VC++实现

// AdjGraph.cpp: implementation of the AdjGraph class.
//
//////////////////////////////////////////////////////////////////////

#include "AdjGraph.h"
#include "iostream.h"
#include "stdlib.h"
#include "string.h"


//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

AdjGraph::AdjGraph()
{


}

AdjGraph::~AdjGraph()
{

}

void AdjGraph::CreatGraph(AdjGraph &gb)
{
	int i,j,r;
	VertexType va,vb;
	cout<<"请输入站点数和交通路线数："<<endl;
    cin>>gb.vexnum>>gb.arcnum;
	for(int k=0;k<gb.vexnum;k++)
	{
		cout<<"请输入第"<<k+1<<"个站点的信息:";
		cin>>gb.adjlist[k].vexdata;
		gb.adjlist[k].firstarc=NULL;
	}
    
	for(k=0;k<gb.arcnum;k++)
	{
		cout<<"请读入一对站点(以空格间隔):"<<endl;		
		cin>>va>>vb;
		cout<<"请读入两站点间的距离:"<<endl;
		cin>>r;
		ArcPointer p=new ArcNode;
		for(i=0;i<gb.vexnum;i++)
			if(strcmp(va,gb.adjlist[i].vexdata)==0) break;
		for(j=0;j<gb.vexnum;j++)
			if(strcmp(vb,gb.adjlist[j].vexdata)==0) break;
	    p->adjvex=j;              //生成结点
		p->nextarc=gb.adjlist[i].firstarc;
		p->right=r;   
		gb.adjlist[i].firstarc=p;
	}
}

void AdjGraph::ShortPath(AdjGraph gb,VertexType q,dist & d,path & p)
{
	int t;
	for(t=0;t<gb.vexnum;t++)	
		if(strcmp(q,gb.adjlist[t].vexdata)==0) break;

	for(int k=0;k<gb.vexnum;k++)  
		d[k]=MAXINT;

	ArcPointer s;
	s=gb.adjlist[t].firstarc;
 
	while(s)
	{
		int temp;
		temp=s->adjvex;
		d[temp]=s->right;
		s=s->nextarc;
	}
    
    int inset[MAX];

    for(int v=0;v<gb.vexnum;v++)
	{
       inset[v]=0 ;            //所有顶点都不在S中
	   for(int w=0;w<gb.vexnum;w++)
		   p[v][w]=0;	 //所有path[i]为空路径
	   if(d[v]<MAXINT)	  
		   p[v][t]=p[v][v]=1;	   //让path[i]={v0，vi}  
  
	}
	d[t]=0;
	inset[t]=1;  

    for(int i=1;i<gb.vexnum;i++)
	{
	  int min=MAXINT;
	  for(int w=0;w<gb.vexnum;w++)	  
	     if(inset[w]==0&&d[w]<min)
		 {
			 v=w;
			 min=d[w];
		 }
	  inset[v]=1;
	  for(w=0;w<gb.vexnum;w++)     //// 修改dist[i]
      {

		  ArcPointer u;
		  u=gb.adjlist[v].firstarc;
		  while(u)
		  {
			 if(u->adjvex==w) break;
			 u=u->nextarc;
		  }

		  if(u&&inset[w]==0&&min<MAXINT&&(min+(u->right)<d[w]))  //	net[j][i]
		  {
			 d[w]=min+(u->right);  //net[j][i]
			 for(int j=0;j<gb.vexnum;j++)
				p[w][j]=p[v][j];		 
			 p[w][w]=1;				 
		  }
	  }
	}	  
}

void main()
{
    AdjGraph gb; 
	dist d;
	path p;
	VertexType s,va,vb;
	int choose;
	int k,i,re,de;

	while(1)
	{
		cout<<"********************************************************************************";
		cout<<"*                      交通查询系统(Dijkstra)                                  *";
		cout<<"*                        1.创建交通网;                                         *";
		cout<<"*                        2.查询指定站点到目的地的情况;                         *";
		cout<<"*                        3.查看指定站点到各个站点的最短路径;                   *";
        cout<<"*                        4.退出;                                               *";
	    cout<<"********************************************************************************"<<endl;

        cin>>choose;    
	    switch(choose)
		{
		case 1:
			gb.CreatGraph(gb);			      
			break;

        case 2:
			cout<<"输入源车站"<<endl;
	        cin>>va;
		    for(re=0;re<gb.vexnum;re++)
        		if(strcmp(va,gb.adjlist[re].vexdata)==0) break;
           
	        cout<<"输入目的车站"<<endl;
            cin>>vb;
			for(de=0;de<gb.vexnum;de++)
        		if(strcmp(vb,gb.adjlist[de].vexdata)==0) break;
		
            gb.ShortPath(gb,va,d,p);
		    if(p[de][re]==1)
			{
				cout<<va<<"站"<<"能到达"<<vb<<"站"<<endl;
		        cout<<"经过的车站有(非路径顺序)："<<endl;
		        for(i=0;i<gb.vexnum;i++)  
				{
					if(p[de][i]==1)
					{	
						cout<<gb.adjlist[i].vexdata<<" "<<endl;
					}
				}
			}

		    else cout<<va<<"站"<<"不能到达"<<vb<<"站"<<endl;
		    break;

		case 3:
			cout<<"请输入要查询的站点"<<endl;
			cin>>s;
			gb.ShortPath(gb,s,d,p);
			cout<<s<<"到各站点的最段路径长度为"<<endl;
            for(re=0;re<gb.vexnum;re++)
        		if(strcmp(s,gb.adjlist[re].vexdata)==0) break;
			for(i=0;i<gb.vexnum;i++)
				
                if(strcmp(gb.adjlist[i].vexdata,s)!=0) 
				{
					if(d[i]-MAXINT)
					{
						cout<<"*************************************************"<<endl;
						cout<<s<<"站"<<"------"<<gb.adjlist[i].vexdata<<"站"<<"的最短路程为"<<d[i]<<endl;
                        if(p[i][re]==1)
						{			
							cout<<"经过的车站有(非路径顺序)："<<endl;
		                    for(k=0;k<gb.vexnum;k++)  
							{
								if(p[i][k]==1)
								{	
									cout<<gb.adjlist[k].vexdata<<" ";
								}                             
							}
						}
						cout<<endl;
					}
                    else cout<<s<<"站"<<"------"<<gb.adjlist[i].vexdata<<"站"<<"无路"<<endl;
                        cout<<"*************************************************"<<endl;
				} 
				cout<<endl;
            break;
		case 4:
			exit(0);
			break;
	
		}
	}
}