1 实验目标概述

本次实验训练抽象数据类型（ADT）的设计、规约、测试，并使用面向对象

编程（OOP）技术实现 ADT。具体来说：

l 针对给定的应用问题，从问题描述中识别所需的 ADT；

l 设计 ADT 规约（pre-condition、post-condition）并评估规约的质量；

l 根据 ADT 的规约设计测试用例；

l ADT 的泛型化；

l 根据规约设计 ADT 的多种不同的实现；针对每种实现，设计其表示

（representation）、表示不变性（rep invariant）、抽象过程（abstraction

function）

l 使用 OOP 实现 ADT，并判定表示不变性是否违反、各实现是否存在表

示泄露（rep exposure）；

l 测试 ADT 的实现并评估测试的覆盖度；

l 使用 ADT 及其实现，为应用问题开发程序；

l 在测试代码中，能够写出 testing strategy 并据此设计测试用例。

2 实验环境配置

实验环境的配置在实验一中已经解决了。

3 实验过程

3.1 Poetic Walks

主要是应用对ADT的规约设计，考察对AF、RI、Spec、safety strategy的撰写，以及对ADT的多种不同的实现。练习TDD测试优先编程，练习对ADT泛型化。

1. 完善Graph接口类，并泛型化，将String类泛化为L
2. 实现Graph接口类，利用两个实现类实现接口，分别用邻接表和边表＋点表的存储方式实现Graph
3. 实现GraphPoet类，利用已经实现的Graph，使用图的思想。具体来说，是将输入的文本抽象为图，并在两个词中增加词，即是在连通的两点之间增加桥点，该点与两点直接连接，并为权值最大的边。

3.1.1 Get the code and prepare Git repository

点击老师给的链接，将代码clone下来

建立好project，然后打开git bash，输入以下命令

git init

git remote add origin git@github.com:ComputerScienceHIT/HIT-Lab2-2021111475.git

git pull origin master

git add .

git commit -m master

git push origin master

在本地创建git仓库并连接到远端

3.1.2 Problem 1: Test Graph <String>

以下各部分，请按照MIT页面上相应部分的要求，逐项列出你的设计和实现思路/过程/结果。

1. GraphStaticTest

这一部分是对Graph.Empty()方法的测试，在3.2实现了Graph.Empty()之后就能跑起来

1. GraphInstanceTest

该部分是对Graph中具体方法的测试，

Graph.add

测试点是否被加入图里
划分为有重复词和无
未重复的词语可以被加入，否则不能

Graph.set
划分为以下几部分
加入边的种类：
加入一条点已经存在的非零边；返回0
加入一条两个点都没有存在的非零边；返回0，点已经被加入
加入一条只有一个点存在的非零边；返回0，点已经被加入
加入一条零边；返回0
加入一条负边；返回-1
权值：
将边权值改为0；返回之前的权值
将上条边权值改为另外的正权值；返回0

Graph.remove
划分为已存在的点和不存在的点
删除一个存在的点；该点被删除，连接该点的边都已被删除
删除一个不存在的点；出现错误

Graph.vertices
划分为空图和非空的图
初始化图，并new一个set作为测试
测试是否生成了一个set
添加点进图，测试是否生成了一个存有该点的set

Graph.sources
划分为空图和非空的图，存在的点和不存在的点
初始化图，并new一个map作为测试
增加点和对应的边，测试是否能存入
删除点，测试是否将点删除

Graph.targets
划分为空图和非空的图，存在的点和不存在的点
初始化图，并new一个map作为测试
增加点和对应的边，测试是否能存入
删除点，测试是否将点删除

测试代码覆盖度

1. ConcreteEdgesGraphTest

该部分继承了GraphInstanceTest，测试toString()方法；测试Edge类

ConcreteEdgesGraph.toString()
划分为点表中是否有点
划分为边表中是否有边
划分为空表和非空表
在点表中存入几个点，测试是否满足设定
在边表存入几条边，测试是否满足设定
测试空表是否满足设定
在点表中存入几个点，在边表中存入几条边，测试是否满足设定

Edge
将边加入边集
测试是否能够成功运行getSource、getTarget、getWeight和toString方法

测试覆盖度

1. ConcreteVerticesGraphTest

该部分继承了GraphInstanceTest，测试toString()方法；测试Vertex类

ConcreteVerticesGraph.toString()
表中是否存有点
表中是否存有边
空图
在点表中加入单点，测试是否满足设定
在点表中加入点和边，测试是否满足设定
测试空图是否满足设定

Vertex
划分为加入边，不加入边
划分为使用不同的构造方法构造图
不加入边，测试getSource方法
加入一条边，测试getTarget方法
用第二种构造方法加入第一条边，再利用addedge方法加入第二条边，测试是否成功加入
加入两条边，并利用removeedge方法删除一条边，测试是否成功删除
不加入边，测试toString方法是否满足设定
加入两条边，测试toString方法是否满足设定

测试覆盖度

3.1.3 Problem 2: Implement Graph <String>

