哈工大软件构造实验1_哈工程 高翔

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

Lab 1实验报告

姓名 高翔
学号 1180300828
班号 1803008
电子邮件 GX313406876@163.com
手机号码 18845771713

目录

1 实验目标概述 1
2 实验环境配置 1
3 实验过程 2
3.1 Magic Squares 3
3.1.1 isLegalMagicSquare() 3
3.1.2 generateMagicSquare() 5
3.2 Turtle Graphics 5
3.2.1 Problem 1: Clone and import 6
3.2.2 Problem 3: Turtle graphics and drawSquare 6
3.2.3 Problem 5: Drawing polygons 7
3.2.4 Problem 6: Calculating Bearings 9
3.2.5 Problem 7: Convex Hulls 10
3.2.6 Problem 8: Personal art 11
3.2.7 Submitting 13
3.3 Social Network 13
3.3.1 设计/实现FriendshipGraph类 13
3.3.2 设计/实现Person类 15
3.3.3 设计/实现客户端代码main() 15
3.3.4 设计/实现测试用例 18
4 实验进度记录 19
5 实验过程中遇到的困难与解决途径 19
6 实验过程中收获的经验、教训、感想 20
6.1 实验过程中收获的经验和教训 20
6.2 针对以下方面的感受 20

1实验目标概述
本次实验通过求解三个问题，训练基本 Java 编程技能，能够利用 Java OO 开发基本的功能模块，能够阅读理解已有代码框架并根据功能需求补全代码，能够为所开发的代码编写基本的测试程序并完成测试，初步保证所开发代码的正确性。另一方面，利用 Git 作为代码配置管理的工具，学会 Git 的基本使用方法。
 1.基本的 Java OO 编程
 2.基于 Eclipse IDE 进行 Java 编程
 3.基于 JUnit 的测试
 4.基于 Git 的代码配置管理
2实验环境配置
1.安装eclipse

选择下面日本的镜像即可
2.JDK下载

