---

前言

本次实验通过求解三个问题，训练基本Java编程技能，能够利用JavaOO开发基本的功能模块，能够阅读理解已有代码框架并根据功能需求补全代码，能够为所开发的代码编写基本的测试程序并完成测试，初步保证所开发代码的正确性。另一方面，利用Git作为代码配置管理的工具，学会Git的基本使用方法。

---

一、Magic Squares

一个n阶MagicSquare定义为一个n*n方阵，包含两两不等的正整数，其中每一行、每一列和对角线的数字之和都相等。
该部分任务主要分为两个部分：
（1）判断给定的五个文本文件中给出的数据是否符合幻方的定义；
（2）使用给定的一个静态方法生成幻方，并向另一个文本文件输出，再利用（1）中编写的判定方法判断数据的合法性。

1. isLegalMagicSquare()

思路与过程：
（1） 首先从文件中按行读出数据，每一行数据存入字符串数组myLine，用整型变量line记录读入的行数；
（2）调用.split("\t")方法将每行字符串myLine[i]分割为粒度更小的字符串，并用整型变量len记录当前行包含的分割后字符串个数。判断len是否与line相等，若不相等说明给定数据不以方阵形式组织，不符合幻方定义。
（3）保证文件数据为方阵后，利用正则表达式[1-9][0-9]*判断当前行每个分割后字符串是否为正整数，若不符合则数据表示不符合幻方要求。若符合正则表达式，则利用Integer.valueOf方法将该分割字符串转化为正整数存入整形数组matrix。

正则表达式判断部分代码如下:

for (int j = 0; j < len; j++) {
    
		if (!strmatrix[i][j].matches("[1-9][0-9]*")) {
    
			System.out.print("error info: " + strmatrix[i][j] + " in "+filename+" is illegal\n");
			return false;
		}
			matrix[i][j] = Integer.valueOf(strmatrix[i][j]);
}

(4) 定义行和数组sumOfRow与列和数组sumOfCol, 用于记录每行与每列的和, 定义主对角线和sumOfDiagonal1与副对角线和sumOfDiagonal2。遍历matrix完成求和后, 将主对角线和设置为标准值, 比较主副对角线和。若两个和值不一致, 提示错误信息并返回false错误。比较行列和数组中每个数据。若过程中发现某个数据与标准值不符, 同样提示错误信息返回false。

2. generateMagicSquare()

主要思路：
正奇数幻方的产生方法，也就是generateMagicSquare()使用的方法可以用口诀来概括：“一居上行正中央，依次斜填切莫忘；上出框时向下放，右出框时向左放；排重便在下格填，右上排重一个样”。
具体来说，添加代码判断输入的n不为负数或偶数后，函数generateMagicSquare首先将数字1放置在幻方最上方正中央位置，而后每次将下一个数放置在右斜上方位置，每放置n个数字行数加一。若到达第一行，则下一次到最后一行放置，否则行数减一；若到达最后一列，则下一次到第一列放置，否则列数加一。放完所有n*n个整数后，将矩阵输出到文件6.txt。

二、Turtle Graphics

该实验的目的主要是通过Java实现一个简单的Turtle小程序并实现简单图形绘制的功能。

Problem 1: Clone and import

从实验手册链接领取P2初始任务代码，克隆到本地仓库，导入eclipse项目目录。

Problem 3: Turtle graphics and drawSquare

Turtle graphics实验任务组包含了“小海龟画图”GUI的简单Java实现版本。实验的主要任务是根据实验指导完成一些功能代码的阅读与补全。
函数drawSquare的实现要求利用forward和turn方法完成一个正方形的绘制。forward方法能够让小海龟在画面上前进给定单位距离，turn方法能够让小海龟又转向90度。
由于每次绘图开始时海龟朝向Y轴正方向，因此只需让小海龟前进sideLength个单位，再右转90度，重复4次即可完成一个正方形的绘制。

Problem 5: Drawing polygons

首先完成函数calculateRegularPolygonAngle(int sides)的实现。该函数接收参数为多边形的边数，返回值为对应多边形内角大小（以度为单位），数值类型为double。由正多边形内角计算公式，可以直接返回180.0 * (sides – 2) / sides。
接下来，运行TurtleSoupTest.java文件，测试对函数calculateRegularPolygonAngle的实现是否正确。
保证该函数实现正确后，要求完成对函数drawRegularPolygon的实现，且需要用到calculateRegularPolygonAngle的实现。实现方法也十分简单：只需要首先利用函数calculateRegularPolygonAngle计算出正多边形内角度数angle，再将turtle朝向右转（450-angle）度，而后进行sides（边数）次循环，每次循环先用forward方法前进sideLength距离，再使用turn方法转向（180-angle）度即可。

