algraph.cpp

(1) 提供对城市信息进行编辑(添加或删除)的功能.(2) 城市之间有两种交通工具:火车和飞机.提供对列车时刻表和飞机航班进行编辑(增设或删除)的功能.(3) 提供两种最优策略:最快到达或最省钱到达.

#include "Traffic.h"

//注意全部使用指针new
ArcNode::ArcNode(int vex,int distance)//构造好了，等待插入
{
	adjvex=vex;
	nextarc=NULL;
	train=new Traffic_Table();
	plane=new Traffic_Table();
}

/*ArcNode::ArcNode(ArcNode &other)
{
	adjvex=other.adjvex;
	nextarc=other.nextarc;
	train=new Traffic_Table(*(other.train));
	plane=new Traffic_Table(*(other.plane));
}
*/
ArcNode::~ArcNode()
{
	delete train;
	delete plane;
}

int ArcNode::GetAdjvex()
{
	return adjvex;
}

t_table ArcNode::GetTrain()
{
	return train;
}

t_table ArcNode::GetPlane()
{
	return plane;
}

void ArcNode::SetNext(aNode next)
{
	nextarc=next;
}

aNode ArcNode::Successor()
{
	return nextarc;
}
//////////////////////////////////////ArcNode定义结束/////////////////////////////////////////////

VNode::VNode(int VID,char* name)//生成空链表
{
	ID=VID;
	firstarc=NULL;
	CityName=new char[strlen(name)+1];
	strcpy(CityName,name);
	CityName[strlen(name)]='\0';
}

VNode::VNode(VNode& other)
{
	ID=other.ID;
	firstarc=other.firstarc;
	CityName=new char[strlen(other.CityName)+1];
	strcpy(CityName,other.CityName);
	CityName[strlen(other.CityName)]='\0';
}

VNode::~VNode()
{
	aNode p=firstarc;
	aNode temp;
	while(p)
	{
		temp=p;
		p=p->Successor();
		delete temp;
	}
	delete CityName;
}

aNode VNode::LocateArc(int destination)//没找到就返回NULL
{
	aNode p;
	for(p=firstarc;p;p=p->Successor())
		if(p->GetAdjvex()==destination)
			break;
	return p;
}

int VNode::ArcNum()////计算弧的个数
{
	int i;
	aNode p;
	for(i=0,p=firstarc;p;p=p->Successor(),i++);
	return i;
}

aNode VNode::GetFirst()
{
	return firstarc;
}

char* VNode::GetName()
{
	return CityName;
}

int VNode::GetID()
{
	return ID;
}

void VNode::SetID(int new_id)
{
	ID=new_id;
}

void VNode::InsertArc(aNode p)//逆序插入，方便从小到大查找
{
	aNode temp=firstarc;
	firstarc=p;
	p->SetNext(temp);
}

void VNode::DeleteArc(aNode p)//认为不存在删错的情况
{
	aNode pre,q=firstarc;
	if(p==q)
		firstarc=q->Successor();////如果删除的是第一个邻接点则改动指针就行了
	else
	{
		for(pre=firstarc,q=pre->Successor();q;pre=q,q=q->Successor())///否则遍历查找
			if(p==q) break;
		pre->SetNext(p->Successor());
	}
	delete p;
}
/////////////////////////////////////VNode定义结束////////////////////////////////////////////////

ALGraph::ALGraph()//id实际上是i+1
{
	///以字母a和p开头的是指飞机，t是指火车，anum(=arcnum)特殊一点，
	///它是当前"name"城市的邻接城市个数(弧个数)
    int id,i,j=0,k,anum,tnum,pnum,adjvex,distance,tstart,astart;
	double tfee,afee;
	char name[50];
	aNode p;
	t_info q;

	arcnum=0;
	ifstream inf;////输出文件类
	inf.open("map.txt");
	if(!inf)
	{
		cout<<"地图文件不存在"<<endl;
		exit(1);
	}
	
	while(!inf.eof())
	{
		inf>>id>>name>>anum;//从数据流中依次读入id和城市名，邻接城市个数
		vertices[j]=new VNode(id,name);
		for(i=0;i<anum;i++)
		{
			inf>>adjvex>>distance>>tnum;//读入具体邻接城市号码、距离、火车车次
			p=new ArcNode(adjvex,distance);
			for(k=0;k<tnum;k++)
			{
				inf>>tstart>>tfee;//读入火车开车时间、该车程乘火车费用
				q=new Traffic_Info(tstart,(double)distance/TRAINSPEED,tfee);
				p->GetTrain()->InsertTable(q);
			}
			inf>>pnum;//读入飞机班次
			for(k=0;k<pnum;k++)
			{
				inf>>astart>>afee;//读入飞机起飞时间、该航班费用
				q=new Traffic_Info(astart,(double)distance/PLANESPEED,afee);
				p->GetPlane()->InsertTable(q);
			}
			vertices[j]->InsertArc(p);
		}
		arcnum+=anum;
		j++;
	}
	vexnum=j;

	inf.close();
}

