lab2

2019年春季学期
计算机学院《软件构造》课程

Lab 2实验报告

姓名 刘泽宇
学号 1170300723
班号 11703007
电子邮件 [email protected]
手机号码 [phone]

目录

1 实验目标概述 1
2 实验环境配置 1
3 实验过程 1
3.1 Poetic Walks 1
3.1.1 Get the code and prepare Git repository 1
3.1.2 Problem 1: Test Graph 1
3.1.3 Problem 2: Implement Graph 1
3.1.3.1 Implement ConcreteEdgesGraph 2
3.1.3.2 Implement ConcreteVerticesGraph 2
3.1.4 Problem 3: Implement generic Graph 2
3.1.4.1 Make the implementations generic 2
3.1.4.2 Implement Graph.empty() 2
3.1.5 Problem 4: Poetic walks 2
3.1.5.1 Test GraphPoet 2
3.1.5.2 Implement GraphPoet 2
3.1.5.3 Graph poetry slam 2
3.1.6 Before you’re done 2
3.2 Re-implement the Social Network in Lab1 2
3.2.1 FriendshipGraph类 2
3.2.2 Person类 3
3.2.3 客户端main() 3
3.2.4 测试用例 3
3.2.5 提交至Git仓库 3
3.3 Playing Chess 3
3.3.1 ADT设计/实现方案 3
3.3.2 主程序ChessGame设计/实现方案 3
3.3.3 ADT和主程序的测试方案 3
3.4 Multi-Startup Set (MIT) 4
4 实验进度记录 4
5 实验过程中遇到的困难与解决途径 4
6 实验过程中收获的经验、教训、感想 4
6.1 实验过程中收获的经验和教训 4
6.2 针对以下方面的感受 4

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实验环境配置
这次实验没什么配置的

在这里给出你的GitHub Lab2仓库的URL地址（Lab2-学号）。
https://github.com/ComputerScienceHIT/Lab2-1170300723
3实验过程
请仔细对照实验手册，针对三个问题中的每一项任务，在下面各节中记录你的实验过程、阐述你的设计思路和问题求解思路，可辅之以示意图或关键源代码加以说明（但千万不要把你的源代码全部粘贴过来！）。
3.1Poetic Walks
主要是用两个类实现gragh接口，一个用边实现一个用点实现，注意数据泄露
3.1.1Get the code and prepare Git repository
Git fetch
3.1.2Problem 1: Test Graph
写测试文件，主要是根据Graph里面各个方法的规格说明，设计测试用例。
这是对于两个实现类还有泛型的测试

3.1.3Problem 2: Implement Graph
3.1.3.1Implement ConcreteEdgesGraph
private L source;
private L target;
private int weight;
这里将边设为了不可变对象，所以需要考虑泄露问题，但是边的field中都是不可变的，所以只需设置成private即可
用set存放点的label，用list存放边。
以下是实现graph中各种方法：
public boolean add(L vertex)
利用set 自身的不重复特性，加入新的标签
public int set(L source, L target, int weight)
调用add方法，因为无论之前有没有结果都没有区别
遍历边的list，如果有这条边，更新权值，返回原来的权值，如果没有，新建一条边，返回0；
public void checkRep()
想法是判断是否有重复的边
public boolean remove(L vertex)
去掉点集中的这个点，再将边中，起点或终点是这个点的边都去掉。
public Set vertices()
返回图中所有label组成的集合
public Map<L, Integer> sources(L target);
返回终点标签为target的边的起点标签，map中存储这个边的权值
public Map<L, Integer> targets(L source);
返回起点标签为source的边的终点标签，map中存储这个边的权值
边的checkrep
public void checkRep() {
assert !(this.weight<=0);
}
通过检查权值是否有负数，来检测是否泄露。（按照提供的操作不可能出现负权，所以如果出现，一定是因为泄露）
类的checkrep
public void checkRep() {
for(int i = 0;i<edges.size();i++) {
for(int j =i+1;j<edges.size();j++) {
assert !(edges.get(i).equals(edges.get(j)));
}
}
}
不应该有相同的边
3.1.3.2Implement ConcreteVerticesGraph
、 private L name;
private Map<L, Integer> targetOfv;
private Map<L, Integer> sourceOfv;
主要思路就是在targetOfv map中存储所有作该点终点的点
在sourceOfv map中存储所有作该点起点的点
点的checkrep
public void checkRep() {
assert !targetOfv.keySet().contains(this.getName());
assert !sourceOfv.keySet().contains(this.getName());
}
这个想法就是检测代码正确性，自己与自己不能有边
类的checkrep
private void checkRep() {
for(int i=0;i<vertices.size();i++) {
for(int j=i+1;j<vertices.size();j++) {
assert !vertices.get(i).equals(vertices.get(j));
}
}
}
不应该有相同的点，
3.1.4Problem 3: Implement generic Graph
3.1.4.1Make the implementations generic
这个只需将所有String 改成L即可，因为在这次实验中，这个Stirng只有标签的作用，唯一的操作是判断是否相等。
3.1.4.2Implement Graph.empty()
在graph.empty中返回任意一个已经实现的新建类即可
3.1.5Problem 4: Poetic walks
3.1.5.1Test GraphPoet
就验证一下题目给的例子是否正确
测试截图，图结构输出

