zuoye.cpp

交通路线最优路径寻找程序

#include<iostream.h>
#include<string.h>


struct citynode
{
	char cityname[15];           //城市名称
	char toolname[15];           //交通工具及代码

	double  usetime;             //花费时间
	double   money;              //票价
};
	citynode beijing[15];        //采用结构数组来描述类似链表的功能
	citynode tianjin[14];
	citynode shanghai[16];
	citynode guangzhou[13];
	citynode baotou[14];
	citynode haerbin[19];
	citynode dalian[13];
	citynode shenyang[16];
	citynode shijiazhuang[15];
	citynode qinhuangdao[13];
struct storecity              //用来存储搜索出来的最短路径节点城市路线
{
	char city[15];            //城市
	char tool[15];            //工具
	double sum;               //总数money or time
};

struct outnode                //存储已经经过的城市节点
{
	char city[15];
};

outnode outcity[11];

bool out(char dd[15])                           //判断是否已经走过该城市
{
	for(int p=0;strcmp(outcity[p].city,"");p++)
		if(!strcmp(outcity[p].city,dd))
			return 1;
		return 0;
}

bool empty(storecity text[11])                  //判断存储数组是否为空
{ 
	if(text[0].sum==-1)
		return 1;
	else
		return 0;
}

storecity lastcity(storecity test[11])          //返回存储数组存储的最后一个城市节点
{
	int i;
	for( i=1;strcmp(test[i].city,"");i++)
		;
	return test[i-1];
}

bool find(storecity full[11],char hh[15])        //在存储链中找到已知城市是否在链中 
{
	for(int j=1;strcmp(full[j].city,"");j++)
		if(!strcmp(full[j].city,hh))
			return 1;
		return 0;
}

void print(storecity weneed[11])                 //打印函数，输出路线
{
	for(int n=1;strcmp(weneed[n].city,"");n++)
		cout<<" -> "<<weneed[n].city<<" "<<weneed[n].tool;
}

storecity searchsmallmoney(char aa[15]);        //查找票价最小节点城市函数
storecity searchsmalltime(char aa[15]);         //查找时间最小节点城市函数
void construction();                            //构建图的函数
void findaway(char begin[15],char over[15],char welike[15]);
//以下是主函数 
void main()
{
	
	char start[15],end[15];
	char like[15];
    int findway=1;
	 construction();

	while (findway)                   //输入零后结束该程序
	{
	  
	    //初始化结构数组为空
	   cout<<"Input start city:";
	   cin>>start;                    //输入开始城市
	   cout<<"Input end city:";
	   cin>>end;                      //目的城市
	   cout<<"Chouse saving money(m) or time(t)?:";
	   cin>>like;                     //策略要求
	   strcpy(outcity[0].city,start);
	   for(int w=1;w<11;w++)
	      strcpy(outcity[w].city,"");
	   findaway(start,end,like);
	   cout<<"If you want use this software again,please do not enter '0'"<<endl;
	   cin>>findway;
	 }
}

