head.h

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

#pragma   warning(disable:4786)
#include<iostream>
#include<stdio.h>
#include<string>
#include<stdlib.h>
#include<fstream>
#include<sstream>
#include<vector>
#include<list>
#include<deque>
#include<malloc.h>
#include<ctime>
#include<algorithm>
#include<math.h>
#define null 0
#define MAX_VERTEX_NUM  300
#define INFINITY    3000
using namespace std;
typedef  string VertexType;
class Traffic_Map;
bool isNumber(string s1);
typedef class PathLink  // 该类用于保存两个任意两个站点间的数据
{
     public :  int      pathlength; // 保存两个站点间的路程，相邻的站点有车经过为1 ， 若两点间没有车经过，系统定义为3 000
	           int      pathnumber; //  若有车经过，记入公交车的路线号
			   int      direction;  // 上行或下行
 
}PathLink;


typedef class InfoType  // 存放两站点间的弧的信息，本系统为null
{

}InfoType;


typedef class ArcBox
{
	public  :int        tailvex,headvex; // 该弧的尾和头顶点的位置
	         ArcBox     *hlink,*tlink;  // 分别为弧头和弧尾相同的弧的链域
	         InfoType   *info; // 该弧的相关信息
}ArcBox;


typedef class VexNode
{
	public  :VertexType   data;
	         ArcBox       *firstin,*firstout; //   分别指向该顶点第一条入弧和出弧
}VexNode;


typedef class Link_station
{
	public  :
		   //  void          serch(string from,string to, int function) ;			 
			 void            node_print() ; //  输入站点名及本系统所对应的序号
			 void            link_print() const; // 为了本来便于调试用
			 void            search(string from,string to,Traffic_Map& s,int type); // 搜索
                              // 路径，type 1为最短路径，2为换乘次数最少
			                 Link_station(Traffic_Map& s1);
			 

	private :
		     VexNode         xlist[MAX_VERTEX_NUM]; // 表头向量
	         int             vexnum,arcnum;  // 有向图的当前顶点数和弧数
			 vector<int>     node_number;  //存放 站点名的序号
			 vector<string>  node; //存放站点名
			 void            createDG(Traffic_Map& s); //  采用十字链表储存，构造向图

			 void            make_node(Traffic_Map& s1);  // 存放站点名及其对应的号
			 int             locateVex(string s); // 返回站点名所对应的序号
			 string          locateName(int number) const; // 放回站点序号所对应站点名
			 void            shortPath(string from,string to,Traffic_Map& s);  //搜索最短路径
			 bool            leastchx1(string from,string to,Traffic_Map& s); //查找两站点间是否可以直达
             bool            leastchx2(string from,string to,Traffic_Map& s); //查找两个站点间是否可以经过转车一次可达		 
			 bool            leastchx2(string pathnumber,string direction,string from,string transfer,string to,Traffic_Map& s); //查找两个站点间是否可以经过转车一次可达
			 bool            leastchx3(string from,string to,Traffic_Map& s);
			 			         
}Link_station;


Link_station::Link_station(Traffic_Map& s1)
{
	make_node(s1);
    createDG(s1);	
}


int Link_station::locateVex(string s) // 返回站点名所对应的序号
{
	for(vector<string>::size_type i=0;i!=node.size();i++){
		if(s==node[i])
			return (int)i;
	}
	return -1;
}


string Link_station::locateName(int number) const // 放回站点序号所对应站点名
{
	for(vector<int >::size_type i=0; ((i!=(vector<int >::size_type)number)&&(i!=node.size()));i++);
	   return node[i];

}

void Link_station::link_print() const // 为了本来便于调试用
{
	cout << "\n以下是图!!!" << endl;
	ArcBox *p=(ArcBox *)malloc(sizeof(ArcBox));
	for(int i=0;i< vexnum;i++){
		cout << locateName(i) << "  :";	    
	    for(p=xlist[i].firstin;p!=null;p=p->hlink)
			cout << p->tailvex << "  ";
        cout <<  "              能到达  :";
		for(p=xlist[i].firstout;p!=null;p=p->tlink)
			cout << p->headvex << "  ";
		cout << endl;

	}
	free(p);
}


void Link_station::node_print()  //  输入站点名及本系统所对应的序号
{
	int i=0;
	cout << endl <<"弧数    :" << arcnum << endl; 
	cout <<"站点数  :"<< vexnum << endl;
	cout << "站名及本系统所相对应的号数 :" << endl;
	vector<int>::iterator ivec=node_number.begin();
	for(vector<string>::iterator svec=node.begin();svec!=node.end();svec++){
		cout << *ivec <<*svec << "  ";
		ivec++;
		if((++i)%6==0)
			cout << endl;
	}
	cout << endl;

}

typedef class Traffic_Map
{		
	public:   void print() ;  // 打印整个交通图
              Traffic_Map(string file_name);
    
	private : int arcnum; 
			  vector< vector<string> >  svecsta;  //保存整个交通图
			  PathLink direArrive(string from,string one);
	
    friend void Link_station::make_node(Traffic_Map& s1);
	friend void Link_station::createDG(Traffic_Map& s1);
	friend void Link_station::shortPath(string from,string to,Traffic_Map& s);
	friend bool Link_station::leastchx1(string from,string to,Traffic_Map& s);
	friend bool Link_station::leastchx2(string from,string to,Traffic_Map& s);
	friend bool Link_station::leastchx2(string from,string to,Traffic_Map& s);
	friend bool Link_station::leastchx2(string pathnumber,string direction,string from,string transfer,string to,Traffic_Map& s);
	friend bool Link_station::leastchx3(string from,string to,Traffic_Map& s);

}Traffic_Map; 
 
