• 欢迎光临~

软件构造 Lab 2

开发技术 开发技术 2022-06-09 次浏览

软件构造 Lab 2

2022年春季学期

计算学部《软件构造》课程

Lab 2实验报告

姓名 赵伟东
学号 120L05****
班号 2003****
电子邮件 986579251@qq.com
手机号码 166********

目录

1 实验目标概述··· 1

2 实验环境配置··· 1

3 实验过程··· 1

3.1 Poetic Walks· 1

3.1.1 Get the code and prepare Git repository· 1

3.1.2 Problem 1: Test Graph · 1

3.1.3 Problem 2: Implement Graph · 1

3.1.3.1 Implement ConcreteEdgesGraph· 2

3.1.3.2 Implement ConcreteVerticesGraph· 2

3.1.4 Problem 3: Implement generic Graph· 2

3.1.4.1 Make the implementations generic· 2

3.1.4.2 Implement Graph.empty()· 2

3.1.5 Problem 4: Poetic walks· 2

3.1.5.1 Test GraphPoet· 2

3.1.5.2 Implement GraphPoet· 2

3.1.5.3 Graph poetry slam·· 2

3.1.6 Before you’re done· 2

3.2 Re-implement the Social Network in Lab1· 2

3.2.1 FriendshipGraph类··· 2

3.2.2 Person类··· 3

3.2.3 客户端main()· 3

3.2.4 测试用例··· 3

3.2.5 提交至Git仓库··· 3

4 实验进度记录··· 3

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

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

6.1 实验过程中收获的经验和教训··· 4

6.2 针对以下方面的感受··· 4

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 实验环境配置

有了第一次实验的经验,本次实验在初始配置环境较为得心应手,在目录设置时出了一点小问题,最开始的P1与P2这两个package是独立的,各自有src和test文件夹,并且在java文件的第一行中是package.graph 和package. Interval,逐个进行修改较为繁琐

可以使用IDEA中refactor来进行统一修改,对应地修改每个java文件中的引用,非常方便。

实验中要用到的coverage覆盖测试的插件IDEA中已经默认安装。

在这里给出你的GitHub Lab2仓库的URL地址(Lab2-学号)。

https://github.com/ComputerScienceHIT/HIT-Lab2-120L052314

3 实验过程

3.1 Poetic Walks

Poetic Walks任务给出了一个图的接口Graph,需要我们继承这个接口来建立一个基于边的图和基于点的图,并实现相关的方法,从而实现抽象数据型(ADT),继而来实现对poet的操作。这个任务的目的是练习ADT的归约设计和ADT的实现。

3.1.1 Get the code and prepare Git repository

git clone git@github.com:ComputerScienceHIT/HIT-Lab2-120L052314.git在本地建立仓库,并使用git管理本地仓库

从https://github.com/rainywang/Spring2022_HITCS_SC_Lab2/tree/master/P1下载实验代码,按照实验要求调整目录。

git add . 将仓库中文件追踪,git commit -m “initial” 提交到本地仓库。

3.1.2 Problem 1: Test Graph

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

根据实验要求得知,对于Graph.empty()静态方法的测试已经在GraphStaticTest.java中给出,需要我们做的是在GraphInstanceTest.java中给出对于所有实例方法的测试策略和具体的测试。Graph中有add()、set()、remove()、vertices()、sources()、targets()几个实例方法,阅读给定的规约后,给出如下的设计策略:

  1. 首先对于每种实例方法都可以进行空图与非空图的划分;

  2. 对于测试顶点的实例方法,可以对顶点进行图中已经存在和图中不存在的划分;

  3. 对于测试边的实例方法,可以对边进行图中已经存在和图中不存在的划分(并且可以进一步细化为两点存在、一点存在、都不存在三种情况)、权值为正和权值不为正的划分;

  4. 根据上述策略来书写不同实例方法对应的不同策略。

编写覆盖上述条件的测试用例即可。

3.1.3 Problem 2: Implement Graph <String>

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

