HIT软件构造lab2实验心得
HIT软件构造lab2实验心得
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实验环境配置
根据实验手册中的网址，在eclipse中：help – Eclipse Marketplace – search – EclEmma Java Code Coverage – install 安装成功
URL地址：
https://github.com/ComputerScienceHIT/HIT-Lab2-1190202013
3实验过程
请仔细对照实验手册，针对三个问题中的每一项任务，在下面各节中记录你的实验过程、阐述你的设计思路和问题求解思路，可辅之以示意图或关键源代码加以说明（但千万不要把你的源代码全部粘贴过来！）。
3.1Poetic Walks
MIT指导页面链接：http://web.mit.edu/6.031/www/sp17/psets/ps2/
该问题已经提供了ADT大体框架，graph的接口，要求我们建立一个边图类ConcreteEdgesGraph、一个点图类ConcreteVerticesGraph实现graph接口，实现抽象数据型，完成poet的工作。Graph接口要求实现add（添加新节点），set（添加新边），remove（移除节点），vertices（获得所有的节点集合），sources（target）获得以target为目标节点的边的起始节点，targes(source)获得以source为起始节点的边的目标节点。
Poet：假设存在一条由a到b的有向边，构造有向图，再给定一句子，如果句子中两个相邻单词在有向图中有一个中间单词，则将该单词插入到a与b中间，若存在多个中间单词，则插入权重最大的那个
3.1.1Get the code and prepare Git repository
如何从GitHub获取该任务的代码、在本地创建git仓库、使用git管理本地开发。
网址：https://github.com/rainywang/Spring2020_HITCS_SC_Lab2/tree/master/P1
gitbash直接执行git clone https://github.com/rainywang/Spring2020_HITCS_SC_Lab2.git下载工程文件
git clone https://github.com/ComputerScienceHIT/Lab2-1190202013.git
本地仓库建好
3.1.2Problem 1: Test Graph
以下各部分，请按照MIT页面上相应部分的要求，逐项列出你的设计和实现思路/过程/结果。
针对Graph设计测试策略，编写测试用例主要利用等价类划分的思想进行测试。
过程：用String类为Graph编写测试用例。共需编写六个函数的测试用例：add, set, remove, vertices, sources, targets。add, set, remove属于mutator；vertices, sources, targets属于observer。如下所示，为所有方法的测试策略
将Graph中的empty()方法修改为：
并对GraphStaticTest进行JUnit测试，如下：
用String类为Graph编写测试用例。共需编写六个函数的测试用例：add, set, remove, vertices, sources, targets。add, set, remove属于mutator；vertices, sources, targets属于observer
在coverage中查看覆盖率如下
3.1.3Problem 2: Implement Graph
分别实现两个实现类ConcreteEgesGraph和ConcreteVerticesGraph，需标注创建的每一个类的AF和RI，如何防止表示泄露。使用函数checkRep来检验是否符合RI，重写toString函数以便输出该类信息。
3.1.3.1Implement ConcreteEdgesGraph
3.1.3.1.1实现Edge:
1、EDGE中的字段包括边的起始节点、目标节点和边权值，定义为私有类型变量，信息对外界隐藏，使用final是其值不可变，防止外部对内部引用使其泄露。
2、实现Edge需要实现的方法：
Fileds 作用
private final L source 起始节点
private final L target 目标节点
private final int weight 边权值
Method 作用
Edge 初始化构造方法，初始化边的起始节点和目标节点和边权值
checkRep() 检查表示不变性，两点不为null且权值非负
getsource() 返回有向边起始节点
gettarget() 返回有向边目标节点
getweight() 返回边权值
@Override toString() 使用@Override注释toString以确保正确覆盖Object方法的toString方法
3、AF、RI和Safety from rep exposure
4、Edge测试策略：
3.1.3.1.2实现ConcreteEdgesGraph类：
1、ConcreteEdgesGraph字段中包括顶点set表和边list表，定义私有类型的表如下图所示：
2、实现ConcreteEdgesGraph需要实现的方法：
Method 作用
private void checkRep() 检查表示不变性，edges长度是大于0的实数，有起始的节点
public boolean add(L vertex) 调用vertices.add，其返回结果为boolean且满足spec定义。
public int set(L source, L target, int weight) 前置条件要求weight>=0，如果weight<0，输出提示信息。在weight>=0的条件下，对图的边表进行遍历，若存在顶点为source，终点为target的边，保存这条边原本的权值，否则设为0。如果weight>0，则将这条边及顶点加入或者修改原有边的权值；如果weight=0，删除这条边。返回原本的权值。
public boolean remove(L vertex) 从vertices中删去，传入的参数vertex点，遍历edges，寻找是否有边的起点或者是终点是该vertex，删去。注意在使用迭代器遍历时要使用iterator.remove方法保证安全。
public Set vertices() 返回vertices集合
public Map<L, Integer> sources(L target) 根据传入的target参数寻找以targe为终点的边。返回一个键值对为（点，权重）的map。
public Map<L, Integer> targets(L source) 根据传入的source参数寻找以source为起点的边。实现同上
public String toString() 将整个图中所有点的指向转化为一条字符串输出
3、AF,RI和Safety from rep exposure
4、测试策略：继承Graph的测试策略，并增加toString的测试
测试结果如下：
检查覆盖率：
3.1.3.2Implement ConcreteVerticesGraph
3.1.3.2.1实现Vertex：
1、字段中应当包括点的名字，点的源点表Map，点的终点表Map，定义私有类型的表
Filed 作用
private L name 节点名字
private Map<L,Integer> sources 所有以name为目标节点的边，<起始节点name,边的权重>
private Map<L,Integer> targets 所有以name为起始节点的边，<目标节点name,边的权重>
2、在Vertex需要实现的方法:
Interface 作用
private void checkRep() 检查表示不变性，每个边的权值应该大于0
public L getname) 返回该节点的name
public Map<L,Integer> getsources() 根据传入的targets参数寻找以targe为终点的边。返回一个键值对为（点，权重）的map。
public Map<L,Integer> gettargets() 根据传入的sources参数寻找以targe为终点的边。返回一个键值对为（点，权重）的map。
public int addsource(L newsource,int weight) 加入一条以source为起点，当前顶点为终点的边，即将source, weight加入sources
public int addtarget(L newtarget,int weight) 加入一条以当前点为起点，当前target为终点的边，即将target, weight加入targets
public int removesource(L newsource) 在源点表中删除某起始点，并返回旧的边长
public int removetarget(L newtarget) 在终点表中删除某终点，并返回旧的边长
public String toString() 得到一个点的字符串表示
3、AF,RI和Safety from rep exposure：
4、测试策略：
3.1.3.2.2实现ConcreteVerticeGraph:
1、ConcreteVerticesGraph的字段为Vertex构成的List，定义私有类型的表：
2、在ConcreteVerticesGraph需要实现的方法：
Method 实现思路
private void checkRep() 检查表示不变性，vertices中没有重复点
public boolean add(L vertex) 检查输入满足vertex!=null，添加一个顶点进入点表中
public int set(L source, L target, int weight) 输入source，target，weight，分别为边的起点、终点和权值。若权值为负，返回-1。若权值为正且新边已经存在，则除去原边并添加新边。若权值为正且新边不存在，则直接添加新边。若权值为0且新边已经存在，则出去原边。只要改变了原边权值，都返回原边权值，没有权值则返回0
public boolean remove(L vertex) 除去某个点及与它相邻的所有边。只需要遍历vertices，寻找是否有与待删除点相同的名字的点直接删去即可，如果名字不相同，则在该点的源点表和终点表中寻找删去即可，使用迭代器实现。
public Set vertices 返回所有的点集
public Map<L, Integer> sources(L target) 输入一个终点，返回与它相连的所有边和起点构成的Map
public Map<L, Integer> targets(L source) 输入一个起点，返回与它相连的所有边和终点构成为的Map
public String toString() 将整个图中所有点的指向转化为一条字符串输出
3、AF,RI和Safety from rep exposure如下图：
4、测试策略：继承Graph的测试策略并增加toString的测试
测试结果：
检查覆盖率：
3.1.4 Problem 3: Implement generic Graph：
3.1.4.1 Make the implementations generic
将所有String改为L，并且Edge需改为Edge，Vertex需改为Vertex。
3.1.4.2 Implement Graph.empty()
选择ConcreteEdgesGraph作为Graph.empty()的实现类，返回new ConcreteEdgesGraph
测试策略：
测试结果：
覆盖率：
3.1.5 Problem 4: Poetic walks
任务要求我们实现一个类，利用之前实现的图结构，能够将语料库转化为该种图结构，并且在图中搜索，完成对输入的诗句的句子进行扩充。
3.1.5.1 Test GraphPoet
测试策略：
GraphPoet()考虑到了输入文件是否存在、文件中含有多个连续空格、大小写、换行符、空行、标点符号、重复的词以及连续的词或词组等特殊情况，依此设计测试用例；
poem()图中没有的词、相邻的两个词、两个词之间的路径经过多个词的情况不作改变；存在两个词在图中有一条只经过一个桥接词的路径；存在两个词在图中有多条只经过一个桥接词的路径。
具体实现读入一系列满足要求的文件：
测试结果为：
测试覆盖率为：
3.1.5.2 Implement GraphPoet
1、构造器GraphPoet(File corpus)
一行一行读入文件，以空格为界将词分开存入列表，以每两个连续的词作为顶点，这两个顶点之间有边，记录两个词连续出现的次数作为边权。
观察器poem(String input)
输入需要进行扩充的字符串，声明声明一个StringBuilder保存，每次读取一个词，当前词作为source，下一个词作为target，然后在garph中寻找source的终点表中是否有与target的源点表中相同的元素，并且找到权值最大的和的点加入source和target之间，返回扩充后的字符串。
Checkrep
检查是否符合RI：图中每个词都不是空，不含有空格和换行符，都是小写，每个词都有边与之相连。
toString
调用ConcreteEdgesGraph中的toString方法，将整个图中所有点的指向转化为一条字符串输出
2、 AF,RI和Safety from rep exposure如下图：
3.1.5.3 Graph poetry slam
运行main函数如下输出：
3.1.6 Before you’re done
如何通过Git提交当前版本到GitHub上你的Lab2仓库。
在这里给出你的项目的目录结构树状示意图。
3.2Re-implement the Social Network in Lab1
这次实验要求我们基于Poetic Walks中定义的Graph及其两种实现（本人使用的是ConcreteVerticesGraph），实现Lab1中Social NetWorek中的各种功能，并且尽可能复用ConcreteVerticesGraph中已经实现的方法，然后运行提供的main()和执行Lab1中的Junit测试用例，使之正常运行。
3.2.1 FriendshipGraph类
(1).FriendshipGraph的字段为Person构成的ConcreteEdgesGraph，定义私有类型的表如下图所示：
(2).在FriendshipGraph需要实现的方法如下图所示：
FriendshipGraph 构造方法
addVertex 在图中增加新Person，只需要调用ConcreteEdgesGraph中的add即可：
addEdge 为某个人增加朋友,a为这个人，b为增加的朋友,直接调用ConcreteEdgesGraph中的set即可：
getallprople 直接返回即可：
getDistance 遍历顶点以及其sources，根据广度优先算法，构建队列。将起点先加入队列，然后每次从队头弹出一个点，将其sources中还未在队列中的顶点压入队尾，直到遍历到终点。在这个过程中记录起点距每个点的距离即可。若直到队空也没有遍历到终点，则返回-1。
00
main 复制Lab1的即可
(3).AF,RI和Safety from rep exposure如下图：
3.2.2 Person类
(1).FriendshipGraph的字段为Person构成的ConcreteEdgesGraph，定义私有类型的表如下图所示：
(2).在FriendshipGraph需要实现的方法如下图所示：
Person 没有重复名字则加入，构造方法
getmyname 返回本人名字，直接返回即可
(3).AF,RI和Safety from rep exposure如下图：
3.2.3 客户端main()
复制Lab1 3.3中的main运行后如下：
3.2.4 测试用例
测试策略：
与Lab1的测试策略相同：
测试结果：
检查覆盖率：(需要提前注释main()函数)：
3.2.4 提交至Git仓库
如何通过Git提交当前版本到GitHub上你的Lab2仓库。
与提交P1相似
在这里给出你的项目的目录结构树状示意图。
4实验进度记录
请使用表格方式记录你的进度情况，以超过半小时的连续编程时间为一行。
每次结束编程时，请向该表格中增加一行。不要事后胡乱填写。
不要嫌烦，该表格可帮助你汇总你在每个任务上付出的时间和精力，发现自己不擅长的任务，后续有意识的弥补。
日期 时间段 计划任务 实际完成情况
5.25 13:00-22:30 完成P1边图类 完成
5.26 15：30-23：30 完成P1点图类 完成
5.28 15：30-20：00 GraphPoet和poem 未按计划完成
5.29 13：00-16：30 Poem 完成
6.3 15：30-20：00 修改完善测试用例 完成
6.4 14：30-19：30 FriendshipGraph 完成
6.10 15：30-16：00 完善测试用例 完成
6.11 13：00-16：00 完善报告 完成
5实验过程中遇到的困难与解决途径
遇到的难点 解决途径
换成泛型后很多警告
按照提示增加<>
Git二次提交
不太会使用git二次提交文件，所以重新增加 master 重新push
6实验过程中收获的经验、教训、感想
6.1实验过程中收获的经验和教训
在自行设计多种类来实现功能的情况下，自己设计的很多类之间有很多重复和矛盾的部分，很多关系弄不清楚
6.2针对以下方面的感受
(1)面向ADT的编程和直接面向应用场景编程，你体会到二者有何差异？
答：面向ADT需要考虑底层实现，而面向应用场景无需了解ADT如何实现各种功能，直接调用即可。
(2)使用泛型和不使用泛型的编程，对你来说有何差异？
答：使用泛型应用范围更广，但设计的时候需要考虑不能应用某一类型内部的方法；不使用泛型应用范围窄，但设计时可以应用某一特定类型包装好的方法。
(3)在给出ADT的规约后就开始编写测试用例，优势是什么？你是否能够适应这种测试方式？
答：能够保证代码的正确性，及时修改。不适应。
(4)P1设计的ADT在多个应用场景下使用，这种复用带来什么好处？
答：可以提高代码的利用率，减少重复。
(5)P3要求你从0开始设计ADT并使用它们完成一个具体应用，你是否已适应从具体应用场景到ADT的“抽象映射”？相比起P1给出了ADT非常明确的rep和方法、ADT之间的逻辑关系，P3要求你自主设计这些内容，你的感受如何？
答：适应方式就是在应用场景时只考虑应用场景，“忘记”ADT内部的具体实现方式。自主实现感觉需要自己考虑的东西变多了。
(6)为ADT撰写specification, invariants, RI, AF，时刻注意ADT是否有rep exposure，这些工作的意义是什么？你是否愿意在以后编程中坚持这么做？
答：保证程序的安全性和健壮性。可能很难坚持。
(7)关于本实验的工作量、难度、deadline。
答：感觉工作量还挺多的。
(8)《软件构造》课程进展到目前，你对该课程有何体会和建议？
答：实验和课堂上的理论结合非常紧密。