软件构造实验一

小编是第一次用JAVA进行编程，实验中遇到了一些困难，java语法不熟练只能边做边学，但是java很友好，一般能用到的方法在java的数据类型中都有了定义。强烈推荐菜鸟教程，语法很详细，还有图解实例，对本人有很大帮助。实验过程中小编也借助了学长火炬，但是就某些问题而言，他们的算法不太好想，小编只能暴力拆解，用一些基础的分情况讨论来完成，测试效果符合预期。在阅读以下实验前，小编给出一些思路供大家参考：

幻方：
读取文件中的数组时，无法确定数组的行列数，建议先用二维动态数组存储，java中List可以进行嵌套。确定好数组的行列数相等之后，可以将List转换为整型数组，然后用约束条件判断是否是幻方。
文件按行读入并存储到二维动态数组中需要思考一下。

turtle：
turtle的几个问题不算很难，需要多注意一些细节，比如小编最初把Math.atan2(y,x)的返回值当做了角度，其实返回值是弧度，需要进一步转化为角度。turtle中画图的方法有很多，可以自行查找。

社交关系：
与数据结构中的图是一样的，数据结构中我们用邻接矩阵或者树来存储点之间的关系，java中有map、hashmap、queue等类供我们使用，最重要的前提是确定好你要使用的数据类型是什么，如何存储这些点的邻接关系，然后仔细查一查他们常用的方法就可以完成实验了。设计测试用例，要考虑等价类分类，尽量覆盖全面些。

实验一： Magic Square

幻方是这样一类n*n的矩阵：矩阵中每个数字都不同，每行每列和两个对角线上的数字之和是一个常数。
任务要求：

1. 创建函数 boolean isLegalMagicSquare(String fileName)。在 main()函数中调用五次 isLegalMagicSquare()函数，将 5 个文本文件名分别作为参数输入进去，看其是否得到正确的输出（true, false）。同时能够处理输入文件的各种特殊情况。
2. 创建函数boolean generateMagicSquare(int n)用于产生一个n*n的Magic Square，保存其产生的文本文件并在用isLegalMagicSquare(String fileName)进行判断。考虑到各种情况，给出提示输出false并退出。

1.isLegalMagicSquare() 1.1目标

1. 文件读入；
2. 将数据写入二维数组，判断是否符合矩阵要求；
3. 判断是否满足幻方行、列、对角线之和相等的条件。

1.2具体实现

1. 文件读入
   通过字符串创建File类型对象，指向该字符串路径下的文件；
   判断文件是否存在，若不存在，返回false；
   文件存在条件下，用BufferedReader读入，使用readline方法每次读一行，每行用“，”分隔，整个文件读完结果保存在String str中；
   用str.split(“,”)将str中的每一行分开，得到的新List rows。
   

2. 将数据写入二维数组，判断是否符合矩阵要求
   创建List vecvc，这是List嵌套List类型，最小的数据类型是Integer;把每一行的数字分离出来保存在stmp中，并记录每行的列数。先通过正则表达式对数据进行判断是否为正整数。如果不是正整数则返回false，如果是正整数，将字符型整数转化为整型数据后保存在ArrayList listrow中，然后将listrow作为元素添加进vecvc中。所有行转化后进行判断，行数和列数是否相等，每行的列数是否相等，不等返回false,相等将vecvc转化为二维数组。
   

   图：将文本数据转化为二维动态数组
   
   图：判断数据是否为正整数
   

图：将动态数组转化为二维整型数组
3. 判断是否满足幻方行、列、对角线之和相等的条件
计算出第一行数据之和rowSum，每行数据之和、每列数据之和、两条对角线数据之和都与rowSum作比较，均相等则返回true,否则返回false。

2. generateMagicSquare() 2.1 对已给函数进行分析

在查阅相关资料后，得知这种创造奇数阶幻方的方法叫做罗伯特法。
具体方法：
把1(或最小的数)放在第一行正中；
按以下规律排列剩下的n2-1个数：
1)每一个数放在前一个数的右上一格；
2)如果这个数所要放的格已经超出了顶行那么就把它放在底行，仍然要放在右一列；
3)如果这个数所要放的格已经超出了最右列那么就把它放在最左列，仍然要放在上一行；
4)如果这个数（例如6）所要放的格已经超出了顶行且超出了最右列那么就把它放在它的下一行同一列的格内；
5)如果这个数所要放的格已经有数填入，处理方法同4)。