Graph接口中已经写好了一些空的方法,需要我们使用具体的边和点来表示Graph,并在实现类中对这些方法进行实现。按照实验要求,我们实现的所有类,都需要注明AF(抽象函数)、RI(表示不变量)和如何避免rep exposure(表示泄露),同时要求我们实现能够检查RI的函数checkRep()和便于输出的toString()函数。此外,实验要求每个不可变类型都必须重写equals和hashCode(本问题集不需要)。

3.1.3.1 Implement ConcreteEdgesGraph

实现ConcreteEdgesGraph首先得实现类Edge,根据实验要求,Edge类需要是不可变类型的。在Fields中添加三个rep,分别表示起始点、终止点和边的权重,并且在Edge中添加方法getSource、getTarget、getWeight。此外,需要重写方法toString,输出[sources,target,weight]的三元组字符串。

根据实验要求,还需要实现checkRep函数来检测表示不变量。

对于上述方法,给出Edge类的测试如下。
软件构造 Lab 2

​ 实现了Edge类后,基于Edge类实现ConcreteEdgesGraph类,首先给出AF、RI和rep exposure的声明:
软件构造 Lab 2

软件构造 Lab 2
EdgeGraph类的checkRep方法:
软件构造 Lab 2
​ 然后来实现Graph接口中的实例方法add、set、remove、vertices、sources、target方法。

  1. add方法

使用Set集合中的contains方法来判断添加的点是否在vertices集合中,如果在集合中,不进行添加操作,返回false;否则,使用Set集合的add方法来将新点添加到vertices集合中。添加成功后,在函数最后调用checkRep函数来检测表示泄露,并返回true。

  1. set方法

首先进行权值的判断,当权值为负数时,直接输出错误提示信息返回-1;当权值为0时,进行边是否存在的判断,如果该边存在于图中,将该边删除,否则不进行任何操作;当权值大于0时,如果该边存在于图中,用新的权值替换原来的权值,否则添加这条边。

当对权值进行变动时返回之前的权值,否则返回0.

并且我们可以观察到,当权值大于0时,需要进行的操作是对权值的更新或者添加这条边。由于我们的权值weight被声明为private final类型,所以无法对其进行改变,我们的操作是直接移除这条边,然后添加权值更新的这条边,这样一来,对权值的更新和直接添加这条边的操作有了重复的步骤,可以简化代码。

  1. remove方法

首先使用Set的contains方法判断当前点是否在有向图中,如果不在,则不进行任何操作返回false;如果在,从vertices中移除此点,并调用边集edges的迭代器来删除所有与当前点相关联的边。

  1. vertices方法

对于vertices方法的实现较为简单,但应注意,直接返回得到的类型为mutable类型,可以使用unmodifiable wrappers将其变为immutable类型。

  1. source和target方法

这两种方法的思想相同,都是通过创建一个HashMap,并利用迭代器来遍历edges集合来寻找点,并利用put方法将点和对于的边的权值对应的键值对添加到HashMap中。最后以使用 unmodifiable wrappers 将其变为immutable类型的。

  1. toString方法

我们可以利用在Edge类中实现的toString方法来实现ConcreteEdgeGraph类的toString方法,具体为创建一个存储为空的String类型edge_graph,使用迭代器遍历edges,每次访问边时,将此边的toString得到的字符串相加。

​ 然后可以在ConcreteEdgeGraphTest中重写这些方法的test,最后得到如下测试结果。
软件构造 Lab 2

3.1.3.2 Implement ConcreteVerticesGraph

对Graph的Vertices实现使用List来表示,其中每个Vertex必须存储以此顶点为起点的终点和对应权值,并且还需要保存此节点的标识。并且根据实验要求,Vertex必须为可变类型。

首先实现Vertex类,在fields中设置name属性来标识节点,设置Map<L,Integer>来记录以此节点为其实节点的所有点的信息和对应的权重。

为了便于Vertex类的操作,添加方法getName、getWeight来获取当前节点的名称和与target节点边的权重。添加add方法来添加target节点和对应权重到Map中。添加Set方法类比上一步来设置target节点和权值。添加Vertices方法来返回Map。最后是重写toString方法来输出这个Vertex。

