《软件构造》Lab 2

2021年春季学期
计算学部《软件构造》课程

Lab 2

目录

1 实验目标概述 1
2 实验环境配置 1
3 实验过程 2
3.1 Poetic Walks 2
3.1.1 Get the code and prepare Git repository 2
3.1.2 Problem 1: Test Graph 3
3.1.3 Problem 2: Implement Graph 3
3.1.3.1 Implement ConcreteEdgesGraph 3
3.1.3.2 Implement ConcreteVerticesGraph 5
3.1.4 Problem 3: Implement generic Graph 7
3.1.4.1 Make the implementations generic 7
3.1.4.2 Implement Graph.empty() 8
3.1.5 Problem 4: Poetic walks 8
3.1.5.1 Test GraphPoet 8
3.1.5.2 Implement GraphPoet 8
3.1.5.3 Graph poetry slam 9
3.1.6 Before you’re done 9
3.2 Re-implement the Social Network in Lab1 10
3.2.1 FriendshipGraph类 10
3.2.2 Person类 11
3.2.3 客户端main() 12
3.2.4 测试用例 12
3.2.5 提交至Git仓库 14
4 实验进度记录 15
5 实验过程中遇到的困难与解决途径 16
6 实验过程中收获的经验、教训、感想 16
6.1 实验过程中收获的经验和教训 16
6.2 针对以下方面的感受 16

1 实验目标概述
本次实验训练抽象数据类型（ADT）的设计、规约、测试，并使用面向对象 编程（OOP）技术实现 ADT。具体来说：
⚫ 针对给定的应用问题，从问题描述中识别所需的 ADT；
⚫ 设计 ADT 规约（pre-condition、post-condition）并评估规约的质量；
⚫ 根据 ADT 的规约设计测试用例；
⚫ ADT 的泛型化；
⚫ 根据规约设计 ADT 的多种不同的实现；针对每种实现，设计其表示 （representation）、表示不变性（rep invariant）、抽象过程（abstraction function）
⚫ 使用 OOP 实现 ADT，并判定表示不变性是否违反、各实现是否存在表 示泄露（rep exposure）；
⚫ 测试 ADT 的实现并评估测试的覆盖度；
⚫ 使用 ADT 及其实现，为应用问题开发程序；
⚫ 在测试代码中，能够写出 testing strategy 并据此设计测试用例。
2 实验环境配置
简要陈述你配置本次实验所需环境的过程，必要时可以给出屏幕截图。
特别是要记录配置过程中遇到的问题和困难，以及如何解决的。

在这里给出你的GitHub Lab2仓库的URL地址（Lab2-学号）。
https://classroom.github.com/a/NL2TjK2z
3 实验过程
请仔细对照实验手册，针对两个问题中的每一项任务，在下面各节中记录你的实验过程、阐述你的设计思路和问题求解思路，可辅之以示意图或关键源代码加以说明（但千万不要把你的源代码全部粘贴过来！）。
3.1 Poetic Walks
一个图形接口，两个具体实现类ConcreteEdgesGraph，ConcreteVerticesGraph。实现类实现了接口的一系列方法，并重写了toString方法，接着进行泛型化，最后一步是基于之前的具体实现完成poet任务。
3.1.1 Get the code and prepare Git repository
如何从GitHub获取该任务的代码、在本地创建git仓库、使用git管理本地开发。
进入该网址https://github.com/ComputerScienceHIT/HIT-Lab2-1190201707即实验二的个人仓库

在本地需要放置项目的文件夹，右键git bash here,
输入git [email protected]:ComputerScienceHIT/HIT-Lab2-1190201707.git
本地仓库创建完毕

3.1.2 Problem 1: Test Graph
思路：根据Graph接口中描述的规约编写测试代码，对每个方法进行等价类划分。
过程：
testAdd：点存在与不在
testSet：边存在与不存在，权值>0,<0,=0
testRemove： 点存在与不在
testVertices：空与非空
testSources：边存在与不存在
testTargets：边存在与不存在
结果：覆盖率较高
3.1.3 Problem 2: Implement Graph
以下各部分，请按照MIT页面上相应部分的要求，逐项列出你的设计和实现思路/过程/结果。
这部分写于泛型化后
3.1.3.1 Implement ConcreteEdgesGraph
（1） Edge类

Edge 初始化构造方法
checkRep 顶点不为空且边权值不为负