首先查看了一下Graph的代码，这里边已经写好了一些空的方法，需要我们利用不同的存储方式来表示Graph，用两种方式来实现他给我们提供的Graph接口。实验要求我们要求注明AF、RI以及避免产生rep exposure的方法的信息，要求设计出合理的检查函数checkRep()，要求设计出合理的构造器、观察器，要求重写equals方法、hashCode方法以及toString方法。这里简单介绍以下相关概念的理解：

Abstraction function：抽象函数（AF），可以看作我们设计的类的成员变量到这些变量所表示的抽象概念的映射。换言之就是我们如何用自己声明的具体变量去表示求解问题时的抽象对象，在本实验中即图的信息：怎样表示这个图包含了哪些顶点与哪些边；

Representation invariant：表示不变量（RI），所有值的一个包含所有合法的值的一个子集，也可以看作对合法信息的一种描述：对于每个变量，怎样的数据（参数）是合法的，怎样的数据（参数）是不合法的；

Safety from rep exposure：防止表示泄露，在代码提供至客户方时，为防止关键信息被修改导致程序崩溃或产生bug，需要对关键数据进行保护，最典型的方法就是使用私有类型变量以及不可变类型变量；

注：撰写实验报告时已经完成实验，故截图是已经实现泛型化的了。

3.1.3.1 Implement ConcreteEdgesGraph

这一部分要求我们利用边来实现Graph

1. 首先来实现Edge类

三个主要的Field，分别表示边的始点，终点，权值

然后设计规约

设计checkRep()函数检查合法性

编写Edge的构造函数

然后依次实现Edge的各个方法

1. ConcreteEdgesGraph

利用Edge类来实现Graph

首先定义两个Field

分别用来记录不能发生重复的名字表(点表)和边表

然后给出规约

编写构造方法，此处给出空图即可

设计checkRep()方法来检查图的合法性

实现Graph的各种方法

public boolean add(L vertex)

根据函数规约，该方法的目的是添加一个点，注意检查该点是否已经存在于vertices中

public int set(L source, L target, int weight)

根据函数规约，该方法的目的是要设置边

如果权值不合法(weight<0)，则报错并返回-1

如果权值合法，则进行以下操作：如果该边已经存在，若权值大于零则更改边权值然后返回原边权值，若权值等于零，则删除该边并返回原权值；如果该边不存在，则添加边并设置权值，返回0；如果点不存在，则添加点、边并返回零

public boolean remove(L vertex)

根据函数规约，该方法的目的是移除一个点

若该点不存在，则报错并返回false

若该点存在，则在vertices()中remove该点，遍历Edge删除source或target是该点的边，成功删除后返回true

public Set<L> vertices()

根据函数规约，这里只需要返回由图的顶点构成的集合即可。注意到保证数据信息不泄露，需要返回一个由vertices集合复制的新集合。

public Map<L, Integer> sources(L target)

根据函数规约，函数需要返回所有直接指向target的点以及与之对应的边的权值。这里规定了返回值的类型为Map，故只需要生成一个Map然后遍历edges集合寻找所有以target为终点的边并将其始点作为键名、权值作为键值添加到新生成的Map中，最后返回该Map即可。

public Map<L, Integer> targets(L source)

根据函数规约，函数需要返回所有source直接指向的点以及与之对应的边的权值。这里规定了返回值的类型为Map，故只需要生成一个Map然后遍历edges集合寻找所有以source为始点的边并将其终点作为键名、权值作为键值添加到新生成的Map中，最后返回该Map即可。

public String toString()

函数需要将图的所有信息打印出来，即所有的点与边的信息。故先将所有的点的名称打印出来，随后遍历edges集合，循环调用Edge类的toString方法即可。

3.1.3.2 Implement ConcreteVerticesGraph

这一部分要求我们用点表来实现Graph

1. Vertex

Vertex类需要包括点以及以该点作为始点的边及边的权值

设计以下两个Field，source存储该点的名字，利用一个Map来构造边，边的终点作为键名，边权为键值

设计规约

给出构造方法，此处给出两种构造方法

根据规约设计checkRep()方法，检查合法性

然后依次实现Vertex中的各个方法

ConcreteVerticesGraph

利用Vertex类来实现Graph

首先设计1个Field，用来存储所有图中的点

设计规约

构造方法只用给出一个空图

根据规约设计checkRep()来检查合法性

然后实现其他方法

public boolean add(L vertex)

根据函数规约，该方法的目的是添加一个点，注意检查该点是否已经存在于vertices中，若存在则提示并返回false

public int set(L source, L target, int weight)

根据函数规约，该方法主要分三种操作：修改已有的边，移除已有的边，添加新的边。因此，先遍历vertices集合，确定源点和终点是否存在。若源点存在，则在其终点集中进行setTargets操作；若终点存在，则在其源点集进行setSources操作。若某一端点不存在，则创建该点，设置对应的源点/终点集，然后在vertices集合加入新生成的点。返回值与对应setTargets/setSources操作返回值相同（checkRep()函数保证了setTargets/setSources操作返回值是相同的，返回任意一个即可）。

public boolean remove(L vertex)

根据函数规约，在vertices集合中找到vertex点，若找到，先将vertex从vertices集合中其他点的源点集与终点集中去除，然后在vertices集合中删除vertex并返回true；若未找到，直接返回false。

