head.h

一． 需求分析 1. 本程序的功能 接受用户的中文输入

	
	}else
		return false ;
}
PathLink Traffic_Map::direArrive(string from,string to) // 反应连个站点间的相关信息，经过的公交的名称，两站点间的距离
                                                 

{
	PathLink *pathlink;
	int i=sizeof(PathLink);
	pathlink=(PathLink *)malloc(sizeof(PathLink));	
	pathlink->pathlength=INFINITY;
//	string sp("hello");pathlink->pathnumber=sp;
	pathlink->pathnumber=INFINITY;
	for(vector<vector<string> >::iterator vster=svecsta.begin();vster!=svecsta.end();vster++){
		vector<string> s1(*vster);
		for(vector<string>::size_type i=0;i!=s1.size();i++){			
				if(!isNumber(s1[i])&&(s1[i]!="上行")&&(s1[i]!="下行")){
					vector<string>::iterator svec=find(s1.begin(),s1.end(),from);
			        if(svec==s1.end())
				         break;
					vector<string>::iterator svec1=find(svec,s1.end(),to);
					if(svec1==s1.end())
						 break;
					else {
						pathlink->pathlength = svec1-svec;
					//	cout << pathlink ->pathlength << " ";
					//	pathlink->pathnumber=*(s1.begin());
						string str =*(s1.begin());
						int sum=0;
						for(i=0;i!=str.size();i++)
                                sum=10*sum+(str[i]-'0');
						pathlink->pathnumber=sum;
						str=*(s1.begin()+1);
						if(str=="上行")
							pathlink->direction=1;
						else
							pathlink->direction=2;
						return *pathlink;
					}
				}
		}
	}
	return *pathlink;
}


void Link_station::shortPath(string from,string to,Traffic_Map& s) // 蒂杰斯特拉算法
{
	const   double   begin=(double)clock()/CLK_TCK;  
	bool flag=true;
    int  v0=locateVex(from);
	if(v0==-1){
		cout << "无此地名  :" << from << endl;
		flag=false;
	}
	int  t0=locateVex(to);
	if(t0==-1){
		cout << "无此地名  :" << to << endl;
		flag=false;
	}

	if(flag==true){
		bool final[MAX_VERTEX_NUM]; 
		int  p[MAX_VERTEX_NUM],D[MAX_VERTEX_NUM];

		for(int v=0;v < vexnum ; ++v){
			final[v]=false;
			string s1=locateName(v);
			D[v]=s.direArrive(from,s1).pathlength;
			p[v]=-1;
			if(D[v] < INFINITY){			
				p[v]=v0;
			}
		}
		D[v0]=0;
		final[v0]=true;	
		int min=0,t1=0;
		//开始主循环，每次求到当前的最短路径的节点，将它加入到以求得的最短路径节点中
		for(int i=1;(i < vexnum);i++){		
			min=INFINITY;
			for(int w=0;w < vexnum;w++){
				if(!final[w]){
					if(D[w] < min){
						v=w;
						min=D[w];
					}
				}
			}
			final[v]=true;	// 离v0顶点的最近的v 加入S中
			if(v==locateVex(to)) //找到目的地的节点
			    break;
			for(int t1=0; t1 < vexnum;++t1){
				int length = s.direArrive(locateName(v),locateName(t1)).pathlength; //求两节点间的距离
				if((!final[t1])&&(min + length < D[t1])){ //修改D[t1],P[t1]
					D[t1]= min + length;
					p[t1]=v;
					
				}
			}
		}
		PathLink *pathlink;
		string direction;
		pathlink=(PathLink *)malloc(sizeof(PathLink));
		if(final[t0]==true){
			cout << "你的坐车路线是 :" << endl; 
			deque<string> path;
			for(int j=t0;locateName(j)!=from;j=p[j]){
			   path.push_front(locateName(j));
			}
			path.push_front(from);
			for(deque<string>::iterator svec=path.begin();svec!=(path.end()-1); svec++){
                *pathlink=s.direArrive(*svec,*(svec+1));
				if(pathlink->direction==1)
					direction="上行  ";
                if(pathlink->direction==2)
					direction="下行  ";
				cout << direction  << pathlink->pathnumber  << "路车 (途经" << pathlink->pathlength <<
					  " 个站 ): " <<*svec << " -> "<< *(svec+1)<< endl;					             
			}	
			free(pathlink);
			path.clear();	
			const   double   end=(double)clock()/CLK_TCK;
			cout << endl<< "总共用时" << end -begin  <<" s"<< endl;
		}
		else {
			cout << "不能到达目的地,在现实生活中是不存在了,可能是本系统的测验数据不完备造成的!!" << endl;
			free(pathlink);
		}
	}
}