实现Vertex类后,针对类中的方法来写测试,将对不同的方法的测试集合在一个总的vertexTest测试中,来验证方法的正确性。测试的基本原则仍然是,利用observer方法来检验instance方法,利用instance方法来对Vertex对象进行改变来测试observer方法。

下面来实现ConcreteVerticesGraph类,首先给出AF、RI和rep exposure的声明:

软件构造 Lab 2

​ 然后来重写ConcreteVerticesGraph的实例方法:

  1. add方法

首先判断当前要添加的点是否在有向图中,注意此处不能简单地调用vertices集合的contains方法,其传入的是Object类型,判断一个Vertex类型是否存在于vertices集合。因此我们需要写一个辅助方法contains来判断,输入一个L类型的vertex,来判断这个点是否在有向图中。

如果在有向图中,不进行任何操作,返回false;否则调用List的add方法来将这个点对应的Vertex(L)类型添加到vertices集合中。

  1. set方法

set的设计思路与ConcreteEdgeGraph中的相似,首先判断weight是否为负,如果为负,输出提示信息。weight大于0,则判断要设置的边是否存在,如果这条边存在,则更新weight;如果这条边不存在,则往图中添加这条边。Weight等于0,则判断要设置的边是否存在,如果这条边存在,则删除之前的边;否则不进行任何操作。

  1. remove方法

首先使用contains方法判断vertex是否存在于图中,如果不存在,直接返回false;如果存在,则通过迭代器来删除这个vertex,以及与这个vertex相关联的所有边。

  1. vertices方法

vertices方法需要返回一个Set类型的集合,里边包含了所有的顶点的L类型的标识。可以通过调用迭代器来将每个顶点的标识添加到Set类型的集合中。

  1. sources方法

首先创建一个Map(L,Integer)类型的集合sour,使用foreach循环遍历vertices集合,找到除target以外的所有顶点,如果其有指向target的边,则将这个顶点的标识和权值组成的键值对添加至sour中。

  1. targets方法

首先创建一个Map(L,Integer)类型的tar,使用foreach循环遍历vertices集合,如果一个顶点的标识等于source,则调用Vertex类型的vertices函数返回即可。如果都没有,则返回空集合。

  1. toString方法

为了便于观看,可以在Vertex类型的toString方法的基础上,在每个Vertex后边增加”n”,删除最后一个”n”即可。

​ 然后可以在ConcreteVerticesGraphTest中重写这些方法的test,最后得到如下测试结果:
软件构造 Lab 2

​ ConcreteEdgeGraph和ConcreteVerticesGraph覆盖度测试如下:
软件构造 Lab 2

3.1.4 Problem 3: Implement generic Graph<L>

3.1.4.1 Make the implementations generic

将Graph<String>类型换为Graph<L>,注意避免使用String类型特有的方法,使用通用的与类型无关的方法即可。(这里,我最开始写的时候,已经将<String>替换为通配符<L>,所以方法的替换已经完成)。

3.1.4.2 Implement Graph.empty()

我们可以通过上边实现的具体的类来Graph<L>接口,从而new一个新的Graph<L>对象,在此,我使用了ConcreteEdgesGraph 类。即直接return new ConcreteEdgesGraph<L>();

3.1.5 Problem 4: Poetic walks

Poetic walsk需要我们在所实现的Graph类的基础上,来实现一个能够根据已有的诗句来扩展语句的程序。

3.1.5.1 Test GraphPoet

这里给出的测试策略是,空图与非空图的测试,测试权重均为1的图和测试权重不都为1的图。针对不同的策略,编写不同的测试样例。

其中1.txt为空图,没有任何输入。2.txt为“a b c d a”,即权重均为1的图。3.txt为“a b c d a b a c”,即a到b的权重为2。由此可以编写如下测试样例。测试1输入字符串并以1.txt为输入,最后的输出应与输入的字符串相同。测试2输入字符串“a c b d”并以2.txt为输入,最后的输出应为“a b c b c d”。测试3输入字符串“a c a d c a”并以3.txt为输入,最后的输出应为“a b c d a c d a c d a”。

3.1.5.2 Implement GraphPoet

实验要求我们利用上一步骤中实现的Poem来实现GraphPoet类,其具有Graph类型的成员变量graph。我们需要实现其构造函数GraphPoet,使用一个文件名当作参数来生成一个语料库,即加权有向图。还要实现poem方法,使用我们生成的语料库来对输入的字符串进行扩充。

  1. GraphPoet的实现

对于一个文件输入,使用FileReader和BufferReader来高效的读取每行。对于每一行,先过滤掉每行末尾可能的标点符号,然后调用split方法将它分解为一个字符串数组。以步长为1来遍历这个字符串数组,每次将当前这个词和下一个词组成的边添加至图中,如果图中已经存在,就将权值加1,否则添加这条边。我们使用Graph类中的已经实现的set方法来实现刚才这个步骤,由于set函数,添加时,如果图中存在此边且输入的权值为正,则替换这个权值,返回之前的权值;如果图中不存在此边且输入的权值为正,则添加新的边,返回0。因此我们可以每次都用权值1来set一条边,通过设置一个preWeight来判断这条边是否存在,如果preWeigh大于0,则重新用preWeigh+1来设置权值;否则不做变动。

  1. Poem的实现

对于输入的每两个相邻的单词,我们需要找到,以前一个单词为source的所有targets和以后一个单词为target的所有sources,要添加的单词即为targets和sources的交集,并且如果交集中有多个元素,则返回两条边权值和最大的那个作为扩充的单词(如果权值都相同,就任选其一)。最后将扩充好的单词都加到同一个字符串中即可。

3.1.5.3 Graph poetry slam

首先使用实现原有的数据进行诗句扩展,得到如下输出:
软件构造 Lab 2

在同目录下添加一首新的小诗到test.txt中进行诗句扩展,得到如下输出:
软件构造 Lab 2

​ GraphPoet的覆盖率测试如下:
软件构造 Lab 2

3.1.6 Before you’re done

请按照http://web.mit.edu/6.031/www/sp17/psets/ps2/#before_youre_done的说明,检查你的程序。

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

git add . 对所有文件进行追踪

git commit -m “P1” 上传到本地仓库

git push 上传到远程仓库

在这里给出你的项目的目录结构树状示意图。
软件构造 Lab 2

3.2 Re-implement the Social Network in Lab1

利用3.1节实现的Graph接口的实现类ConcreteEdgeGraph类和ConcreteVertice类来重新实现Lab1中的FriendshipGraph类。

3.2.1 FriendshipGraph类

给出你的设计和实现思路/过程/结果。

1) addVertex()、addEdge()

我们可以利用ConcreteEdgeGraph类中的add方法和set方法来实现这两个方法。

addVertex方法通过add方法的返回值来判断是否添加成功并输出对应信息和返回值。

addEdge()方法通过set方法的返回值来判断是否添加成功并返回值,并且该图中每两个节点的权值始终为-1。

具体实现如下:
软件构造 Lab 2
软件构造 Lab 2

2) getDistance()

getDistance()利用BFS来计算两个节点的距离,与Lab1的思路相似,较为便捷的一点是可以借助ConcreteEdgeGraph类中的targets方法来获取与一个节点相邻的所有节点。具体实现见下图:
软件构造 Lab 2

3.2.2 Person类

Person类中只需要保存其节点信息即可,边的信息在ConcreteEdgeGraph中由List<Edge>保存。具体实现如下:
软件构造 Lab 2

3.2.3 客户端main()

将Lab1中的客户端代码复制到main方法中,可以发现客户端代码仍然和预期的输出相同。
软件构造 Lab 2

3.2.4 测试用例

给出你的设计和实现思路/过程/结果,覆盖度报告。