public Set<L> vertices()

根据函数规约，这里只需要返回由图的顶点构成的集合即可。构建一个新的集合，将vertices集合中所有点的标识加入该集合中即可。

 public Map<L, Integer> sources(L target)

根据函数规约，需要返回该点的始点集合，遍历vertices集合找到所有以该点为终点的始点集合，返回该始点集即可

根据函数规约，直接返回source点的终点集即可。注意到保证数据信息不泄露，需要返回一个由source点的源点集复制的新集合。

public String toString()

函数需要将图的所有信息打印出来，即所有的点与边的信息。故先将所有的点的名称打印出来，随后遍历vertices集合，循环调用vertices类的toString方法即可

3.1.4 Problem 3: Implement generic Graph<L>

这一部分需要我们将用String实现的类都泛型化为L

3.1.4.1 Make the implementations generic

在类的声明中更改为L即可

更改每一个实现类及其内部的方法

3.1.4.2 Implement Graph.empty()

任选一个实现类来构造一个空图即可

我选用的是ConcreteEdgeGraph()

3.1.5 Problem 4: Poetic walks

这一部分要求我们用刚刚已经实现的Graph类来撰写一个添加词汇的作诗类

3.1.5.1 Test GraphPoet

将整个测试集划分为如下的等价类

GraphPoet()

将读入的文件类型作为依据，划分为三个等价类，依次设计测试

 Poem()

将输入的字符串划分为三个等价类，分别测试无输入、输入带有桥点的文字、输入不带桥点的文字的情况，分别设计测试

 toString()

将图按照是否为空，划分为两个等价类，分别设计测试

3.1.5.2 Implement GraphPoet

设计field，用已经实现的Graph来存该图

设计规约

 GraphPoet的构造方法

从文件中读入一段文字，若打开文件失败则抛出异常；若成功打开文件，则按行读入文件中的文字，在每一行用split按空格切割，存入words中

将words转为图，每一个元素为图中的点，相邻的元素初始化为权值为1的边，每次出现边权加一

checkRep

设计checkRep来检查合法性

 Poem

该方法是输入一段文字，判断能否在每两个词A、B之间增加单词

增加的单词，必须有以A为始点，直接相连的边以及以B为终点直接相连的边，并且边的权值为所有这样的点中的最大值。

遍历输入的文字，每两个单词之间遍历图查询一遍是否存在桥点，若存在就加入，将最终的结果返回 

toString

直接利用构造出来的图的toString方法即可。

3.1.5.3 Graph poetry slam

在所给的txt文件中写入一首英文小短诗

在main方法中运行

运行结果

与预期结果一致

3.1.6 使用Eclemma检查测试的代码覆盖度

1. Graph

1. GraphPoet

3.1.7 Before you’re done

如何通过Git提交当前版本到GitHub上你的Lab2仓库。

$git add .

$git commit -m master

$git push origin master

在这里给出你的项目的目录结构树状示意图。

3.2 Re-implement the Social Network in Lab1

这一部分要求我们重新实现实验1中的FriendshipGraph类

3.2.1 FriendshipGraph类

设计Field

设计规约

设计构造方法，利用已经实现的Graph，我选用的是ConcreteVerticesGraph

再利用已经实现的方法实现FriendshipGraph的其他方法

addVertex

addEdge

getDistance

3.2.2 Person类

设计Field，存储Person对象的名字

设计规约

设计checkRep()

构造方法

其他方法：

3.2.3 客户端main()

运行结果

3.2.4 测试用例

1. 对addVertex方法进行测试
2. 对addEdge方法进行测试
3. 对getDistance()方法进行测试

测试覆盖度：

3.2.5 提交至Git仓库

如何通过Git提交当前版本到GitHub上你的Lab3仓库。

在这里给出你的项目的目录结构树状示意图。

4 实验进度记录

5 实验过程中遇到的困难与解决途径

6 实验过程中收获的经验、教训、感想

6.1 实验过程中收获的经验和教训（必答）

6.2 针对以下方面的感受（必答）

(1) 面向ADT的编程和直接面向应用场景编程，你体会到二者有何差异？

面向ADT的编程就像给问题逐层抽象，更像是一个划分为多个子问题的解法，直接面向应用场景编程，更类似于一个全局的抽象

(2) 使用泛型和不使用泛型的编程，对你来说有何差异？

使用泛型的编程对于复用更有利，适用范围也更广

(3) 在给出ADT的规约后就开始编写测试用例，优势是什么？你是否能够适应这种测试方式？

依据规约来对用例进行约束，更容易发现代码的bug

(4) P1设计的ADT在多个应用场景下使用，这种复用带来什么好处？

能够简化编程

(5) 为ADT撰写specification, invariants, RI, AF，时刻注意ADT是否有rep exposure，这些工作的意义是什么？你是否愿意在以后编程中坚持这么做？

为了防止客户了解和更改内部的细节，有助于提高代码效率。愿意

(6) 关于本实验的工作量、难度、deadline。

挺多的，但是也还行

(7) 《软件构造》课程进展到目前，你对该课程有何收获和建议？

无