VB.net 2010 視頻教程 VB.net 2010 視頻教程 VB.net 2010 視頻教程
SQL Server 2008 視頻教程 c#入門經典教程 Visual Basic從門到精通視頻教程
當前位置:
魔兽世界wow > 編程開發 > C#編程 >
  • C#教程之用C#開發的一個通用的地鐵換乘查詢工具

  • 2019-01-20 21:11 來源:未知

魔兽世界wow www.geyjm.icu 日常生活中,上班下班坐地鐵已經是常事,每當我想去某一個遠一點的地方,如果有地鐵首選就是地鐵,因為方便嘛!每次坐地鐵,我們都是憑肉眼去得出我們心中最佳的換乘方案,但是,如果對于線路較少的城市來說,這個方法是最快的,但是如果對于線路較多的城市,例如北京或者上海,十幾條線路交叉穿梭,我們可能看到都暈了,怎么坐才是時間最短路程最短的,我們要算出來不是不可以但是很麻煩,我們也可以想一想,百度地圖的地鐵換乘算法是怎么實現的,于是,閑著沒事,我就想寫一個通用的地鐵換乘查詢程序,想用計算機運算得出科學一點的換乘方案供自己參考,假設先不考慮站點間的距離差異,我們以乘坐站點數最少為最優方案,依照這個條件去編碼實現查找的算法,其實也沒用上什么高大上的算法,因為也不會哈哈,話不多說,先上效果圖:

3.png

