软件构造lab2实验心得

软件构造lab实验心得

实验目标概述
本次实验训练抽象数据类型（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实验环境配置
EclEmma已经集成到eclipse中，无需另外配置环境。

3.1Poetic Walks
用两种不同的方法去实现Graph接口，基于点和边分别构造图结构，并应用于作诗当中。
3.1.1Get the code and prepare Git repository
1.获取代码：从所给的github网址clone或者直接下载代码
2.本地创建git仓库：新建一个文件夹作为本地仓库，使用git-bash
切换到该文件夹，输入git init指令，即可创建本地仓库。当前目录会多出一个.git文件，即创建成功
3.使用git管理：（只介绍一些常用的命令）
git add ‘filename’ 添加文件到暂存区
git commit -m “message” 提交暂存区文件到本地仓库
git log 查看日志，包括提交信息等
git status 查看当前工作区状态
git remote add origin https:…… 创建远程链接
git push -u origin master 将本地仓库提交到远程仓库
git pull 拉取整合远程仓库到本地仓库(相当于git fetch加git merge) 等等
3.1.2Problem 1: Test Graph
为Graph中的实例方法编写测试，即测试其中的add，remove，vertices，set，sources，targets方法即可。具体的测试策略请移步代码处。
由于GraphInstanceTest是一个抽象类，无法直接测试。

3.1.3Problem 2: Implement Graph
以下各部分，请按照MIT页面上相应部分的要求，逐项列出你的设计和实现思路/过程/结果。
3.1.3.1Implement ConcreteEdgesGraph
1.checkRep(): 检查顶点和边是否为空，边邻接的顶点是否都加入vertices中，检验是否有相同边，均使用assert断言测试即可
2.add(L vertex)：加入顶点，先判断是否已包含，若已存在该顶点则返回false，否则加入到vertices中并返回true。
3.set(L source，L target，int weight)：首先判断weight是否非负，若为负数抛出异常；然后添加两个顶点，判断是否两顶点间是否已经存在这条边，若有则删除该边(因为Edge是不可变类型)，再判断weight是否大于0，大于则添加新边，否则直接返回preweight
4.remove(L vertex)：先判断该点是否存在，不存在返回false，存在则从vertices中删除该点，并在edges中查找以该点为src或tag的边并删除即可，返回true
5.vertices()：将vertices包装成不可变类型unmodifiableset再返回
6.sources(L target)：遍历edges，查找target的source并将其加入新建的map，最后用不可变类型unmodifiablemap包装即可
7.targets(L source):和sources类似，查找source的target并加入map，用不可变类型包装返回即可
8.toString()：将图以文字化的形式显示即可，这里我将各个边的toString()连接即可
Edge类：
1.构造器：Edge(L src，L tag，int w):输入source，target和weight即可创建新边
2.checkRep():检查src，tag不为空，weight大于等于0即可
3.getSrc():获取src
4.getTag():获取tag
5.getWeight()：获取weight
6.toString()：形式为src->tag[weight]

测试：
ConcreteEdgesGraphTest():
除继承GraphInstanceTest的测试方法外，添加了对toString()的测试以及对Edge类的测试，主要测试toString()，策略见代码处。
3.1.3.2Implement ConcreteVerticesGraph
1.checkRep()：检查顶点不能为空且不允许重名，使用assert断言即可
2.add(L vertex)：加入顶点，先判断是否已包含，若已存在该顶点则返回false，否则加入到vertices中并返回true。
3.set(L source，L target，int weight)：首先判断weight是否非负，若为负数抛出异常；然后添加两个顶点，判断weight是否等于0，若等于0则返回preweight，不为0则加入边
4.remove(L vertex)：先判断该点是否存在，不存在返回false，存在则从vertices中删除该点，并查找以该点为src或tag的边并删除即可，返回true
5.vertices()：将vertices包装成不可变类型unmodifiableset再返回
6.sources(L target):找到target后调用vertex的getSrc()即可
7.targets(L source):和sources类似，找到source后调用vertex的getTag()即可
8.toString()：将图以文字化的形式显示即可，这里我将各个点的toString()连接即可

