进度：第四周
讲义 E3
在开始本练习之前，我们建议你仔细阅读整个问题。
介绍
在本练习中，你将设计并实现一个抽象类型。设计一个抽象类型需要确定它应该提供什么服务以及这些服务应该有什么样的行为——也就是编写一个规格说明。实现一个抽象类型包括选择一个表示和一个算法，并填写它们的代码。本练习的重点是设计，因此你的主要精力应该放在设计上面。为了检查你的设计是否可行，你需要使用你的设计建立一个小程序来寻找我们提供的波士顿地铁地图中所有的T形位置。
图
你将要设计的抽象类型应该是一个有向标记多重图。一个图表是一组相互之间由边相连的结点的集合。每个边将一个结点与另一个结点相连。可以有不与任何边相连的结点，但是每条边都必须与两个结点相连。一个结点可以和它自己相连。结点之间可以有零条、一条或多条边相连。每条边都有一个标记，不同的边可以有相同的标记。
这里是一些有向标记多重图应用的举例：
- 一个编译器可以使用一个图来表示控制流，其中结点代表程序中的功能点、边代表程序的语句。可以使用这个图来分析，例如常数值的传播；这个图还可以用作转换，例如将一个语句从循环中提出。
-
一个网站设计工具可以使用一个图来表示站点，其中用结点来表示文档，用边来表示它们之间的链接。这个工具可以检查网站的连通性、查找无效的链接、当一个文档移动后自动更新所有的文档等等......
- 一个课程设计工具可以使用图来表示课程之间的先决关系，查找不一致的课程安排，并选择可行的课程顺序。
- 一个用来生成驾驶向导的程序可以使用图来表示街道地图，从而计算一个地点到另一个地点的最短路径。
- 一个Java™编译工具可以使用图来表示各个源代码文件之间的依赖关系，以确定合理的编译顺序。
你所设计的类型将被用来寻找波士顿地铁中的位置，在使用时用结点来表示车站，用边来表示一段铁轨。但是你的设计和实现应该是支持多态性的。也就是说你的设计中的结点类型应该是通用的，图的设计及其实现应该可以在不同的应用场合中使用。
你的图的实现必须是高效的。也就是说，当处理中等规模（包含数以千计的结点和边，而不是百万计）的图时你的实现应该表现出良好的性能，假设这个图不是过分稀疏（结点数远远大于边数）或稠密（大部分的结点之间都有边相连）的。
设计思想
为了给出一些你在设计中需要考虑的机制，在这里我们给出了一些你可能需要考虑的问题。这些问题通常没有一个简单的答案。你需要练习做仔细的判断，认真思考你所做的选择之间的相互作用关系。
- 你所设计的图应该是易变的还是不可变的？边的标记能不能改变？
- 图中能否允许没有标记的边存在？
- 边的标记应该是字符串还是一般对象？如果是对象，能否将一个结点、一个边甚至一个图作为一个标记？
- 结点是否只需要满足java.lang.Object的接口？或者你将会为结点设计一个Java™接口？
- 图将作为一个单独的类来实现还是分别使用一个Java™接口来对应图的规格说明，一个类来对应图的实现？
- 边是否应该有它们自己的类？对于一个抽象类的客户端它们是否应该可见？
- 从一个单独结点能不能找到它的子结点，图是不是也应该这样？一个结点能否从属于多个图？
- 你的类型应该包含什么样的迭代器 ？
- 寻找路径的操作应该作为图的一个方法，或者应该在图上面一级的客户端代码中实现？
- 你的类型是否应该提供一些视图，比如由java.util.Map中的entrySet方法返回的集合视图？
- 你的类型是否需要执行一些标准Java™
集合接口？
- 你的类的实现中是否需要使用一些标准Java™
集合？
问题 1：图的规格说明 [60 分]
为有向标记图设计一个抽象数据类型。你所设计的记录应该包含在一个或多个与它的实现代码相区别的文件中，还至少应包含以下元素：
- 一段简述说明哪些类或接口对于图的客户端是可见的，它们扮演什么角色，以及一个展示它们之间关系的模块依赖图。
- 对于图的计算复杂性的评价：说明你希望改进哪些方法的计算效率，给出它们的近似消耗计算的限度以及空间需求的限度。例如，你可以说（相当难以置信的）addNode是最消耗资源的方法，随着图的增长，它的消耗将以图大小增长的平方速度增长，而保存图所需的空间将随着边的增长以其指数级数增长。
- 对于每个公有类或接口：
- 使用一段简述解释这个接口或类描述了什么对象，以及它们是否可变。
- 每个方法都应有规格说明。
- 一个简短的设计原理列表（不超过半页），对于各个功能点，你所考虑过的众多的设计中被你放弃了的那些，以及你放弃这些设计的理由。
问题 2：图的实现 [20 分]
实现你所设计的图，并使用JUnit测试它。
你应该提交：
- 你选择的表示的一个简短介绍，还应包括对于你的表示的原理论证以及与其他方案的比较。
- 一个展示你的实现中类和接口的模块依赖图，以及它们之间的关系。
- 良好注释了的源代码。
- 你的测试用例的代码。
- 一段陈述说明你的代码是否通过了所有测试。如果你什么也不说，我们将认为你的代码没有通过测试。
对于本练习，一小组合适的测试就够了。在下周的练习中，你还要回到你的代码中，并更加仔细的对它们进行检查。这里测试的目的是让你熟悉JUnit的使用，并剔除一些严重的错误以保证你的练习能够完成。
问题 3：图的使用
[20 分]
创建一个波士顿地铁系统导向程序。它将以命令行方式接收两个车站的名字作为输入，并输出一系列将进行的步骤的列表。
一个简单的广度优先搜索就足够了。不用担心所要处理问题的复杂性，这将比真实的问题简单的多（例如选择一列在Park
Street的Green Line列车，并将多个车站合并成一条单独的路线）。
我们编写了一些分析波士顿地铁系统描述文件的代码。bostonmetro.txt文件应该作为这个程序的输入。代码则在MetroMapParser.java文件中。你应该对文件进行一些修改，以加入对你的图的ADT（抽象数据类型）的调用。这个调用将因你的ADT的设计而不同。例如，如果你建立了一个不可改变的图，那么在创建你的图之前就需要收集所有的地铁系统信息；而你要是创建了一个可以改变的图，那么就可以一边分析地铁信息文件一边创建你的图。无论如何，你都应该仔细的阅读我们给出的分析代码，而且应该提供一份清楚的描述了你所做改动的文档。
你应该提交：
- 良好注释了的源代码。
- 测试用例的输出的举例。
我们提供的代码
以下的类将以源代码形式提供给你：
- <MetroMapParser.java>
<BadFileException.java>
开始
在开始开发之前，请确定你已经按照“使用工具”一节讲义中创建目录和使用Java所介绍的方法正确的安装与使用了Java™。
创建一个ex3目录，并将我们提供的文件拷贝到里面：
mkdir ~/6.170/ex3
cp -p /mit/6.170/www/psets/ex3/ex3-spec/* ~/6.170/ex3
提示
查阅问题指南和建议 。
你可以使用Integer.parseInt(String s)方法将字符串类型转换为整型。
虽然在深思熟虑之前就开始编码不是一个好主意，但是那常常能形成设计与代码的交叉进行，从而完成有意义的增量式开发。在你完成你的规格说明框架后，你可能需要编写一些测试代码，这将给你一些关于规格说明中各个方法能否满足需求的具体反馈。如果你自信你所提供的方法已经足够完成任务了，你也可以在你的类型设计完成后再开始编写测试代码。
这个策略也有可能导致漫无目的的开发，从而造成低效的代码以及不一致的规格设计。为了避免这种情况，你需要记住三件事情。第一，你必须接受重新开始：如果你不打算抛弃它们，实验代码就不是实验了。第二，无论何时开始编程，你都必须明确你打算实现的是什么。对于含混不清且没有关键细节的规格说明编程是没有意义的。这并不是说当你的规格说明完全完成并且没有任何错误以后才可以开始编程，而是说在你完成一个方法的详细说明之前不要对它进行编码。第三，是否应该只写下方法的说明而不对它作任何设想？如果这样的话你会很容易使自己感到迷惑。在你开始编码之前，尝试将它们写在纸上并认真的对其各种情况进行设想。坐在编辑器前写一些规格说明，然后再围绕它们展开编码是很诱人的工作方式，但是那么做并没有多高的效率。
好好利用你的助教。在去实验室之前将你设计的规格说明拿给你的助教看看，并从他那里获得一些关于设计和风格上的反馈，这将节省你很多时间！
请记住第一课中Hoare的忠告。
勘误
- 练习3中的bostonmetro.txt文件中存在一个错误，下面这一行
41 Copley GreenB 51 34 GreenC 51 34 GreenD 51 34 GreenE 54 34
应该改为：
41 Copley GreenB 51 34 GreenC 51 34 GreenD 51 34 GreenE 53 34
- 这个错误将导致GreenE line的入站在Prudential过早的结束。
感谢Ben Brown指出了这个问题。
问题&回答
这部分将对练习中一些常见问题进行澄清和回答。我们将尽力保持对这部分的更新，因此，当你遇到问题时这部分应该是你最先查看的地方（在仔细的阅读问题描述讲义和规格说明之后）。