3.1.5.2Implement GraphPoet
1.文件输入，以空格和换行符分割获得单词。
2.根据要求建立图，每个节点label是一个单词，如果相同的边出现两次 ，权值为2，以此类推。
3.对于给定的句子，据要求架桥，原则是：a c 如果 a 有到b的边，b有到c的边，则b可以作为桥，若有多个b满足条件，则选择最高权值的b
3.1.5.3Graph poetry slam

测试截图

3.1.6Before you’re done
请按照http://web.mit.edu/6.031/www/sp17/psets/ps2/#before_youre_done的说明，检查你的程序。
如何通过Git提交当前版本到GitHub上你的Lab2仓库。
Git add
Git commit -m
Git push origin master

项目结构：

3.2Re-implement the Social Network in Lab1
这个就是对graph泛型接口的应用
3.2.1FriendshipGraph类
使用3.1的图还有提供的方法，得到两点之间的最短距离，还是用队列宽搜的方式。
因为有了特殊的起点，所以采用宽搜的方式，以p1为起点，队列实现广度优先搜索，每次出队表示关系远了一层，距离加1；找到p2 则退出搜索，返回距离。如果宽搜完毕，未找到p2则返回-1
这里求最小距离时，要注意判断是否此点的所有邻接点都已经加入队列，距离再加一，否则当图中有环时，会出问题。
3.2.2Person类
这个直接拿原来实验1的person即可
给出你的设计和实现思路/过程/结果。
每个Person有name元素
为了方便对图中每个人的操作。每个Person增加了序号index属性。
若未在图中，index = -1；若在图中，为index赋值。具体方法：加入图时，根据已加入图的元素个数，为index赋值。这样每个person和图中的邻接矩阵，就有了很方便的一一对应关系。同时，易于判断此人是否在图中。
缺点是此时的person类有些类似friendshipGraph的子类，所有person对象都只能为一个graph对象服务，不过已经可以满足现在的设计需求
3.2.3客户端main()
给出你的设计和实现思路/过程/结果。

3.2.4测试用例
Person ross = new Person(“ross”);
Person rachel = new Person(“Rachel”);
Person ben = new Person(“Ben”);
Person kramer = new Person(“Kramer”);
Person hamer = new Person(“hamer”);
graph.addVertex(rachel);
graph.addVertex(ross);
graph.addVertex(ben);
graph.addVertex(kramer);
graph.addEdge(rachel, ross);
graph.addEdge(ross, rachel);
graph.addEdge(ben, ross);
graph.addEdge(ross, ben);
graph.addEdge(hamer, ben);
3.2.5提交至Git仓库
如何通过Git提交当前版本到GitHub上你的Lab3仓库。
在这里给出你的项目的目录结构树状示意图。

3.3Playing Chess
3.3.1ADT设计/实现方案
设计了哪些ADT（接口、类），各自的rep和实现，各自的mutability/ immutability说明、AF、RI、safety from rep exposure。
必要时请使用UML class diagram（请自学）描述你设计的各ADT间的关系。

public class Position （immutability）
Field
private int x = -1;
private int y = -1; //表示位置
public Piece onPiece = null; //表示该位置上的棋子
接口：
public boolean equals(Object position) 重写的equals方法
public String toString() 重写的toString方法，返回表示位置的字符串

public class Piece （immutability)
Field
Private int color; //0表示白子，1表示黑子
Private String Piecename = null; //表示棋子的种类
接口：
public Piece(String name,int color) //新建一种棋子
说明一下，这里定义的棋子是棋子的种类，代表一类棋子，而不是一个，这样再扩展规则的时候，可以直接在piece中增加field。

public class Board （mutability)
Field
private int Size; //棋盘的实际大小
public Position[][] boardPositions = new Position[19][19]; //这里是觉得围棋棋盘应该就是最大的了。
接口：
public Board(int gametype)
根据游戏种类生成不同大小的棋盘，同时生成一个position类型的二维数组，来表示棋盘，因为游戏的变动，所以将其设置为public，但是这里应该不会泄露，因为用户端正常来讲是不用直接操作board的，设计游戏时只需用game和action，即使用户通过调用game中的getboard方法，也只是一个相同内容的副本。
public String toString()
可以看到当前的棋盘信息，哪个位置上放的哪类棋子
public int size()
返回棋盘的大小