storecity searchsmallmoney(char aa[15])    //选择最小票价节点城市函数
{
	double small=10000;

	storecity bb;

	 if(!strcmp("shanghai",aa))
			{
				for(int g=1;strcmp(shanghai[g].cityname,"");g++)
				if(out(shanghai[g].cityname))
					;
				else if(small>shanghai[g].money)
				{
					small=shanghai[g].money;
					strcpy(bb.city,shanghai[g].cityname);
					strcpy(bb.tool,shanghai[g].toolname);
			    	bb.sum=small;
				}
				return bb;
			}
		else if(!strcmp("beijing",aa))
			{
				for(int g=1;strcmp(beijing[g].cityname,"");g++)
				if(out(beijing[g].cityname))
					;
				else if(small>beijing[g].money)
				{
					small=beijing[g].money;
					strcpy(bb.city,beijing[g].cityname);
					strcpy(bb.tool,beijing[g].toolname);
			    	bb.sum=small;
				}
				return bb;
			}
		else if(!strcmp("tianjin",aa))
			{
				for(int g=1;strcmp(tianjin[g].cityname,"");g++)
				if(out(tianjin[g].cityname))
					;
				else if(small>tianjin[g].money)
				{
					small=tianjin[g].money;
					strcpy(bb.city,tianjin[g].cityname);
					strcpy(bb.tool,tianjin[g].toolname);
			    	bb.sum=small;
				}
				return bb;
			}
		 else if(!strcmp("guangzhou",aa))
			{
				for(int g=1;strcmp(guangzhou[g].cityname,"");g++)
				if(out(guangzhou[g].cityname))
					;
				else if(small>guangzhou[g].money)
				{
					small=guangzhou[g].money;
					strcpy(bb.city,guangzhou[g].cityname);
					strcpy(bb.tool,guangzhou[g].toolname);
			    	bb.sum=small;
				}
				return bb;
			}
		 else
			 if(!strcmp("shijiazhuang",aa))
			{
				for(int g=1;strcmp(shijiazhuang[g].cityname,"");g++)
				if(out(shijiazhuang[g].cityname))
					;
				else if(small>shijiazhuang[g].money)
				{
					small=shijiazhuang[g].money;
					strcpy(bb.city,shijiazhuang[g].cityname);
					strcpy(bb.tool,shijiazhuang[g].toolname);
			    	bb.sum=small;
				}
				return bb;
			}

		 else if(!strcmp("baotou",aa))
			{
				for(int g=1;strcmp(baotou[g].cityname,"");g++)
				if(out(baotou[g].cityname))
					;
				else if(small>baotou[g].money)
				{
					small=baotou[g].money;
					strcpy(bb.city,baotou[g].cityname);
					strcpy(bb.tool,baotou[g].toolname);
			    	bb.sum=small;
				}
				return bb;
			}
		   else if(!strcmp("qinhuangdao",aa))
			{
				for(int g=1;strcmp(qinhuangdao[g].cityname,"");g++)
				if(out(qinhuangdao[g].cityname))
					;
				else if(small>qinhuangdao[g].money)
				{
					small=qinhuangdao[g].money;
					strcpy(bb.city,qinhuangdao[g].cityname);
					strcpy(bb.tool,qinhuangdao[g].toolname);
			    	bb.sum=small;
				}
				return bb;
			}
		   else if(!strcmp("dalian",aa))
			{
				for(int g=1;strcmp(dalian[g].cityname,"");g++)
				if(out(dalian[g].cityname))
					;
				else if(small>dalian[g].money)
				{
					small=dalian[g].money;
					strcpy(bb.city,dalian[g].cityname);
					strcpy(bb.tool,dalian[g].toolname);
			    	bb.sum=small;
				}
				return bb;
			}
			else if(!strcmp("shenyang",aa))
			{
				for(int g=1;strcmp(shenyang[g].cityname,"");g++)
				if(out(shenyang[g].cityname))
					;
				else if(small>shenyang[g].money)
				{
					small=shenyang[g].money;
					strcpy(bb.city,shenyang[g].cityname);
					strcpy(bb.tool,shenyang[g].toolname);
			    	bb.sum=small;
				}
				return bb;
			}
			else if(!strcmp("haerbin",aa))
			{
		    	for(int g=1;strcmp(haerbin[g].cityname,"");g++)
				if(out(haerbin[g].cityname))
					;
				else if(small>haerbin[g].money)
				{
					small=haerbin[g].money;
					strcpy(bb.city,haerbin[g].cityname);
					strcpy(bb.tool,haerbin[g].toolname);
			    	bb.sum=small;
				}
				return bb;
			}
		 else
			 ;

}
storecity searchsmalltime(char aa[15])           //选择最小时间节点城市函数
{
	double small=10000;

	storecity bb;
	
	    if(!strcmp("shanghai",aa))
			{
				for(int g=1;strcmp(shanghai[g].cityname,"");g++)
				if(out(shanghai[g].cityname))
					;
				else if(small>shanghai[g].usetime)
				{
					small=shanghai[g].usetime;
					strcpy(bb.city,shanghai[g].cityname);
					strcpy(bb.tool,shanghai[g].toolname);
			    	bb.sum=small;
				}
				return bb;
			}
		 else if(!strcmp("beijing",aa))
			{
				for(int g=1;strcmp(beijing[g].cityname,"");g++)
				if(out(beijing[g].cityname))
					;
				else if(small>beijing[g].usetime)
				{
					small=beijing[g].usetime;
					strcpy(bb.city,beijing[g].cityname);
					strcpy(bb.tool,beijing[g].toolname);
			    	bb.sum=small;
				}
				return bb;
			}
	    else if(!strcmp("tianjin",aa))
			{
				for(int g=1;strcmp(tianjin[g].cityname,"");g++)
				if(out(tianjin[g].cityname))
					;
				else if(small>tianjin[g].usetime)
				{
					small=tianjin[g].usetime;
					strcpy(bb.city,tianjin[g].cityname);
					strcpy(bb.tool,tianjin[g].toolname);
			    	bb.sum=small;
				}
				return bb;
			}
		 else if(!strcmp("guangzhou",aa))
			{
				for(int g=1;strcmp(guangzhou[g].cityname,"");g++)
				if(out(guangzhou[g].cityname))
					;
				else if(small>guangzhou[g].usetime)
				{
					small=guangzhou[g].usetime;
					strcpy(bb.city,guangzhou[g].cityname);
					strcpy(bb.tool,guangzhou[g].toolname);
			    	bb.sum=small;
				}
				return bb;
			}
		else if(!strcmp("shijiazhuang",aa))
			{
				for(int g=1;strcmp(shijiazhuang[g].cityname,"");g++)
				if(out(shijiazhuang[g].cityname))
					;
				else if(small>shijiazhuang[g].usetime)
				{
					small=shijiazhuang[g].usetime;
					strcpy(bb.city,shijiazhuang[g].cityname);
					strcpy(bb.tool,shijiazhuang[g].toolname);
			    	bb.sum=small;
				}
				return bb;
			}

		  else if(!strcmp("baotou",aa))
			{
				for(int g=1;strcmp(baotou[g].cityname,"");g++)
				if(out(baotou[g].cityname))
					;
				else if(small>baotou[g].usetime)
				{
					small=baotou[g].usetime;
					strcpy(bb.city,baotou[g].cityname);
					strcpy(bb.tool,baotou[g].toolname);
			    	bb.sum=small;
				}
				return bb;
			}
		 else if(!strcmp("qinhuangdao",aa))
			{
				for(int g=1;strcmp(qinhuangdao[g].cityname,"");g++)
				if(out(qinhuangdao[g].cityname))
					;
				else if(small>qinhuangdao[g].usetime)
				{
					small=qinhuangdao[g].usetime;
					strcpy(bb.city,qinhuangdao[g].cityname);
					strcpy(bb.tool,qinhuangdao[g].toolname);
			    	bb.sum=small;
				}
				return bb;
			}
		 else if(!strcmp("dalian",aa))
			{
				for(int g=1;strcmp(dalian[g].cityname,"");g++)
				if(out(dalian[g].cityname))
					;
				else if(small>dalian[g].usetime)
				{
					small=dalian[g].usetime;
					strcpy(bb.city,dalian[g].cityname);
					strcpy(bb.tool,dalian[g].toolname);
			    	bb.sum=small;
				}
				return bb;
			}
		 else if(!strcmp("shenyang",aa))
			{
				for(int g=1;strcmp(shenyang[g].cityname,"");g++)
				if(out(shenyang[g].cityname))
					;
				else if(small>shenyang[g].usetime)
				{
					small=shenyang[g].usetime;
					strcpy(bb.city,shenyang[g].cityname);
					strcpy(bb.tool,shenyang[g].toolname);
			    	bb.sum=small;
				}
				return bb;
			}
		else if(!strcmp("haerbin",aa))
			{
		    	for(int g=1;strcmp(haerbin[g].cityname,"");g++)
				if(out(haerbin[g].cityname))
					;
				else if(small>haerbin[g].usetime)
				{
					small=haerbin[g].usetime;
					strcpy(bb.city,haerbin[g].cityname);
					strcpy(bb.tool,haerbin[g].toolname);
			    	bb.sum=small;
				}
				return bb;
			}
		 else
			 ;
	
}

void construction()                             //用于构建初始的图结构
{


	strcpy(beijing[0].cityname,"beijing");      //数组第一位存储出发城市名称北京
	strcpy(beijing[0].toolname,"");
	beijing[0].usetime=0;
	beijing[0].money=0;
	strcpy(beijing[1].cityname,"guangzhou");    //以下为与北京相接连的城市
	strcpy(beijing[1].toolname,"飞机fm2275");
	beijing[1].usetime=3;