// Abstraction function:
//AF(start)=起点
//AF(end)=终点
//AF(weight)=权值
// Representation invariant:
//weight>=0,start和end不是空的
// Safety from rep exposure:
//全部设置为private
测试的时候就挨个对每个方法进行测试
(2) ConcreteEdgesGraph类

顶点集和边集
// Abstraction function:
//AF(vertices)=图中的点
//AF(edges)=图中的边
// Representation invariant:
//edges长度大于0，有起始点
//边的点必须包含在vertices中
// Safety from rep exposure:
// private anf defensive copies
checkRep edges长度大于0，边的点必须包含在vertices中
@Override public boolean add(L vertex) 顶点存在返回false，不存在就添加并返回true
@Override public int set(L source, L target, int weight) weight<0时返回-1，weight=0时若该边存在删除并返回原weight，若不存在返回0，weight>0时若该边存在则替换并返回原weight，若不存在直接添加新边并返回0
@Override public boolean remove(L vertex) 删除顶点和相关边，该点存在返回true，否则返回false
@Override public Set vertices() 返回点集
@Override public Map<L, Integer> sources(L target) 返回输入点的起点与边权重的map
@Override public Map<L, Integer> targets(L source) 返回输入点的终点与边权重的map

测试

覆盖率

3.1.3.2 Implement ConcreteVerticesGraph
（1） Vertices类

// Abstraction function:
//AF(name)=顶点名字
//AF(to_this_point)=到达这个顶点的点以及对应边权重
//AF(from_this_point)=从这个顶点出发到达的点以及对应边权重
// Representation invariant:
//名字不为空，边权值大于0
// Safety from rep exposure:
//private
public L getname() 返回顶点名字
public Map<L,Integer> getsource() 返回该点的起点集
public Map<L,Integer> gettarget() 返回该点的终点集
（2） ConcreteVerticesGraph类

// Abstraction function:
//AF(vertices)顶点的list
// Representation invariant:
//vertices不重复

// Safety from rep exposure:

//private defensive copies

checkRep 顶点不重复
@Override public boolean add(L vertex) 顶点存在返回false，不存在就添加并返回true
@Override public int set(L source, L target, int weight) weight<0时返回-1，weight=0时若该边存在删除并返回原weight，若不存在返回0，weight>0时若该边存在则替换并返回原weight，若不存在直接添加新边并返回0
@Override public boolean remove(L vertex) 删除顶点和相关边，该点存在返回true，否则返回false
@Override public Set vertices() 返回点集
@Override public Map<L, Integer> sources(L target) 返回输入点的起点与边权重的map
@Override public Map<L, Integer> targets(L source) 返回输入点的终点与边权重的map

测试

覆盖率

3.1.4 Problem 3: Implement generic Graph
3.1.4.1 Make the implementations generic
泛型化，我选择直接ctrl+f然后替换，例如String替换为L，Edge替换为Edge，然后对toString等稍作修改
3.1.4.2 Implement Graph.empty()
返回一个具体实现

3.1.5 Problem 4: Poetic walks
3.1.5.1 Test GraphPoet
空文件，单行，多行，边权值全为1，边权值大于1，行尾与下一行有关联等情况进行考虑

覆盖率

3.1.5.2 Implement GraphPoet
// Abstraction function:
//AF(graph)=表示两个单词相连次数的有向图
// Representation invariant:
//读取文章后graph!=null
// Safety from rep exposure:
//private
private final Graph graph = Graph.empty();返回一个边图

readline逐行读，用split（“ ”）分割为数组，相邻元素调用set函数，若返回零说明图中原本不存在且已添加，若不为零则说明图中原本存在，则需要将边权值赋值为旧的权值oldEdgeWeight+1
3.1.5.3 Graph poetry slam

先String ans=words[0];记录首字母大写
对于输入语句同上面按行读划分为数组，对于相邻元素：
（1） 至少有一个不在graph，则直接执行ans+=" “+words[i].toLowerCase();
（2） 都在graph且存在点恰在二者之间，用retainAll方法取出这些点，找到权值和最大的存在inter，执行ans+=” “+inter+” “+words[i].toLowerCase();
（3） 都在graph但不存在点恰在二者之间，执行ans+=” "+words[i].toLowerCase();

3.1.6 Before you’re done
请按照http://web.mit.edu/6.031/www/sp17/psets/ps2/#before_youre_done的说明，检查你的程序。
如何通过Git提交当前版本到GitHub上你的Lab2仓库。
git status查看状况
执行push：
git add .
git commit -m “P1”
git push
在这里给出你的项目的目录结构树状示意图。