ALGraph::~ALGraph()
{
	int i;
	for(i=0;i<vexnum;i++)
		delete vertices[i];
}

int ALGraph::LocateVex(char* name)//没有找到就返回-1
{
	int i;
	for(i=0;i<vexnum;i++)
		if(!strcmp(vertices[i]->GetName(),name))///若找到相等则break跳出，无谓浪费时间继续查找
			break;
	
	if(i<=vexnum-1)
		return i;
	else
		return -1;
}

void ALGraph::InsertVex()//注意插入一对
{
	int id=vexnum+1,pos,distance,tstart,astart;
	double tfee,afee;
	char name[50],choice,temp[50];
	aNode p,r;
	t_info q,s;

	do    ////查询所增加的城市是否已重复存在
	{
		cout<<"请输入新增加的城市名称："<<endl;
		cin>>name;
		pos=LocateVex(name);
		if(pos==-1) break;
		else
			cout<<"该城市已经存在"<<endl;
	} while(1);
	
	vexnum++;
	vertices[id-1]=new VNode(id,name);/////增加城市节点
	do								  /////注意下面各个"break"和"do~while"的妙用
	{
		cout<<"是否增加新的路径？(y/n)"<<endl;
		cin>>choice;
		if(choice=='n'||choice=='N') break;
		do 
		{
			cout<<"请输入目的地："<<endl;
			cin>>name;
			pos=LocateVex(name);
			if(pos>=0)   //已存在的城市作为目的地才正确！
				break;
			else
				cout<<"错误的目的地"<<endl;
		} while(1);

		do 
		{
			cout<<"请输入距离(单位：公里)："<<endl;
			cin>>temp;
			distance=atoi(temp);
			if(distance>0) break;
			else
				cout<<"错误的距离"<<endl;
		} while(1);
		
		p=new ArcNode(pos+1,distance);//目的城市要增加弧
		r=new ArcNode(id,distance);/////新增城市也要增加弧
		
		do//编辑火车时刻表 
		{
			cout<<"是否增加列车信息？(y/n)"<<endl;
			cin>>choice;
			if(choice=='n'||choice=='N') break;

			do 
			{
				cout<<"请输入火车的出发时间：(24小时制)"<<endl;
				cin>>temp;
				tstart=atoi(temp);
				if(tstart>=0 && tstart<=23) break;
				else
					cout<<"错误的时刻"<<endl;
			} while(1);

			do 
			{
				cout<<"请输入火车的费用："<<endl;
				cin>>temp;
				tfee=atof(temp);
				if(tfee>0) break;
				else
					cout<<"错误的费用"<<endl;
			} while(1);
		
			///把新增邻接表结点接入邻接表里
			q=new Traffic_Info(tstart,(double)distance/TRAINSPEED,tfee);
			s=new Traffic_Info(tstart,(double)distance/TRAINSPEED,tfee);
			p->GetTrain()->InsertTable(q);
			r->GetTrain()->InsertTable(s);
		} while(1);

		do//编辑航班时刻表 
		{
			cout<<"是否增加航班信息？(y/n)"<<endl;
			cin>>choice;
			if(choice=='n'||choice=='N') break;
			do 
			{
				cout<<"请输入飞机的出发时间：(24小时制)"<<endl;
				cin>>temp;
				astart=atoi(temp);
				if(astart>=0 && astart<=23) break;
				else
					cout<<"错误的时刻"<<endl;
			} while(1);
			do 
			{
				cout<<"请输入飞机的费用："<<endl;
				cin>>temp;
				afee=atof(temp);
				if(afee>0) break;
				else
					cout<<"错误的费用"<<endl;
			} while(1);
			q=new Traffic_Info(astart,(double)distance/PLANESPEED,afee);
			s=new Traffic_Info(astart,(double)distance/PLANESPEED,afee);
			p->GetPlane()->InsertTable(q);
			r->GetPlane()->InsertTable(s);
		} while(1);
		
		vertices[id-1]->InsertArc(p);
		vertices[pos]->InsertArc(r);
		arcnum+=2;  //两个城市来回两趟增加两条弧
	} while(1);
}

