实验目标概述
本次实验训练抽象数据类型（ADT）的设计、规约、测试，并使用面向对象 编程（OOP）技术实现 ADT。具体来说：
1、针对给定的应用问题，从问题描述中识别所需的 ADT；
2、设计 ADT 规约（pre-condition、post-condition）并评估规约的质量；
3、根据 ADT 的规约设计测试用例；
4、ADT 的泛型化；
5、根据规约设计 ADT 的多种不同的实现；针对每种实现，设计其表示 （representation）、表示不变性（rep invariant）、抽象过程（abstraction function） 6、使用 OOP 实现 ADT，并判定表示不变性是否违反、各实现是否存在表 示泄露（rep exposure）；
7、 测试 ADT 的实现并评估测试的覆盖度；
8、使用 ADT 及其实现，为应用问题开发程序；
9、在测试代码中，能够写出 testing strategy 并据此设计测试用例。
实验环境配置
简要陈述你配置本次实验所需环境的过程，必要时可以给出屏幕截图。
特别是要记录配置过程中遇到的问题和困难，以及如何解决的。
处理Eclipse IDE和git的使用外，在Eclipse中安装配置了EclEmma，用于统计Junit测试用例的代码覆盖度的plugin。配置过程根据网上教程，直接在eclipse中的help的MarketPlace中搜索自动安装即可。
该实验还增加了对不变量的测试，主要是书写checkRep函数，然后分别在每个函数执行前调用检查不变量。
在这里给出你的GitHub Lab2仓库的URL地址（Lab2-学号）。
https://github.com/ComputerScienceHIT/Lab2-1170300503
实验过程
请仔细对照实验手册，针对三个问题中的每一项任务，在下面各节中记录你的实验过程、阐述你的设计思路和问题求解思路，可辅之以示意图或关键源代码加以说明（但千万不要把你的源代码全部粘贴过来！）。
Poetic Walks
在这里简要概述你对该任务的理解。
根据Graph接口完成ConcreteEdgesGraph实例类和ConcreteVerticsGraph实例类，然后用这两个实例化类及其方法完成拼写诗句的操作。
Poet创作的抽象过程中，首先要把每个单词当做一个节点，相邻两个单词之间用有向边连接。根据给定单词拼写诗句的方法中，如果给定的相邻两个单词之间有单词，则选择出现频率最高的单词插入，否则输出语句直接拼接上该给定单词。
Get the code and prepare Git repository
根据实验指导手册（PPT），点击给定的GitHub Classroom 中的 URL地址，创建GitHub Lab2仓库，然后点击下载，将仓库下载到本地即可。
由于无法连接 MIT 的 Athena 服务器，P1的代码框架是从PPT上给定的地址点击下载的，点击地址链接，找到对应的git代码库，然后通过git clone 到本地并放到Eclipse中。
Problem 1: Test Graph \
Problem相对简单，由于Graph是个接口，所以需要完成的只有静态方法empty（），该方法可返回一个新的ConcreteEdgesGraph实例化类或ConcreteVerticsGraph实例化类。
Problem 2: Implement Graph \
以下各部分，请按照MIT页面上相应部分的要求，逐项列出你的设计和实现思路/过程/结果。
Implement ConcreteEdgesGraph
首先，该ConcreteEdgesGraph实例化类继承Graph接口并实现接口的对应方法。
add方法中首先判断该vertex对象是否已经被添加，如果未被添加，则add到顶点集中，返回true，否则直接返回false。
Set方法相对复杂，首先需要判断要更新的边的两个顶点是否相同，如果相同，直接返回0；否则，接着判断该条边是否已经存在，如果已经存在，若weight不等于0，则将边的权重更新，否则将该条边删除，返回该边之前的weight，结束。若该条边不存在，若weight=0,则直接返回0，结束，否则，加上该条边，返回0，结束。
remove方法中需要先判断该条边是否存在，如果存在，删除该条边及其顶点集中边的两个顶点中的对应关系，返回true，否则返回false，结束。
Sources和targets方法中需要对所有边进行遍历，如果存在一条边以该顶点为target（source），则将另一个顶点加入对应的sources（targets）map集合，最终将结果集返回。
Implement ConcreteVerticesGraph
该ConcreteVerticessGraph实例化类和ConcreteEdgesGraph实例化类类似，实现方法也大致类似，首先继承Graph接口并实现接口的对应方法。
add方法中首先判断该vertex对象是否为空，如果为空，返回false，结束；否则，判断该顶点是否已经被添加，如果未被添加，则add到顶点集中，返回true，否则直接返回false。
set方法也相对复杂，但实现方法略有不同，首先将两个顶点加入顶点集。之后，判断该条边是否已经存在，若存在且weight不等于0，则将边的权重更新，否则将该条边删除，返回该边之前的weight，结束。若该条边不存在，若weight=0,则直接返回0，结束，否则，加上该条边，返回0，结束。
remove方法中需要先判断该顶点是否存在，如果存在，删除该顶点及该顶点涉及的各个边，返回true，否则返回false，结束。
Sources和targets方法中需要对该顶点的sources（targets）map集合进行遍历，如果存一条边以该顶点为target（source），则将另一个顶点加入对应的最终将结果集返回。
####### Problem 3: Implement generic Graph\
Make the implementations generic
在这里将所有String类型改为泛型L，例：
该泛型过程中，个别类型需要强转，其他并无太大问题。
Implement Graph.empty()
这里只需将对应接口改为泛型L即可：
####### Problem 4: Poetic walks
Test GraphPoet
完成GraphPoet的测试类，根据接口定义的函数对每个方法进行测试。
Implement GraphPoet
按行读取文件，将每行的字母先全部转化为小写便于匹配，按空格分割。将每个单词调用add方法加入顶点集，将与之相连的前一个和后一个单词用有向边连接，构成有向图。
给定单词生成诗句的过程中，遍历，依次查找相邻两个单词之间是否有其他单词，使之组成两个顺次的有向边，如果有这样的单词，选择出现频率最大的加入到句子中，否则直接输出前一个单词。最后输出句子的时候，需要将对应单词的大小写还原。
Graph poetry slam
首先按照要求修改main函数，然后使用不同的单词输入对各个方法进行测试。
Before you’re done
请按照http://web.mit.edu/6.031/www/sp17/psets/ps2/#before_youre_done的说明，检查你的程序。
如何通过Git提交当前版本到GitHub上你的Lab2仓库。
找到本地仓库所在目录，将Eclise中的项目复制更新到仓库，然后，右键，点击git bash here，在git命令框中使用如下命令提交：
git add .
git commit -m “ ”
git push origin master
在这里给出你的项目的目录结构树状示意图。
Re-implement the Social Network in Lab1
在这里简要概述你对该任务的理解。
该实验是基于P1中的Graph及其两种实现类ConcreteVerticessGraph实例化类和ConcreteEdgesGraph实例化类，重新实现Lab1中的的 FriendshipGraph 类。ConcreteVerticessGraph实例化类和ConcreteEdgesGraph实例化类中的add方法、set方法等可在构建社交图的时候直接调用，使得网络图的构建变得十分简单。
FriendshipGraph类
AddVertex直接调用add方法，addEdge调用set方法，变得非常简单易操作。getDistance方法利用队列，采用广搜来完成。首先将该person加入队列，并标记为已访问过，当队列不为空的时候循环：
队首元素出队，搜索和当前person相关的人，如果匹配到了另一个人，返回距离值，结束；否则将搜索到的相关person依次加入队列，标记为已访问过。如果遍历的层数增加，则两个人的距离加1。
最终返回距离值，结束。如果循环结束未匹配到另一个，则返回-1。
Person类
属性和唯一表示均是name，带有set/get方法，默认构造方法中传入参数name。
客户端main()
构造实例化对象FriendshipGraph和四个不同姓名的person对象，调用add方法将四个person加入到有向图中，然后设计person之间的关系，并调用set方法完成对应有向图的构造，最后，调用getDistance方法计算其中两个人的距离并输出。
测试用例
构造实例化对象FriendshipGraph和四个不同姓名的person对象，调用add方法将四个person加入到有向图中，然后设计person之间的关系，并调用set方法完成对应有向图的构造，最后，调用getDistance方法计算其中两个人的距离进行Junit测试。
提交至Git仓库
如何通过Git提交当前版本到GitHub上你的Lab3仓库。
找到本地仓库所在目录，将Eclise中的项目复制更新到仓库，然后，右键，点击git bash here，在git命令框中使用如下命令提交：
git add .
git commit -m “ ”
git push origin master
在这里给出你的项目的目录结构树状示意图。
Playing Chess
ADT设计/实现方案
设计了哪些ADT（接口、类），各自的rep和实现，各自的mutability/ immutability说明、AF、RI、safety from rep exposure。
必要时请使用UML class diagram（请自学）描述你设计的各ADT间的关系。
接口：Piece、Player、Position、Game、ChessAction、GoAction
类：Board、ChessGame实现Game接口和ChessAction接口、GoGame类实现Game接口和GoAaction接口，ChessPiece类实现Piece接口，GoPiece实现Piece接口，ChessPlayer类实现Player接口，GoPlayer类实现Player接口，ChessType枚举，MyChessAndGoGame类
最终各个方法的在main函数中调用，main函数循环执行menu函数，menu函数根据用户的选择调用对应的方法执行对应操作，menu函数的设计如下：
主程序MyChessAndGoGame设计/实现方案
辅之以执行过程的截图，介绍主程序的设计和实现方案，特别是如何将用户在命令行输入的指令映射到各ADT的具体方法的执行。
定义的全局变量如下：
MyChessAndGoGame类中设计了统计两个玩家棋子的方法和菜单。
main函数中，先让玩家确定游戏类型，根据所选择的类型初始化棋盘等，然后创建两个玩家对象，游戏开始，循环执行menu函数。
Menu函数（菜单）主要是两次循环，以便让两个玩家交替进行游戏。然后根据他们所选择的游戏类型判断游戏过程中前两项是吃子还是提子等操作，后四项选择一样，分别是查询某位置的占用情况，计算棋子总数、跳过和end，根据玩家的选项执行对应的方法。
ChessGame实例类中有movePiece（移动棋子）方法和eatPiece（吃子）方法及棋盘的初始化方法。movePiece方法和eatPiece方法中需要先判断输入的两个位置是否越界，是否有对应玩家的棋子等情况。GoGame实例类中实现pickPiece（提子）方法和placePiece（放置棋子）方法，实现过程中也需要输入的位置是否越界，是否有对应玩家的棋子等情况。
ADT和主程序的测试方案
介绍针对各ADT的各方法的测试方案和testing strategy。
介绍你如何对该应用进行测试用例的设计，以及具体的测试过程。
分别对两种游戏进行测试。
对象棋的测试方法中，首先创建ChessGame实例化对象，并创建棋盘和两个玩家，分别调用eatPiece方法和movePiece方法测试吃子和移动棋子的方法。
对围棋的测试方法中，首先创建GoGame实例化对象，并创建棋盘和两个玩家，分别调用placePiece方法和pickPiece方法测试放置棋子和提子的方法。
Multi-Startup Set (MIT)
目录结构如下：
实验进度记录
请使用表格方式记录你的进度情况，以超过半小时的连续编程时间为一行。
| 日期 | 时间段 | 计划任务 | 实际完成情况 |
|---|---|---|---|
| 2019-03-12 | 09:02 | 完成P1的Problem1 | 按时完成 |
| 2019-03-13 | 18:15-19:25 | 完成P1的Problem2 | 延迟一天完成 |
| 2019-03-13 | 19:27-23:45 | 完善Problem2的测试 | 延迟两个小时完成 |
| 2019-03-14 | 13:55-14:10 | 完成P1的Problem3 | 按时完成 |
| 2019-03-14 | 14:35-16:32 | 完成P1的Problem4 | 按时完成 |
| 2019-03-14 | 18:40-19:34 | 完成P2 | 按时完成 |
| 2019-03-22 | 10:35-16：06 | 基本完成P3 | 顺延一周完成 |
| 2019-03-22 | 16:06-16:41 | 完善P3 | 按时完成 |
| 2019-03-22 | 16:41-17:15 | 完善P3测试 | 按时完成 |
实验过程中遇到的困难与解决途径
| 遇到的难点 | 解决途径 |
|---|---|
| 第一遍测试代码覆盖率较低 | 通过跟踪查询，发现大部分是因为实例类中的get/set方法未被调用，就适当的删除了一些不必要的get/set方法 |
| 棋盘各个类的接口和对应实现类的设计困难 | 画出各个对象直之间的联系，找出不同棋类之间的联系与区别，根据关系设计接口和对应方法及实现类 |
实验过程中收获的经验、教训、感想
实验过程中收获的经验和教训
要进一步深入理解ADT，注意编程规范，测试的时候尽量考虑所有情况，尽可能的提高代码覆盖率。
针对以下方面的感受
(1) 面向ADT的编程和直接面向应用场景编程，你体会到二者有何差异？
面向ADT编程是每一个实例对象看做一个完整的实体，更符合人的感知，同时，代码效率也大大提高了。
(2) 使用泛型和不使用泛型的编程，对你来说有何差异？
泛型的使用使得函数具有通用性。
(3) 在给出ADT的规约后就开始编写测试用例，优势是什么？你是否能够适应这种测试方式？
面向ADT编程的过程中适应性挺快，因为符合人类的思维习惯，基本能够适应这种测试方式。
(4) P1设计的ADT在多个应用场景下使用，这种复用带来什么好处？
切换不同场景的时候，代码的迁移能力强，相似的场景代码可复用。
(5) P3要求你从0开始设计ADT并使用它们完成一个具体应用，你是否已适应从具体应用场景到ADT的“抽象映射”？相比起P1给出了ADT非常明确的rep和方法、ADT之间的逻辑关系，P3要求你自主设计这些内容，你的感受如何？
基本能够适应，决定P3要求很高，没有框架的约束，对接口和类的设计就要有很好的全局把握，自顶向下的设计模式很重要。
(6) 为ADT撰写specification, invariants, RI, AF，时刻注意ADT是否有rep exposure，这些工作的意义是什么？你是否愿意在以后编程中坚持这么做？
检查不变量。为了提高代码的正确性，愿意坚持。
(7) 关于本实验的工作量、难度、deadline。
该实验工作量适中，P3的自主设计提高了实验的难度，但实验时间还是非常充足的。
(8) 《软件构造》课程进展到目前，你对该课程有何体会和建议？
能够提高编程规范、设计以及健壮性等，觉得受益匪浅。