public class Player （immutability)
Field：
private String PlayerName = null; 棋手名字
private String HistoryString = “”; 棋手走棋历史
private Set OwnPieces = new HashSet(); 该棋手拥有的棋子
Private int color; 棋手执白或黑
接口：
Set\Get
这里简写所有设置或取得该类field的方法
public String toString
返回该棋手拥有的棋子组成的字符串

public class Action （immutability)
Field：
private Board gameBoard; //表示该操作在哪个棋盘上
接口：
public boolean checkrep(Position position)
位置合法性检查
以下是实验要求中要实现的几个操作，包括了异常情况处理和错误提醒
public boolean MovePiece(Player player, Position startPosition, Position endPosition)
public boolean SetPiece(Player player, Piece piece, Position position)
public boolean inSetPiece(Player player, Piece piece, Position position)
public boolean remove(Player player, Position position)
public boolean Eat(Player player, Position StartPosition, Position EndPosition)

public class Game （immutability)
Field：
private int gameType; //游戏类型
private Board gameBoard; //棋盘
private Action gameAction; //
private Player player1 = new Player();
private Player player2 = new Player();
接口：
public Game(int gameType)
新建游戏，表明游戏类型
public Board getBoard()
返回与本board相同内容的副本
public void Init(String player1,String player2)
初始化棋盘
3.3.2主程序MyChessAndGoGame设计/实现方案
利用while（true）循环不断游戏，定义round变量，初值为0，若某一方执行了正确操作（实验指导书中）则round++，根据round的奇偶性，可以判定是哪一方走棋。
象棋中会有move 和eat操作，用户输入起点和终点的位置就可以完成操作

这里0操作是为了方便观察棋盘情况，不在要求之内，所以行动方并未更换。

查询和计算操作，承接上面的move和eat，展示history

围棋有set和remove操作 输入该点位置坐标即可

查询 计算 history和象棋相同

一些异常情况

3.3.3ADT和主程序的测试方案

\

这里只需测试Action。因为所有的东西都体现在这五个操作上，如果这五个操作没有问题，说明这几个类配合无误。
至于主程序MyChessAndGoGame，已经演示过了，测试也就多此一举了
3.4Multi-Startup Set (MIT)
请自行设计目录结构。
注意：该任务为选做，不评判，不计分。
4实验进度记录
请使用表格方式记录你的进度情况，以超过半小时的连续编程时间为一行。
每次结束编程时，请向该表格中增加一行。不要事后胡乱填写。
不要嫌烦，该表格可帮助你汇总你在每个任务上付出的时间和精力，发现自己不擅长的任务，后续有意识的弥补。
日期 时间段 计划任务 实际完成情况
2019.3.25 18：30-22：30 p1 遇到困难未完成
2019.4.1 18：30-22：30 p1，p2 按计划完成
2019.4.3 13：30-20：30 P3 按计划完成
5实验过程中遇到的困难与解决途径
遇到的难点 解决途径
P1 对实验要求理解，还有对不变量的理解
与同学讨论，浏览博客
P3 开始思维很混乱，觉得每个类都有很多实现方式，不知道怎么组合起来最好。

抓住棋盘这个不变的东西，找到了个人觉得较好的一种实现方式

6实验过程中收获的经验、教训、感想
6.1实验过程中收获的经验和教训
三思而后写代码
6.2针对以下方面的感受
(1)面向ADT的编程和直接面向应用场景编程，你体会到二者有何差异？
ADT泛用性更高，希望能提供更好的扩展性，于此同时有不变性。
而应用场景扩展性就不用考虑那么多。
(2)使用泛型和不使用泛型的编程，对你来说有何差异？
使用泛型，要让泛型的那个变量不需要对自身计算
(3)在给出ADT的规约后就开始编写测试用例，优势是什么？你是否能够适应这种测试方式？
一开始不太能适应，但是先写测试，有助于更好的理解函数功能，已经思考异常情况，这样编程的时候就有了帮助
(4)P1设计的ADT在多个应用场景下使用，这种复用带来什么好处？
减少码量
(5)P3要求你从0开始设计ADT并使用它们完成一个具体应用，你是否已适应从具体应用场景到ADT的“抽象映射”？相比起P1给出了ADT非常明确的rep和方法、ADT之间的逻辑关系，P3要求你自主设计这些内容，你的感受如何？
突然*反而有点束手束脚，怕这样实现不够好，多想想就好了
(6)为ADT撰写specification, invariants, RI, AF，时刻注意ADT是否有rep exposure，这些工作的意义是什么？你是否愿意在以后编程中坚持这么做？
意义在于对自己到底在写什么有了数，尤其是多个类配合的时候尤为重要，rep exposure 对于提高程序健壮性，大型程序的debug都有很大的意义。
虽然很麻烦，但还是很有必要的
(7)关于本实验的工作量、难度、deadline。
工作量很大
(8)《软件构造》课程进展到目前，你对该课程有何体会和建议？
为何实验内容先于课堂内容？？？