1.题目

上海的地铁交通网络已基本成型，建成的地铁线十多条，站点上百个，现需建立一个换乘指南打印系统，通过输入起点站和终点站，打印出地铁换乘指南，指南内容包括起点站、换乘站、终点站。

图形化显示地铁网络结构，能动态添加地铁线路和地铁站点
根据输入起点站和终点站，显示地铁换乘指南
通过图形界面显示乘车路径

2.软件功能

本软件实现一个地铁交通网络管理和线路查询系统。软件可以：

以二维结点（地铁站）、线（地铁线路）排布的方式来显示地铁网络
允许用户通过拖动的方式重排结点（地铁站）
自由添加、删除地铁站和地铁线路
在本地存储中存储和读取地铁地图的配置和排布，以便重新打开软件时仍可继续上一次工作
以 JSON 字符串的形式导入和导出地铁地图的配置和排布
内置一幅上海轨道交通图，可自由加载到软件
查询给定的起点站和终点站之间的最短线路，并以图形和文字的方式展示乘车路径

3.设计思想

本软件的实现方式为 HTML5 + CSS + JavaScript，主体编程语言为 JavaScript。

3.1 数据结构设计思想

对于图形化展示地铁线路、导入导出地铁线路等功能，用一套较为简单的数据结构存储地铁地图，包括站点、线路；而对于查询最短路径的功能，不能直接用前述数据结构来计算，而要将前述数据结构转换为有向图的形式，使用 Dijkstra 算法求得地铁最短路径。

在计算最短路径时，有这样一些约束：

简单地将相邻两站之间的距离认为是 1（鉴于方便而定，若有自定义每站间距离的需求，此数据结构和算法也可在稍微修改后兼容）
用户会存在为不换乘而多坐几站的想法，故将地铁的同站换乘产生的距离认为是一个固定常数，换乘权重 c（每次计算时可由用户指定）
将支线和主线看作两条不同的地铁线，但允许将环线看作一条线

在这样的约束下，可以将前述数据结构转换为一种特殊的有向图来方便求得最短路径。转换的函数名称为 dataToGraph()，其转换方法描述如下：

对于每一个站点，创建 n 个图上的结点，其中 n=1+(该地铁站连接到的线路数)×2。这些结点首先包括站点的“中心结点”，和一系列“站台结点”。每条连接的地铁线路的上行方向和下行方向各有一个“站台结点”。每个站点的“中心结点”只和自己的“站台结点”连接，其“入”方向的弧权值为 c，“出”方向的弧权值为 0。站台之间的连接，用同一方向、同一线路的“站台节点”的连接实现。如所有“2 号线上行方向”的结点按运行次序用弧连接。这样，所有的结点连接在一起，可以模拟地铁的行程、换乘关系。

建立图之后，可以对其用 Dijkstra 最短路径算法求得最短路径。源结点选为出发站点的“中心结点”，目标结点选为目的站点的“中心结点”。计算出后，由于从目的站点的“站台结点”进入“中心节点”额外计算了路径，故路径值应减去换乘权重的一倍。

由于地铁站的设计要求，每个站通过的线路不应该很大，故考虑为常数级。这样，图的结点数为站点数的常数级倍，则算法的时间复杂度为（为站点数）。

3.2 图形界面设计思想

用可以在 HTML5 里直接展示的 SVG 图像格式来展示地铁地图；同时，用基于事件响应的 JavaScript 方法来处理用户输入、改变界面图像、给出输出。

4.逻辑结构与物理结构

4.1 必要的说明

本软件的数据结构用 JavaScript 实现。JavaScript 除整数、字符串等基本数据类型外，对于数组、对象的赋值都是引用传递，故物理结构在实现逻辑结构时，每个对象中，基本数据类型的属性存放在对象的内存空间内部，而子数组、子对象类型的属性存放在内存的其他位置，通过将它们的引用绑定到父对象的属性来实现联系。这样，物理结构和逻辑结构的转换较为容易，故此处略去物理结构的说明，只说明逻辑结构。

JavaScript 不是面向对象的编程语言，而是基于原型（Prototype-based）的编程语言，但可以模拟面向对象式的编程。下面将介绍两类主要数据结构的原型。

4.2 地图数据结构

地图数据结构用全局变量 mapData 存储，其代码如下：

mapData = {stations: {}, lines: {}}

mapData 具有两个属性：stations，以车站 ID 为索引，Station 对象为值，存储所有的车站；lines，以线路 ID 为索引，Line 对象为值，存储所有的线路。一个实际使用中的 mapData 中结构如下：

4.2.1 Station 数据结构

Station 对象的原型代码如下：

var StationPrototype = { 
// __proto__: {             
  x: 30,            
  y: 30,       
  name: "[UNNAMED]",   
  id: undefined,       
  captionOffsetX: 0, 
  captionOffsetY: stationRadius, 
// }            
  _nested_: undefined,  
  _elemStation_: undefined,  
  _elemCaption_: undefined, 
  set nested(value){        
    if (this._nested_ != undefined)   
      this._nested_.remove() 
    this._nested_ = value         
  }, 
  get nested(){     
    return this._nested_     
  }, 
  removeNested: function(){    
    this.nested = undefined   
  }, 
  get elemStation(){    
    return this._elemStation_     
  }, 
  get elemCaption(){    
    return this._elemCaption_     
  }, 
  draw: function(){}, 
  drawCaption: function(){}, 
  dispose: function(){}
}

除去一些与绘制有关的属性外，其基本属性是：

x, y 坐标
名称（name）
ID
站台文字相对于站台图形元素来说的偏移位置(captionOffsetX, captionOffsetY)

4.2.2 Line 数据结构

Line 对象的原型代码如下。

var LinePrototype = {    
// __proto__: {    
  name: "[UNNAMED]",   
  id: undefined,           
  drawOffset: 0,         
  color: "red",          
  stations: [],    
// }       
  _groupLine_: undefined,      
  _elemLegend_: undefined,    
  svgLines: [], 
  set groupLine(value) {     
    if (this._groupLine_ != undefined) {  
      this._groupLine_.remove()  
    } 
    this._groupLine_ = value    
  }, 
  get groupLine(){return this._groupLine_}, 
  drawLine: function(x1, y1, x2, y2){}, 
  draw: function(){},  updateAtStation: function(stationID){}, 
  dispose: function(){}