bool Link_station::leastchx1(string from,string to,Traffic_Map& s)//查看两个站点间能否直接可达，若可以返回true
{
	PathLink length;
	const   double   begin=(double)clock()/CLK_TCK;
    length=s.direArrive(from,to);///若直接可达返回的
	if(length.pathlength < INFINITY){ //一下输出相关的信息
		cout << "你坐的路线是(有直达的车) :" << endl; 
		cout <<length.pathnumber << " 路车 ";
	    if(length.direction==1) 
			cout << " 上行" ;
		else
			cout << " 下行  ";
		cout << from << "-->" << to << endl;
        const   double   end=(double)clock()/CLK_TCK;
	    cout << endl <<"搜索总共用时" << end - begin  <<" s"<< endl;
		return true;
	}	
	return false;
}


bool Link_station::leastchx2(string from,string to,Traffic_Map& s)
{
	PathLink length;
	bool find=false;
	static int n=1;
	const   double   begin=(double)clock()/CLK_TCK;
	for(vector<vector<string> >::iterator vster=s.svecsta.begin();vster!=s.svecsta.end();vster++){
		vector<string> s1(*vster);//一条公交线路
		deque<string > qs;
		qs.push_back(s1[0]); //存入公交线路名及是上行，还是下行
		qs.push_back(s1[1]);
		bool findfrom=false;	    
		for(vector<string>::size_type i=2;i!=s1.size();i++){			
			if(s1[i]==from||findfrom==true){ //将从再一条公交线路中从from能够到底的站名放入deque中
				qs.push_back(s1[i]);
                findfrom=true;			    
				length=s.direArrive(s1[i],to);
				if(length.pathlength < 300){ //经过s1[i]第一次中转能够到达
					 find=true; // 输入站点的相关的信息
					 cout << endl <<"你坐的路线是(你至少要转车一次)第"  << n++ << "种方案 :"<< endl;
					 cout << qs[0]  << " 路车 " << qs[1]  << "(途经 " << s.direArrive(from,s1[i]).pathlength << " 个站) : " ;
					 cout << from   <<" -->  " << s1[i]  << endl; 
					 cout <<length.pathnumber << " 路车 ";
					 if(length.direction==1) 
						cout << "上行" ;
					 else
						cout << "下行";
					 cout << "(途经 " << length.pathlength << " 个站) : " << s1[i] << " -->  " << to << endl;						 
				}
			}
		}
		qs.clear();
	}
	if(find){		
		const   double   end=(double)clock()/CLK_TCK;
	    cout << endl <<"搜索总共用时" << end -begin  <<" s"<< endl;
		return true;
	}
	else
		return false ;
}
 
bool Link_station::leastchx2(string pathnumber,string direction,string from,string transfer,string to,Traffic_Map& s)
{
	//本函数用于leastchx3()调用
	PathLink length;
	bool find=false;
	
	for(vector<vector<string> >::iterator vster=s.svecsta.begin();vster!=s.svecsta.end();vster++){
		vector<string> s1(*vster); //存入公交线路名及是上行，还是下行
		deque<string > qs;
		qs.push_back(s1[0]);
		qs.push_back(s1[1]);
		bool findfrom=false;
		static int n=1;
		for(vector<string>::size_type i=2;i!=s1.size();i++){			
			if(s1[i]==transfer||findfrom==true){ //将从再一条公交线路中从from能够到底的站名放入deque中
				qs.push_back(s1[i]);
                findfrom=true;			    
				length=s.direArrive(s1[i],to);//经过s1[i]做第二次中转能够到达
				if(length.pathlength < 300){
					 find=true;
					 cout << endl   <<"你坐的路线是(你至少要转车两次)第"  << n++ << "种方案 :"<< endl;
					 cout << pathnumber << " 路车 " << direction << "(途径 " <<s.direArrive(from,transfer).pathlength << "个站 ):"; 
					 cout << from << " --> " << transfer << endl;
					 cout << qs[0]  << " 路车 " << qs[1]  << "(途经 " << s.direArrive(transfer,s1[i]).pathlength << " 个站) : " ;
					 cout << transfer   <<" -->  " << s1[i]  << endl; 
					 cout <<length.pathnumber << " 路车 ";
					 if(length.direction==1) 
						cout << "上行" ;
					 else
						cout << "下行";
					 cout << "(途经 " << length.pathlength << " 个站) : " << s1[i] << " -->  " << to << endl;						 
				}
			}
		}
		qs.clear();
	}
	if(find){		
		return true;
	}else
		return false ;
}

bool Link_station::leastchx3(string from,string to,Traffic_Map& s)
{
	const   double   begin=(double)clock()/CLK_TCK;
	bool find=false;
	for(vector<vector<string> >::iterator vster=s.svecsta.begin();vster!=s.svecsta.end();vster++){
		vector<string> s1(*vster);  //存入公交线路名及是上行，还是下行
		deque<string > qs;
		qs.push_back(s1[0]);
		qs.push_back(s1[1]);
		bool findfrom=false;
		for(vector<string>::size_type i=2;i!=s1.size();i++){			
			if(s1[i]==from||findfrom==true){ //将从再一条公交线路中从from能够到底的站名放入deque中
				qs.push_back(s1[i]);
                findfrom=true;	
                if(leastchx2(qs[0],qs[1],from,s1[i],to,s)) //用是s1[i]做第一次中转能够到达，调用leastchx2时函数又中转一次
					find=true;
			}
		}
		qs.clear();
	}
	if(find){
		const   double   end=(double)clock()/CLK_TCK;
	    cout << endl <<"搜索总共用时" << end -begin  <<" s"<< endl;
		return true;