📄 city.java
字号:
// ls.clear();
// }
// return ls;
// }
//
//
// /**
// * 方法名称：getLineByStation<p>
// * 方法功能：根据站点名称获取经过此站点的路线 <p>
// * 参数说明：@param st1 要查询的起始站点
// * 参数说明：@param st2 要查询的结束站点
// * 参数说明：@return <p>
// * 返回：ArrayList 路线集<p>
// * 作者：luoc
// * 日期：2005-2-28
// **/
// public ArrayList getLineByStation(String st1,String st2)
// {
// ArrayList lnTmp=new ArrayList();//临时用的ArrayList对象
// ArrayList lns=new ArrayList();//返回路线的结果集
//
// //进行路线Id和Lines中的位置转换
// ArrayList lnsSt1=(ArrayList)CityStations.get(st1);//经过站点st1的路线
// ArrayList lnsSt2=(ArrayList)CityStations.get(st2);//经过站点st2的路线
// if(lnsSt1.size()==0 || lnsSt2.size()==0)//如果站点st1或站点st2不存在则返回
// {
// return lns;
// }
// for(int i=0;i<lnsSt1.size();i++)
// {
// lnTmp.add(String.valueOf(getLineIdxById((String)lnsSt1.get(i))));//将路线Id转换为路线在Lines中的位置
// }
// lnsSt1=(ArrayList)lnTmp.clone();//获取临时对象的克隆
// lnTmp.clear();//清空临时对象
//
// for(int i=0;i<lnsSt2.size();i++)
// {
// lnTmp.add(String.valueOf(getLineIdxById((String)lnsSt2.get(i))));//将路线Id转换为路线在Lines中的位置
// }
// lnsSt2=(ArrayList)lnTmp.clone();//获取临时对象的克隆
// lnTmp.clear();//清空临时对象
//
// //开始进行搜索
// return lns;
// }
// 以下为采用图搜索算法进行的路线查询
/**
* 方法名称：getLineByStation<p>
* 方法功能：根据站点名称获取经过该站点的路线 <p>
* 参数说明：@param st 要查询的站点名称
* 参数说明：@return <p>
* 返回：ArrayList 路线集<p>
* 作者：luoc
* 日期：2005-2-28
**/
public ArrayList getLineByStation(String st)
{
ArrayList lns=new ArrayList();
ArrayList lines=(ArrayList)CityStations.get(st);
if(lines==null)
{
return lns;
}
for(int i=0;i<lines.size();i++)
{
Line ln=getLineById((String)lines.get(i));//根据路线Id获取路线
lns.add(ln);
}
return lns;
}
/**
* 方法名称：getLineByStation<p>
* 方法功能：根据起始终止站点查询路线集 <p>
* 参数说明：@param st1 起始站点
* 参数说明：@param st2 终止站点
* 参数说明：@return <p>
* 返回：ArrayList 符合最少转车次数的路线Id集<p>
* 作者：luoc
* 日期：2005-3-24
**/
public ArrayList getLineByStation(String st1,String st2)
{
ArrayList lns=new ArrayList();//符合最少转车的路线集
//开始查询-------------------------
ArrayList lnSt1=getLineByStation(st1);//获取经过站点1的路线 Id
lnSt1=chgLineToIdx(lnSt1);//转换
ArrayList lnSt2=getLineByStation(st2);//获取经过站点2的路线 Id
lnSt2=chgLineToIdx(lnSt2);//转换
if(lnSt1.size()>0&&lnSt2.size()>0)//可能存在记录
{
ArrayList stSrt=new ArrayList();//起始站点
ArrayList stEnd=new ArrayList();//终止站点
for(int i=0;i<lnSt1.size();i++)
{
ArrayList stTmp=new ArrayList();
stTmp.add(lnSt1.get(i));
stSrt.add(stTmp.clone());//将路线分别写入数组中
stTmp=null;
}
for(int i=0;i<lnSt2.size();i++)
{
ArrayList stTmp=new ArrayList();
stTmp.add(lnSt2.get(i));
stEnd.add(stTmp.clone());//将路线分别写入数组中
stTmp=null;
}
lns=hasMatchLines(stSrt,stEnd);
boolean toFind=true;
ArrayList stSrtTmp=new ArrayList();//临时用于存储新生成的路线集
while(lns.size()==0 && toFind==true)//还未找到
{
stSrtTmp.clear();
toFind=false;
for(int i=0;i<stSrt.size();i++)
{
ArrayList alTmp=(ArrayList)stSrt.get(i);
//获取已添加的最后一路线下标
int i_st=Integer.parseInt((String)alTmp.get(alTmp.size()-1));//最后一路线
//查询与站点i_st有交点的路线
for(int k=0;k<getSize();k++)
{
ArrayList alTmp1=(ArrayList)alTmp.clone();
if(LineRelation[i_st][k]==1 && i_st!=k)//存在交点
{
String s_k=String.valueOf(k);
if(!lnSt1.contains(s_k))//不存在已有路线中则添加
{
lnSt1.add(s_k);
alTmp1.add(s_k);
stSrtTmp.add(alTmp1.clone());
toFind=true;
}
}
alTmp1=null;
}
}
lns=hasMatchLines(stSrtTmp,stEnd);
}
}
//转换为路线Id集
ArrayList lnsTmp=new ArrayList();
for(int i=0;i<lns.size();i++)
{
//System.out.println("路线Idxs:"+lns.get(i));
ArrayList lnTmp=chgLineIdxToId((ArrayList)lns.get(i));
lnsTmp.add(lnTmp);
}
lns=(ArrayList)lnsTmp.clone();
//结束查询-------------------------
//释放内存-----------
lnSt1=null;
lnSt2=null;
lnsTmp=null;
//-------------------
return lns;
}
/**
* 方法名称：chgLineToIdx<p>
* 方法功能：将路线集转换为对应路线位置下标Idx集<p>
* 参数说明：@param Lns 路线集
* 参数说明：@return <p>
* 返回：ArrayList 路线下标Idx集<p>
* 作者：luoc
* 日期：2005-3-24
**/
public ArrayList chgLineToIdx(ArrayList Lns)
{
ArrayList LnIdxs=new ArrayList();
for(int i=0;i<Lns.size();i++)
{
Line ln=(Line)Lns.get(i);
LnIdxs.add(String.valueOf(getLineIdxById(ln.getId())));//转换
}
Lns=null;
return LnIdxs;
}
/**
* 方法名称：chgLineIdxToId<p>
* 方法功能：将路线位置下标Idx集转换为对应路线Id集<p>
* 参数说明：@param LnIdx
* 参数说明：@return <p>
* 返回：ArrayList 路线Id集<p>
* 作者：luoc
* 日期：2005-3-24
**/
public ArrayList chgLineIdxToId(ArrayList LnIdx)
{
ArrayList LnIds=new ArrayList();
for(int i=0;i<LnIdx.size();i++)
{
LnIds.add(getLine(Integer.parseInt((String)LnIdx.get(i))+1).getId());//路线Id
}
return LnIds;
}
/**
* 方法名称：hasSameElement<p>
* 方法功能：比较集合ls1和ls2中是否有相同的元素<p>
* 参数说明：@param ls1
* 参数说明：@param ls2
* 参数说明：@return <p>
* 返回：boolean <p>
* 作者：luoc
* 日期：2005-3-24
**/
public boolean hasSameElement(ArrayList ls1,ArrayList ls2)
{
for(int i=0;i<ls1.size();i++)
{
if(ls2.contains(ls1.get(i)))
{
return true;
}
}
return false;
}
/**
* 方法名称：hasMatchLines<p>
* 方法功能：比较数组st和ed中是否有有相同记录，有则返回集合组 <p>
* 参数说明：@param st
* 参数说明：@param ed
* 参数说明：@return <p>
* 返回：ArrayList 转车次数最少的路线集<p>
* 作者：luoc
* 日期：2005-3-24
**/
protected ArrayList hasMatchLines(ArrayList st,ArrayList ed)
{
ArrayList Lines=new ArrayList();
for(int i=0;i<st.size();i++)//st
{
for(int j=0;j<ed.size();j++)//ed
{
ArrayList st1=(ArrayList)st.get(i);
ArrayList ed1=(ArrayList)ed.get(j);
if(hasSameElement(st1,ed1))//存在，则表示打到合适路径
{
ArrayList Lns=new ArrayList();
for(int k=0;k<st1.size();k++)
{
Lns.add(st1.get(k));//加入st1的路线
}
for(int k=0;k<ed1.size();k++)
{
//将不在Lns中的路线加入
if(!Lns.contains(ed1.get(k)))
{
Lns.add(ed1.get(k));//加入ed1的路线
}
}
Lines.add(Lns);//加入其中一个转车次数最少的路线集
}
}
}
return Lines;
}
/**
* 比较两条路线是否有相同的站点有则返回true，无则返回false
* 如果比较的两条路线号一致则返回false
* @param ln1 Line
* @param ln2 Line
* @return boolean
*/
public boolean hasSameStation(Line ln1,Line ln2)
{
if(ln1.getId().equals(ln2.getId()))//两条路线号一致就返回false
{
return false;
}
for(int i=1;i<=ln1.getSize();i++)
{
if(ln2.getStation(ln1.getStation(i).getName())!=null)//存在相同的站点
{
return true;
}
}
return false;
}
/**
* 比较两条路线是否有相同的站点有则返回true，无则返回false
* 如果比较的两条路线号一致则返回false ---模糊查询
* @param ln1 Line
* @param ln2 Line
* @return boolean
*/
public boolean hasSameStationLike(Line ln1,Line ln2)
{
if(ln1.getId().equals(ln2.getId()))//两条路线号一致就返回false
{
return false;
}
for(int i=1;i<=ln1.getSize();i++)
{
ArrayList ls=ln2.getStationLike(ln1.getStation(i).getName());
if(ls.size()>0)//存在相同的站点
{
return true;
}
}
return false;
}
/**
* 方法名称：createStationMap<p>
* 方法功能：将城市中的所有站点保存到图结构中，用于搜索，结构为key:站点名称,values:经过该站点的路线Id <p>
* 参数说明： <p>
* 返回：void <p>
* 作者：luoc
* 日期：2005-2-28
**/
public void createStationMap()
{
CityStations.clear();//清空原图
//System.out.println("Line size="+getSize());
for(int i=1;i<=getSize();i++)//将所有路线中的站加进去
{
Line ln=getLine(i);
//System.out.println(i+" station size="+ln.getSize());
for(int j=1;j<=ln.getSize();j++)//路线中的站点
{
Station st=ln.getStation(j);
ArrayList sary=(ArrayList)CityStations.get(st.getName());//查看是否已经有该站
//System.out.println("Map: "+st.getName());
if(sary==null)//原不存在
{
sary=new ArrayList();
sary.add(ln.getId());//加入路线号
CityStations.put(st.getName(),sary);
}else//已经存在，则直接加一路线号
{
sary.add(ln.getId());
}
}
}
}
/**
* 方法名称：getStationMap<p>
* 方法功能：返回城市中所有站点的图 <p>
* 参数说明：@return <p>
* 返回：Hashtable <p>
* 作者：luoc
* 日期：2005-2-28
**/
public Hashtable getStationMap()
{
return CityStations;
}
/**
* 方法名称：createLineRelation<p>
* 方法功能：生成路线之间的关系图，数组中的[i][j] i、j分别指对应路线的位置而非路线Id（编号）<p>
* 参数说明： <p>
* 返回：void <p>
* 作者：luoc
* 日期：2005-2-28
**/
public void createLineRelation()
{
LineRelation=new int [getSize()][getSize()];
for(int i=0;i<getSize();i++)
{
LineRelation[i][i]=1;
for(int j=i+1;j<getSize();j++)
{
if(hasSameStation(getLine(i+1),getLine(j+1)))
{
LineRelation[i][j]=1;
}else
{
LineRelation[i][j]=0;
}
}
}
//填充下三角
for(int i=getSize()-1;i>=0;i--)
{
for(int j=i-1;j>=0;j--)
{
LineRelation[i][j]=LineRelation[j][i];
}
}
/*/输出
for(int i=0;i<getSize();i++)
{
for(int j=0;j<getSize();j++)
{
System.out.println("LineRelation["+i+"]["+j+"]="+LineRelation[i][j]);
}
}//*/
}
/**
* 重载方法：clone <p>
* 参阅：@see java.lang.Object#clone() <p>
* 参数说明：@return <p>
**/
public Object clone()
{
try
{
return super.clone();
}catch(CloneNotSupportedException e)
{
return null;
}
}
/**
* 重载方法：toString <p>
* 参阅：@see java.lang.Object#toString() <p>
* 参数说明：@return 对象描述<p>
**/
public String toString()
{
return "City: Id="+Id+", Name="+Name+", Lines size="+Lines.size()+"\r\n";
}
/*城市属性，全局变量*/
private String Id=null;//城市编号
private String Name=null;//城市名称
private ArrayList Lines=null;//城市公交路线
private Hashtable CityStations=null;//保存城市中所有站点数据 构成一个图
private int LineRelation[][];//路线之间的关系图，0表示路线之间有交点，1表示路线之间有交点
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -