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

jy_121 发表于 2015-5-18 16:24
想问下两个List中的node应该如何比较大小啊？怎样转换object类型的item啊？谢谢了~

node比较大小我用的是compareTo（）和item（）方法
我当时是查了下comparable的文档http://docs.oracle.com/javase/7/docs/api/
其中有例子可以参考啦

amyzen 发表于 2015-5-19 10:25
node比较大小我用的是compareTo（）和item（）方法
我当时是查了下comparable的文档http://docs.oracle. ...

好的，谢谢啊，我去看一下。

总算做完了，感谢楼上同学的指导。以后编程时要先把思路理清，不能光靠后期调试。。。

先贴作业：

总结：
1. Comparable
Comparable是个接口，which extends Object，所以Object可以cast到Comparable，从而Object类型的item之间可以比较大小。
题目中main()给的是整数来测试，当然还可以用其他一些类型，因为java自己在这些常用类里面都有compareTo()的implementation。
如果是你自己的类(比如 MyClass item)，就需要你自己implements Comparable了，否则java按它的机制给的compareTo()不一定makes sense to you.

2. union 和 intersect的算法
两个sorted list合并，那就是merge sort的其中一步啊。merge sort是O(nlogn)的，每一步O(n)有若干个sorted sublist，每两个sublist的合并便和本题一样了。
具体来讲，可以maintain两个list的最小值；每次小中取小拎出来，然后更新这两个最小值；时间复杂度，也就是更新的次数，就是两者长度之和啦。
题目又要求不能复制node，所以小中取小“拎出来”，就变成了小中取消“决定是否插入this list”，当然更新还是一样的更新。
intersect()同理，只不过小中取小插入变成了小中取小删除。

PS：
这次图片好大，结果上传图片最大只能380KB...跪求斑竹加学分早日高级农民.....
另外还有我的project 1求加分～～～：
http://www.1point3acres.com/bbs/thread-99119-3-1.html

做完了，过程很久，对于概念没有深入理解，这次作业的内容老师上课时就给予了一定的提示和讲解，只怪当时学的不深入。。。我的收获是：
1，comparable 类型 cast，概念
2，抽象类不能实例化，但是能用作变量的静态类型，
3，sorted set 的 union 和intersect，
4，为了不论何种类型的list都能实现SET，创建添加节点时调用List或ListNode中抽象的method。
作业真的很值得做！

Homework 5终于弄完了

好久没写Java了，又生疏了。
这次作业感觉还好。碰到的问题有。
1. 如何在DListNode 中 使用 newNode()方法来生成结点。因为 myList 是 List类型的。不可能使用 DList的方法 newNode(). 但是后来发现myList的本质是DList。在构造器中已经实现了一次子类转超类。所以下面直接强制转换就可以使用 newNode 方法了。
2. 在使用 DListNode.next(); 方法时，需要在对应的方法上 throws Exception。  这个不知道算不算违背了题意，不知道允不允许改。但除了next还能用什么呢？用了next，自然就得抛出异常。所以这个问题我没能解决。希望有同学可以指点下。
3.之前听同学说这次作业用到了 Comparable。 但这个真的不是侧重于Comparable的定义啊。 之前看过了Comparable 和 Comparator的区别，并没有在这里体现出来。
还有，我每次使用 compareTo， 代码下面都有小黄线表示警告。
Type safety: The method compareTo(Object) belongs to the raw type Comparable. References to generic type Comparable<T> should be parameterized
谁能告诉我下，这个是哪里有问题吗？
还有，为什么会有 Comparable<T> 的形式。 这是干什么的？
还有个注意点。 假设比较时，代码如下。
ListNode setHead = s.setList.front();               
ListNode thisHead = this.setList.front();


if (((Comparable) tempSetHead.item).compareTo(temp.item) > 0)

之前疑惑为什么这里需要进行强制转换。后来想了下感觉有道理，不知道对不对。
tempSetHead 是 ListNode 类型的， item是他的成员，是 Object类型的。
当生成该结点时，传入的是 Integer类型。 但 用的是 Object来接收，其实已经完成了一次向上转型。
所以这里的item是 Objec类型的，但其本质是 Integer类型的。
但是上网查了下 Object里面的方法，

