针对给定的应用问题，从问题描述中识别所需的ADT；
设计ADT规约（pre-condition、post-condition）并评估规约的质量；
根据ADT的规约设计测试用例；
ADT的泛型化；
根据规约设计ADT的多种不同的实现；针对每种实现，设计其表示（representation）、表示不变性（rep invariant）、抽象过程（abstraction function）
使用OOP实现ADT，并判定表示不变性是否违反、各实现是否存在表示泄露（rep exposure）；
测试ADT的实现并评估测试的覆盖度；
使用ADT及其实现，为应用问题开发程序；
在测试代码中，能够写出testing strategy并据此设计测试用例。

实验环境配置

Windos10专业版，eclipse，jdk-9.01，Junit5.

在这里给出你的GitHub Lab2仓库的URL地址（Lab2-学号）

实验过程

请仔细对照实验手册，针对三个问题中的每一项任务，在下面各节中记录你的实验过程、阐述你的设计思路和问题求解思路，可辅之以示意图或关键源代码加以说明（但千万不要把你的源代码全部粘贴过来！）。

1. Poetic Walks

该部分首先分别利用边表和邻接表实现图这一数据结构，随后在其基础上实现以String为顶点的图，并在其基础上进行简单的先广搜索。

1. 1. Get the code and prepare Git repository

本次实验直接访问GitHub教室并在其上下载源码得到压缩包

在本地创建git仓库，在本地文件目录下打开git bash，输入命令git init即可完成本地仓库的初始化

如何从GitHub获取该任务的代码、在本地创建git仓库、使用git管理本地开发。

1. 1. Problem 1: Test Graph <String>

测试用例部分我们首先从最简单的add方法开始测试

（1）方法add

方法add参数为L，功能为向有向图中添加顶点

对于add的测试，我们首先调用add方法向有向图中加入一个图中不存在的点“Grizz”，返回值应为true；随后，由于顶点“Grizz”已存在，再向图中加入顶点“Grizz”就会返回false。类似地，我们也可以加入顶点“Panda”和“Ice_Bear”

（2）方法set

方法set参数为L,L,int，功能为向有向图中添加带权边

对于set的测试，我们首先调用已经测试完成的方法add，向图中加入顶点“Grizz”和“Panda”。然后调用方法set，在顶点“Grizz”和“Panda”中间添加一条权重为1的边；再次调用set方法，将其权重改为10，则其返回值应为1

调用set添加边从“Grizz”到“Ice_Bear”权重为1的边，由于图中初始并不存在顶点“Ice_Bear”，故方法set调用后，图中会添加顶点“Ice_Bear”，可调用方法add证实；我们还可以利用set删除从“Grizz”到“Ice_Bear”的边

（3）方法remove

该方法的测试分为两个部分：

第一部分主要测试最基础的删除操作，即在没有边的情况下进行删除，测试其删除图中顶点的反应以及删除顶点不存在时的返回值。

第二部分则测试在顶点与边关联时的行为，分别测试有入边和出边时程序的行为。

（4）其余方法

其余方法主要是observer类方法，实现较为简单，具体详见源码，在此不作赘述

1. 1. Problem 2: Implement Graph <String>

该部分分别利用边表和邻接表两种方式实现图。

1. 1. 1. Implement ConcreteEdgesGraph

类ConcreteEdgesGraph以String为顶点，以类Edge为边，实现一个可变权重的有向图。

首先需要实现类Edge，类Edge实现有向图的一条有向边，其UML图如下所示

按照MIT实验要求，该类为不可变类，首先，对于成员变量source、target、weight都使用final关键字进行修饰；同时，本类中不提供mutator。类Edge的observer中不存在表示泄露的问题，因为String本身为不可变类，并且用final关键字修饰，故其值和指向都是不可变的；int类型在返回时是值传递，不存在表示泄露的问题。

Observer中方法ifincident的目的是检查输入的顶点是否与本条边相关联，参数mod是为了区分起点和终点。

类ConcreteEdgesGraph的UML图如下所示

函数	实现思路
add(String vertex)	首先判断待加入顶点是否已经在顶点集中，若在则返回false，否则在将其加入顶点集后返回true
set(String source, String target, int weight)	首先检查三个输入的合法性。当没有该边并且weight非零，直接添加该边，返回值为0；如果已经有该边，则记录weight并删除原边、添加修改后的边。如果weight=0，直接删除该边
remove(String vertex)	首先判断输入的vertex是否在点集中，若不在则直接返回；若在点集中，则删除该顶点，并在遍历边集查找与该顶点关联的边并删除
vertices()	使用防御性复制返回点集
targets(String source)	遍历边集，查找与source相关联的边并返回
sources(String target)	同上

测试结果如下所示：

测试用例覆盖度如下所示：

1. 1. 1. Implement ConcreteVerticesGraph

类ConcreteVerticesGraph以邻接表的形式存储可变权有向图，vertices为其各个顶点。

首先要实现类Vertex，Vertex为有向图的顶点及其出边邻接表，UML图如下所示：

由于类Vertex的成员变量和方法较为简单，自此不再赘述，源码中有详细注释

类ConcreteVerticesGraph与类ConcreteEdgesGraph的UML图和方法原型基本相同，在此仅介绍方法中的不同之处

函数	实现思路
add(String vertex)	首先判断待加入的顶点是否已经在顶点集中，若在则返回false，否则在为其创建邻接表并将其加入顶点集后返回true
set(String source, String target, int weight)	首先检查三个输入的合法性。然后判断source是否已经在顶点集中，若不在顶点集中，则将source及其邻接表添加进入顶点集；若在顶点集中，则判断target是否在顶点集中，若不在，则添加在顶点集中添加target并在source的邻接表中添加边；若在顶点集中，则根据weight的值进行判断，weight非零则更新source邻接表，weight为零则在source邻接表中删除target
remove(String vertex)	首先判断输入的vertex是否在点集中，若不在则直接返回；若在点集中，则删除该顶点，并遍历顶点集，在各顶点的邻接表中删除所有与vertex相关的边
vertices()	使用防御性复制返回顶点集
targets(String source)	直接使用防御性复制返回source的邻接表
sources(String target)	遍历所有顶点的邻接表，将所有指向target的边都加入到新创建的顶点target的入边邻接表中

测试结果如下所示：

测试用例覆盖度如下所示：

1. 1. Problem 3: Implement generic Graph<L>

在3.1.3节中，我们已经用String类型实现了Graph，现在为了扩大Graph的使用范围，我们将使用泛型实现Graph

1. 1. 1. Make the implementations generic

在已实现Graph<String>的基础上将其改为泛型L的难度并不大，只需要将其中很多的String改为L即可，二者具体差别详见GitHub中第四次提交和第三次提交的差别。

注意到，由于泛型L的方法未知，故在此处去掉顶点标签不能为空的限制。

1. 1. 1. Implement Graph.empty()

该部分返回一个通过类ConcreteVerticesGraph<String>实现的空图

1. 1. Problem 4: Poetic walks
    1. Test GraphPoet

测试语料库为space.txt，即MIT实验指导网页语料库的完整版。

输入：Space, the frontier.

输出：Space the final frontier

1. 1. 1. Implement GraphPoet

类GraphPoet的UML图如下所示

首先，类读取GraphPoet文件中的语料库进行初始化。初始化部分主要由分为读取文件和构建图两部分。读取文件由函数readfile实现，函数readfile将会返回语料库文件中各单词组成的顺序列表，其中各单词均被转化为小写并去除了标点符号。构建图部分则由构造函数GraphPoet实现，该函数首先调用函数readfile得到顺序列表L，通过遍历L，将图初始化。由于set方法的功能较为多样，故本处可以用一种很优雅的方式实现：

即在遍历顺序列表L的同时，直接调用set对图进行初始化。

在完成初始化后，我们将问题进行形式化：对于输入I中的连续单词A-B，我们需要在图中寻找路径A-C-B，若存在该路径，则将C加入到AB中间；若不存在，则继续执行。若存在多个Ci ，则选取其中使得该路径权重最大的Ci 作为最终结果。

在具体实现过程中，我们使用TreeMap对权重进行排序（由于规约中未定义权重相同时函数的行为，故舍弃部分相同的权重的可接受的），将最大的权重对应的字符串作为填充。同时，也要注意到，由于在初始化时所得字符串图中的顶点均为小写字符，故在比较过程中也应将输入转化为小写字符进行比较。

1. 1. 1. Graph poetry slam

该部分的语料库为《V字仇杀队》中V的自我介绍。

输入：You call V

输出：You may call me V

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

Problem2和Problem3的测试代码覆盖度已在前面的报告中给出，在此不再赘述，本处将给出Problem4的测试代码覆盖度

