#include<iostream.h>
#include<fstream.h>
#include<string.h>
#include<math.h>
///* change 是用于轉一次車的情況  *///
struct change/////標記中轉一次時由起點到終點的所有屬性
{
	char round[20];////中轉點名稱
	char begin_line[20];////起始到中轉點要坐的車號
	int begin_id;/////起點到中轉的id號
	char end_line[20];///記錄中轉到終點的車號
	int end_id;////中轉到終點的id號
	int lu_cheng;/////要經過的路程數
	
};

struct two_to_out
{
	int my_id;////記錄實現起點到終點的方案的ID號

	char begin_to_zhongzhuan1[20];/////起點到中轉1所要經過的公交路線
//	int begin_to_zhongzhuan1_id;/////起點到中轉1所要經過的公交路線的ID號
	int begin_to_zhongzhuan1_begin_num;/////在起點到中轉1的公交線路中，起點站在這個公交線路中的位置
	int begin_to_zhongzhuan1_end_num;/////在起點到中轉1的公交線路中,中轉1在這個公交線路中的位置
//	char begin_to_zhongzhuan1_stage[50][20];//////起點到中轉線路所要經過的公交站點的名字
	int begin_to_zhongzhuan1_stage_flag;/////記錄實際上從起點到中轉1有多少公交站臺
	
	char zhongzhuan1_to_zhongzhuan2[20];/////中轉1到中轉2的公交路線
//	int zhongzhuan1_to_zhongzhuan2_id;//////中轉1到中轉2的公交路線的ID號
	int zhongzhuan1_to_zhongzhuan2_begin_num;/////在中轉1到中轉2的路線中，中轉1在整個中間路線中的位置
	int zhongzhuan1_to_zhongzhuan2_end_num;/////在中轉1到中轉2的路線中，中轉2在整個公交線路中的位置
//	char zhongzhuan1_to_zhongzhuan2_stage[50][20];////中轉1到中轉2所要經過的站點的名字
	int zhongzhuan1_to_zhongzhuan2_stage_flag;/////中轉1到中轉2實際上要經過的站點的數目
	
	char zhongzhuan2_to_end[20];////中轉2到終點的公交路線的名字	
//	int zhongzhuan2_to_end_id;/////中轉2到終點的公交路線的ID號
	int zhongzhuan2_to_end_begin_num;////在中轉2到終點的公交路線中，中轉2所處的位置
	int zhongzhuan2_to_end_end_num;////在中轉2到終點的公交路線中，終點所處的位置
//	char zhongzhuan2_to_end_stage[50][20];/////中轉2到終點所經過的公交站點的名字
	int zhongzhuan2_to_end_stage_flag;//////中轉2到終點實際上經過的站點的數目
	
	char zhongzhuan1_stage[20];///////中轉1的站臺名字
		
	char zhongzhuan2_stage[20];/////中轉2的展臺名字
	
	int begin_to_end_distance;/////起點到終點所要經過的站臺總數目
	
};


two_to_out final_out[600];///////用于最后的數據的輸出，存放的是起點到終點需要轉兩次車的所有方案，假設最多兩百種
int final_out_flag=0;/////記錄實際上輸出的方案的數目，和上面的數組是相對應的


////***以下的結構體的定義是為了轉車兩次的情況服務**///
struct station_change_bus
{
	int change_line_num;//////記錄從起點或終點到站臺change_round[20]的所有可能的公交路線的數量
	char change_line_name[30][20];/////由起點或終點到中轉的公交路線名字/*和下面的change_line_id 是一一對應的*/
	int change_line_id[30];////由起點或者終點到中轉的公交路線ID號	   /*和上面的change_line_name 是一一對應的*/
	char change_round[20];////中轉站的名字
	
	int qidian_stage_num[30];////起點在當前公交線路中的位置，即num    /*和上面的一一對應，由于同一個起點或終點站在不同的公交線路中所對應的站號也不同*/
	int zhongdian_stage_num[30];//////中轉1在當前公交線路中的位置   /*和上面的相對應，由于同一個中轉在不同的公交線路中所對應的站號不同*/


	int change_round_id;////對應于上面的中轉站的ID號
	int distance[20];////由到中轉所要的距離								/*和上面的相對應*/
};

///*  change_twice 是用于轉兩次車的情況  *///
struct change_twice
{
	int my_id;////記錄在轉兩次的線路選擇中的id號，通過輸入id號就可以得到轉兩次車的乘車方案
	
	station_change_bus begin_to_change1[500];//////假設從起點到中轉1的方案總數至多為500個，此時中轉1的站臺還沒有確定
	int begin_to_change1_flag;////標記實際上從起點到中轉1的方案數目，初始值為0
	
	char change_line2[20];////由第一道中轉站到第二道中轉所要的公交路線的名字，為最早得到的值
	int change_id2;/////第一道中轉到第二段中轉的公交車的ID號，即change_line2[20]的id號
	
	station_change_bus end_to_change2[500];///////從終點到中轉2的方案，至多為500個，此時中轉2的站臺還沒確定
	int end_to_change2_flag;////標記實際上從終點到中轉2的方案數目，初始值為0
	
	int lu_cheng[500];/////總共要經過的站臺的數目
	
};
change_twice change_two[600];///// 支持最多的轉兩路車的情況有六百種方案
int change_two_flag=0;/////標記實際的中轉路線的條數
struct together
{
	char way[20];////標記是哪一路車
	int num;////標記著一路車在整個路線的位置
};

char input1[20];////
char input2[20];////兩個字符數組，用于存放兩個輸入的字符

