开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 图形图像 > GIS编程 > 查看源码
CPath.cs
资源名称：MainSystem.rar　[点击查看]
上传用户：xum6868
上传日期：2009-12-02
资源大小：102k
文件大小：12k
源码类别：

GIS编程

开发平台：

C#

CPath.cs：源码内容
  1. using System;
  2. using System.Collections; 
  4. namespace MainSystem
  5. {
  6. struct Routine //一条公交线路
  7. {
  8. public short nFlag; //0:双向;1:上行;2:下行
  9. public short nStationNumber;
  10. public string szRoutineName;
  11. public string[] szStaionName;
  12. };
  14. struct Node
  15. {
  16. public short nNodeNumber;
  17. public short[] nRoutineOrder;
  18. public short[] nStationOrder;
  19. };
  21. struct Station
  22. {
  23. public string szStationName;
  24. public short nRoutineNumber;
  25. public short[] pnRoutineID;
  26. public short[] pnOrder;
  27. };
  29. struct PathNode
  30. {
  31. public short nSegNumber;
  32. public string[] szRoutineName;
  33. public string[] szFromStationName;
  34. public string[] szToStationName;
  35. };
  37. /// <summary>
  38. /// Summary description for CPath.
  39. /// </summary>
  40. public class CPath
  41. {
  42. private int TIMELIMIT = 3;
  43. private Routine[] _pRoutine;
  44. private Station[] _pStations;
  45. private short _nRCount;
  46. private short _nSCount;
  48. public CPath()
  49. {
  50. _pRoutine = new Routine[1000];
  51. _pStations = new Station[5000];
  52. }
  54. public void Build(CEnvironment env)
  55. {
  56. _nRCount = BuildRoutine(_pRoutine,env);
  57. _nSCount = BuildStationIndex(_pRoutine,_nRCount,_pStations);
  58. }
  60. short BuildRoutine(Routine[] pRoutine, CEnvironment env)
  61. {
  62. System.Data.DataTable typeTbl = env.m_dataSet.Tables["公交车站路线"];
  64. System.Data.DataRow[] rowstypes;
  65. if (env.m_szBusFilter != "")
  66. rowstypes = typeTbl.Select(env.m_szBusFilter);
  67. else
  68. rowstypes = typeTbl.Select();
  70. short nCount = 0;
  71. short nSCount = 0;
  73. string rName;
  74. string sName;
  75. string sTemp1;
  76. string sTemp2;
  77. string[] sNames = new string[350];
  78. foreach (System.Data.DataRow myRow in rowstypes)
  79. {
  80. rName = myRow[0].ToString();
  81. sTemp1 = myRow[1].ToString();
  82. sName = myRow[2].ToString();
  83. sTemp2 = myRow[0].ToString();
  85. if(nCount ==0)
  86. {
  87. pRoutine[nCount] = new Routine();
  88.  
  89. pRoutine[nCount].szRoutineName=string.Copy (rName);
  90. if(rName.Length > 4 && rName.Substring(rName.Length - 4,4).Equals("上行"))
  91. pRoutine[nCount].nFlag = 1;
  92. else if(rName.Length > 4 && rName.Substring(rName.Length - 4,4).Equals("下行"))
  93. pRoutine[nCount].nFlag = 2;
  94. else 
  95. pRoutine[nCount].nFlag = 0;
  96. nCount++;
  97. nSCount = 0;
  98. sNames[nSCount] = string.Copy(sName);
  99. nSCount = 1;
  100. }
  101. else
  102. {
  103. if(pRoutine[nCount-1].szRoutineName.Equals( rName))
  104. {
  105. sNames[nSCount]=string.Copy( sName);
  106. nSCount++;
  107. }
  108. else
  109. {
  110. //结束上一站
  111. pRoutine[nCount-1].nStationNumber = nSCount;
  112. pRoutine[nCount-1].szStaionName = new string [nSCount];
  113. for(short i=0;i<nSCount;i++)
  114. pRoutine[nCount-1].szStaionName[i] = string.Copy (sNames[i]);
  116. pRoutine[nCount] = new Routine();
  117. if(rName.Length > 4 && rName.Substring(rName.Length - 4,4).Equals("上行"))
  118. pRoutine[nCount].nFlag = 1;
  119. else if(rName.Length > 4 && rName.Substring(rName.Length - 4,4).Equals("下行"))
  120. pRoutine[nCount].nFlag = 2;
  121. else 
  122. pRoutine[nCount].nFlag = 0;
  123. pRoutine[nCount].szRoutineName=string.Copy( rName);
  124. nCount++;
  125. nSCount = 0;
  126. sNames[nSCount]=string.Copy (sName);
  127. nSCount = 1;
  128. }
  129. }
  130. }
  131. pRoutine[nCount-1].nStationNumber = nSCount;
  132. pRoutine[nCount-1].szStaionName = new string [nSCount];
  133. for(short i=0;i<nSCount;i++)
  134. pRoutine[nCount-1].szStaionName[i]= string.Copy( sNames[i]);
  136. return nCount;
  137. }
  139. short BuildStationIndex(Routine[] pAllRoutines,short nSize,Station[] pStations)
  140. {
  141. short nCount = 0;
  142. for(short i=0;i<nSize;i++)
  143. {
  144. for(short j=0;j<pAllRoutines[i].nStationNumber;j++)
  145. {
  146. short k;
  148. for( k=0;k<nCount;k++)
  149. {
  150. if(pStations[k].szStationName.Equals(pAllRoutines[i].szStaionName[j]))
  151. break;
  152. }
  153. if(k==nCount)
  154. {
  155. //添加一个新站
  156. pStations[k] = new Station();
  157.  
  158. pStations[k].szStationName=string.Copy(pAllRoutines[i].szStaionName[j]);
  159. pStations[k].nRoutineNumber=1;
  160. nCount++;
  161. }
  162. else
  163. pStations[k].nRoutineNumber++;
  164. }
  165. }
  166. //为各个站的信息分配内存
  167. for(int i=0;i<nCount;i++)
  168. {
  169. pStations[i].pnRoutineID = new short[pStations[i].nRoutineNumber];
  170. pStations[i].pnOrder = new short[pStations[i].nRoutineNumber];
  171. pStations[i].nRoutineNumber = 0; //下面重新数
  172. }
  174. //重新设置信息
  175. for(int i=0;i<nSize;i++)
  176. {
  177. for(short j=0;j<pAllRoutines[i].nStationNumber;j++)
  178. {
  179. short k;
  181. for(k=0;k<nCount;k++)
  182. {
  183. if(pStations[k].szStationName.Equals(pAllRoutines[i].szStaionName[j]))
  184. break;
  185. }
  186. pStations[k].pnRoutineID[pStations[k].nRoutineNumber] = (short)i;
  187. pStations[k].pnOrder[pStations[k].nRoutineNumber] = j;
  188. pStations[k].nRoutineNumber++;
  189. }
  190. }
  191. return nCount;
  192. }
  194. public ArrayList Search(string sz1, string sz2,ArrayList array)
  195. {
  196. Search(_pRoutine,_nRCount,_pStations,_nSCount,sz1,sz2,array);
  197. return array;
  198. }
  200. short Search(Routine[] pAllRoutines,short nSize,Station[] pStations,short nSCount,string szFrom,string szTo,ArrayList pResPath)
  201. {
  202. short nCount = 0;
  204. short nStationOrder;
  205. Node nodeCurrent  ;
  206. Queue queueNodes = new Queue(); //存储需要访问的节点
  207. short nRoutineCurrent;
  208. short nStationCurrent;
  209. short i;
  210. short nMinChangeTimes=1000; //第一次找到的换乘次数
  212. //先得到起点站的线路
  213. for(i=0;i<nSize;i++)
  214. {
  215. nStationOrder = HasStation( pAllRoutines[i],szFrom,0,0);
  216. if(nStationOrder >= 0)
  217. {
  218. nodeCurrent = new Node();
  219. nodeCurrent.nNodeNumber = 1;
  220. nodeCurrent.nRoutineOrder = new short [10];
  221. nodeCurrent.nStationOrder = new short [10];
  223. nodeCurrent.nRoutineOrder[0] = i;
  224. nodeCurrent.nStationOrder[0] = nStationOrder;
  225. //入队列操作
  226. queueNodes.Enqueue(nodeCurrent);
  227. }
  228. }
  230. while( !(0 == queueNodes.Count) )
  231. {
  232. nodeCurrent = (Node)queueNodes.Dequeue();//.GetFront();
  234. if((nodeCurrent.nNodeNumber>=TIMELIMIT+1) || (nodeCurrent.nNodeNumber>nMinChangeTimes-1) || (queueNodes.Count >1500000)) //换乘次数限制
  235. break;
  236. //得到队列头
  237. //从队头站点序列的最后一个站开始检索是否能够找到到站
  238. nRoutineCurrent = nodeCurrent.nRoutineOrder[nodeCurrent.nNodeNumber-1];
  239. nStationCurrent = nodeCurrent.nStationOrder[nodeCurrent.nNodeNumber-1];
  241. nStationOrder = HasStation( pAllRoutines[nRoutineCurrent], szTo, nStationCurrent, pAllRoutines[nRoutineCurrent].nFlag);
  242. if(nStationOrder>=0)  //表示找到
  243. {
  244. nodeCurrent.nRoutineOrder[nodeCurrent.nNodeNumber] = nRoutineCurrent;
  245. nodeCurrent.nStationOrder[nodeCurrent.nNodeNumber] = nStationOrder;
  246. nodeCurrent.nNodeNumber++;
  248. if(nodeCurrent.nNodeNumber>nMinChangeTimes)
  249. break;
  251. PathNode pPathTempNode = new PathNode();
  252. pPathTempNode.nSegNumber = (short)(nodeCurrent.nNodeNumber-1);
  253. pPathTempNode.szRoutineName = new string[pPathTempNode.nSegNumber];
  254. pPathTempNode.szFromStationName = new string[pPathTempNode.nSegNumber];
  255. pPathTempNode.szToStationName = new string[pPathTempNode.nSegNumber];
  256. for(i=0;i<pPathTempNode.nSegNumber;i++)
  257. {
  258. pPathTempNode.szRoutineName[i] =string.Copy(pAllRoutines[nodeCurrent.nRoutineOrder[i]].szRoutineName);
  259. pPathTempNode.szFromStationName[i] = string.Copy(pAllRoutines[nodeCurrent.nRoutineOrder[i]].szStaionName[nodeCurrent.nStationOrder[i]]);
  260. pPathTempNode.szToStationName[i] = string.Copy(pAllRoutines[nodeCurrent.nRoutineOrder[i+1]].szStaionName[nodeCurrent.nStationOrder[i+1]]);
  261. }
  262. pResPath.Add(pPathTempNode);
  264. if(nCount == 0)
  265. nMinChangeTimes = nodeCurrent.nNodeNumber;
  266. nCount++;
  267. if(nCount >20)
  268. break;
  269. }
  270. else  //要将所有可能的路径加入队列
  271. {
  272. for(i=(short)(nStationCurrent+1);i<pAllRoutines[nRoutineCurrent].nStationNumber;i++)
  273. {
  274. string szTheStation;
  275. szTheStation= string.Copy(pAllRoutines[nRoutineCurrent].szStaionName[i]);
  277. short j = SearchStation(pStations,nSCount,szTheStation);
  278. for(short k=0;k<pStations[j].nRoutineNumber;k++)
  279. {
  280. short l;
  281. for(l=0;l<nodeCurrent.nNodeNumber;l++)
  282. if(pStations[j].pnRoutineID[k]==nodeCurrent.nRoutineOrder[l])
  283. break;
  284. if(l<nodeCurrent.nNodeNumber) //说明已经处理过该线路
  285. continue;
  287. Node nodeTemp = new Node();
  288. nodeTemp.nNodeNumber = (short)(nodeCurrent.nNodeNumber+1);
  289. nodeTemp.nRoutineOrder = new short [10];
  290. nodeTemp.nStationOrder = new short [10];
  291. for(l=0;l<nodeCurrent.nNodeNumber;l++)
  292. {
  293. nodeTemp.nRoutineOrder[l] = nodeCurrent.nRoutineOrder[l];
  294. nodeTemp.nStationOrder[l] = nodeCurrent.nStationOrder[l];
  295. }
  296. nodeTemp.nRoutineOrder[nodeCurrent.nNodeNumber]=pStations[j].pnRoutineID[k];
  297. nodeTemp.nStationOrder[nodeCurrent.nNodeNumber]=pStations[j].pnOrder[k];
  298. queueNodes.Enqueue(nodeTemp);
  299. }
  300. }
  301. if( pAllRoutines[nRoutineCurrent].nFlag==0 ) //双向线路，需要两个方向查询
  302. {
  303. for(i=(short)(nStationCurrent-1);i>=0;i--)
  304. {
  305. string szTheStation;
  306. szTheStation=string.Copy(pAllRoutines[nRoutineCurrent].szStaionName[i]);
  308. short j = SearchStation(pStations,nSCount,szTheStation);
  309. for(short k=0;k<pStations[j].nRoutineNumber;k++)
  310. {
  311. short l;
  312. for(l=0;l<nodeCurrent.nNodeNumber;l++)
  313. if(pStations[j].pnRoutineID[k]==nodeCurrent.nRoutineOrder[l])
  314. break;
  315. if(l<nodeCurrent.nNodeNumber) //说明已经处理过该线路
  316. continue;
  317. Node nodeTemp = new Node();
  318. nodeTemp.nNodeNumber = (short)(nodeCurrent.nNodeNumber+1);
  319. nodeTemp.nRoutineOrder = new short [10];
  320. nodeTemp.nStationOrder = new short [10];
  321. for(l=0;l<nodeCurrent.nNodeNumber;l++)
  322. {
  323. nodeTemp.nRoutineOrder[l] = nodeCurrent.nRoutineOrder[l];
  324. nodeTemp.nStationOrder[l] = nodeCurrent.nStationOrder[l];
  325. }
  326. nodeTemp.nRoutineOrder[nodeCurrent.nNodeNumber]=pStations[j].pnRoutineID[k];
  327. nodeTemp.nStationOrder[nodeCurrent.nNodeNumber]=pStations[j].pnOrder[k];
  328. queueNodes.Enqueue(nodeTemp);
  329. }
  330. }
  331. }
  332. }
  333. }
  334. return nCount;
  335. }
  337. //根据站名得到它是一条公交线路上第几站,基0,-1表示没有
  338. //nSearchFrom为开始搜寻的站序号
  339. //nFlag标记向那个方向搜索,0表示双方向,1表示单向
  340. short HasStation(Routine theRoutine,string szStation,short nSearchFrom,short nFlag)
  341. {
  342. if( nFlag!=0 )
  343. {
  344. for(short i=nSearchFrom;i<theRoutine.nStationNumber;i++)
  345. if(theRoutine.szStaionName[i].Equals(szStation))
  346. return i;
  347. }
  348. else if( nFlag==0 )
  349. {
  350. for(short i=nSearchFrom;i<theRoutine.nStationNumber;i++) //正向搜索
  351. if(theRoutine.szStaionName[i].Equals(szStation))
  352. return i;
  353. for(short i=nSearchFrom;i>=0;i--) //反向搜索
  354. if(theRoutine.szStaionName[i].Equals(szStation))
  355. return i;
  356. }
  357. return -1;
  358. }
  360. short SearchStation(Station[] pStations,short nSCount,string theName)
  361. {
  362. short j;
  363. //用于统计时间
  364. for(j=0;j<nSCount;j++)
  365. {
  366. if(pStations[j].szStationName.Equals(theName))
  367. {
  368. return j;
  369. }
  370. }
  371. return j;
  372. }
  374. void FreeStationIndex(Station[] pStations,short nSize)
  375. {
  376. for(short i=0;i<nSize;i++)
  377. {
  378. pStations[i].pnRoutineID = null;
  379. pStations[i].pnOrder = null;
  380. }
  381. }
  383. void FreeRoutineInfo(Routine[] pAllRoutines,short nSize)
  384. {
  385. for(short i=0;i<nSize;i++)
  386. {
  387. pAllRoutines[i].szStaionName = null;
  388. }
  389. }
  393. }
  394. }