根据需要下载Windows x64版本
3.配置JDK
点击 : Window -> Prefernces -> Java -> Installed JREs -> Add -> Standard VM -> 选择 JDK 目录 D:\Program Files\jdk-13.0.2 -> Finish -> 在列表勾选刚刚添加的 JDK -> Apply
4.JUnit
4.1建立Java程序（test测试程序）
4.2将JUnit加入library中
项目名字（右键）-> Build Path -> Configure Build Path
Library(中间上面） - > classpath （左边） -> Add Libraries（右边）
右键相应的Java程序，按JUnit进行运行

在这里给出你的GitHub Lab1仓库的URL地址（Lab1-学号）。
https://github.com/ComputerScienceHIT/Lab1-1180300828
3实验过程
请仔细对照实验手册，针对四个问题中的每一项任务，在下面各节中记录你的实验过程、阐述你的设计思路和问题求解思路，可辅之以示意图或关键源代码加以说明（但无需把你的源代码全部粘贴过来！）。
为了条理清晰，可根据需要在各节增加三级标题。
3.1Magic Squares
1.幻方是n*n个不同数字，它满足每行每列且每个对角线上数字之和都相同，这样的矩阵称之为幻方，这个程序就是要求判断一个矩阵是否为幻方。
2.Main函数有两个部分，其中之一是读取5个矩阵，分别判断是否为幻方，另一部分则是生成一个幻方写入到一个新的文本中。在读取时，用for循环分别将字符1到5拼入地址中，输出同理。其中在生成幻方之前，判断n的合法性。

3.1.1isLegalMabicSquare()
该函数要实现判断一个矩阵是否为幻方。
1.读入文件
1.1创建FileReader、BufferReader、StringBuilder对象
1.2初始化line

2.逐行将字符串转换为整型矩阵存储
将头尾空格去除后转换为数字存储到二维数组中，之后对数组进行判错，最后则判断行列长度是否相等。

3.计算两条斜线的和并比较
计算两条对角线的和，进行比较，相等记录为基准值，不等则报错。

4.计算每条纵线和横线和和并比较
计算每行每列的和，并且分别和基准值进行判断，不等报错。

5.确定是否为幻方，是输出true，不是则输出false
3.1.2generateMagicSquare()
该函数目的是要求生成一个边长为奇数的幻方，使Row = 0，Col = n/2，之后进行不断循环对矩阵进行填充，将矩阵的[row,col]位置填充为i，i++，使其满足幻方的要求。

3.2Turtle Graphics
P2要求我们在clone已有的程序的前提下，对此程序进行修改，使其按照要求画图，其中需要利用一定的几何知识，并且将这些知识设计成相应的编程语言，使其实现。
最后，按照每个人自己的想法进行Person Art，即进行自己设计的画图。
3.2.1Problem 1: Clone and import
1.获取代码：
根据老师提供的任务代码地址，上网查找，将老师提供的代码下载到桌面上。
2.本地创建git仓库
在eclipse中打开git视图
Window -> Perspective -> Other Perspective -> Other…
Git -> Open
之后在git窗口点击Clone a Git Repository…
填写URL及相关信息后选择目标地址，建立文件夹到桌面
效果：

3.2.2Problem 3: Turtle graphics and drawSquare
该函数需要实现：根据已知边长画出指定的正方形。参数是turtle和sidelength。
首先设置画笔颜色为黑色。然后执行4次前进sidelength长度，同时每次转过90度，即可完成次正方形。
如图：

3.2.3Problem 5: Drawing polygons
该问题首先希望已知正多边形边数的情况下计算正多边形的内角度。根据几何知识可以推导得公式：
(double)180.0−(double)360.0/sides (double) 180.0 - (double) 360.0 / sides(double)180.0−(double)360.0/sides
使用该公式，实现calculateRegularPolygonAngle，通过运行TurtleSoupTest中的Junit测试得：

该问题还希望已知正多变型得边数和边长画出一个正多边形。参照画正方形的方法，可以先前进sidelength，再使海龟旋转一个角度，执行“边数”次。其中，这个角度是正多边形内角的补角，利用calculateRegularPolygonAngle的功能计算出多边形内角，再用180°减去这个值即可。边长为100的正六边形效果如下：

3.2.4Problem 6: Calculating Bearings
该问题首先希望解决，已知起点和当前朝向角度，想知道到终点需要转动的角度。例如，如果海龟在（0，1）朝向 30 度，并且必须到达（0，0）它必须再转动 150 度。
1.首先使用Math.atan2函数计算两点之间的边在坐标系的角度，减去当前朝向的角度；
2.然后取相反数（海龟旋转的方向是顺时针，坐标轴角度的旋转角度的逆时针）；
3.再减去90°（海龟的0°线是向上，坐标轴的0°线是向右，向右到向上要逆时针旋转90°）；
4.最后调整为0-360°之间（可能大于360°或小于0°）。

基于上一个问题，此时有若干个点，想知道从第一个点开始到第二个点，再从第二个点到第三个点……以此类推每次转向的角度。
1.将“起点”选为第一个点（坐标为(xCoords.get(0),yCoords.get(0))）；
2.循环n-1次（n为点的个数）
3.每次将第i+1号点设置为“终点”，通过上一个函数计算旋转角度并存储到List中；
4.将下一次的“起点”用当前“终点”更新，继续循环；
5.退出循环后返回List。

3.2.5Problem 7: Convex Hulls
算法描述：
1.我们发现任意凸包上的点，你会发现以该点建立一个极角坐标系，该点连结其它所有点的极角中，该点逆时针方向的第一凸包点到该点极角最小，例如P0，到所有点的极角中P0P1极角最小。
2.算法中首先找到最左边的点，这个点必然在凸包上，然后计算该点连接点极角最小的，这里计算有技巧，算法中进行toright测试,直到找到到最右端的点，找到P1后，就可以从P1开始，接着顺次找到P2，又以P2为起点……
时间复杂度：
因为每次的起点都是上次找到的凸包点，因此外层循环的复杂度为O(H)，H为凸包上的点，内层循环每次都会全部遍历点，因此时间复杂度为 O(n) ,因此总的是间复杂度为 O(nH) ,在一般情况下 凸包上的点的期望为logn ，算法复杂度为 O(nlogn) ,极端情况下，如下所示，所有点都在类似圆弧上的话，外层循环也是n，因此会达到O(n^2)。

3.2.6Problem 8: Personal art
想法：在画正多边形的基础上，步长不是一直相同，而是越来越长，并且角度比画正多边形需要的角度多一些，每次拐弯都需要变换颜色。
Size是螺旋的大小
Step的每一步的长度，每走一步拐弯一次
Densi是密度，角度越小，螺旋越密
ColorNum是色彩的数量，更改时要在switch里更改

3.2.7Submitting
如何通过Git提交当前版本到GitHub上你的Lab1仓库。
1.打开Git Bash
2.打开文件所在目录
3.输入git init初始化

4.添加远程仓库URL

5.添加上传文件

6.利用git status查看状态

7.添加修改日志

8. git push
   3.3Social Network
   该任务要求设计一张社交网络图，基于连接人与人，并且能计算任意两人之间的联系情况。网络图基于两个类，分别是FriendshipGraph类和Person类。
   3.3.1设计/实现FriendshipGraph类
   该类的实际意义是一张社交网络图，包括了代表每个Person的点、代表每两个Person之间联系的边、以及建立点和联系和计算距离的方法。
   1.邻接表存储结构
   2.Class Node
   Node类要实现的是将一个Person转换为邻接表里的点，所以一个Node有邻接表中点的重要成员变量：下一个Node为next，对应的Person对象person，直接连接的边lastEdge，以及实现邻接表的相关方法。此外，为了能实现方法getDistance，另外增设了vis和dis两个变量用来记录是否访问过以及与当前起点的最近距离。

Class Node.Edge
该类是邻接表中的边，每个Edge对象存储了邻接表中的下一条边，以及对应的边的两个Person所对应的Node。
Method Node.LoadData
该方法将Person对象导入到Node中进行存储，需要的时候可以直接调用。
Method Node.addNode
该方法将相应的Node加入到Node的链表中（即邻接表图中的纵向链表）。
Method Node.addNodeEdge
该方法将新的边加入到对应的Node中，更新每个Node后的Edge链表。
3.Method addVertex()
该方法目标是在社交网络图中增加一个新的节点，参数是要加入的Person类。首先，方法要对Person的名字进行判重：用哈希集合HashSet记录下已加入的所有Person的名字，每当新加入一个Person则进行判断是否在集合中；然后则新建一个Node类，使每一个Person与一个Node对应起来。
4.Method addEdge()
该方法目标是将两个Person之间进行联系，在邻接表中，用有向边来代表“有社交关系”，由于题目设定是社交默认为双向，则需要在函数中两次调用Node中的addNodeEdge方法加两个方向的边。考虑到可扩展性和可复用性，程序考虑到了“单向社交的情况”，仅需将双向加边中的“B->A”删除即可。
5.Method getDistance()
该方法要求计算任意两个Person之间的距离，若没有任何社交关系则输出“-1”。两个Person之间计算使用BFS；默认边权为1，则在搜索到边时加1即可，搜索到目标点则立即退出；特殊情况根据要求输出0或-1。
3.3.2设计/实现Person类
该类的目的是为了将每一个人对应到一个Person对象，并储存名字的信息。此外，为了方便，可以将每个Person对象在FriendshipGraph中对应的Node储存在对应Person的成员变量中。

3.3.3设计/实现客户端代码main()
1.重复名字错误测试

2.简单图测试

3.复杂图测试

3.3.4设计/实现测试用例
1.名字重复错误测试
测试当有重复名字“a”时，程序是否能停止
2.简单图测试

分别测试：
1.Rachel和Ross距离是1，Rachel和Ben距离为2
2.Rachel和Rachel距离为0
3.Rachel和Kramer距离为-1
3.复杂图测试

分别测试：
1.AE距离为2，AD距离为1，AG距离为3，BF距离为3，DF距离为2，HJ距离为2
2.II距离为0
3.DJ距离为-1，CI距离为-1，FH距离为-1
4.JUnit测试结果