2.2 流程图

2.3 异常分析

1. java.lang.ArrayIndexOutOfBoundsException
   

异常产生的原因是数组越界,原因是在生成函数中,i<=nn,计算机面对非整数时常用的方法是向下取整,输入奇数时col = n / 2的值会向下取整,所以此时即使i=nn,数组也不会越界,而如果输入为偶数时,当i = n*n时就会发生越界 ,原因是在下标为n的数组中放入了大于n个的数据。
2. java.lang.NegativeArraySizeException

异常产生的原因是数组下标为负值,输入的n为负值循环时数组下标为负,所以报错。

2.4 运行结果

实验2 Turtle Graphics

安装和配置实验环境，将源代码导入到本机项目中，用Turtle graphics绘制正方形、正多边形并使用JUnit测试、计算方位、计算凸包、自由绘制图形，最后将项目推送到GitHub上。

1 Problem 1: Clone and import

如何从GitHub获取该任务的代码、在本地创建git仓库、使用git管理本地开发。
在GitHub上对P2进行clone或者download，或者fork到自己的仓库中。

打开eclipse->文件->导入->常规->文件系统->浏览->选择需要导入的文件夹->完成
打开导入后的文件会发现上面有红叉，点进每一个文件里更改package 名称。

图：更改前

图：更改后

2 Problem 3: Turtle graphics and drawSquare

根据提示了解到turtle类中的forward和turn两种方法，画正方形需要画一条边旋转一次90度，所以循环四次上述 *** 作。

图：drawSquare的实现

图：运行结果

3 Problem 5: Drawing polygons 3.1 实现calculateRegularPolygonAngle

计算正多边形内角公式：（边数-2）*180/边数

图：calculateRegularPolygonAngle的实现

3.2 实现drawRegularPolygon

直接将degree=calculateRegularPolygonAngle返回结果作为旋转角度会发现运行结果与预期不同，原因是forward(units)按照惯例初始朝上，所以旋转角度应该为180-degree，运行后结果符合预期。

图：drawRegularPolygon的实现

图：绘制正八边形

4 Problem 6: Calculating Bearings 4.1 实现calculateBearingToPoint

该函数目的是求向量方向为currentBearing需要顺时针旋转多少角度与向量（targetX-currentX）,（targetY-currentY）同向。
先算出向量（x,y）=（（targetX-currentX）,（targetY-currentY）），根据x和y的正负进行分类，求出向量（x,y）与y轴正向之间夹角（顺时针旋转）temp，再计算出currentBearing顺时针旋转到temp时旋转角度degree，对degree进行加圈减圈至degree的范围为0<=degree<360。

图：calculateBearingToPoint的实现

4.2 实现calculateBearings

List类型的返回值degrees中元素个数等于xCoords长度-1，循环次数为xCoords.size()-2。求解第一个degrees中的元素时，currentBearing代为0.0，求解其他元素时，currentBearing为上一个degrees中的元素。

5 Problem 7: Convex Hulls 5.1 凸包定义

假设平面上有n个点，过某些点做一个多边形，使得这个多边形能够覆盖所有的点，当这个多边形是凸多边形时，称之为“凸包”。

凸包问题：把这些点放在二维坐标系里面，那么每个点都能用 (x,y) 来表示。
现给出点的数目n，和各个点的坐标。求构成凸包的点所组成的最小集合。

5.2 Gift-Wrapping算法

查阅资料发现Gift-Wrapping算法也称Jarvis步进法（Jarvis march），运行时间是O（nh）,其中h为凸包中的顶点数。
算法思想：
首先在平面上建立一个平面直角坐标系，先找到最左边的点，这个点一定是在凸包中的，然后遍历点集，计算与该点连接点中偏转角最小的点，找到后放入点集，然后再次以这个新放入的点为计算点，再次计算偏转角中最小的点。依次循环下去，直到回到起始点。
具体实现：
判断集合中的点数，小于等于3返回原点集，否则遍历寻找左下角的点。

