哈工大软件构造实验一_java

哈工大软件构造实验一
在今天终于完成了软件构造的实验，由于同时要进行计算机系统的实验以及准备形式语言的考试，所以这几天几乎是连轴转的状态。下面我来浅述以下软件构造这门课的实验一。
首先，总的来说，这次实验的难度不大，而用了这么时间来做这个实验的原因就在于，我对这次实验的一切都是不熟悉的。不熟悉Java，更不熟悉IDEA。所以一切都只得从头学习，但最后收获颇丰。这次实验一共有三个任务，前两个任务是来自MIT的，第三个任务是来自CMU的。从中也能看出我们的学校和这样的计算机学科世界顶尖的学校的差距吧。实验环境的配置过程我不再进行赘述，下面我说说实验中值得分享的东西。
首先第一个实验是MagicSquare（幻方），而我们要做的就是从文本中读取数据，检验是否是幻方，我认为整个实验最重要的就是判断输入的数据格式是否正确。在菜鸟教程上学到了利用正则表达式的方法，比直接硬来方便许多。我主要采取的方法就是把期望的符号都换成空串，这样符合要求的最后长度就是0，以此筛选出符合格式要求的串。具体就是把代表数字的\d，回车符\n，制表符\t还有.和-的闭包进行替换（还好这学期学了形式语言这门课），代码如下。

 public static boolean isLegalChar(String str) {
        if (str.replaceAll("-*\.*\d*\t*\n*", "").length() == 0) {
            return true;
        }
        System.out.println("Contain illegal char");
        return false;
    }

值得注意的是，与C语言的转义符不同，Java中\表示它本身的意思，\\才表示转义。
我认为这个任务最难的部分就在于这里了，剩下的只是计算行、列还有对角线的和。

第二个任务就是实现Turtle绘图，这个任务的GUI已经搭建好，主要就是熟悉一下JUnit测试，实际函数中比较难的是凸包算法，首先找到左下角的点，也就是找到 x 值和 y 值都最小的点，然后依次找到从当前点旋转角度最小到达的点，加入到返回 Set 中，再把找到的这个点当做当前点，直到所找到的下一个点与初始点相同。

public static Set<Point> convexHull(Set<Point> points) {
        //throw new RuntimeException("implement me!");
        if (points.size() < 3)//The number is less than three directly returned
            return points;
        Point[] spots = points.toArray(new Point[points.size()]);
        int temp = 0; //Saves the current bottom-right point
        for (int i = 1; i < spots.length; i++) {
            temp = spots[i].x() < spots[temp].x() ? i : temp;
            if (spots[i].x() == spots[temp].x()) {
                temp = spots[i].y() < spots[temp].y() ? i : temp;
            }
        }
        int bpoint = temp;
        Set<Point> result = new HashSet<Point>();
        result.add(spots[temp]);
        double mindegree = 0, mindegree1 = 360;
        int npoint = temp == 0 ? 1 : 0;
        while (bpoint != npoint) {
            for (int i = 0; i < spots.length; i++) {
                if (temp != i) {
                    double temp1 = calculateBearingToPoint(mindegree, (int)spots[temp].x(), (int)spots[temp].y(),
                            (int)spots[i].x(), (int)spots[i].y());
                    if (temp1 < mindegree1) {
                        npoint = i;
                        mindegree1 = temp1;
                    }
                }
            }
            mindegree += mindegree1;
            if (mindegree > 360) mindegree -= 360;
            result.add(spots[npoint]);
            temp = npoint;
            mindegree1 = 360;
        }
        return result;
    }

下面也分享一下我自己画出来的图吧。

public static void drawPersonalArt(Turtle turtle) {

        //throw new RuntimeException("implement me!");
        PenColor[] colors = new PenColor[6];
        colors[0] = PenColor.RED;
        colors[1] = PenColor.ORANGE;
        colors[2] = PenColor.YELLOW;
        colors[3] = PenColor.GREEN;
        colors[4] = PenColor.BLUE;
        colors[5] = PenColor.MAGENTA;
        for (int i = 1; i <= 30; i++) {
            for (int j = 0; j < 6; j++) {
                turtle.color(colors[j]);
                drawRegularPolygon(turtle, 3, i * 8);
                turtle.turn(60);
            }
        }
        for (int i = 30; i > 0; i--) {
            for (int j = 0; j < 6; j++) {
                turtle.color(colors[j]);
                drawRegularPolygon(turtle, 6, i * 4);
                turtle.turn(60);
            }
        }
    }

第三个任务是来自CMU的，创建社交网络，个人认为这个不像前两个那样有意思。最难的部分是实现一个广度优先算法，这里使用Map和Queue来实现，比C语言中手打方便的多。

public int getDistance(Person per1, Person per2) {
        if (per1.getThisName().equals(per2.getThisName())) {
            return 0;
        }
        else {
            Queue<Person> personQueue = new LinkedList<>();
            Map<Person, Integer> personIntegerMap = new HashMap<>(); //Save distance from everyone
            personQueue.offer(per1);
            personIntegerMap.put(per1, 0);
            int distance = 0;
            while (!personQueue.isEmpty()) { //Breadth-first search
                Person first = personQueue.poll();
                Set<Person> firstFriends = first.getFriends();
                for (Person i:firstFriends) {
                    if (!personIntegerMap.containsKey(i)) {
                        personQueue.offer(i);
                        personIntegerMap.put(i, distance + 1);
                        if (i.getThisName().equals(per2.getThisName())) {
                            return distance + 1;
                        }
                    }
                }
                distance ++;
            }
            return -1;
        }
    }