3.2 Re-implement the Social Network in Lab1
一个图形接口，两个具体实现类ConcreteEdgesGraph，ConcreteVerticesGraph。实现类实现了接口的一系列方法，并重写了toString方法，接着进行泛型化，最后一步是基于之前的具体实现完成poet任务。

3.2.1 FriendshipGraph类

结合任务一，将ConcreteEdgesGraph的L变为Person
public FriendshipGraph() 直接graph=new ConcreteEdgesGraph<>();
void addVertex(Person person) 直接graph.add(person);
void addEdge(Person p1,Person p2) 直接graph.set(p1, p2, 1);

getDistance思路类似lab1，但实现形式以前面的graph为基础，就像蛋卷一样一层一层向外拓展，越到外面越大，里面最中心只有一个人，每一层都代表里面一层target的集合（用集合vis表示是否遍历过），每一层都没有contains成功就有dis++（距离++）。
3.2.2 Person类
若未重名构造方法将值赋给myName
便于测试
public String getMyName() {
return this.myName;
}
3.2.3 客户端main()
同lab1

3.2.4 测试用例

测试结果

覆盖率，较低是因为main函数

3.2.5 提交至Git仓库
如何通过Git提交当前版本到GitHub上你的Lab3仓库。
git status查看状况
执行push：
git add .
git commit -m “final commit”
git push

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

4 实验进度记录
请使用表格方式记录你的进度情况，以超过半小时的连续编程时间为一行。
每次结束编程时，请向该表格中增加一行。不要事后胡乱填写。
不要嫌烦，该表格可帮助你汇总你在每个任务上付出的时间和精力，发现自己不擅长的任务，后续有意识的弥补。
日期 时间段 计划任务 实际完成情况
6.3 下午 写P1 发现P1有点多，只实现了ConcreteEdgesGraph的一部分
6.4 下午 完成P1 。。。写到了泛型化
6.11 19：00-22:00 完成poet 完成
6.13 上午10：00 完成P2 P2代码量并不大，完成
5 实验过程中遇到的困难与解决途径
遇到的难点 解决途径
最浪费时间的一个问题是关于remove函数，最早使用for(Edge edge:edges)
找到关联边就删除，但是测试总是出错，最后找到原因是删除了一个edge后for-each循环的逻辑就会出错，无法再找到下一个edge。

先进行一份copy然后遍历copy，删除的确实实际的edges中的元素，便可以避免之前的问题，后来了解到，可以直接用迭代器实现同样效果

FriendshipGraphTest测试没想到如何进行
FriendshipGraph中：

FriendshipGraphTest中：
FriendshipGraph graph=new FriendshipGraph();
ConcreteEdgesGraph g=graph.getGraph();
6 实验过程中收获的经验、教训、感想
6.1 实验过程中收获的经验和教训
起初因为缺乏经验以及对oop还是不够熟悉走了一些弯路，发觉了想要写出逻辑清晰关系明了的代码并不容易，自己写的有一点混乱，以后会通过实践进一步加强练习。
6.2 针对以下方面的感受
(1) 面向ADT的编程和直接面向应用场景编程，你体会到二者有何差异？
ADT是一个类一个对象写，更加抽象，感觉如果熟悉了会有利于大型任务的编写。面向过程就注重一步步的细节，差距很大。
(2) 使用泛型和不使用泛型的编程，对你来说有何差异？
泛型更灵活更容易扩展。
(3) 在给出ADT的规约后就开始编写测试用例，优势是什么？你是否能够适应这种测试方式？
按照规约写更不容易出错，逻辑框架上显然提前设计好强于边写边想，也更容易写测试，但是不太适应。
(4) P1设计的ADT在多个应用场景下使用，这种复用带来什么好处？
提高利用率。减轻负担，逻辑也更清晰。
(5) 为ADT撰写specification, invariants, RI, AF，时刻注意ADT是否有rep exposure，这些工作的意义是什么？你是否愿意在以后编程中坚持这么做？
意义在于时时告诫自己不要超出规约不要有rep exposure也就避免了很多错误，自己会努力熟悉这种方式。
(6) 关于本实验的工作量、难度、deadline。
对于三周来说挺适中的
(7) 《软件构造》课程进展到目前，你对该课程有何体会和建议？
Mit的英文任务看起来会很费时间>_<