Berkeley CS 61B Data Structures(in Java) Homework5 加分+讨论帖

打卡hw5，因为各种事情好久没来学了，也就不贴图了。大概说一说总结，其实感觉自己遇到的问题反而有点不太一样，我感觉hw5最难的还是多态的理解。DListNode.insertAfter()等操作中需要新建节点使用newNode，而且作业明确提示了用myList.newNode(),这里我想了很长很长时间,首先myList是List类型，List类型没有newNode方法，因此即便用(DList)myList来强制向下转型是不能调用newNode方法的，所以只有一种可能那就是myList的本质就是DList类型，这个我就很费解，之前只有一位层主提起过这件事，说是在构造方法中myList的本质已经是DList了，然后我找到了构造方法，它位于DListNode.java中，但是这个方法不是不用吗？我们不是应该去用DList里面的构造方法吗？所以不明白“myList的本质就是DList”从哪里可以体现出来？；另一个问题就是Comparable的多态问题，首先Comparable继承了Object，一切皆对象，但是Object本身没有compareTo方法，那么这样的话加上Comparable的cast同样不能调用compareTo方法，所以问题在哪里呢？在每次插入元素的时候都插入了Integer这样的包装类，然后Integer都向上转为Object类，因此(Comparable)(currentnode.item())其实就是“本质为Integer的Comparable类型，而包装类都实现了compareTo方法，因此是ok的，同样insert(Comparable c)中的传入参数c也是本质为Integer的Comparable类，因此才可以使用compareTo方法；继承有多态，接口也有多态，但是myList为什么可以调用newNode方法我还是不明白；
然后后面的union和intersect倒是没有遇到很多难题，反正就是觉得链表的归并排序比数组的归并排序似乎更好实现。
这次作业估计以后还得过几遍，感觉还是有不少内容没有吃透，，，现在要加速了，hw6走起啊！！！

附上截图，重点在于set里面函数的implementation。

先说DList：
1、protected的作用：protected DListNode newNode        
//这里是直接访问数据结构，外面封装一层函数，其他函数要new 的话就访问函数，不要再直接访问(new)数据结构了 //【注意这里是protected！只方便与package内的其他函数使用，所以Set作为外部class不能访问这个函数，只能访问下面是Public的函数！】


2、为什么要把insertAfter()等函数放在ListNode而不是List中了？
        一般来说，直接改变数据结构的method就放在数据结构的那个class里
        //如果是以前，我们需要调用的时候会写 list.insertAfter(item,node);
        //如果list中没有那个node呢？？？
        //所以要直接改变数据结构的函数放在这个数据结构node里面，调用时写node.insertAfter(item);
        // 就不需要判断是否这个node在这个list里面了。因为调用函数不用知道它的list了！

3、关于ListNode中List myList这个field
//之前List里有ListNode head的field，现在ListNode反过来有一个List的field，即myList，指向对应的List class，这样就清楚地规定了node在哪个List中
// 注意是父类（List），使用时转为子类（DList/SList）先

再说Set (集合) class
1、关于它的field：protected List setList;
//集合中用的数据结构为父类中的纯虚函数List
//这里就体现出为什么要有纯虚函数List了
// 由于纯虚函数没有构造器，所以作者想让你在这步选择是DList还是SList
        //【如果你哪天想改成SList，只要改这一处就好了！】
        //【这就是纯虚函数 和 设计elegant的接口的目的！】

2、明确set作为外部函数，调用数据结构（List和ListNode）只能用它的【Public】interface且不能随意改变里面的field，只能按照interface的规定来
例如：public int cardinality() {

        // Set作为package外部函数，不能直接访问【setlist.size】！！
        //看回List class里 size是protected声明

        return setList.length(); //这就是为什么要加length（）函数的原因。这个函数就是一个elegant的接口
    }