protected Object	clone()Creates and returns a copy of this object.
boolean	equals(Object obj)Indicates whether some other object is "equal to" this one.
protected void	finalize()Called by the garbage collector on an object when garbage collection determines that there are no more references to the object.
Class<?>	getClass()Returns the runtime class of this Object.
int	hashCode()Returns a hash code value for the object.
void	notify()Wakes up a single thread that is waiting on this object's monitor.
void	notifyAll()Wakes up all threads that are waiting on this object's monitor.
String	toString()Returns a string representation of the object.
void	wait()Causes the current thread to wait until another thread invokes the notify() method or the notifyAll() method for this object.
void	wait(long timeout)Causes the current thread to wait until either another thread invokes the notify() method or the notifyAll() method for this object, or a specified amount of time has elapsed.
void	wait(long timeout, int nanos)Causes the current thread to wait until another thread invokes the notify() method or the notifyAll() method for this object, or some other thread interrupts the current thread, or a certain amount of real time has elapsed.

果然没有compareTo.
所以虽然这个item的本质是Integer，但其类型确实Object，对Integer所包含的compareTo方法不可见。无法使用。因此需要进行强制转换。
这里又涉及到interface怎么可以接收对象。是可以的
接口作为引用类型来使用，任何实现该接口的类的实例都可以存储在该接口类型的变量中，通过这些变量可以访问类中所实现的接口中的方法，Java 运行时系统会动态地确定应该使用哪个类中的方法，实际上是调用相应的实现类的方法。（转载）


然后估计就是这么样的原理吧。
其他的感觉没什么好说的了。算法复杂度什么的稍微意会下就行了。另外 union 挺像是归并排序里面的那种感觉啊。
homework4 和 5 我的印象很深。写完了这两个作业，一个很明显的感受是。Java是一个等级十分严格的语言。最超类，万物之主就是Object，然后在一类类的往下走。十分十分严格。然后各个阶级之间的转换也是严格按照所定的规则进行的，很完美。
还有个问题， 动态规划（DP）貌似很重要，这玩样到底是什么。这次作业里面的 union 和 intersect 来操作两个链表融合算不算是 DP？ DP是不是就是专门用来处理链表或者数组的？在最小的复杂度下，完成我们对数组的操作，常见的方法就是设置一个 标志位数组？ 这个东西是不是就是DP？还是只是DP中的一个方面？
记录在此，以后有时间再来看。
两个有用的链接分享下。
http://www.weixueyuan.net/view/6009.html
http://fuxueliang.com/tech/2013/ ... omparable-tutorial/

忘了还有个问题。我之前看的是2006年的视频，后来发现2014版本的作业更好。那么，我现在是否可以看着2006的视频，做着2014的作业呢？会不会冲突？还是得都改成2014的？但2006的板书版本讲的真的很详细啊！

part1图片过大懒得压缩了。这个一般都是对的。所以我就不上传了。

ypandxy 发表于 2015-5-31 07:34
做完了，过程很久，对于概念没有深入理解，这次作业的内容老师上课时就给予了一定的提示和讲解，只怪当时学 ...

有个问题。 虽然我也知道 Comparable 可以强制转换Obeject然后使用compareTo方法。但是 Object本身是没有compareTo方法的啊？虽然他的本质是Integer类型，具有compareTo方法，那也应该对Integer类型进行强制转换？ 比如，  (Comparable) (Integer object) 虽然我知道这样一定是错的，但为什么对Object利用Comparable进行Cast后，就可以使用它自己都看不见的，隐藏起来的方法呢？

我是流氓我怕谁 发表于 2015-4-6 21:34
"Your Set class must use a List to store the elements of the set."

求问大神 能解释得再详细一些么？
谢谢！

czbnlzd920706 发表于 2015-6-13 00:51
好久没写Java了，又生疏了。
这次作业感觉还好。碰到的问题有。
1. 如何在DListNode 中 使用 newNode()方 ...

请问您后来是怎么把DList l这个值赋到每个node.myList上的？大概的思路什么样，因为不管是哪种insert，argument都不带mylist啊
我为了测试，厚颜无耻的在函数里直接新增这个对象然后赋值....