面向对象课程 HW9

前言

本单元主要做的事情是读 JML 并且按照 JML 描述的规格编写对应的代码。在代码难度上较前两个单元有所下降，但是耗费的时间不一定比前两个单元少…

第九次作业设计

虽然是按着 JML 写代码，但是具体的实现方式完全由自己决定，JML 只是规定了你要实现什么，没有说你要怎么做。

第九次作业中实现了以下几个类：

NetWork：社交网络类
Person：人员类

人们处于同一个社交网络中，人和人之间可能有 “好友” 关系。本次作业中主要要实现的 NetWork 功能有：

addPerson：向社交网络中添加一个人
addRelation：建立两个人之间的关系
queryValue：查询两个人的关系值
isCircle：查询两个人之间是否有好友链
queryBlockSum：查询有几个不同的好友链
queryTripleSum：查询有几对三角关系（三个人之间相互认识）

在 Person 中要实现 id-value 的映射，在 NetWork 中要实现 id-person 的映射。很自然地使用 HashMap 来存储这两组键值关系。

此外实现了一个并查集来存储人员之间的关系。当两个人建立关系时，将此二人塞到同一颗树下。这样查询两个人直接是否有好友链和查询有几个不同的好友链时都可以直接查询，无需额外的时间开销。

针对三角关系的查询，采取了动态维护的策略。比如说，当建立 $A$ 与 $B$ 的关系时，遍历 $A$ 的所有熟人 $C_i$，若 $C_i$ 与 $B$ 之间有关系则让计数加一。

伪代码

// 并查集
DisjoinSet:
merge();        // 合并
addPerson();    // 添加人
find();         // 以上均为并查集内函数

int blockSum;   // 好友链数量

if merge: blockSum--;
if addPerson: blockSum++;

// 社交网络
NetWork:

int cntTriple;

addPerson(person1, person2):
    for person in person1.acquaintance
        if isCircle(person2, person) 
            cntRtiple++;