void ALGraph::DeleteVex()//注意删除相关弧
{
	int pos,i;
	char name[50];
	aNode p,temp;
	
	do 
	{
		cout<<"请输入想要删除的城市名称："<<endl;
		cin>>name;
		pos=LocateVex(name);
		if(pos>=0) 
			break;
		else
			cout<<"错误的城市名称"<<endl;
	} while(1);

	for(i=0;i<vexnum;i++)//删除跟要删除城市相关的弧，遍历
	{
		for(p=vertices[i]->GetFirst();p;)
		{
			if(p->GetAdjvex()==(pos+1))///找到了! pos+1实际上就是删除的城市的“ ID”号
			{
				temp=p;////p指向就是要删除的城市结点
				p=p->Successor();
				vertices[i]->DeleteArc(temp);
				continue;
			}
			p=p->Successor();
		}
	}
	
	arcnum-=2*vertices[pos]->ArcNum();///注意"来回"共两倍于所删除城市结点所含的弧个数
	
	delete vertices[pos];///最后delete要删除城市头顶点结点
	vertices[pos]=new VNode(pos+1,"已删除");//标识“已删除”

}


int ALGraph::GetaSize()
{
	return arcnum;
}

int ALGraph::GetvSize()
{
	return vexnum;
}

vNode* ALGraph::GetVertices()
{
	return vertices;
}

void ALGraph::ShowGraph()
{
	int i;
	for(i=0;i<vexnum;i++)
	{
		if(i%5==0 && i!=0)
			cout<<endl;
		cout<<i+1<<" "<<vertices[i]->GetName()<<"     ";
	}
	cout<<endl;
}

void ALGraph::SaveToFile()////其实也就是重写一遍记录覆盖掉之前的记录
{
	int i,dist;
	aNode p;
	t_info q;
	ofstream outf;
	
	outf.open("map.txt",ios::out|ios::trunc);
	
	for(i=0;i<vexnum;i++)//遍历所有的结点
	{
		outf<<vertices[i]->GetID()<<" "<<vertices[i]->GetName()<<" "
			<<vertices[i]->ArcNum()<<" ";
		for(p=vertices[i]->GetFirst();p;p=p->Successor())//遍历所有的弧
		{
			dist=(int)(p->GetTrain()->GetHead()->m_Successor()->m_GetCost()*TRAINSPEED);
			outf<<p->GetAdjvex()<<" "<<dist<<" "<<p->GetTrain()->GetSize()<<" ";//火车个数在此写入

			for(q=p->GetTrain()->GetHead()->m_Successor();q;q=q->m_Successor())//遍历火车链表
				outf<<q->m_GetStart()<<" "<<q->m_GetFee()<<" ";

			outf<<p->GetPlane()->GetSize()<<" ";//飞机个数在此写入

			for(q=p->GetPlane()->GetHead()->m_Successor();q;q=q->m_Successor())//遍历飞机链表
				outf<<q->m_GetStart()<<" "<<q->m_GetFee()<<" ";
		}
		outf<<"\n";
	}

	outf.close();
}

void ALGraph::BakeUp()///备份文件，自动生成，由main()函数调用，
                     ////跟上面函数"SaveToFile()"原理一模一样
{
	int i,dist;
	aNode p;
	t_info q;
	ofstream outf;
	
	outf.open("map_bak.txt",ios::out|ios::trunc);
	
	for(i=0;i<vexnum;i++)//遍历所有的结点
	{
		outf<<vertices[i]->GetID()<<" "<<vertices[i]->GetName()<<" "
			<<vertices[i]->ArcNum()<<" ";
		for(p=vertices[i]->GetFirst();p;p=p->Successor())//遍历所有的弧
		{
			dist=(int)(p->GetTrain()->GetHead()->m_Successor()->m_GetCost()*TRAINSPEED);
			outf<<p->GetAdjvex()<<" "<<dist<<" "<<p->GetTrain()->GetSize()<<" ";//火车个数在此写入
			
			for(q=p->GetTrain()->GetHead()->m_Successor();q;q=q->m_Successor())//遍历火车链表
				outf<<q->m_GetStart()<<" "<<q->m_GetFee()<<" ";
			
			outf<<p->GetPlane()->GetSize()<<" ";//飞机个数在此写入
			
			for(q=p->GetPlane()->GetHead()->m_Successor();q;q=q->m_Successor())//遍历飞机链表
				outf<<q->m_GetStart()<<" "<<q->m_GetFee()<<" ";
		}
		outf<<"\n";
	}
	
	outf.close();
}