222222.cpp

北京公交线路选择问题 功能完全实现的工交算法

create   table   Line(lineID   int,state   nvarchar   
  (10),orderid   int,primary   key(lineID,orderid))   
  insert   Line   select   1,'鼓楼'     ,1   
  union     all     select   1,'新街口',2   
  union     all     select   1,'汽车站',3   
  union     all     select   1,'火车站',4   
  union     all     select   2,'新街口',1   
  union     all     select   2,'飞机场',2   
  union     all     select   2,'天安门',3   
  union     all     select   3,'天安门',1   
  union     all     select   3,'石门坎',2   
  union     all     select   3,'驾校'     ,3   
  go   
    
  --   查询的存储过程   
  create   proc   p_qry   
  @begin_state   nvarchar(10),   
  @end_state   nvarchar(10)   
  as   
  set   nocount   on   
  declare   @l   int   
  --正向搜索线路   
  set   @l=0   
  --把数据插入临时表   
  select   lineID,line=cast('('+rtrim(lineID)   
  +':   '+rtrim(state)   as   varchar(8000))   
  ,state,orderid=orderid+1,level=@l,gid=1   
  into   #t   from   Line   where   state=@begin_state   
  while   @@rowcount>0   and   not   exists(select   *   from     
  #t   where   state=@end_state)   and   exists(select   *   from   line   where   state=@end_state)   
  begin   
  set   @l=@l+1   
  --   如果循环次数大于所有站点数，则跳出循环   
  if   @l>(select   count(*)   from   line)   
  break   
  else     
  --把数据插入临时表   
  insert   #t(line,lineID,state,orderid,level,gid)   
  select     
  line=a.line+case   
  when   a.lineID=b.lineID   
  then   '->'+rtrim(b.state)   
  else   ')   =>   ('+rtrim(b.lineID)+':   '+rtrim(b.state)   
  end,   
  lineID=b.lineID,state=b.state,orderid=b.orderid+1,   
  @l,   
  case   when   a.lineID=b.lineID   then   a.gid   else     
  a.gid+1   end   
  from   #t   a,Line   b   
  where   a.level=@l-1   
  and(   
  a.lineID=b.lineID   and   a.orderid=b.orderid   
  or     
  a.state=b.state   and   a.lineID<>b.lineID)   
  continue   
  end   
    
  --     
  --   如果正向思索存在线路，则选择出来   
  if   exists(select   起点站=@begin_state   
  ,终点站=@end_state   
  ,转车次数=gid   
  ,经过站数=case   when   gid<3   then   @l   else   @l-gid+2     
  end   
  ,乘车线路=line+')'     
  from   #t   where   level=@l   and   state=@end_state)   
    
  begin   
  select   起点站=@begin_state   
  ,终点站=@end_state   
  ,转车次数=gid   
  ,经过站数=case   when   gid<3   then   @l   else   @l-gid+2     
  end   
  ,乘车线路=line+')'     
  from   #t   where   level=@l   and   state=@end_state   
    
  end   
  --如果正向搜索不存在线路，则反向搜索   
  if   not   exists(select   起点站=@begin_state   
  ,终点站=@end_state   
  ,转车次数=gid   
  ,经过站数=case   when   gid<3   then   @l   else   @l-gid+2     
  end   
  ,乘车线路=line+')'     
  from   #t   where   level=@l   and   state=@end_state)   
    
  begin   
    
  --反向搜索线路向搜索线路   
    
    
  set   nocount   on   
    
  set   @l=0   
  select   lineID,line=cast('('+rtrim(lineID)   
  +':   '+rtrim(state)   as   varchar(8000))   
  ,state,orderid=orderid-1,level=@l,gid=1   
  into   #m   from   Line   where   state=@begin_state   
  while   @@rowcount>0   and   not   exists(select   *   from     
  #m   where   state=@end_state)   and   exists(select   *   from   line   where   state=@end_state)   
  begin   
  set   @l=@l+1   
  if   @l>(select   count(*)   from   line)   
  break   
  else     
  insert   #m(line,lineID,state,orderid,level,gid)   
  select     
  line=a.line+case   
  when   a.lineID=b.lineID   
  then   '->'+rtrim(b.state)   
  else   ')   =>   ('+rtrim(b.lineID)+':   '+rtrim(b.state)   
  end,   
  lineID=b.lineID,state=b.state,orderid=b.orderid-1,   
  @l,   
  case   when   a.lineID=b.lineID   then   a.gid   else     
  a.gid+1   end   
  from   #m   a,Line   b   
  where   a.level=@l-1   
  and(   
  a.lineID=b.lineID   and   a.orderid=b.orderid   
  or     
  a.state=b.state   and   a.lineID<>b.lineID)   
  continue   
  end   
  select   起点站=@begin_state   
  ,终点站=@end_state   
  ,转车次数=gid   
  ,经过站数=case   when   gid<3   then   @l   else   @l-gid+2     
  end   
  ,乘车线路=line+')'     
  from   #m   where   level=@l   and   state=@end_state   
    
    
    
  --   从正反两面判断是否存在路线，如果不存在，则提示！   
  if   not   exists(select   起点站=@begin_state   
  ,终点站=@end_state   
  ,转车次数=gid   
  ,经过站数=case   when   gid<3   then   @l   else   @l-gid+2     
  end   
  ,乘车线路=line+')'     
  from   #t   where   level=@l   and   state=@end_state)     
  and     
  not   exists(select   起点站=@begin_state   
  ,终点站=@end_state   
  ,转车次数=gid   
  ,经过站数=case   when   gid<3   then   @l   else   @l-gid+2     
  end   
  ,乘车线路=line+')'     
  from   #m   where   level=@l   and   state=@end_state)     
    
  --   print   '没有符合条件的记录，请重新输入数据！！！'     
  begin   
  print   '没有找到符合条件的记录'   
  end   
    
    
  end   
    
    
  go   
    
  --调用     
    
    
    
  exec   p_qry   '石门坎','鼓楼'   
  exec   p_qry   '火车站','鼓楼'   
  exec   p_qry   '鼓楼','石门坎'   
  exec   p_qry   '石门坎','鼓楼'   
  go   
    
  --   删除测试   
  drop   table   Line   
  drop   proc   p_qry