软件构造Lab2记录

First Post:

Last Update:

Word Count:
1.3k

Read Time:
5 min

软件构造Lab2记录

实验目标概述

本次实验训练抽象数据类型（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并据此设计测试用例。

实验环境配置

由于IDEA中集成了jacoco，故直接在配置界面开启即可

实验过程

Poetic Walks

该任务主要是实验一个图的模块，并基于此使用。

  • 完善Graph接口类，并运用泛型的思想，将String拓展为泛型L类；

  • 实现Graph类的方法：add、set、remove、vertices、sources、targets；

  • 利用实现的Graph类，应用图的思想，实现GraphPoet类，如果输入的文本的两个单词之间存在桥接词，则插入该桥接词；若存在多个单一桥接词，则选取边权重较大者。

Get the code and prepare Git repository

git clone即可

Problem 1: Test Graph

测试静态方法生成String类型的Graph。

Problem 2: Implement Graph

该部分要求重写Graph里的方法，分别以点为基础的图和以边为基础的图。两种类型的图都经过同一个实例测试。

Implement ConcreteVerticesGraph

Vertex是点的抽象类，包含3个信息：点的标识、指向该点的边、由该点引出的边。Vertex需要能访问这3个信息，以及增加/删除进边/出边。
ConcreteVerticesGraph是以点为基础的图，每个点通过唯一的标识进行区分，set和remove都依赖与Vertex类中的添加和删除操作，sources和targets也调用了Vertex类的方法。

Problem 3: Implement generic Graph

Make the implementations generic

在程序中选择选择“String”并选择更改所有匹配项，即可实现泛化类型。

Implement Graph.empty()

使Graph.empty()能返回一个新的空实例即可。

Problem 4: Poetic walks

给定一个语料库corpus，根据corpus中的文本生成一个单词图，然后给定一条语句输入，在图中搜索词之间的关系，自动补全语句中可能可以完善的部分。
图的构建规则是，在corpus中，对每一个不一样的单词看作一个顶点，相邻的单词之间，建立一条有向边，相邻单词对出现的次数，作为这条有向边的权值。在输入信息补全时，对相邻单词A和B做检查，如果存在一个单词C，在图中可以由前一个单词A通过这个单词C到达单词B，那么就在A和B之间补全C，补全的优先级按照权值越大者优先。

Implement GraphPoet

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public GraphPoet(File corpus) throws IOException {
    BufferedReader reader = new BufferedReader(new FileReader(corpus));
    String line = "";
    String[] words;
    while ((line = reader.readLine()) != null) {
        line = line.replace(".", " ");
        words = line.split(" ");
        for (int i = 0; i < words.length; i++) {
            graph.add(words[i].toLowerCase());
            if (i > 0) {
                int lastEdgeWeight = graph.set(words[i - 1].toLowerCase(), words[i].toLowerCase(), 1);
                if (lastEdgeWeight != 0)
                    graph.set(words[i - 1].toLowerCase(), words[i].toLowerCase(), lastEdgeWeight + 1);
            }
        }
    }
    reader.close();
    checkRep();
}

Re-implement the Social Network in Lab1

这部分任务就是用我们在3.1中写的ADT，把第一次实验中的FriendshipGraph重新实现一遍，图中的节点仍然是Person类型，所以泛型L一律为Person. 而对于已经写好的FriendshipGraph中的方法，要用3.1中的Graph ADT中的方法来实现它们。

FriendshipGraph类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
import graph.*;

import java.util.*;
import java.util.LinkedList;
import java.util.Queue;

public class FriendshipGraph {
    private final Graph<Person> graph = Graph.empty();


    public boolean addVertex(Person newPerson) {
        return graph.add(newPerson);
    }


    public int addEdge(Person a, Person b) {
        int lastEdgeWeight;
        lastEdgeWeight = graph.set(a, b, 1);
        lastEdgeWeight = graph.set(b, a, 1);
        return lastEdgeWeight;
    }
    

    public int getDistance(Person sta, Person end) {
        if (sta.equals(end))
            return 0;
        Map<Person, Integer> dis = new HashMap<>();
        Map<Person, Boolean> vis = new HashMap<>();
        Queue<Person> qu = new LinkedList<Person>();
        Set<Person> persons = graph.vertices();
        for (Person person : persons) {
            dis.put(person, 0);
            vis.put(person, false);
        }
        vis.remove(sta);
        vis.put(sta, true);
        for (qu.offer(sta); !qu.isEmpty();) {
            Person person = qu.poll();
            for (Map.Entry<Person, Integer> edge : graph.targets(person).entrySet()) {
                Person target = edge.getKey();
                if (!vis.get(target)) {
                    qu.offer(target);
                    vis.remove(target);
                    vis.put(target, true);
                    dis.remove(target);
                    dis.put(target, dis.get(person) + 1);
                    if (target.equals(end))
                        return dis.get(target);
                }
            }
        }
        return -1;
    }
}

Person类

1
2
3
4
5
6
7
8
9
10
11
public class Person {
    private final String Name;

    public Person(String PersonName) {
        this.Name = PersonName;
    }

    public String getName() {
        return this.Name;
    }
}

客户端main()

1
2
3
4
5
6
7
8
9
10
11
12
13
package poet;

import java.io.File;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        final GraphPoet nimoy = new GraphPoet(new File("src/P1/poet/mugar-omni-theater.txt"));
        final String input = "Test the system.";
        System.out.println(input + "\n>>>\n" + nimoy.poem(input));
    }

}

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

  • 设计一个完整的软件，需要从底层的ADT设计起

    • 检验ADT的正确性后才能检测软件的正确性