Problem 6: Calculating Bearings

该任务要求实现用于计算方位角的两个函数。
首先实现calculateBearingToPoint。该函数根据当前点，当前朝向与目标点坐标计算指向目标点的方位角。
直接利用Math.atan2函数计算出来由当前位置指向目的位置向量的与X轴正向的夹角，然后计算当前朝向的夹角，然后作差即可。主要不能出现负角度，可在适当时候增加360度达到此目的。

Problem 7: Convex Hulls

利用Gift wrapping algorithm算法计算给定集合中的凸包，首先找到最左下角的点加入集合，然后比较剩余点到此点的偏转角，找到偏转角最小的加入集合，当偏转角相同时，找到距离当前点最远的点加入集合。而后选择最新加入集合的点为基点，比较剩余其他各点到该点的偏转角，同样按照上述方法找到符合条件的点。以此类推，直到之后找到符合条件的点为起始点，得到凸包的点集。

Problem 8: Personal art

该部分要求利用以上实现各个函数实现个人图形的绘制。自由发挥即可。

submitting

在本地仓库文件夹下，打开git bash，键入命令行序列：
$git add .
$git commit -m “statement”
$git push origin master

三、Social Network

该任务要求实现Person和FriendshipGraph两个类，用FriendshipGraph来构建Person之间的关系来模拟一个社交网络，能够计算出每两个Person之间的社交距离。

1.设计/实现FriendshipGraph类

设计思路：考虑将FriendshipGraph类的实现与Person类的实现尽量独立，减少耦合。FriendshipGraph中顶点代表个人Person，有向边(A,B)代表B是A的单向好友，顶点与边采用邻接表的数据结构存储。FriendshipGraph类中除去两个实例构造方法，还包含其他四个方法：
（1）addVertex向社交网络中添加个人节点；
（2）addEdge向社交网络中添加单向好友关系；
（3）getDistance获取图中两人之间好友关系的最短路径长度；
（4）main方法负责测试实验指导中给出的样例数据。
其中，getDistance部分采用广度优先搜索从起点先广搜索目标节点并获取最短路径长度。
实现思路与过程：
1）邻接表部分，FriendshipGraph类中设置两个内部类：Edge类表示图中好友关系，包含Person类型成员person以及Edge类型成员next；Vertex类表示图中个人，包含Person类型成员person以及Edge类型属性next。

public class Vertex {
    
		Person person; 
	    Edge next; 
		Vertex(Person P, Edge next) {
    
			this.person = P;
			this.next = next;
		}
}
public class Edge {
    
		 Person person;
		 Edge next; 
		 Edge(Person P, Edge next) {
    
			this.person = P;
			this.next = next;
		}
}

同时，FriendshipGraph类中还包含Map集合vertexsMap，存储从Person到Vertex的映射，以保证后续不会有重复名字的Person被添加进社交网络；以及Map集合visMap，保证每次调用getDistance方法进行广度优先搜索时同一个顶点不会被搜索两次。

Map<Person, Vertex> vertexsMap; 
Map<Person, Boolean> visMap; 

2）由实验指导手册可知，FriendshipGraph应该支持默认参数构造和带Person类参数构造两种构造方法。

public FriendshipGraph() {
    
	this.vertexsMap = new HashMap<>();
	this.visMap = new HashMap<>();
}
public FriendshipGraph(Person P) {
    
	this.vertexsMap = new HashMap<>();
	this.vertexsMap.put(P, new Vertex(P, null));
	this.visMap = new HashMap<>();
	this.visMap.put(P, false);
}

3）Main方法与设计思路相似，添加实验指导中测试代码段即可。
4）addVertex方法方法接收参数Person P。若P为空或P不空，但P的身份无效（即Person中属性valid==false），则提示信息无效并返回false。若映射表vertexsMap中已经包含与P相同的键值，则给出添加非法提示并返回false，表示添加失败；否则，遍历vertexsMap的键值部分，若包含与P姓名相同的键值，则P不予添加，并调用P的denuStatus方法否决P的身份有效性，防止P进入后续操作，给出非法添加提示并返回false。若以上两次判重成功通过，说明P的身份独特性和有效性，新建P节点并将其添加至vertexsMap。
关键代码如下：

