软件构造实验2 : 实验记录
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. 实验环境配置
在idea中创建项目,然后建立本地仓库
再将本地仓库与GitHub仓库关联
在这里给出你的GitHub Lab2仓库的URL地址(Lab2-学号)。
3. 实验过程
请仔细对照实验手册,针对三个问题中的每一项任务,在下面各节中记录你的实验过程、阐述你的设计思路和问题求解思路,可辅之以示意图或关键源代码加以说明(但千万不要把你的源代码全部粘贴过来!)。
3.1. Poetic Walks
该任务主要是ADT的内容,要自己实现一个有向图的抽象数据类型,在实验中要掌握AF RI 和rep等概念
3.1.1. Get the code and prepare Git repository
直接从老师发的github的链接中获取实验代码,将其导入到本地工程中
之后在项目文件夹建立本地仓库
在idea中创建项目,然后建立本地仓库
再将本地仓库与GitHub仓库关联
3.1.2. Problem 1: Test Graph <String>
3.1.2.1. 测试add
分成三种情况讨论
(空)
(非空,同点)
(非空,不同点)
用contains()和size()保证图的点集正确
3.1.2.2. 测试set函数
/**
* 测试set函数
* 测试策略:
* weight: 0、非0
* source:已存在、不存在
* target:已存在、不存在
* 原来的source与target之间:有边、无边
*/
做一个比较详尽的测试·,尽量覆盖所有可能,主要关注对不存在的点和边的操作
要用contains去看有没有缺少或多出来点,边的多少通过下一个set()的结果反映
3.1.2.3. 测试remove函数
/**
* 测试remove函数
* 该点:存在、不存在
* 与该点邻接的边:存在、不存在
*/
注意不要用source和target函数等还没测的函数,否则出错了可能看不出来是哪里的问题
用已经测试过的set更好
3.1.2.4. 测试vertices
/**
*测试vertices函数
*测试策略:
* 点集:为空 ,一个点,多个点
*/
尤其要注意测试是否有表示泄露,是否是immutable的
3.1.2.5. 测试Sources
注意测试边的方向相反的边是否会引起不该有的增加
3.1.2.6. 测试targets
测试方法同上
测试结果(后补充):
3.1.3. Problem 2: Implement Graph <String>
以下各部分,请按照MIT页面上相应部分的要求,逐项列出你的设计和实现思路/过程/结果。
3.1.3.1. Implement ConcreteEdgesGraph
Edge类的实现
AF:
RI:
Rep exposure:
构造器:
普普通通,符合RI即可
由于Edge类要求是immutable类型的,所以类中所有成员都必须是final关键字标识的
由于graph中的set可能涉及到更改边的权值,所以在edge实现了判断同一条边的函数,这里和equals是不同的 不比较weight
实现sameedge:
实现equals
Edge类中要求保持的不变量为:
Target与source不为null且不相等,然后权值大于0
利用checkrep判断
剩下的几个method 都比较简单,都不加赘述了
ConcretEdgeGraph类的实现
AF:
RI:
Rep exposure
checkRep
关键是要调用上面的egde里的sameEdge来检查没有相同的重复边
由于是set 不用关心有没有重复的点
set实现:
完成删边操作 对不存在的边也返回0
加边和调整放在一起实现
这里注意到要顺便把可能的重复边也删了
remove实现:
先去边再去点,注意不能foreach 有改动
用i来遍历 i--
vertices()实现
注意防御性拷贝
sources()实现
targets()实现同上
tostring 实现 注意美观
ConcretEdgeGraphTest
对于ConcreteGraphTest只需要补充对于graph的toString和edge的toString,只需要用一个图的实例然后将该图实例预期得到的输出和toString进行对比。
测试结果:
3.1.3.2. Implement ConcreteVerticesGraph
首先是vertex类的实现
点类Vertex由一个标识label,和两个分别分别是表示入边和出边的边表map,之后实现graph中对边的操作都将体现到这两个map中
AF:
// Abstraction function:
// Save point's label, map edges in with theirs sources and weights
// , map edges out with theirs targets and weights
// a edge can be find twice in the map of both source and target
RI:
// Representation invariant:
// all weight >0
// all vertex , label , source and target in edges should not be null
// in any map ,there should no be edges with the same source/target
// ,even if the weight is different
Rep exposure:
// Safety from rep exposure:
// getter methods defensively copy out the data
// setter methods safely change a vertex
// all rep are private ,label ,if is string ,is immutable
checkRep:
这里为了识别是否有重复的边,使用了一个新的set,把每条边的label 加入进来,如果没有重复则会返回true
这里使用了entrySet方法来遍历Map
// TODO checkRep
private void checkRep()
{
Set<String> inset =new HashSet<>();
for (Map.Entry<String,Integer>e:in.entrySet())
{
assert e.getKey()!=null;
assertTrue(inset.add(e.getKey()));
assert e.getValue()>0;
}
Set<String> outset =new HashSet<>();
for (Map.Entry<String,Integer>e:out.entrySet())
{
assert e.getKey()!=null;
assertTrue(outset.add(e.getKey()));
assert e.getValue()>0;
}
}
之后要重写equals方法
只要label 相同就算是equal的
重写注意判断类型(从object开始)
/**
* Judge whether two points are equal
* @param other another object(should be Vertex otherwise meaningless)
* @return if other is a Vertex and the label of the two points is
* equal is considered to be the same point to return true, otherwise returns false
*/
@Override
public boolean equals(Object other)
{
if (other == null || !(other instanceof Vertex))//Object not Vertex ,quick false
return false;
final Vertex vertex = (Vertex)other; //back to Vertex
if (this.getLabel().equals(vertex.getLabel())) //label is what it really matters
return true;
return false;
}
重写tostring
@Override
public String toString()
{
String ans = "[Vertex: "+label+" with Egdes:\n";
for (Map.Entry<String,Integer> e:out.entrySet())
{
ans+="[edge: "+label+"->"+e.getKey()+" weighted "+e.getValue()+" ]\n";
}
for (Map.Entry<String,Integer> e:in.entrySet())
{
ans+="[edge: "+e.getKey()+"->"+label+" weighted "+e.getValue()+" ]\n";
}
ans+="]\n";
return ans;
}
ConcreteVerticeGraph类的实现
首先成员域已经给定
要保持list没有重复点,然后没有点到自身的边,保证list中没有指向null的点
// @throws error when this violate RI
private void checkRep()
{
for(int i = 0;i<vertices.size();i++)
{
assert vertices.get(i)!=null;//not null
for (int j = i+1;j<vertices.size();j++)
{
assert !vertices.get(i).equals(vertices.get(j));//no repeat member
}
}
}
其余的方法均按照规约进行即可,由关于边的增删改动的需要通过点获得相应的map,在map中进行更改即可
set 实现:
首先判定非法输入,quick false
再看两点是否存在 不存在要补上
找到相关点 直接调用setTarget或setSource 函数
@Override public int set(String source, String target, int weight)
{
if(source.equals(target)||weight<0)
assert false;
int ans =0;
Vertex sampleSource= new Vertex(source);
Vertex sampleTarget= new Vertex(target);
if (!vertices.contains(sampleSource))
vertices.add(sampleSource);
if (!vertices.contains(sampleTarget))
vertices.add(sampleTarget);
checkRep();
for (Vertex si : vertices)
{
if (si.getLabel().equals(source))
{
ans=si.setTarget(target, weight);
}
if (si.getLabel().equals(target))
{
ans=si.setSource(source, weight);
}
}
checkRep();
return ans;
}
下面展示一下setTarget,以明确set的正确性和防御性
/**
* To reset the out edge
* @param target target of the edge
* @param weight weight of the edge
*/
public Integer setTarget(String target,int weight)
{
int ans =0;
if (out.containsKey(target))
{
ans=out.get(target);
removeSource(target);
}
if (weight>0)
out.put(target,weight);
checkRep();
return ans;
}
Test
需要补充对toString 和vertex的测试
测试结果
3.1.4. Problem 3: Implement generic Graph<L>
3.1.4.1. Make the implementations generic
只需要将原代码中的String全部替换成泛型L即可,然后在类,函数前进行泛型的声明。
静态检查永远的神!!(全靠它找哪里要改类型呢)
3.1.4.2. Implement Graph.empty()
3.1.5. Problem 4: Poetic walks
3.1.5.1. Test GraphPoet
根据Mit 实验指导网页上的示例语料库和工程中已有的示例语料库和输入查看输出字符串与预期字符串是否相等。
这里使用了一个文档种给出的例子并且自己编写了一个例子
语料库:
1 1
2 1
3 1
4 1 1 2 3 4 2 2 3 3 4 1 14
包含了:换行、重复、自我重复、权重不同、权重相同、间隔多个、不存在的字、有大与2的通路
public void graphPoetTest() throws IOException {
final GraphPoet nimoy = new GraphPoet(new File("src/P1/poet/mugar-omni-theater.txt"));
final String input = "I am going to test the omni system.";
assertEquals("I am going to test of the mugar omni system.",nimoy.poem(input));
final GraphPoet test = new GraphPoet(new File("src/P1/poet/test.txt"));
final String inputTest = "1 2 3 4 5 4 3 2 1 1 2 2 3";
assertEquals("1 1 2 3 3 3 4 5 4 1 3 1 2 1 1 1 1 1 2 1 2 3 3",test.poem(inputTest));
}
测试结果(后补充):
3.1.5.2. Implement GraphPoet
实现GraphPoet类
rep:
public class GraphPoet {
private final Graph<String> graph = Graph.empty();
AF:
// Abstraction function:
// According to the input file build a corpus,
// and according to the input string,
// output string poetry after modification
// To map a String type of graph to a corpus
RI:
// Representation invariant:
// refer to Graph
Rep exposure:
// Safety from rep exposure:
// use final and private keywords
3.1.5.3. 实现构造方法
使用Bufferreader 来读取文件(实现readlines)
对null文件直接报错,对空文件直接返回
逐行合并入Stringbulider line 里成一行
split成String [ ] sourceWords
然后把边加入到graph中
先加第一个词
遍历时注意是不是第一条边,不是要增加权重,用set方法
注意这里只能用graph接口中的方法
/**
* Create a new poet with the graph from corpus (as described above).
*
* @param corpus text file from which to derive the poet's affinity graph
* @throws IOException if the corpus file cannot be found or read
*/
public GraphPoet(File corpus) throws IOException {
//reading file
BufferedReader bufreader = new BufferedReader(new FileReader(corpus));
String temp = "";
StringBuilder line = new StringBuilder();
while(true)
{
temp = bufreader.readLine();
if (temp!=null)
line.append(temp+" ");
else
{
if (line.length()==0)
{
bufreader.close();
return;
}//empty corpus
line.deleteCharAt(line.length()-1);
break;
}
}
bufreader.close();
String [] sourceWords =(new String(line).toLowerCase()).split(" ");
//build a graph
graph.add(sourceWords[0]);
for (int i = 1;i<sourceWords.length;i++)
{
graph.add(sourceWords[i]);
if (!graph.targets(sourceWords[i-1]).containsKey(sourceWords[i]))
{
graph.set(sourceWords[i-1],sourceWords[i],1);
}
else
{
graph.set(sourceWords[i-1],sourceWords[i],
graph.targets(sourceWords[i-1]).get(sourceWords[i])+1);
}
}
}
3.1.5.4. 实现poem方法
首先考虑语料库不足、输入句为空的情况,直接return防止出错
因为有大小写转换问题,每次加入一个词(+可能的bridge),仅在判断的时候生成一个小写版本的原词,从语料库中匹配bridge
/**
* Given an input string, GraphPoet generates a poem by attempting to
* insert a bridge word between every adjacent pair of words in the input.
* The bridge word between input words "w1" and "w2" will be some "b" such that
* w1 -> b -> w2 is a two-edge-long path with maximum-weight weight among all
* the two-edge-long paths from w1 to w2 in the affinity graph.
* If there are no such paths, no bridge word is inserted.
* In the output poem, input words retain their original case, while bridge
* words are lower case. The whitespace between every word in the poem is a
* single space.
* @param input string from which to create the poem(can be empty)
* @return poem (as described above)
*/
public String poem(String input)
{
if (input==""||graph.vertices().size()<=1)//quick done empty work
return input;
//after here corpus and input should not be empty
String [] rawWords = input.split(" ");
ArrayList<String> temp = new ArrayList<>();
temp.add(rawWords[0]);
Set<String> sourceWordSet = graph.vertices();
for (int i = 1;i<rawWords.length;i++)
{
String LowerBeforeWord = rawWords[i-1].toLowerCase();
String LowerAfterWord = rawWords[i].toLowerCase();
if ((sourceWordSet.contains(LowerBeforeWord))&&(sourceWordSet.contains(LowerAfterWord)))
{
String bridge ="";
int biggestWeight = -1;
Map<String,Integer> ins = graph.targets(LowerBeforeWord);
Map<String,Integer> outs = graph.sources(LowerAfterWord);
for(Map.Entry<String,Integer> brigdei:ins.entrySet())
{
if (outs.containsKey(brigdei.getKey()))
{
int newBridgeWeight = ins.get(brigdei.getKey())+outs.get(brigdei.getKey());
if (newBridgeWeight>biggestWeight)
{
bridge = brigdei.getKey();
biggestWeight = newBridgeWeight;
}
}
}
if (bridge != "")
{
temp.add(bridge.toLowerCase());
}
}
temp.add(rawWords[i]);
}
StringBuilder ans = new StringBuilder();
ans.append(temp.get(0));
for (int i = 1;i<temp.size();i++)
{
ans.append(" " + temp.get(i));
}
return new String(ans);
}
测试结果:
3.1.5.5. Graph poetry slam
new Main
使用原语料库和一个比较复杂的新语料库
还有一个Shall I compare thee to a summer’s day?
Thou art more lovely and more temperate:
Rough winds do shake the darling buds of May,
And summer’s lease hath all too short a date:
莎士比亚的十四行诗用他的另外两首诗歌来替换
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,commit,push等命令即可提交到仓库中
在这里给出你的项目的目录结构树状示意图。
3.2. Re-implement the Social Network in Lab1
该任务要求重新实现Lab1的P3实验,要求尽量复用Lab2 P1自己实现的graph类及其方法。
3.2.1. FriendshipGraph类。
3.2.1.1. 设计思路
复用graph中的方法,建立一个Graph<Person>,然后addVertex复用graph的add方法向图中加顶点,addEdge复用graph的set方法向图中加边。Getdistance依旧以BFS算法为基础进行计算最短距离。
3.2.1.2. 具体实现
rep:
public class FriendshipGraph
{
private Graph<Person> graph = Graph.empty();
AF:
// Abstraction function:
// To map a directed graph to figure of a social network
RI:
// Representation invariant:
// The directed graph is not empty, no recurring point in the figure
Rep exposure:
// Safety from rep exposure:
// The graph is set to private variables and
// does not provide said leaked method may be produced
Addvertex和addEdge两个方法比较简单这里不再进行赘述,再实现这两个方法的时候主要要注意到各种特殊情况,比如两个人重名,或者要加入的人已经在图中等。
实现gitDistance
使用近似于DFS的算法,用队列实现
对初始结点进行广度优先搜索,
每次设立一个flag(也是人)来记录每一层的第一个元素,
若这个元素出队则说明进入下一次搜索
更新标记位和层数,
访问到目标节点时return 层数=distance(必然最短)
/**
* The shortest distance between the calculated from A to B
* @param A The starting point
* @param B End point
* @return If A or B is null or didn't in the graph then return -2,
* returns 0 if A and B is the same point,
* if there is no road between AB then return 1,
* the rest of the normal situations returns the shortest distance
*/
public int getDistance(Person A,Person B)
{
if (A==null||B==null)
{
return -2;
}
if (A.equals(B))
{
return 0;
}
Map<Person,Boolean> visited = new HashMap<>();
Set<Person> personSet = graph.vertices();
if (!personSet.contains(A)||!personSet.contains(B))
{
System.out.println("The person in vexlist!");
return -2;
}
for (Person p : personSet)
{
visited.put(p,false);
}
// now everyone is unvisited
int distanceCounter = 0;
Queue<Person> searchQueue = new LinkedList<>();
Person firstOneInQueue = A;
boolean startNextTurn = false;
visited.put(A,true);
searchQueue.offer(A);
while (!searchQueue.isEmpty())
{
Person tempone = searchQueue.poll();
if (tempone.equals(firstOneInQueue))
{
distanceCounter++;
startNextTurn = true;
}
for (Map.Entry<Person,Integer>entry:graph.targets(tempone).entrySet())
{
if (!visited.get(entry.getKey()))//avoid repeat ones
{
if (startNextTurn)
{
startNextTurn = false;
firstOneInQueue = entry.getKey();
}
Person person1 = entry.getKey();
if (person1.equals(B))
return distanceCounter;
searchQueue.offer(person1);
visited.put(person1,true);
}
}
checkRep()
}
return -1;
}
3.2.2. Person类
3.2.2.1. 设计思路
Person类只有一个成员String类型的name进行唯一标识,Persion类为immutable类型,需要重写equals和hashCode函数。
3.2.2.2. 实现
/**
* The shortest distance between the calculated from A to B
* @param A The starting point
* @param B End point
* @return If A or B is null or didn't in the graph then return -2,
* returns 0 if A and B is the same point,
* if there is no road between AB then return 1,
* the rest of the normal situations returns the shortest distance
*/
public int getDistance(Person A,Person B)
{
if (A==null||B==null)
{
return -2;
}
if (A.equals(B))
{
return 0;
}
Map<Person,Boolean> visited = new HashMap<>();
Set<Person> personSet = graph.vertices();
if (!personSet.contains(A)||!personSet.contains(B))
{
System.out.println("The person in vexlist!");
return -2;
}
for (Person p : personSet)
{
visited.put(p,false);
}
// now everyone is unvisited
int distanceCounter = 0;
Queue<Person> searchQueue = new LinkedList<>();
Person firstOneInQueue = A;
boolean startNextTurn = false;
visited.put(A,true);
searchQueue.offer(A);
while (!searchQueue.isEmpty())
{
Person tempone = searchQueue.poll();
if (tempone.equals(firstOneInQueue))
{
distanceCounter++;
startNextTurn = true;
}
for (Map.Entry<Person,Integer>entry:graph.targets(tempone).entrySet())
{
if (!visited.get(entry.getKey()))//avoid repeat ones
{
if (startNextTurn)
{
startNextTurn = false;
firstOneInQueue = entry.getKey();
}
Person person1 = entry.getKey();
if (person1.equals(B))
return distanceCounter;
searchQueue.offer(person1);
visited.put(person1,true);
}
}
checkRep()
}
return -1;
}
3.2.3. 客户端main()
抄写上次的
public static void main(String[] args)
{
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));
System.out.println(graph.getDistance(rachel,ben));
System.out.println(graph.getDistance(rachel,rachel));
System.out.println(graph.getDistance(rachel,kramer));
}
3.2.4. 测试用例
3.2.4.1. 根据各种特殊情况对方法进行测试
测试addVertex方法
public void addVertexTest()
{
FriendshipGraph graph = new FriendshipGraph();
Person p1 = new Person("A");
Person p2 = new Person("B");
Person p3 = new Person("A");
assertEquals(true,graph.addVertex(p1));
assertEquals(true,graph.addVertex(p2));
assertEquals(false,graph.addVertex(p1));
}
测试addEdge方法
public void addEdgeTest()
{
FriendshipGraph graph = new FriendshipGraph();
Person p1 = new Person("A");
Person p2 = new Person("B");
Person p3 = new Person("C");
Person p4 = new Person("D");
graph.addVertex(p1);
graph.addVertex(p2);
graph.addVertex(p3);
assertEquals(true,graph.addEdge(p1,p2));
assertEquals(false,graph.addEdge(p1,p1));
assertEquals(false,graph.addEdge(p1,p4));
assertEquals(false,graph.addEdge(p1,p2));
assertEquals(true,graph.addEdge(p1,p3));
}
3.2.4.2. 利用实际中较为复杂的图进行测试
public void getDistanceTest()
{
FriendshipGraph graph = new FriendshipGraph();
Person v0 = new Person("v0");
Person v1 = new Person("v1");
Person v2 = new Person("v2");
Person v3 = new Person("v3");
Person v4 = new Person("v4");
Person v5 = new Person("v5");
Person v6 = new Person("v6");
Person v7 = new Person("v7");
Person v8 = new Person("v8");
Person v9 = new Person("v9");
graph.addVertex(v0);
graph.addVertex(v1);
graph.addVertex(v2);
graph.addVertex(v3);
graph.addVertex(v4);
graph.addVertex(v5);
graph.addVertex(v6);
graph.addVertex(v7);
graph.addVertex(v8);
graph.addEdge(v0,v1);
graph.addEdge(v0,v2);
graph.addEdge(v0,v3);
graph.addEdge(v1,v4);
graph.addEdge(v1,v2);
graph.addEdge(v2,v5);
graph.addEdge(v3,v5);
graph.addEdge(v4,v6);
graph.addEdge(v5,v7);
graph.addEdge(v7,v8);
assertEquals(2,graph.getDistance(v0,v4));
assertEquals(3,graph.getDistance(v0,v6));
assertEquals(1,graph.getDistance(v0,v1));
assertEquals(1,graph.getDistance(v0,v2));
assertEquals(1,graph.getDistance(v0,v3));
assertEquals(2,graph.getDistance(v0,v5));
assertEquals(3,graph.getDistance(v0,v7));
assertEquals(4,graph.getDistance(v0,v8));
assertEquals(-1,graph.getDistance(v1,v0));
assertEquals(1,graph.getDistance(v1,v2));
assertEquals(-1,graph.getDistance(v1,v3));
assertEquals(1,graph.getDistance(v1,v4));
assertEquals(2,graph.getDistance(v1,v5));
assertEquals(2,graph.getDistance(v1,v6));
assertEquals(3,graph.getDistance(v1,v7));
assertEquals(4,graph.getDistance(v1,v8));
assertEquals(-1,graph.getDistance(v2,v0));
assertEquals(-1,graph.getDistance(v2,v1));
assertEquals(0,graph.getDistance(v2,v2));
assertEquals(-1,graph.getDistance(v2,v3));
assertEquals(-1,graph.getDistance(v2,v4));
assertEquals(1,graph.getDistance(v2,v5));
assertEquals(-1,graph.getDistance(v2,v6));
assertEquals(2,graph.getDistance(v2,v7));
assertEquals(3,graph.getDistance(v2,v8));
assertEquals(-1,graph.getDistance(v3,v0));
assertEquals(-1,graph.getDistance(v3,v1));
assertEquals(-1,graph.getDistance(v3,v2));
assertEquals(0,graph.getDistance(v3,v3));
assertEquals(-1,graph.getDistance(v3,v4));
assertEquals(1,graph.getDistance(v3,v5));
assertEquals(-1,graph.getDistance(v3,v6));
assertEquals(2,graph.getDistance(v3,v7));
assertEquals(3,graph.getDistance(v3,v8));
assertEquals(-1,graph.getDistance(v4,v0));
assertEquals(-1,graph.getDistance(v4,v1));
assertEquals(-1,graph.getDistance(v4,v2));
assertEquals(-1,graph.getDistance(v4,v3));
assertEquals(0,graph.getDistance(v4,v4));
assertEquals(-1,graph.getDistance(v4,v5));
assertEquals(1,graph.getDistance(v4,v6));
assertEquals(-1,graph.getDistance(v4,v7));
assertEquals(-1,graph.getDistance(v4,v8));
assertEquals(-1,graph.getDistance(v5,v0));
assertEquals(-1,graph.getDistance(v5,v1));
assertEquals(-1,graph.getDistance(v5,v2));
assertEquals(-1,graph.getDistance(v5,v3));
assertEquals(-1,graph.getDistance(v5,v4));
assertEquals(0,graph.getDistance(v5,v5));
assertEquals(-1,graph.getDistance(v5,v6));
assertEquals(1,graph.getDistance(v5,v7));
assertEquals(2,graph.getDistance(v5,v8));
assertEquals(-1,graph.getDistance(v6,v0));
assertEquals(-1,graph.getDistance(v6,v1));
assertEquals(-1,graph.getDistance(v6,v2));
assertEquals(-1,graph.getDistance(v6,v3));
assertEquals(-1,graph.getDistance(v6,v4));
assertEquals(-1,graph.getDistance(v6,v5));
assertEquals(0,graph.getDistance(v6,v6));
assertEquals(-1,graph.getDistance(v6,v7));
assertEquals(-1,graph.getDistance(v6,v8));
assertEquals(-1,graph.getDistance(v7,v0));
assertEquals(-1,graph.getDistance(v7,v1));
assertEquals(-1,graph.getDistance(v7,v2));
assertEquals(-1,graph.getDistance(v7,v3));
assertEquals(-1,graph.getDistance(v7,v4));
assertEquals(-1,graph.getDistance(v7,v5));
assertEquals(-1,graph.getDistance(v7,v6));
assertEquals(0,graph.getDistance(v7,v7));
assertEquals(1,graph.getDistance(v7,v8));
assertEquals(-1,graph.getDistance(v8,v0));
assertEquals(-1,graph.getDistance(v8,v1));
assertEquals(-1,graph.getDistance(v8,v2));
assertEquals(-1,graph.getDistance(v8,v3));
assertEquals(-1,graph.getDistance(v8,v4));
assertEquals(-1,graph.getDistance(v8,v5));
assertEquals(-1,graph.getDistance(v8,v6));
assertEquals(-1,graph.getDistance(v8,v7));
assertEquals(0,graph.getDistance(v8,v8));
assertEquals(-2,graph.getDistance(v9,v0));
FriendshipGraph graph1 = new FriendshipGraph();
Person rachel = new Person("Rachel");
Person ross = new Person("Ross");
Person ben = new Person("Ben");
Person kramer = new Person("Kramer");
graph1.addVertex(rachel);
graph1.addVertex(ross);
graph1.addVertex(ben);
graph1.addVertex(kramer);
graph1.addEdge(rachel, ross);
graph1.addEdge(ross, rachel);
graph1.addEdge(ross, ben);
graph1.addEdge(ben, ross);
assertTrue(graph1.getDistance(rachel,ross)==1);
assertTrue(graph1.getDistance(rachel, ben)==2);
assertTrue(graph1.getDistance(rachel, rachel)==0);
assertTrue(graph1.getDistance(rachel, kramer)==-1);
}
5. 实验过程中遇到的困难与解决途径
遇到的难点 |
解决途径 |
MIT实验的英文网站太难读了,且经常缺少很多细节,需要再到代码里慢慢看 |
读 |
Junit测试覆盖率不高 |
重写测试方法,增加复杂度,按照输入分类,尽量覆盖到每一个分支 |
P2实现用户输入姓名关系建立有向图 |
初始化一个map,key值为名字,value为对应的Person类即可实现 |
一开始做实验的时候不懂AF、RI、rep等概念 |
课上听老师讲,上网查博客,看mit课程网页上的reading资料进行学习终于理解其中的含义 |
设计graph的时候对泛型不理解 |
上网查博客,查菜鸟教程学习泛型的相关用法 |
做P3的时候开始时候的设计有缺陷,出现了严重的表示暴露,不符合ADT的特征 |
经过习题课老师的讲解加上自己的思考,将之前设计中冗余的地方去掉,将可能表示泄露的功能用其他方式实现,将新的设计力求符合条件 |
6. 实验过程中收获的经验、教训、感想
6.1. 实验过程中收获的经验和教训
就拿P3为例,要求自己从0开始设计ADT,一定要将所有的设计做好了之后再进行写代码的工作,否则就有可能返工……
做设计的时候头脑一定要清晰,用名词分析法,分析有什么名词,那些是对象,哪些是属性,然后考虑清楚哪些是可变类型哪些是不可变类型,然后秉承着让不可变类型尽可能多的原则进行设计。
6.2. 针对以下方面的感受
(1) 面向ADT的编程和直接面向应用场景编程,你体会到二者有何差异?
面向ADT的话将很多方法抽象出来,程序员只需要按照规约完成相应的方法即可,不用考虑应用场景的复杂情况,然后再根据ADT提供的方法应用到实际中,这样ADT和应用耦合度不是那么高,相应的ADT的方法可以进行复用
(2) 使用泛型和不使用泛型的编程,对你来说有何差异?
使用泛型的编程可以适应各种情况,尤其是在编写一些容器类的时候
(3) 在给出ADT的规约后就开始编写测试用例,优势是什么?你是否能够适应这种测试方式?
优势是在写好ADT的方法之后立马就能找出错误,不太能立马适应,总感觉不把方法都实现了就调用方法写测试用例总有种空中楼阁的感觉……但是自己也在努力感受这种方法的好处也在尽快适应这种测试优先的开发方式。
(4) P1设计的ADT在多个应用场景下使用,这种复用带来什么好处?
极大的减少了程序员的任务量
(5) P3要求你从0开始设计ADT并使用它们完成一个具体应用,你是否已适应从具体应用场景到ADT的“抽象映射”?相比起P1给出了ADT非常明确的rep和方法、ADT之间的逻辑关系,P3要求你自主设计这些内容,你的感受如何?
适应了,我的感受就是要用名词分析法,将应用场景种的名词剖析出来,看看哪些可以抽象成类,哪些是这些类的属性,然后再根据动词,看这些类的行为,之后再设计每个类的方法和规约。
(6) 为ADT撰写specification, invariants, RI, AF,时刻注意ADT是否有rep exposure,这些工作的意义是什么?你是否愿意在以后编程中坚持这么做?
这些工作的意义是明白每个类的作用,以及每个类合法的前提条件,以及保证信息的隐藏,减少错误发生的机会。愿意。
(7) 关于本实验的工作量、难度、deadline。
工作量比上次大了不少,难度主要集中在自己从零开始设计一个ADT上,deadline四周时间的话不多不少比较合适。
(8) 《软件构造》课程进展到目前,你对该课程有何体会和建议?
该课程是我们学习真正开发过程的一门课,对于之后走上开发岗位很有帮助。建议就是希望将实验课程的安排晚于课堂讲授一个周期或者半个周期,否则课上还没有讲述AF RI等概念以及没有用习题课做设计ADT的开发范例之前就留这个实验的话,很有可能学生会走很多弯路,倘若课上先讲了这些,之后再开设实验,学生讲课上所学应用到实验中效果会更好,也更省时间。
上一篇: 软件构造 课堂笔记4