但是，不能改变返回length（）的值。
例如：temp.insertBefore(c); //这里面已经有size++了
                        //事实上，如果你输入setList.length()++;会报错
                        // 因为我们建立接口是只读状态（不能改变return的值）
                        // 这就防止了直接引用数据结构造成的corruption

3、关于comparable接口
Comparable c；
c.compareTo(temp.item()）成立

      //你真正传进去的item是Integer，Integer implement了Comparable
        // 同时Inherent了Object，所以Integer可以作为item传入ListNode
        // 这个时候item就具有了使用compareTo的特性，可以强制转为Comparable，然后使用compareTo

4、Union（并集）算法简介：
注意改变的是this而不是括号里的参数s

            ListNode thistemp = this.setList.front();  //如果setList里面一个node都没有，就不能输入这两行
            ListNode temp = s.setList.front();

    //由于两个set都是sorted的，所以第一个thistemp和第一个temp比，比thistemp大，下一个thistemp
        //若等于，输出中文字符，下一个thistemp
        //若小于，那就是temp是没见过的，把它中的【item】作为new出来的node中的item插入this里面，下一个temp
        //【没有重置thistemp！】比过的就不倒车了

同时注意边界条件：空集，两个集合元素数量不同的情况：
例如：ListNode current = this.setList.front(); //如果set集合为空，就不能用这句！
// 因为head是不可以访问的（head的mylist为null）

5、Intersection（交集）算法简介：
注意改变的是this而不是括号里的参数s

            ListNode thistemp = this.setList.front(); //如果setList里面一个node都没有，就不能输入这两行
            ListNode temp = s.setList.front();

和上面相反，看这俩元素有没有相同的，如果有保留thistemp，没有的删除

同时注意边界条件：空集，两个集合元素数量不同的情况，同上。

附上截图：

重点在于Set.java 里面的实现是利用了链表这个结构实现的，在这个基础上保证：元素从小到大排列，不能有重复的元素，可进行并集交集插入等运算。

先说链表数据结构的优化：
1、myList的作用
之前List里面有一个ListNode head，指向对应的Node；现在在Node里面也有一个List myList的field，引用回对应的List，这样的好处是防止这个ListNode与List不对应的情况。
其次，如果我们删除一个Node，实际上还是会访问到它，所以现在remove（）时使这个node的myList=null;  如果其他method要调用这个Node，会throws一个InvalidNodeException

【注意】双向链表里面的sentinel也是invalid的，它的myList也是null。这样我们就可以保证head这个对外是访问不到的。也保证了当没有head时（例如单向链表）我们不用改变一些method的implementation（就是说如果一些method用到了sentinel，当换成SList还得改，不用sentinel就不用改）。我们在做implementation时也要时刻注意链表头尾的访问不要越界，非常容易出错
例如：setList.next().prev(); 如果ListNode到头了，setList.next()返回的就是head，那它的prev()就会throw Exception，不仔细检查真的很难发现！

2、Protected的作用：
protected DListNode newNode(Object item, DList list, DListNode prev, DListNode next) {//这里是外面封装的函数
        return new DListNode(item, list, prev, next);                                                                //这里直接访问了数据结构
}
        //这里是直接访问数据结构，外面封装一层函数，其他函数（在package内的）要new 的话就访问函数，不要再直接访问(new)数据结构了
        //【注意这里是protected！所以Set不能访问这个函数，只能访问下面是Public的函数（只要Public函数才是对【外】的接口）

3、改变数据结构的method放在哪里好呢？
一般直接放在能直接访问数据结构的那个class里（见homework05 的readme）
例如：ListNode里面经常放一些可以【直接】修改数据结构的方法

        //如果是以前，我们需要调用的时候会写 list.insertAfter(item,node);
        //如果list中没有那个node呢？？？
        //所以要直接改变数据结构的函数放在这个数据结构node里面，比如我们将remove（）这个方法放在ListNode而不是List里面：调用时写node.insertAfter(item);
        // 就不需要判断是否这个node在这个list里面了。因为调用函数不用知道它的list了！

Set（集合）作为外部调用链表的类，一些关键点和算法：
1、Set中用的数据结构，或称field为父类中的纯虚函数List setList; ，它的子类分别为单向链表和双向链表
由于纯虚函数没有构造器，所以在Set（）构造器的时候选择是DList还是SList
        //【如果你哪天想改成SList，只要该这一处就好了】
        // 要尽量保证单向链表和双向链表的接口一样，做法就是将它们统一写一个父类纯虚函数，只有声明没有implementation，让子类去继承，从而有不同的实现！
        【这就是纯虚函数 和 elegant的接口的目的！！】

2、接口的隐私性再次强调
         // Set作为package外部函数，不能直接访问setlist.size！！
        //看回List class里 size是protected声明
所以，要访问size，要用setList.length(), length就是访问size的接口。
最重要的是，避免了size的改变，如果编写length（）++；是错误的。不能改变return的值，只能读取。

3、Comparable 接口
Comparable c;
c.compareTo(temp.item()) 成立

如果要用这个接口，需要cast一下，例如((Comparable) temp.item()).conparableTo.(c); 也是成立的
         //真正传进去的item是Integer，Integer implement了Comparable
        // 同时Inherent了Object，所以Integer可以作为item传入ListNode
        // 这个时候item就具有了使用compareTo的特性，可以强制转为Comparable，然后使用compareTo。

4、Union（求并集）的算法

            ListNode thistemp = this.setList.front();  //如果setList里面一个node都没有，就不能输入这两行，所以空集要单独讨论
            ListNode temp = s.setList.front();

        //由于两个set都是sorted的，所以第一个thistemp和第一个temp比，比thistemp大，下一个thistemp
        //若等于，输出中文字符，下一个thistemp
        //若小于，那就是temp是没见过的，把它中的【item】作为new出来的node中的item插入this里面，下一个temp
        //【没有重置thistemp！】比过的就不倒车了

注意特殊情况：空集，两个集合元素数量不同的情况

最后改变的是this.的元素，而传入的参数（括号里的）set 不变化

5、Intersection（求交集）的算法
和上面相反，看这俩元素有没有相同的，如果有保留thistemp，没有的删除

注意特殊情况：空集，两个集合元素数量不同的情况

最后改变的是this.的元素，而传入的参数（括号里的）set 不变化

做hw5收获最大的是对comparable interface有了更多的了解，也纠正了自己之前对于java数据类型的不正确理解。
当时最大的疑问是，为什么set java用到了compareTo（）这个comparable的方法，但是不需要implement Comparable？
我们都知道，Comparable是一个interface，可以implement后进行改写。
object根类是没有compareTo（）这个method的（这也解释了为什么需要将item进行comparable 强制转换），但目前已知的Boolean，Character，Integer，Float都已经实现了这个方法。
具体哪些类实现了compareTo（）方法可查：https://docs.oracle.com/javase/7 ... ang/Comparable.html。

所以在set java主函数中，s.insert(new Integer(3))这行代码做的事情是：
//生成一个integer的instance（直至这里我才知道了integer是int的包装类，不是一回事。。）
//这个integer class的对象调用了自己class 里的compareTo（） method来进行比较。
//调用他的是integer，那么自然set是不需要implement Comparable的。

那什么时候set 需要implement Comparable？
我们需要新创造一个method用于比较两个set的逻辑关系时候，才需要implement Comparable，并且自己重新写compareTo。

这里也顺便说以下equals和compareTo的区别之一，equals（）是object类的方法，所以基本上都可以使用，compareTo只有implement Comparable这个接口的类才能够使用。

学这门课最大的心得是，做完了练习再回过去多问自己一些 为什么？才发现之前可能只是似懂非懂。

交作业part II 增加了invalid node的测试

这个作业写的我累死了 每一个都不对 debug到了List package 里
test里是隐式调用了tostring 所以一开始我全都打印不出来
后来发现这个问题之后就很顺利了