将Lab1的Junit测试的方法进行面向Graph类进行修改(使用Graph中的方法初始化),测试用例全部通过。
软件构造 Lab 2

​ 覆盖度测试如下:
软件构造 Lab 2

3.2.5 提交至Git仓库

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

git add . 对所有文件进行追踪

git commit -m “P2” 上传到本地仓库

git push 上传到远程仓库

在这里给出你的项目的目录结构树状示意图。
软件构造 Lab 2

4 实验进度记录

请使用表格方式记录你的进度情况,以超过半小时的连续编程时间为一行。

每次结束编程时,请向该表格中增加一行。不要事后胡乱填写。

不要嫌烦,该表格可帮助你汇总你在每个任务上付出的时间和精力,发现自己不擅长的任务,后续有意识的弥补。

日期 时间段 计划任务 实际完成情况
5.26 17:00-18:00 完成第P1的test Graph 未能按时完成,刚开始对于测试策略的实现与理论未能统一地实现
5.27 17:00-18:00 Implement Graph 按时完成
5.27 18:00-19:00 Implement generic Graph 延后半小时,对于泛型的了解不够
5.27 20:00-22:00 Test GraphPoet和Implement GraphPoet 完成Graph poetry slam 延后半小时完成,对于文件读写操作仍然不够熟练,并且对于Set、Map中的一些方法如:addAll、retainAll不了解
5.29 15:00-17:00 实现FriendshipGraph 中的 addVertex()、addEdge()和 getDistance()方法,并重新执行测试用例 getDistance步骤延时半小时,对于Java中的Queue的操作不够熟练
5.29 19:00-22:00 按照要求完善代码,书写报告 按计划完成

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

遇到的难点 解决途径
覆盖度测试时出现报错 修改用户名为英文,重新安装JDK,
泛型转换出错 对实现Graph的需要避免使用String类的方法
Queue的使用 阅读相关书籍,进一步得知了类似方法的不同之处

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

6.1 实验过程中收获的经验和教训

(1) 本次实验历时较久,相较上一次实验来说,不能紧凑地完成,在第一周实验周中由于对实验要求的阅读不够仔细,导致对于实验的入手没有头绪,面对复杂的文件结构不知道从哪一个开始。今后再做实验应该仔细阅读每一个细节,再整体去把握。

(2) 本次实验第二个收获就是感受到了spec的重要性,spec帮助我们去更快更清晰的认知一个方法的功能,在实验刚开始时没有仔细阅读归约,导致编写代码时,出现不同的错误,从而降低编程的效率。

6.2 针对以下方面的感受

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

面向 ADT 的编程一切只需要符合 ADT 的 spec 即可,具体有何应用场景,程序员无需知晓;而直接面向应用场景编程,程序员需要首先考虑如何设计 ADT,这是面向 ADT 的编程所不需要的。

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

不适用泛型可以利用一些具体的方法来实现,难度较泛型编程更简单一些。

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

能够最大地避免代码设计过程中代码对测试用例设计的影响,避免表示泄露,使得测试用例更具有可信性。最开始的时候觉得非常奇怪,因为平常的测试用例都是针对具体的代码,无中生有式设计最开始难以理解,以至于托了许久。但是当实验做到最后才如梦初醒,意识到给出归约就开始编写测试用例的优势。

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

使得代码更简洁,后续如果需要修改代码也更加方便。

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

这些工作的意义是为了确保ADT的安全性、健壮性等等,以及是否符合spec。我愿意在以后坚持这么做,因为这么做可以使编程规范并且高效。

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

工作量中等偏上,主要是开始对于这种编程模式难以适应,难度始终,deadline较紧,本学期由于学时压缩,许多课程的考试都提前,本次实验的过程中还需兼顾其他课程的复习,所以整体压力略大。

(7) 《软件构造》课程进展到目前,你对该课程有何体会和建议?

越来越在代码中体会到这课程的奥妙之处,所以针对每一个知识点,希望能多给出一点针对代码的训练和指导。

程序员灯塔
转载请注明原文链接:软件构造 Lab 2
喜欢 (0)