将最小点将入集合中并作为当前点，寻找与当前点偏转角最小的点，偏转角相同时，找与当前点距离最远的点，找到后加入集合中，并作为当前点重复上述 *** 作，直至当前点为最小点。

6 Problem 8: Personal art

彩色棒棒糖：设置颜色数目，每次循环通过取模结果选择画笔颜色，步长增加1，旋转30度，最后添加直线作为棒棒。

运行结果：

7 Submitting

如何通过Git提交当前版本到GitHub上你的Lab1仓库。
Git先与远程仓库连接。通过下面的指令可以将当前版本推送至Github。

实验3 Social Network

构造一个无向图，可以添加顶点和边，返回两点间通路最小长度。可以由有向图扩展为无向图，若有A->B， B->A，则A和B互达，通过小范围修改可以求解有向图中两点通路长度。设计结束后设计测试用例进行测试。
3.3.1 设计/实现FriendshipGraph类
设计数据类型和方法：

功能

名称	功能
graph	存储键值对，key为Person p,value为p的朋友们构成的列表
addVertex	向图中加入顶点
addEgde	向图中加入两点间的边
getDistance	两点间最短路长
main	进行测试

1 实现addVertex

实现public void addVertex(Person p)的基本思想：
先判断是否在图的点集合中，若不在则添加到点集中，并且令该点的朋友们为本身，否则输出“姓名重复”，结束。
3.3.1.2 实现addEgde
实现public void addEdge(Person p1,Person p2)的基本思想：
首先判断两个是否均在图的点集中，若至少一个点不在点集中，则输出提示先将点添加到点集中。若均在点集中，判断图中p1的朋友们中是否有p2，没有则添加p2到p1的朋友们中，若有则提示已存在，结束。
3.3.1.3 实现getDistance
实现public int getDistance(Person p1,Person p2)的基本思想：
若p1=p2，返回0；
若p1和p2至少有一点不在点集中，返回-1；
若p1和p2均在点集中：
从点p1开始进行层序遍历，采用队列存储已扫描的点，至队列中包含p2,返回已有层数。如果全部遍历后队列中仍无p2，则返回-1。
例如：

队列：

2 设计/实现Person类

Person的属性只有一个name，类内的方法有默认的构造和给名字赋值，获得名字。

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

直接使用的实验手册上的main（）
运行结果：

将graph.addEdge(rachel,ross)注释掉（意即 rachel 和 ross 之间只存在单向的社交关系 ross->rachel），第 14-17 行的代码应输出-1，-1，0，-1，让程序执行，其实际输出结果与期望并不一致，原因是在getDistance函数中将单向关系拓展为了双向关系，如果想得到期望结果，则需要把如下代码注释掉，便可以用于求有向图中的通路长度。

运行结果：

将第 3 行引号中的“Ross”替换为“Rachel”，输出姓名重复，且之后涉及到Person ross的语句均会提示错误。

4 设计/实现测试用例 4.1 测试addVertex

设计等价类：
{与图中点集名字不同的Person}
{与图中点集名字相同的Person}

4.2 测试addEdge

设计等价类

等价类	期望结果
(p1,p2)={ 两点都在图中且有双向边}	不重复添加
(p1,p2)={ 两点都在图中且只有单向边}	若已有p1->p2,，则不添加；若无，则添加p1->p2
(p1,p2)={ 两点都在图中且无边}	添加p1->p2
(p1,p2)={ 前者在图中，后者不在图中}	不添加边，提示将p2加入点集中
(p1,p2)={ 前者不在图中，后者在图中}	不添加边，提示将p1加入点集中
(p1,p2)={ 两者都不在图中}	不添加边，提示将p1和p2加入点集中

4.3 测试getDistance

等价类	期望结果
(p1,p2)={两点都在图中，但其中一个无朋友}	-1
(p1,p2)={p1和p2相等 }	0
(p1,p2)={至少一点不在图中 }	-1
(p1,p2)={p1和p2之间有通路 }	返回最短路长

测试样例：