void Link_station::search(string from,string to,Traffic_Map& s,int type)
{
	if(isNumber(from)){
        int n1=0;
		for(int i=0;i!=from.size();i++)
               n1=10*n1+(from[i]-'0');		
		if(n1 >= vexnum){
			cout << "没有与 "<< from << "所对应的节点请重新输入" << endl;
	 	    return ;
		}
		from=locateName(n1);
	}
    if(isNumber(to)){
        int n2=0;
		for(int i=0;i!=to.size();i++)
               n2=10*n2+(to[i]-'0');
		if(n2 >= vexnum){
			cout << "没有与 "<< to << " 所对应的节点请重新输入" << endl;
		    return ;
		}
		to=locateName(n2);
	}
	if(from==to){
		cout << "起点和目的地相同请重新输入" << endl;
		return ;
	}
	bool find=false;
	if(type==1){
		cout << "你选择最短路径 !!!" << endl;
		shortPath(from,to,s);	
	}if(type==2){
		cout << "你选择换乘次数最少 !!!"<< endl ;
		if(!leastchx1(from,to,s)){//没有直接到达的车
			if(!leastchx2(from,to,s)) //转乘一次不能到达
				if(!leastchx3(from,to,s)){
					cout << " 转车三次不到,在现实生活中是不存在了,可能是本系统的测验数据不完备造成的!!" << endl;
				}
		}
	}

}


void Link_station::createDG(Traffic_Map& G)
{
	vexnum=node.size();
	arcnum=G.arcnum;
	for(int i=0;i<vexnum;i++){
		vector<string>::iterator svec=node.begin();
		xlist[i].data=*svec; //站点的名字
		svec++;
		xlist[i].firstin=null; //初始化指针
		xlist[i].firstout=null;
    }
	int j=0;
    for(vector<vector<string> >::iterator vster=G.svecsta.begin();vster!=G.svecsta.end();vster++){
		vector<string> s1(*vster);
		for(vector<string>::size_type s=2;s!=s1.size()-1;s++){
                  
			      i=locateVex(s1[s]); // 输入个弧并构造十字链表
				  j=locateVex(s1[s+1]);
			      ArcBox *p=(ArcBox *)malloc(sizeof(ArcBox));
                  p->tailvex=i;
				  p->headvex=j;
				  p->hlink=xlist[j].firstin; //对节点赋值
				  p->tlink=xlist[i].firstout;
				  p->info=null;
				  xlist[j].firstin=p;
				  xlist[i].firstout=p; //完成再入弧和出弧链头的插入
		}
	}
		
}


void Link_station::make_node(Traffic_Map& s)  // 存放站点名及其对应的号
{
	int j=0;
	for(vector<vector<string> >::iterator vster=s.svecsta.begin();vster!=s.svecsta.end();vster++){
		vector<string> s1(*vster); //一个公交线路的站点
		for(vector<string>::size_type i=0;i!=s1.size();i++){			
			if(!isNumber(s1[i])&&(s1[i]!="上行")&&(s1[i]!="下行")){ // 忽略掉与站点无关的信息
					vector<string>::iterator svec=find(node.begin(),node.end(),s1[i]);
			        if(svec==node.end())
				         node.push_back(s1[i]); //记录站点
					     node_number.push_back(j++); //记录站点的序号
				}
		}
	}

}



Traffic_Map::Traffic_Map(string file_name){
	    arcnum=0;
		ifstream f(file_name.c_str());	
		ofstream   fo; 
		fo.open("E:\\ds\\a\\lines2.txt",ios::binary); //将从文件输入的数据专程更为可用的文件，也可以不输出
		string line,word;
		while(getline(f,line)){  // 得到一行的数据
			vector<string> s;
			istringstream stream(line);
			while(stream >> word){  //以空格为分隔符读取数据
				if((word!=";")&&(word!="-")){
				   arcnum++;
				   s.push_back(word);
				   fo << word << "  ";		   
				}
				else if(word=="-"){
				}
				else if(word==";"){ // 已经到达一条公交网络的末尾
				   arcnum=arcnum-3;
				   svecsta.push_back(s); //将这条公交网络储存
				   fo << " ;" << endl;
				}			
			}
		}
		fo.close();					
}


void Traffic_Map::print() 
{
		for(vector<vector<string> >::iterator vster =svecsta.begin();vster!=svecsta.end();vster++){
			vector<string> s(*vster);//一个公交线路的站点
			int sum=0;
			for(vector<string>::size_type i=0;i!=s.size();i++){
				cout << s[i] << " ";
				sum++;
				if(sum%9==0)//每九个站点答应一个回车
					cout << endl;
			}
			cout << endl;
		}
}


bool isNumber(string s1)//计算string是否为全数字
{
	for(int i=0;i!=s1.length();i++)
		if(s1[i]!='0'&&s1[i]!='1'&&s1[i]!='2'&&s1[i]!='3'&&s1[i]!='4'&&s1[i]!='5'
			&&s1[i]!='6'&&s1[i]!='7'&&s1[i]!='8'&&s1[i]!='9')
			  return false;
	return true;
}
void note()//打印出系统的提示消息
{
		ifstream f("note.txt");	
		string line;
		while(getline(f,line)){
			cout << line << endl;
		}
}