struct station
{
	char name[20];////站點的名字
	together biaoji[100];///包括車號和站點的排序
	int num;////標記已經有了多少個站臺庫，相當于ID號
	int line_in;////標記有了多少條線路入棧
	int quan;/////比較在模糊算法中的比較權值
	//	int way[100];////經過站點的車的車號
	//	int biaoji[200];////biaoji數組的作用是標明當前站臺是某一條公交線的正向第幾站
	//	station *next;///指向下一個站點
};

struct bus
{
	
	char name[20];////公交車的車號
	char line[100][20];///////記錄這一條公交線所經過的車站的名字
	int geshu;////記錄這一條線共有多少條站
	int id;/////用于記錄本站在bus_line數組中的標號
	
};
station stage[3000];
bus bus_line[600];
int stage_num=0;////record tmpe stage
int bus_num=0;///record temp bus

///*以下函數的作用是根據輸入的公交線路的名字來確定此公交線路的id號*///
int return_bus_id(char *p)
{
	for(int light0=0;light0<=bus_num;light0++)
	{
		int tmp_light1;
		tmp_light1=strcmp(bus_line[light0].name,p);
		if(tmp_light1==0)
		{
			return bus_line[light0].id;
			
		}
		
	}
}

///** 以下函數的作用是根據輸入的站臺的名字來返回站臺的ID號    **///
int return_stage_id(char *p)
{

	for(int tmp_use=0;tmp_use<=stage_num;tmp_use++)////遍歷所有的站點
	{
		int tmp_me;
		tmp_me=strcmp(stage[tmp_use].name,p);
		if(tmp_me==0)
		{
		
		return stage[tmp_use].num;///////返回ID號
		
		}
	
	
	}
	return -1;
}

///***以下函數的作用是根據一條公交線路中的起始位置和終了位置，輸出處于期間的公交站點的名字**////
void output_stage_with_line(int start_num,int end_num,int bus_in_id)
{	
	if(start_num>end_num)/////如果起始的站牌號大于終了的站牌號
	{
		int out_enter_here=0;

		for(int wjs0=start_num;wjs0>=end_num;wjs0--)
		{
			out_enter_here++;
			if(out_enter_here%6==0)cout<<endl;///每6個站點一行輸出一個回車
			cout<<bus_line[bus_in_id].line[wjs0]<<" ->";
		}		
		
	}
	else/////如果起始的站牌號小于終了站點的站牌號
	{
		int out_enter_here1=0;
		for(int wjs1=start_num;wjs1<=end_num;wjs1++)
		{
			out_enter_here1++;
			if(out_enter_here1%6==0)cout<<endl;/////每六個站點輸出一個回車
			cout<<bus_line[bus_in_id].line[wjs1]<<"-> ";			
		}		
	}	
}

//////////***函數的作用是產生字符串比較的權值，看他們的相似程度***////////////
int mohu(char *mohu_in,char *have)
{
	
	int tmp_num=0;
	int ret_num=0;
	int max;////數組中長度比較長的那一個的長度
	int min;////數組中長度比較短的那一個
	if(strlen(mohu_in)>=strlen(have))
	{
		
		max=strlen(mohu_in);
		min=strlen(have);
		
	}
	else
	{
		
		max=strlen(have);
		min=strlen(mohu_in);
		
		
	}
	
	for(int wife0=0;wife0<=(max-min);wife0++)////總共要比較的次數
	{
		for(int wife1=0;wife1<min;wife1++)///對于每一次比較而言所要比較的字符的數目
		{
			if(strlen(mohu_in)>=strlen(have))//////字符char0的長度大于字符串char1的情況
			{
				
				if(have[wife1]==mohu_in[wife1+wife0])
					tmp_num++;
				
			}
			else
			{
				if(mohu_in[wife1]==have[wife1+wife0])
					tmp_num++;				
			}
			
		}
		if(tmp_num>=ret_num)
			ret_num=tmp_num;
		tmp_num=0;
		
	}
	return ret_num;
	
}
///////////////////////****以上函數是模糊搜索要用到的函數*****///////////////////////////

////////****下面函數的作用是建立stage結構體和bus結構體*****////////////
void read_file(void)
{
	char ch;
	int tmp1=0;////用于記錄站牌的數字
	int tmp2=0;////用于記錄在一條公交線上的站牌數量
	int tmp3=0;////用于記錄一個站牌的字符到了第幾個
	int enable_add_line=1;////允許現在是加入到公交線路中
	
	ifstream infile;
	infile.open("公交線路.txt");
	
	while(infile>>ch)
	{	
		
		if(ch==' ')continue;/////不考慮空格在其中的作用
		if(ch==':')///////當遇到':'時表示公交線路名字的輸入結束，把輸入字符只當作字符來看
		{
			enable_add_line=0;
			continue;
		}
		
		if(enable_add_line==1)
		{
			bus_line[bus_num].name[tmp1]=ch;
			tmp1++;
			//		if(tmp1==3)tmp1=0;
			//////****首先得到站牌的號碼***/////
		}
		else
		{
			
			if(ch==',')////tmp2記錄在每一條線上的站點
			{
				tmp2++;
				tmp3=0;
			}
			else
			{
				if(ch==';')
				{
					enable_add_line=1;//////當遇到';'時表示一條公交線路的錄入結束了，允許加入到公交線的名字
					bus_line[bus_num].id=bus_num;
					
					//曹金燦改	bus_line[bus_num].num=convert(bus_line[bus_num].name);
					bus_line[bus_num].geshu=tmp2;
					bus_num++;////;為每一條線路的結束標志
					
					tmp1=0;
					tmp2=0;
					tmp3=0;
					///////***重新初始化等待下一次**//////
				}
				else
				{
					bus_line[bus_num].line[tmp2][tmp3]=ch;
					//		cout<<tmp2;
					tmp3++;
				}
				
			}