求车站中转站算法?

Question

Train 表
Name(车次)                 StartStation                     ENDStation
1522                        哈尔滨                             天津
...
TrainStation表Train_Name (对应Train 表Name)    StationId  StationName City
1522                                 1         吉林      吉林
....需求:如从哈尔滨-重庆的中转站,希望列出所有的中转站名称.
 求理想算法.

Answer 1

select n.* from train m , trainstation n where m.name = n.train_name

Answer 2

/*
Train 表
Name(车次)                 StartStation                     ENDStation
1522                        哈尔滨                             天津
...
TrainStation表
Train_Name (对应Train 表Name)    StationId  StationName City
*/
select TS.StationName from TrainStation TS join Train T on TS.Train_Name=T.Name

Answer 3

错误,应该首先找 StartStation ='哈尔滨'  ENDStation = '重庆'
但是这个没有直达,所以要处理好几条这样的路条.

Answer 4

CREATE TABLE T_Line(
ID      nvarchar(10),  --公交线路号
Station nvarchar(10),  --站点名称
Orders  int)           --行车方向(通过它反应每个站的上一个、下一个站)
INSERT T_Line 
SELECT N'8路'  ,N'站A',1 UNION ALL
SELECT N'8路'  ,N'站B',2 UNION ALL
SELECT N'8路'  ,N'站C',3 UNION ALL
SELECT N'8路'  ,N'站D',4 UNION ALL
SELECT N'8路'  ,N'站J',5 UNION ALL
SELECT N'8路'  ,N'站L',6 UNION ALL
SELECT N'8路'  ,N'站M',7 UNION ALL
SELECT N'20路' ,N'站G',1 UNION ALL
SELECT N'20路' ,N'站H',2 UNION ALL
SELECT N'20路' ,N'站I',3 UNION ALL
SELECT N'20路' ,N'站J',4 UNION ALL
SELECT N'20路' ,N'站L',5 UNION ALL
SELECT N'20路' ,N'站M',6 UNION ALL
SELECT N'255路',N'站N',1 UNION ALL
SELECT N'255路',N'站O',2 UNION ALL
SELECT N'255路',N'站P',3 UNION ALL
SELECT N'255路',N'站Q',4 UNION ALL
SELECT N'255路',N'站J',5 UNION ALL
SELECT N'255路',N'站D',6 UNION ALL
SELECT N'255路',N'站E',7 UNION ALL
SELECT N'255路',N'站F',8
GO--乘车线路查询存储过程
CREATE PROC p_qry
@Station_Start nvarchar(10),
@Station_Stop  nvarchar(10)
AS
SET NOCOUNT ON
DECLARE @l int
SET @l=0
SELECT ID,Station,
Line=CAST('('+RTRIM(ID)+': '+RTRIM(Station) as nvarchar(4000)),
Orders=Orders,
[Level]=@l
INTO # FROM T_Line
WHERE Station=@Station_Start
WHILE @@ROWCOUNT>0 
AND NOT EXISTS(SELECT * FROM # WHERE Station=@Station_Stop)
BEGIN
SET @l=@l+1
INSERT #(Line,ID,Station,Orders,[Level])
SELECT 
Line=a.Line+CASE
WHEN a.ID=b.ID THEN N'->'+RTRIM(b.Station)
ELSE N') ∝ ('+RTRIM(b.ID)
+N': '+RTRIM(b.Station) END,
b.ID,b.Station,b.Orders,@l
FROM # a,T_Line b
WHERE a.[Level]=@l-1
AND(a.Station=b.Station AND a.ID<>b.ID
OR a.ID=b.ID AND(
a.Orders=b.Orders+1
OR
a.Orders=b.Orders-1))
AND LEN(a.Line)<4000
AND PATINDEX('%[ >]'+b.Station+'[-)]%',a.Line)=0
END
SELECT N'起点站'=@Station_Start
,N'终点站'=@Station_Stop
,N'乘车线路'=Line+N')' 
FROM # 
WHERE [Level]=@l 
AND Station=@Station_Stop
IF @@ROWCOUNT =0 --如果未有可以到达的线路,则显示处理结果表备查
SELECT * FROM #
GO--调用
EXEC p_qry N'站A',N'站L'
/*--结果
起点站  终点站  乘车线路
---------- ------------ -----------------------------------------------------------
站A    站L    (8路: 站A->站B->站C->站D->站J->站L)
--*/

Answer 5

以中转石家庄1站为例:--测试数据
create table train(Name varchar(10),StartStation varchar(10),EndStation varchar(10))
insert train select '1522','哈尔滨','天津'
union all select '1526','哈尔滨','石家庄'
union all select 'T9','石家庄','重庆'
go
create table trainstation(Train_Name varchar(10),StationId int,StationName varchar(10),City varchar(10))
insert trainstation select '1526','1','哈尔滨','哈尔滨'
union all select '1526','2','石家庄','石家庄'
union all select 'T9','3','石家庄','石家庄'
union all select 'T9','4','重庆','重庆'
go--查询
SELECT a.Name as '车次',a.StartStation as '始发站',e.Name as '中转车次',e.StartStation as '中转站',g.Name as '车次',g.EndStation as '目的站'
FROM trainstation b JOIN trainstation d ON (b.Train_Name=d.Train_Name)
JOIN train a ON (b.Train_Name=a.Name)
JOIN train c ON (d.Train_Name=c.Name)
JOIN train e ON (c.EndStation=e.StartStation)
JOIN trainstation f ON (e.Name=f.Train_Name)
JOIN trainstation h ON (f.Train_Name=h.Train_Name)
JOIN train g ON (h.Train_Name=g.Name) WHERE a.StartStation='哈尔滨' AND g.EndStation='重庆' AND d.StationId>b.StationId AND h.StationId>f.StationId/*--测试结果车次  始发站  中转车次  中转站   车次  目的站 
1526  哈尔滨    T9     石家庄    T9    重庆--*/

Answer 6

从 AND NOT EXISTS(SELECT * FROM # WHERE Station=@Station_Stop)
BEGIN
开始就进入死循环了。

Answer 7

--测试数据 
create table test(Train_Name varchar(10),StationId int,StationName nvarchar(10),City nvarchar(10)) 
insert test select '1526','1',N'哈尔滨',N'哈尔滨' 
union all select '1526','2',N'石家庄',N'石家庄' 
union all select 'T9','1',N'石家庄',N'石家庄' 
union all select 'T9','2',N'长沙',N'长沙' 
union all select 'T9','3',N'重庆',N'重庆' 
union all select 'T10','1',N'重庆',N'重庆' 
union all select 'T10','2',N'成都',N'成都' 
union all select 'T12','1',N'广州',N'广州' 
union all select 'T12','2',N'南昌',N'南昌' 
union all select 'T11','1',N'北京',N'北京' 
union all select 'T11','2',N'广州',N'广州' 
union all select 'T13','1',N'哈尔滨',N'哈尔滨' 
union all select 'T13','2',N'上海',N'上海' 
go
--存储过程
create proc p (@start nvarchar(10),@end nvarchar(10))
as
--判断是否需转车
if exists(select 1  from test t 
where Train_Name in (select Train_Name from test where StationName=@start)
and StationName=@end)
begin
select distinct 坐车方案=Train_Name+':'+@start+'——'+@end  from test t 
where Train_Name in (select Train_Name from test where StationName=@start)
and StationName=@end
return
enddeclare @i int
set @i=1
--取起始车次
select *,0 i into #t  from test t 
where exists(select 1 from test where Train_Name=t.Train_Name and StationName=@start)
--计算最少中转次数
while not exists(select 1 from #t where  StationName=@end) and @i<10
begin
insert #t
select *,@i from test t 
where exists(select 1 from test a
inner join #t b on a.StationName=b.StationName 
   where a.Train_Name=t.Train_Name )
set @i=@i+1
end
if @i>=10
begin
select 坐车方案=N'中转次数过多或无车到达'
return
end
--组合坐车方案
select * into #t1 from #t  t
where not exists(select 1 from #t where Train_Name=t.Train_Name and i<t.i)
select  k=Train_Name+':'+@start+'——'+StationName+N' 转 '+
(select Train_Name from #t1 where StationName=t.StationName and i=1) ,
t=(select Train_Name from #t1 where StationName=t.StationName and i=1)
into #t2
from #t1 t 
where i=0 
  and exists(select Train_Name from #t1 where StationName=t.StationName and i=1)
set @i=1
while not exists(select 1 from test a
inner join #t2 b on a.Train_Name=b.t 
where a.StationName=@end )
begin
update a set k=k+':'+b.StationName+N' 转 '+
(select Train_Name from #t1 where StationName=b.StationName  and i=@i+1),
t=(select Train_Name from #t1 where StationName=b.StationName and i=@i+1)
from #t2 a
inner join #t1 b on a.t=b.Train_Name
where exists(select 1 from #t1 where StationName=b.StationName and i=@i+1)
set @i=@i+1
end
select 坐车方案=k+':'+@end from #t2
goexec p N'哈尔滨',N'石家庄'--直达
/*
---------------------------------
1526:哈尔滨——石家庄
*/
exec p N'上海',N'成都'--中转
/*
---------------------------------------------------------
T13:上海——哈尔滨 转 1526:石家庄 转 T9:重庆 转 T10:成都
*/
exec p N'北京',N'火星'--无法到达
/*
-----------
中转次数过多或无车到达
*/

Answer 8

先找出 所有经过或者到 重庆的 Train.
在找出 所有始发或者经过 哈尔滨的 Train. 然后取交集...

Answer 9

if exists (select name 
   from   sysobjects 
   where  name = n'answerstod' 
   and    type = 'p')
    drop procedure  answerstod
go
create procedure  answerstod(@s_id int, @d_id int, @r int, @r_line varchar(1000) output)
as
begin
  /* --本程序假设源到目的是双向的，所有的站点访问完成，则退出
   table line(源站点, 目的站点)
   1 2 -- 从顶点1 可以走到 顶点2 同时也表示顶点2 可以走到 顶点1
   1 3
   2 4
   3 4
   3 6
   4 5
   7 6
   7 9
   现举例说明 1 - > 9
   ##answerlinefrom 记录从起始站出发，可以到达哪些站，sn 表示中转次数
   0 1 2  -- 第一层可以从1 到 2 
   0 1 3  -- 也可以从 1 到 2 列举所有可能到达
   1 2 4  -- 第二层从2出发可以到达 4
   1 3 4  --      从3出发可以达到 4
   1 3 6          从3出发可以达到 6   ##answerlineto  同上
   0    7 9 -- 第一层 7 到 9
   1    6 7 -- 第二层 7 到 6
   
   第三次根据 1 3 6 <-> 1 6  7 就表示存在公共站点6 完成查找  */
  set @r_line = ''
  declare @mid_id int, @temps_id int, @tempd_id int, @rowcount int, @tempr int
  set @rowcount = 0
  set @mid_id = 0
  if @r = 0 --第一次，判断是否有直达
  begin
    if  not exists(select * from tempdb.dbo.sysobjects where name='##answerlinefrom')
    begin
      create table ##answerlinefrom(sn int not null, s_id int not null, d_id int not null)
      create  clustered  index [ix_answerlinefrom] on ##answerlinefrom(sn, d_id) on [primary] --去掉唯一索引即可
    end     if  not exists(select * from tempdb.dbo.sysobjects where name='##answerlineto')
    begin
      create table ##answerlineto(sn int not null, s_id int not null, d_id int not null)
      create  clustered  index [ix_answerlineto] on ##answerlineto(sn, s_id) on [primary]
    end     delete from ##answerlinefrom
    delete from ##answerlineto    if exists(select * from line where (s_id = @s_id and d_id = @d_id) or (d_id = @s_id and d_id = @d_id)) --存在直达
    begin
      set @r_line = @r_line + '->' + convert(varchar, @s_id)  + '->' +  convert(varchar, @d_id)
      return
    end
    else --不存在直达，生成源站可以直接到达的目的站, 同时生成可以达到目的站的源站
    begin
      insert into ##answerlinefrom(sn, s_id, d_id)
      select @r, @s_id, case when s_id = @s_id then d_id else s_id end
      from line 
      where s_id = @s_id or d_id = @s_id
      if @@rowcount = 0  return --无路可走      insert into ##answerlineto(sn, s_id, d_id)
      select @r, case when d_id = @d_id then s_id else d_id end, @d_id
      from line 
      where d_id = @d_id or s_id = @d_id
      if @@rowcount = 0 return --无路可走      set @r = @r + 1 
      exec answerstod @s_id, @d_id, @r , @r_line = @r_line output
    end
  end
  else
  begin
    --是否存在公共中间站点
    select @mid_id = ##answerlinefrom.d_id, @temps_id = ##answerlinefrom.s_id, @tempd_id = ##answerlineto.d_id
    from  ##answerlinefrom inner join ##answerlineto 
      on (##answerlinefrom.d_id = ##answerlineto.d_id) 
    where ##answerlinefrom.sn = @r - 1 and ##answerlineto.sn = @r - 1
    if isnull(@mid_id, 0) = 0
    begin 
      select @mid_id = ##answerlinefrom.d_id, @temps_id = ##answerlinefrom.s_id, @tempd_id = ##answerlineto.d_id
      from  ##answerlinefrom inner join ##answerlineto 
        on (##answerlinefrom.d_id = ##answerlineto.s_id) 
      where ##answerlinefrom.sn = @r - 1 and ##answerlineto.sn = @r - 1 
    end    if isnull(@mid_id, 0) = 0
    begin 
      select @mid_id = ##answerlinefrom.d_id, @temps_id = ##answerlinefrom.s_id, @tempd_id = ##answerlineto.d_id
      from  ##answerlinefrom inner join ##answerlineto 
        on (##answerlinefrom.d_id = ##answerlineto.s_id) 
      where ##answerlinefrom.sn = @r - 1 and ##answerlineto.sn = @r - 1 
    end    if @mid_id > 0 --有中间转间点 其中中间点有多个，目前只求出一个
    begin
      if @mid_id = @tempd_id
        set @r_line = @r_line + '->' +  convert(varchar, @temps_id) +  '->' + convert(varchar, @mid_id)
      else
        set @r_line = @r_line + '->' +  convert(varchar, @temps_id) +  '->' + convert(varchar, @mid_id)  + '->' +  convert(varchar, @tempd_id)
      
      set @tempr = @r - 2
      while @tempr >= 0 --起始开始回退累加线路
      begin
        select @temps_id = isnull(s_id, 0)
        from ##answerlinefrom
        where d_id = @temps_id and sn = @tempr
        set @r_line = '->' +  convert(varchar, @temps_id)  + @r_line
        set @tempr = @tempr - 1
      end      set @tempr = @r - 2
      while @tempr >= 0 --终点开始回退累加线路
      begin
        select @tempd_id = isnull(d_id,0)
        from ##answerlineto
        where s_id = @tempd_id and sn = @tempr
        set @r_line = @r_line + '->' +  convert(varchar, @tempd_id)  
        set @tempr = @tempr - 1
      end
       return 
    end
    else
    begin
      set  @rowcount = 0
       insert into ##answerlinefrom(sn, s_id, d_id)
      select @r, ##answerlinefrom.d_id as s_id,  line.d_id
      from ##answerlinefrom inner join  line
           on ((##answerlinefrom.d_id = line.s_id))
      where ##answerlinefrom.sn = @r - 1 and not exists(select * from ##answerlinefrom a 
                                   where a.d_id = ##answerlinefrom.d_id and a.s_id =  line.d_id and a.sn= @r-1)
      set @rowcount = @rowcount + @@rowcount      insert into ##answerlinefrom(sn, s_id, d_id)
      select @r, ##answerlinefrom.d_id as s_id, line.s_id
      from ##answerlinefrom inner join  line
           on ((##answerlinefrom.d_id = line.d_id))
      where ##answerlinefrom.sn = @r - 1  and not exists(select * from ##answerlinefrom a 
                                   where a.d_id = ##answerlinefrom.d_id and a.s_id =  line.s_id and a.sn= @r-1)
      set @rowcount = @rowcount + @@rowcount 
      if @rowcount = 0  return --无路可走 后面的 not exists 防止产生回路      set @rowcount = 0
      insert into ##answerlineto(sn, s_id, d_id)
      select @r, line.s_id,  ##answerlineto.s_id 
      from ##answerlineto inner join  line
           on ((##answerlineto.s_id = line.d_id))
      where ##answerlineto.sn = @r - 1 and not exists(select * from ##answerlineto a 
                                   where a.d_id =  line.s_id and a.s_id =  ##answerlineto.s_id and a.sn= @r-1)
      set @rowcount = @rowcount + @@rowcount 
      insert into ##answerlineto(sn, s_id, d_id)
      select @r, line.d_id,  ##answerlineto.s_id 
      from ##answerlineto inner join  line
           on ((##answerlineto.s_id = line.s_id))
      where ##answerlineto.sn = @r - 1 and not exists(select * from ##answerlineto a 
                                   where a.d_id =  line.d_id and a.s_id =  ##answerlineto.s_id and a.sn= @r-1)
      set @rowcount = @rowcount + @@rowcount       if @rowcount = 0  return --无路可走      set @r = @r + 1
      exec answerstod @s_id, @d_id, @r, @r_line = @r_line output
    end  end
end
go

Answer 10

  if     not   Exists(Select   *   from   dbo.sysobjects   where   name='Line')   
  begin   
      Create   Table   Line(S_ID   int   not   null,   D_ID   int   not   null   
              CONSTRAINT   [t_key_Line]   PRIMARY   KEY     CLUSTERED     
  (   
      S_ID,   D_ID   
  )     ON   [PRIMARY]     
          )   
  end     
    
  if     not   Exists(Select   *   from   dbo.sysobjects   where   name='Linetest')   
  begin   
      Create   Table   Linetest(Sn   int,   S_ID   int   not   null,   D_ID   int   not   null,   Line   varchar(2000),   BgTime   DAtetime,   EdTime   DAteTime,   useTime   DateTime)   
  end     
  Go   
  /*Begin   随机生成数据*/   
  Declare   @R_Line   varchar(1000),   @S_ID   int,   @D_ID   int,   @Count   int,   @BgTime   DateTime,   @EdTime   DateTime   
  DeClare   @maxCount   int   
  Set   @maxCount   =   100000   
  Set   @S_ID   =   0   
  Set   @D_ID   =   10000   
  Select     @Count   =   Count(*)   from   Line     
  while   @Count   <   @maxCount   
  begin   
      Set   @S_ID   =   convert(int,   (@maxCount+   DatePart(ss,   GetDate()))   /   10   *   rand(10000000   *   RAND((DATEPART(ss,   GETDATE())   *   10000   )   +   (DATEPART(ms,   GETDATE())   *   100   )   +   DATEPART(ss,   GETDATE())   )))   
      Set   @D_ID   =   convert(int,   (@maxCount   +   @S_ID)   /   10   *rand(1000000000   *   RAND((DATEPART(mi,   GETDATE())   *   100000   )   +   (DATEPART(ss,   GETDATE())   *   1000   )   +   DATEPART(ms,   GETDATE())   )))   
    
      if   @S_ID   =   @D_ID     
      begin   
          Set   @D_ID   =   @S_ID   +   convert(int,   (@maxCount+   DatePart(ss,   GetDate()))   /   10   *   rand(10000000   *   RAND((DATEPART(ss,   GETDATE())   *   10000   )   +   (DATEPART(ms,   GETDATE())   *   100   )   +   DATEPART(ss,   GETDATE())   )))   
      end   
      while   exists(select   1   from   Line   where   S_ID   =@S_ID   and   D_ID=   @D_ID   or   S_ID   =   @D_ID   and   D_ID   =   @S_ID)     
      begin   
          Set   @S_ID   =   @S_ID   +   convert(int,   (@maxCount+   DatePart(ss,   GetDate()))   /   10   *   rand(10000000   *   RAND((DATEPART(ss,   GETDATE())   *   10000   )   +   (DATEPART(ms,   GETDATE())   *   100   )   +   DATEPART(ss,   GETDATE())   )))   
      end   
      Insert   into   Line(S_ID,   D_ID)     
          Values(@S_ID   ,   @D_Id)   
      print   @Count   
      Set   @Count   =   @count   +   1   
  end   
  /*   end   随机生产数据*/   
        
  Go   
    
  Select   *   from   Line   
  /*   Begin   开始测试   */   
  Declare   @R_Line   varchar(1000),   @S_ID   int,   @D_ID   int,   @Count   int,   @BgTime   DateTime,   @EdTime   DateTime   
  DeClare   @maxCount   int   
  Set   @maxCount   =   100000   
  Set   @S_ID   =   0   
  Set   @D_ID   =   10000   
  Select   @Count   =   Count(*)   from   Linetest   
  while   @Count   <   500   --循环次数   
  begin   
      Set   @S_ID   =   convert(int,   (@maxCount+   DatePart(ss,   GetDate()))   /   10   *   rand(10000000   *   RAND((DATEPART(ss,   GETDATE())   *   10000   )   +   (DATEPART(ms,   GETDATE())   *   100   )   +   DATEPART(ss,   GETDATE())   )))   
      Set   @D_ID   =   convert(int,   (@maxCount   +   @S_ID)   /   10   *rand(1000000000   *   RAND((DATEPART(mi,   GETDATE())   *   100000   )   +   (DATEPART(ss,   GETDATE())   *   1000   )   +   DATEPART(ms,   GETDATE())   )))   
    
      if   @S_ID   =   @D_ID     
      begin   
          Set   @D_ID   =   @S_ID   +   convert(int,   (@maxCount+   DatePart(ss,   GetDate()))   /   10   *   rand(10000000   *   RAND((DATEPART(ss,   GETDATE())   *   10000   )   +   (DATEPART(ms,   GETDATE())   *   100   )   +   DATEPART(ss,   GETDATE())   )))   
      end   
      Set   @BgTime   =   GetDate()   
      Exec   AnswerSToD   @S_ID,   @D_ID,   0,   @R_Line   =   @R_Line   OutPut   
      Set   @EDTime   =   GetDate()   
      Insert   into   Linetest(Sn,   S_ID,   D_ID,   Line,   BgTime,   EdTime,   useTime)     
          Values(@Count,   @S_ID   ,   @D_Id,   @R_Line,   @BgTime,   @Edtime,   @EdTime   -   @BgTime)   
      Select   @Count   
      Set   @Count   =   @count   +   1   
  end   
  /*End   开始测试   */   
    
  Select   Sn,   S_ID,   D_ID,   Line,   Convert(varchar,   BgTime,   114)   as   BgTime,   Convert(varchar,   edTime,   114)   as   EdTime,     Convert(varchar,   useTime,   114)   from   Linetest   
  --Delete   from   Linetest   
    
  /*   从测试结果选择结果   */   
  Declare   @R_Line   varchar(1000)   
  Exec   AnswerSToD   2294,   4291,   0,   @R_Line   =   @R_Line   OutPut   
  Select   'Line',   @R_Line   
  --选择其中一个最长查看执行计划