有對應城市的線路圖(支持鼠標滾輪放大縮?。?/p>

2.png

站點智能提示:

5.png

項目結構圖:

7.png

我的開發思路:

1、采用xml存儲站點數據,如下:

6.png

2、代碼中使用集合初始化線路數據

復制代碼
 1 /// <summary>
 2         /// 初始化地鐵線路數據
 3         /// </summary>
 4         /// <param name="city">城市</param>
 5         public static void InitSubwayLine(CityEnum city)
 6         {
 7             if (AllSubwayLines != null && AllSubwayLines.Any() && _currentCity == city) return;
 8             _currentCity = city;
 9             var xmlName = Path.Combine(AppDomain.CurrentDomain.BaseDirectory, "xml/" + city.ToString() + ".xml");
10             _doc = XDocument.Load(xmlName);
11             AllSubwayLines = _doc.Root.Elements().Select(x =>
12             {
13                 var line = new SubwayLine
14                 {
15                     No = x.Attribute("No").Value,
16                     Name = x.Attribute("Name").Value,
17                     IsRound = x.Attribute("IsRound") == null ? false : bool.Parse(x.Attribute("IsRound").Value),
18                     Stations = x.Elements().Select((y, i) => new Station
19                     {
20                         Index = i,
21                         Name = y.Attribute("Name").Value,
22                         LineNo = x.Attribute("No").Value,
23                         CanTransfer = y.Attribute("CanTransfer") == null ? false : bool.Parse(y.Attribute("CanTransfer").Value),
24                         TransferNo = y.Attribute("TransferNo") == null ? null : y.Attribute("TransferNo").Value
25                     }).ToList()
26                 };
27                 var translines = line.GetTransStations().Select(z => z.TransferNo.Split(',')).ToList();
28                 foreach (var transline in translines)
29                 {
30                     foreach (var li in transline)
31                     {
32                         line.TransferLines.Add(li);
33                     }
34                 }
35                 line.TransferLines = line.TransferLines.Distinct().ToList();
36                 return line;
37             }).ToList();
38         }
復制代碼

3、分多種情況進行處理,核心代碼(代碼有點長,我也在想方法濃縮代碼,還望各位看官耐心(┬_┬)):

復制代碼
  1         /// <summary>
  2         /// 獲取地鐵乘車信息
  3         /// </summary>
  4         /// <param name="depStation">出發站</param>
  5         /// <param name="destStation">到達站</param>
  6         /// <param name="city">所在城市</param>
  7         /// <returns>返回各種換乘方案</returns>
  8         public static List<QueryResult> GetRideSubwayInfo(string depStation, string destStation, CityEnum city)
  9         {
 10             InitSubwayLine(city);
 11             if (string.IsNullOrWhiteSpace(depStation) || string.IsNullOrWhiteSpace(destStation)
 12                 || !AllSubwayLines.Exists(x => x.Stations.Exists(y => y.Name.Equals(depStation)))
 13                 || !AllSubwayLines.Exists(x => x.Stations.Exists(y => y.Name.Equals(destStation))))
 14                 return null;//出發站或到達站在線路上不存在!
 15 
 16             //各種換乘提示
 17             //同一條線路
 18             var msg_oneline = "在{0}【{1}】上車,經過{2}站到達目的站【{3}】。\r\n具體線路為:\r\n(出發){4}(到達)\r\n總搭乘站點數:{5}\r\n";
 19             //換乘1次
 20             var msg_transOnce = "在{0}【{1}】上車,經過{2}站在【{3}】下車,換乘{4},經過{5}站到達目的站【{6}】。\r\n具體線路為:\r\n(出發){7}(此處換乘{4})-->{8}(到達)\r\n總搭乘站點數:{9}\r\n";
 21             //換乘2次
 22             var msg_transTwice = "在{0}【{1}】上車,經過{2}站在【{3}】下車,換乘{4},經過{5}站在【{6}】下車,換乘{7},經過{8}站到達目的站【{9}】。\r\n具體線路為:\r\n(出發){10}(此處換乘{4})-->{11}(此處換乘{7})-->{12}(到達)\r\n總搭乘站點數:{13}\r\n";
 23             //換乘3次
 24             var msg_transThreetimes = "在{0}【{1}】上車,經過{2}站在【{3}】下車,換乘{4},經過{5}站在【{6}】下車,換乘{7},經過{8}站在【{9}】下車,換乘{10},經過{11}站到達目的站【{12}】。"
 25                 + "\r\n具體線路為:\r\n(出發){13}(此處換乘{4})-->{14}(此處換乘{7})-->{15}(此處換乘{10})-->{16}(到達)\r\n總搭乘站點數:{17}\r\n";
 26             //換乘4次
 27             var msg_transFourtimes = "在{0}【{1}】上車,經過{2}站在【{3}】下車,換乘{4},經過{5}站在【{6}】下車,換乘{7},經過{8}站在【{9}】下車,換乘{10},經過{11}站在【{12}】下車,換乘{13},經過{14}站到達目的站【{15}】。"
 28                 + "\r\n具體線路為:\r\n(出發){16}(此處換乘{4})-->{17}(此處換乘{7})-->{18}(此處換乘{10})-->{19}(此處換乘{13})-->{20}(到達)\r\n總搭乘站點數:{21}\r\n";
 29 
 30             //保存各種換乘方案
 31             var result = new List<QueryResult>();
 32             //第一步:先查找始發站和到達站在哪一條線路
 33             var afterDepLines = GetAcrossLines(depStation);
 34             var afterDestLines = GetAcrossLines(destStation);
 35             //根據同一條線和不同線路展開分析
 36             if (IsSameLine(depStation, destStation))
 37             {
 38                 #region 同一條線路
 39                 var commLines = afterDepLines.Where(x => afterDestLines.Select(y => y.No).Contains(x.No)).ToList();
 40                 //判斷線路是否相同,相同直接計算站點距離
 41                 var depIndex = GetIndexOnLine(depStation, commLines.First());
 42                 var destIndex = GetIndexOnLine(destStation, commLines.First());
 43                 var crossStations = commLines.First().Stations.Between(depIndex, destIndex).Select(x => x.Name).ToList();
 44                 var range = crossStations.Count - 1;
 45                 if (depIndex > destIndex) crossStations.Reverse();
 46                 var rs = msg_oneline.FormatTo(commLines.First().ToString(), depStation, range, destStation,
 47                          crossStations.ToJoinString(), range);
 48                 result.Add(new QueryResult() { Description = rs, Range = range });
 49                 #endregion
 50             }
 51             else
 52             {
 53                 #region 不同線路
 54                 if (!IsTransferStation(depStation) && !IsTransferStation(destStation))//如果始發站和終點站都不是換乘站,則表示始發站和到達站都是只有一條線路通過
 55                 {
 56                     if (afterDepLines.First().IsIntersect(afterDestLines.First()))
 57                     {
 58                         #region 如果兩條線路交叉,一定有換乘站點
 59                         var clist = GetAcrossStations(afterDepLines.First(), afterDestLines.First()).Select(x => x.Name).ToList();
 60                         var i = GetIndexOnLine(depStation, afterDepLines.First());
 61                         var j = GetIndexOnLine(clist.First(), afterDepLines.First());
 62                         var k = GetIndexOnLine(destStation, afterDestLines.First());
 63                         var l = GetIndexOnLine(clist.First(), afterDestLines.First());
 64                         var coss1 = afterDepLines.First().Stations.Between(i, j).Select(x => x.Name).ToList();
 65                         var coss2 = afterDestLines.First().Stations.Between(k, l).Select(x => x.Name).ToList();
 66                         if (i > j) coss1.Reverse();
 67                         if (k < l) coss2.Reverse();
 68                         var rang1 = coss1.Count - 1;
 69                         var rang2 = coss2.Count - 1;
 70                         var h = rang1 + rang2; //站點數
 71                         var rs = msg_transOnce.FormatTo(afterDepLines.First().ToString(), depStation, rang1, clist.First(),
 72                             afterDestLines.First().ToString(), rang2, destStation,
 73                             coss1.ToJoinString(), coss2.Where(x => x != clist.First()).ToJoinString(), h);
 74                         result.Add(new QueryResult()
 75                         {
 76                             Description = rs,
 77                             Range = h,
 78                             TransferStations = new List<string>() { clist.First() },
 79                             TransferTimes = 1
 80                         });
 81                         #endregion
 82                     }
 83                     else
 84                     {
 85                         #region 不交叉,需要通過第三條線路換乘,即多次換乘
 86                         var depSta = GetStation(depStation);
 87                         var destSta = GetStation(destStation);
 88                         //找出兩條線路的可換乘站點,找出可換乘相同線路的站點
 89                         var trans1 = afterDepLines.First().GetTransStations();
 90                         var trans2 = afterDestLines.First().GetTransStations();
 91                         var trans3 = new List<Station>();
 92                         var trans4 = new List<Station>();
 93                         var expets = trans1.Join(trans2, x => x.TransferNo, y => y.TransferNo, (x, y) =>
 94                         {
 95                             trans3.Add(x);
 96                             trans4.Add(y);
 97                             return x.Name + "---" + y.Name;
 98                         }).ToList();
 99                         if (expets.Any())
100                         {
101                             #region 兩次換乘
102                             //trans3.Count和trans4.Count必定相等
103                             //計算最短距離,列出所有換乘方案
104                             for (var i = 0; i < trans3.Count; i++)
105                             {
106                                 var tranLine = GetLine(trans3[i].TransferNo);
107                                 //獲取這兩個站點在此線路的索引                   
108                                 var ix1 = depSta.Index;
109                                 var ix2 = destSta.Index;
110                                 var iix1 = GetIndexOnLine(trans3[i].Name, depSta.LineNo);
111                                 var iix2 = GetIndexOnLine(trans4[i].Name, destSta.LineNo);
112                                 var tx1 = GetIndexOnLine(trans3[i].Name, tranLine);
113                                 var tx2 = GetIndexOnLine(trans4[i].Name, tranLine);
114 
115                                 var depRange = afterDepLines.First().Stations.Between(ix1, iix1).Select(x => x.Name).ToList();
116                                 var destRange = afterDestLines.First().Stations.Between(ix2, iix2).Select(x => x.Name).ToList();
117                                 var transRange = tranLine.Stations.Between(tx1, tx2).Select(x => x.Name).ToList();
118                                 if (ix1 > iix1) depRange.Reverse();
119                                 if (ix2 < iix2) destRange.Reverse();
120                                 if (tx1 > tx2) transRange.Reverse();
121                                 var r1 = depRange.Count - 1;
122                                 var r2 = destRange.Count - 1;
123                                 var r3 = transRange.Count - 1;
124                                 var r = r1 + r2 + r3;
125                                 var rs = msg_transTwice.FormatTo(afterDepLines.First().ToString(), depStation, r1,
126                                     trans3[i].Name,
127                                     tranLine.ToString(), r3, trans4[i].Name, afterDestLines.First().ToString(), r2,
128                                     destStation, depRange.ToJoinString(),
129                                         transRange.Where(x => !x.IsSame(trans3[i].Name) && !x.IsSame(trans4[i].Name)).ToJoinString(),
130                                      destRange.ToJoinString(), r);
131                                 result.Add(new QueryResult()
132                                 {
133                                     Description = rs,
134                                     Range = r,
135                                     TransferTimes = 2,
136                                     TransferStations = new List<string>() { trans3[i].Name, trans4[i].Name }
137                                 });
138                             }
139                             #endregion
140                         }
141                         #region 查找3次以上換乘的可能結果,尋求最短距離
142                         var trlines1 = afterDepLines.First().TransferLines.Select(GetLine).ToList();
143                         var trlines2 = afterDestLines.First().TransferLines.Select(GetLine).ToList();
144                         var destss = new List<Station>();
145 
146                         #region 換乘3次
147                         foreach (var depline in trlines1)
148                         {
149                             foreach (var destline in trlines2)
150                             {
151                                 var ss = destline.GetAcrossStations(depline);
152                                 if (!ss.Any()) continue; //3次換乘
153                                 var slist1 = afterDepLines.First().GetAcrossStations(depline);
154                                 if (!slist1.Any()) continue;
155                                 var s1 = slist1.GetClosestStation(depSta.Name);
156                                 var s1_ix1 = depSta.Index;
157                                 var s1_ix2 = s1.Index;
158                                 var s1_range =
159                                     afterDepLines.First()
160                                         .Stations.Between(s1_ix1, s1_ix2)
161                                         .Select(x => x.Name)
162                                         .ToList();
163                                 var s1_h = s1_range.Count - 1;
164                                 if (s1_ix1 > s1_ix2) s1_range.Reverse();
165 
166                                 var s2_ix1 = GetIndexOnLine(s1.Name, depline);
167                                 var s2_ix2 = GetIndexOnLine(ss.First().Name, depline);
168                                 var s2_range = depline.Stations.Between(s2_ix1, s2_ix2).Select(x => x.Name).ToList();
169                                 var s2_h = s2_range.Count - 1;
170                                 if (s2_ix1 > s2_ix2) s2_range.Reverse();
171 
172                                 var slist3 = destline.GetAcrossStations(afterDestLines.First());
173                                 if (!slist3.Any()) continue;
174                                 var s3 = slist3.GetClosestStation(ss.First().Name);
175                                 var s3_ix1 = s3.Index;
176                                 var s3_ix2 = ss.First().Index;
177                                 var s3_range = destline.Stations.Between(s3_ix1, s3_ix2).Select(x => x.Name).ToList();
178                                 var s3_h = s3_range.Count - 1;
179                                 if (s3_ix1 < s3_ix2) s3_range.Reverse();
180 
181                                 var s4_ix1 = GetIndexOnLine(s3.Name, afterDestLines.First());
182                                 var s4_ix2 = destSta.Index;
183                                 var s4_range =
184                                     afterDestLines.First()
185                                         .Stations.Between(s4_ix1, s4_ix2)
186                                         .Select(x => x.Name)
187                                         .ToList();
188                                 var s4_h = s4_range.Count - 1;
189                                 if (s4_ix1 > s4_ix2) s4_range.Reverse();
190 
191                                 var h = s1_h + s2_h + s3_h + s4_h;
192                                 var rs = msg_transThreetimes.FormatTo(afterDepLines.First().ToString(), depStation,
193                                     s1_h, s1.Name,
194                                     depline.ToString(), s2_h, ss.First().Name,
195                                     GetLine(ss.First().LineNo).ToString(), s3_h, s3.Name,
196                                     afterDestLines.First().ToString(), s4_h, destStation, s1_range.ToJoinString(),
197                                     s2_range.Where(x => x != s1.Name).ToJoinString(),
198                                     s3_range.Where(x => x != ss.First().Name).ToJoinString(),
199                                     s4_range.Where(x => x != s3.Name).ToJoinString(), h);
200                                 result.Add(new QueryResult()
201                                 {
202                                     Description = rs,
203                                     Range = h,
204                                     TransferTimes = 3,
205                                     TransferStations =
206                                         new List<string>()
207                                         {
208                                                         s1.Name,
209                                                         ss.First().Name,
210                                                         s3.Name
211                                         }
212                                 });
213                                 destss.AddRange(ss);
214                             }
215                         }
216                         #endregion
217 
218                         if (!destss.Any()) //換乘4次
219                         {
220                             #region 換乘4次
221                             foreach (var depline in trlines1)
222                             {
223                                 foreach (var destline in trlines2)
224                                 {
225                                     var deptrlines =
226                                         depline.TransferLines.Where(x => x != afterDepLines.First().No)
227                                             .Select(GetLine)
228                                             .ToList();
229                                     foreach (var line in deptrlines)
230                                     {
231                                         var s1 = line.GetAcrossStations(destline);
232                                         if (!s1.Any()) continue; //4次換乘
233                                         var trlist1 = afterDepLines.First().GetAcrossStations(depline);
234                                         if (!trlist1.Any()) continue;
235                                         var tr1 = trlist1.GetClosestStation(depSta.Name);
236                                         var s1_ix1 = depSta.Index;
237                                         var s1_ix2 = tr1.Index;
238                                         var s1_range =
239                                             afterDepLines.First()
240                                                 .Stations.Between(s1_ix1, s1_ix2)
241                                                 .Select(x => x.Name)
242                                                 .ToList();
243                                         var h1 = s1_range.Count - 1;
244                                         if (s1_ix1 > s1_ix2) s1_range.Reverse();
245 
246                                         var trlist2 = GetLine(tr1.TransferNo).GetAcrossStations(line);
247                                         if (!trlist2.Any()) continue;
248                                         var tr2 = trlist2.GetClosestStation(tr1.Name);
249                                         var s2_ix1 = GetIndexOnLine(tr1.Name, depline);
250                                         var s2_ix2 = tr2.Index;
251                                         var s2_range =
252                                             depline.Stations.Between(s2_ix1, s2_ix2)
253                                                 .Select(x => x.Name)
254                                                 .ToList();
255                                         var h2 = s2_range.Count - 1;
256                                         if (s2_ix1 > s2_ix2) s2_range.Reverse();
257 
258                                         var s3_ix1 = GetIndexOnLine(tr2.Name, line);
259                                         var s3_ix2 = s1.First().Index;
260                                         var s3_range =
261                                             line.Stations.Between(s3_ix1, s3_ix2)
262                                                 .Select(x => x.Name)
263                                                 .ToList();
264                                         var h3 = s3_range.Count - 1;
265                                         if (s3_ix1 > s3_ix2) s3_range.Reverse();
266 
267                                         var trlist3 = destline.GetAcrossStations(afterDestLines.First());
268                                         if (!trlist3.Any()) continue;
269                                         var tr3 = trlist3.GetClosestStation(s1.First().Name);
270                                         var s4_ix1 = GetIndexOnLine(s1.First().Name, destline);
271                                         var s4_ix2 = tr3.Index;
272                                         var s4_range =
273                                             destline.Stations.Between(s4_ix1, s4_ix2)
274                                                 .Select(x => x.Name)
275                                                 .ToList();
276                                         var h4 = s4_range.Count - 1;
277                                         if (s4_ix1 > s4_ix2) s4_range.Reverse();
278 
279                                         var s5_ix1 = GetIndexOnLine(tr3.Name, afterDestLines.First());
280                                         var s5_ix2 = destSta.Index;
281                                         var s5_range =
282                                             afterDestLines.First()
283                                                 .Stations.Between(s5_ix1, s5_ix2)
284                                                 .Select(x => x.Name)
285                                                 .ToList();
286                                         var h5 = s5_range.Count - 1;
287                                         if (s5_ix1 > s5_ix2) s5_range.Reverse();
288                                         var h = h1 + h2 + h3 + h4 + h5;
289                                         var rs =
290                                             msg_transFourtimes.FormatTo(afterDepLines.First().ToString(),
291                                                 depStation, h1, tr1.Name,
292                                                 depline.ToString(), h2, tr2.Name,
293                                                 line.ToString(), h3, s1.First().Name,
294                                                 destline.ToString(), h4, tr3.Name,
295                                                afterDestLines.First().ToString(), h5, destStation,
296                                                 s1_range.ToJoinString(),
297                                                 s2_range.Where(x => x != tr1.Name).ToJoinString(),
298                                                 s3_range.Where(x => x != tr2.Name).ToJoinString(),
299                                                 s4_range.Where(x => x != tr2.Name && x != s1.First().Name).ToJoinString(),
300                                                 s5_range.Where(x => x != tr3.Name).ToJoinString(), h);
301                                         result.Add(new QueryResult()
302                                         {
303                                             Description = rs,
304                                             Range = h,
305                                             TransferTimes = 4,
306                                             TransferStations =
307                                                 new List<string>()
308                                                 {
309                                                             tr1.Name,
310                                                             tr2.Name,
311                                                             s1.First().Name,
312                                                             tr3.Name
313                                                 }
314                                         });
315                                         destss.AddRange(s1);
316                                     }
317                                 }
318                             }
319                             #endregion
320                         }
321                         if (!destss.Any())//換乘4次以上
322                         {
323 
324                         }
325                         #endregion
326                         #endregion
327                     }
328                 }
329                 else //始發站和到達站有其中一個是換乘站
330                 {
331                     //