Vertex类:
1.构造器：Vertex(L name):输入标签即可创建顶点
2.checkRep():判断名字，sources,targets不为空即可
3.getname():获取name
4.getSrc():将sources包装成不可变的unmodifiableMap再返回即可
5.getTag():将targets包装成不可变的unmodifiableMap再返回即可
6.setSrc(L src, int weight):若weight为0，则移除该边，否则加入边或者修改边，使用Map.put即可
7.setTag():同setSrc()
8.toString():形式为{[src:weight]->[tag:weight]}

测试 ：
ConcreteVertexGraphTest():
除继承GraphInstanceTest的测试方法外，添加了对toString()的测试以及对Vertex类的测试，主要测试toString()，策略见代码处。
3.1.4Problem 3: Implement generic Graph
3.1.4.1Make the implementations generic
泛型化Graph，将所有的String改成L,Graph,Vertex,Edge等加个<>即可。
这样就可以创建任何类型标签的图。

3.1.4.2Implement Graph.empty()
具体返回一个Graph实例，new一个ConcreteEdgesGraph()或者ConcreteVertexGraph()实例都可以。
并编写其他类型标签的测试。
3.1.5Problem 4: Poetic walks
3.1.5.1Test GraphPoet
编写测试用例：测试通过poem()得到的诗句和我们期待的是否相同即可
3.1.5.2Implement GraphPoet
1.checkRep():检验顶点集是否为空，使用assert断言即可
2.构造器：GraphPoet(File corpus)读取文件中的语料，并将其按空格分隔，存成一个图的形式。
3.poem(String input):将输入按空格分隔，并在每两个分隔中都去已经构造好的图里寻找有无两个词的桥边，即存在一个词，既是第一个词的target，又是第二个词的source，选择权重最大的桥词加入，构成output,即作诗完成
3.1.5.3Graph poetry slam
自己给出输入和语料库进行作诗即可。
3.2Re-implement the Social Network in Lab1
利用P1实现的Graph重新构造人际关系图，考察对ADT的灵活使用
3.2.1FriendshipGraph类
1.FriendshipGraph类继承了ConcreteEdgesGraph类
2.addVertex(Person person)：调用父类中的add()方法即可
3.addEdge(Person a, Person b)：调用父类中的set(a, b, 1)即可
4.getdistance(Person a, Person b):
该方法用于计算a和b之间的距离。借助bfs算法的思想。
与a距离为1的朋友成为第一层朋友，以此类推。我定义了一个队列queue和一个Set类型的layer。思路如下：
1).初始化所有Person中的flag均为false(意为没有访问过),distance初始化为0
2).如果a与b名字相同，则返回distance(两人为同一人)
3).把a添加进queue中
4).while(queue不为空时){
将queue中元素拷贝至layer中并将queue清空；
遍历layer中的元素，并把layer中元素的未被访问过的朋友(即targets)添加进queue中(即a的下一层朋友)；
遍历并清空layer中元素(a的该层朋友),看b是否存在于该层中；若存在，则返回distance；
若不存在，则distance++,继续循环
}
5).若queue为空时仍不存在，则返回-1
3.2.2Person类
1.私有字段name存储名字
2.构造器Person(String name): 输入名字即可构造一个Person类
3.getname():获取Person的名字
4.重写equals方法，因为Person是放入set中的，set判断一个对象是否在其中使用的contain方法调用了equals方法

		FriendshipGraph graph = new FriendshipGraph();
		Person rachel = new Person("Rachel");
		Person ross = new Person("Ross");
		Person ben = new Person("Ben");
		Person kramer = new Person("Kramer");
		graph.addVertex(rachel);
		graph.addVertex(ross);
		graph.addVertex(ben);
		graph.addVertex(kramer);
		graph.addEdge(rachel, ross);
		graph.addEdge(ross, rachel);
		graph.addEdge(ross, ben);
		graph.addEdge(ben, ross);
		System.out.println(graph.getDistance(rachel, ross)); 
		//should print 1
		System.out.println(graph.getDistance(rachel, ben)); 
		//should print 2
		System.out.println(graph.getDistance(rachel, rachel)); 
		//should print 0
		System.out.println(graph.getDistance(rachel, kramer)); 
		//should print -1

3.2.4测试用例
1.public void testAddVertex() throws Exception
addVertex的测试，主要测试加入的Person类是否存入了FriendshipGraph类中的vertex字段中。

2.public void testAddEdge() throws Exception
addedge的测试，主要测试加入的类是否存在于graph的targets中。

3.public void testGetDistance() throws Exception
测试求出的距离与实际距离是否相等即可