本文只提供部分代码及思路

1 实验目标概述

本次实验训练抽象数据类型（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 实验环境配置

略

3 实验过程

3.1 Poetic Walks

在这个问题要实现图的抽象类，这个抽象数据类型需要分别实现基于点的实现和基于边的实现

3.1.1 Get the code and prepare Git repository

3.1.2 Problem 1: Test Graph

在GraphInstanceTest中给graph的各个函数写测试函数

3.1.3 Problem 2: Implement Graph

3.1.3.1 Implement ConcreteEdgesGraph

int set(L source, L target, int weight)
首先遍历边的集合，看是否有与传入边相同的边，如果有，就先删除边，如果传入的weight>0,就将新的边加入集合，如果weight==0,就不做处理。
如果边的集合中没有相同的边，就将新的边加入边的集合。

3.1.3.2 Implement ConcreteVerticesGraph

int set(L source, L target, int weight)
首先判断如果weight>0，就先将这两个点加入点的集合，然后分别寻找到source,target这两个点，将source点的出边添加或删除指定边，将target的入边添加或删除指定边。

3.1.4 Problem 3: Implement generic Graph

3.1.4.1 Make the implementations generic

3.1.4.2 Implement Graph.empty()

返回一个新的实例化对象ConcreteVerticesGraph

3.1.5 Problem 4: Poetic walks

3.1.5.1 Test GraphPoet

给定一个input。从文件中读取poet，调用Graph.poem()后
观察输出与预期是否相等

3.1.5.2 Implement GraphPoet

String getBridge(String source, String target)
这个函数输入两个相邻的单词，然后遍历图，寻找权重最大的bridge-word，并返回，如果没有符合条件的单词，就返回””.

3.1.5.3 Graph poetry slam

3.1.6 Before you’re done

3.2 Re-implement the Social Network in Lab

这个实验是基于在Poetic Walks中定义的Graph及其两种实现，重新实现Lab1中的 FriendshipGraph类。我们需要尽可能复用ConcreteEdgesGraph或 ConcreteVerticesGraph中已经实现的add()和set()方法，而不是从零开始。另外基于所选定的 ConcreteEdgesGraph 或 ConcreteVerticesGraph的rep来实现，而不能修改父类的rep。

3.2.1 FriendshipGraph类

利用P1中的graph对象，然后addVertex()，addEdge()函数都是调用graph中的add(),set()函数。

3.2.2 Person类

用一个字符串保存人名

3.2.3 客户端main()

3.2.4 测试用例

测试添加person和边的关系

3.3 Playing Chess

3.3.1 ADT设计/实现方案

使用 Java OOP 实现一个简单的棋类模拟软件。为“一盘棋类游戏”、“玩
家”、“棋盘”、“棋子”、“棋盘上的位置”、“下棋动作”设计 ADT（类或
接口），命名分别为 Game、Player、Board、Piece、Position、Action。

3.3.2 主程序MyChessAndGoGame设计/实现方案

3.3.3 ADT和主程序的测试方案

测试piece，player，position等是否成功添加