测试结果如下所示：

测试用例覆盖度如下所示：

1. 1. 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 *

git push lab2 master

项目名称：Lab2-1190202428

--src

--P1

--graph

--ConcrerteEdgesGraph.java

--ConcrerteVerticesGraph.java

--Graph.java

--poet

--GraphPoet.java

--Main.java

--mugar-omni-theater.txt

--test

--P1

--graph

--ConcreteEdgesGraphTest.java

--ConcreteVerticesGraphTest.java

--GraphInstanceTest.java

--GraphStaticTest.java

--poet

--GraphPoetTest.java

--space.txt

1. Re-implement the Social Network in Lab1

本处社交网络可以通过有向图建模，每个Person为图中的一个节点。若两个Person有关联，则图中对应的两个顶点之间有边。

1. 1. FriendshipGraph类

本次重新实现类FriendshipGraph只需要将上文中实现的Graph中的定点类型更改为类Person即可，其余方法均可复用。

其中计算距离部分采用bfs即可实现

1. 1. Person类

根据上文中实现的Graph类，Person类只需要存储每个人的名字name即可

1. 1. 客户端main()

首先让用户输入节点个数，依次输入节点名字；随后输入边的个数，并依次输入各边；最后输入两个人的名字求得两个人之间的距离。

1. 1. 测试用例

类FriendshipGraph的测试采用黑箱测试，直接输入Lab1中的测试用例即可

测试结果如下所示：

测试用例覆盖度如下所示：

注：由于测试用例未对main函数进行测试，故覆盖率可能较低，去除main函数后覆盖率如下所示：

1. 1. 提交至Git仓库

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

上文中已经写过，不在此赘述

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

项目名称：Lab2-1190202428

--src

--P2

--FriendshipGraph.java

--Person.java

--test

--P2

--FreindshipGraphTest.java

实验进度记录

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

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

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

日期	时间段	计划任务	实际完成情况
2021-6-4	17:00-22:00	完成实验1	Problem4未进行测试
2021-6-5	10:00-12:00	完成实验1 的剩余部分并撰写报告	按时完成
2021-6-5	14:00-17:00	完成实验2	按时完成

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

遇到的难点	解决途径
撰写报告	慢慢写
不能访问GitHub	你猜呢

实验过程中收获的经验、教训、感想
1. 实验过程中收获的经验和教训

本次实验比较简单，收获的只是写完代码的快感以及复习上课学过的知识，不过看着自己写完的代码和规约还是挺有成就感的。

教训就是课下要及时复习，否则上课听的东西忘得很快，AF、RI什么的基本上都是现学现用的。

1. 针对以下方面的感受
面向ADT的编程和直接面向应用场景编程，你体会到二者有何差异？

面向ADT编程往往考虑得更多的是ADT会做什么，ADT怎么做，具体怎么实现这些问题；而像C语言这种面向过程的编程更需要将整个任务拆分成几大块，然后分块实现

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

没有特别大的差异，就是使用泛型时候需要注意有一些特定类的方法就不能使用了，否则就会报错

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

我觉得这个东西优劣参半吧，有些bug真的需要等你写代码之后才能想得到；不过写代码之前先把测试用例写完也可以发现很多写代码时候的疏忽和遗漏。我测试用例是先写了一部分，然后写代码时候突然灵光一闪感觉某个实现方式可能会出bug，然后就相应地构建出测试用例了

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

好处就是不用重复造*了；这种方式的好坏我觉得还是取决于代码质量，要不然ADT很容易隐藏bug

P3要求你从0开始设计ADT并使用它们完成一个具体应用，你是否已适应从具体应用场景到ADT的“抽象映射”？相比起P1给出了ADT非常明确的rep和方法、ADT之间的逻辑关系，P3要求你自主设计这些内容，你的感受如何？

基本适应了，感觉自己设计ADT很爽，可以很清楚底层是怎么实现的，如果出bug了也很快就能想到是那块出的问题

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

就是为了代码的健壮性呗；这个还是要看情况，看代码是要用在什么地方，有些时候我觉得快速实现出来比那些有的没的的健壮性要重要得多

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

都可以接受，就是我觉得没啥必要写这个实验报告，直接提交代码不好吗

《软件构造》课程进展到目前，你对该课程有何体会和建议？

用Java写代码还是挺爽的，比C语言舒服多了，不过我觉得课上讲的部分有的没的的东西貌似没啥大用

码农公寓

相关文章