for(Person q: vertexsMap.keySet()) {
    
		if (q.getName().equals(P.getName())) {
    
				System.out.println("Error: The name \""+P.getName()+"\" has existed in records.");
				P.denyStatus();
				return false;
			}
}

5）addEdge方法接收有向边起始点begin和终点end（二者为Person类型），若二者中有一方为空，打印错误信息并返回false；若二者中有一方身份无效，则提示信息无效并返回false。若二者有一在图中没有对应顶点，同样打印错误信息并返回false。保证二者不空且在图中有对应顶点后，新建有向边并将其添加进begin的邻接表。关键代码如下：

Vertex beginVertex = vertexsMap.get(begin);
Vertex endVertex = vertexsMap.get(end);
if (beginVertex == null) {
    
	System.out.println("Error: The beginpoint "+begin.getName()+" does not exist");
	return false;
}
if (endVertex == null) {
    
	System.out.println("Error: The endpoint "+end.getName()+" does not exist");
	return false;
}

6）getDistance方法接收Person类参数begin和end，判定图中是否存在二者对应顶点，若不存在则打印提示信息并返回-1，否则将二者作为参数传入先广搜索方法BFS计算最短距离。
7）私有方法BFS接收起点个人start，目标个人end，以及顶点遍历标记visMap。若start与end相同，返回0；若二者其中之一为空返回-1；否则建立Map集合dis，记录起始点到各顶点距离Integer。而后通过广度优先搜索尝试寻找end，并更新距离信息。一旦在队列中发现end，返回end对应距离。
搜索过程需要用到辅助队列Queueq。起始时，q中只包含start顶点，且start访问标记为true，到自身距离为0;若队列q不空，则取出队头节点，遍历队头顶点的边表，依次将其中未被访问过的顶点添加至队尾，更新距离，而后判断顶点是否为end，若是则返回对应距离，否则继续。当循环结束后，若距离表dis中没有end的记录，说明start无法到达end，返回-1，否则返回end对应距离。

2. 设计/实现Person类

设计思路：Person类包含两个属性，分别是String类型的name表示姓名，和boolean类型的valid表示身份的有效性。除此之外，Person包含4个方法：带姓名的构造方法，获取姓名方法getName，获取身份状态方法getStatus，以及否定身份方法denyStatus。加入身份有效性的考虑在于，在不使用static类型全局变量的前提下，校验不同Person之间姓名的互异性成为一个不容忽视的问题。引入身份有效性后，通过将Person加入到社交网络时的行为来判定个人身份的有效性，即判重。

3. 设计/实现客户端代码main()

直接复制实验指导的代码稍加修改即可。

4. 设计/实现测试用例

设计思路：分别对addVertex, addEdge, getDistance，main四个方法进行测试。
1）对于addVertex，设计test用例testaddVertex，内建四个Person对象全部执行addVertex，判断vertexsMap中是否包含这些对象即可。
2）对于addEdge，设计测试用testaddEdge，内建8个Person对象，执行addVertex后，执行addEdge然后判断他们的朋友中是否包含彼此即可。
3）对于getDistance，设计test用例testgetDistance，内建8个Person对象，执行addVertex，addEdge后，测试三种距离等价类：距离为-1，距离为0，距离为正整数。
4）对于main方法，设计测试用例testSampleCase，测试其中代码执行结果是否与原版实验指导给出的相同。

四、实验过程中遇到的困难与解决途径

遇到的困难	解决途径
Eclipse将java项目转换为maven项目后找不到主类	将目标源文件夹移出build path后再移入或 项目右击->maven->update maven project
Eclipse导入maven文件报错”Editor does not contain a main type”	将目标源文件夹移出build path后再移入或 项目右击->maven->update maven project
Git clone时报错OpenSSL SSL_read: Connection was reset, errno 10054:	设置git代理

---

五、总结

作为软件构造的首个实验，其任务量还是不小的，特别是对于此前缺乏JAVA编程经验的我来说，快速入门并且完成实验需要花费比较多的时间。但是总体来说，收获还是挺大的，起码对于Git的使用更为熟练一些。希望自己还是能扎实学些东西，好好提升一下自己的代码能力。