一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 5782|回复: 168
收起左侧

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

  [复制链接] |试试Instant~ |关注本帖
jaly50 发表于 2014-6-8 20:02:44 | 显示全部楼层 |阅读模式

[其他]CS 61B Data Structures(in Java) #1 - 2014-06-08@Berkeley

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 jaly50 于 2014-6-8 20:04 编辑

作业入口:http://www.cs.berkeley.edu/~jrs/61b/hw/hw5/

虽然不难,但又一次写了很久...TAT

我不明白的是interface Comparable里明明没有declare compareTo的内容...为什么我们就可以直接用了?!!!

作业的知识点主要就是:package, interface,linkedList, inheritance,exception

我的Set.java和DList.java的输出如下:

hw5_set

hw5_set

hw5_DList

hw5_DList




相关链接:      

       【公开课讨论+加分总贴】:UC Berkeley CS 61B Data Structures(in Java)
       【课程网站】:http://www.cs.berkeley.edu/~jrs/61b/
       【视频网站】:【Youtube】【Youku

        【教材】:Head First Java 【中文版】【英文版
                      Data Structures and Algorithms in Java, 5th Edition. 【英文版


评分

1

查看全部评分

caominki 发表于 2016-4-11 17:29:22 | 显示全部楼层
收获
0、Set.java 与package list真正体现了protected不作用于package之外。Set.java只能调用list中声明的public函数来调用相关信息。对于set来讲,set看不到list内部数据结构的实现形式:DList或者SList。
1、封装:ListNode加入了List类型的field,使两个class更加紧密的耦合在一起,避免错误的调用外部节点。同样的,这些信息在Set看来,都是隐藏于list之内的。list向外呈现的只有:
inEmpty();length();insertFront();insertBack();front();back();/isValidNode();item();setItem();prev();next(); insertAfter(); insertBefore(); remove();
2、注意方法的归属要准确。
ListNode类:【isValidNode();item();setItem();prev();next(); insertAfter(); insertBefore(); remove();】
List类:【inEmpty();length();insertFront();insertBack();front();back();】
3、接口可以用来引用实现这个接口的对象,这也是接口的意义所在,如Comparable接口。始终注意:“可以引用”不等于“可以调用对象所有属性与方法”----接口的遥控按钮与对象所属类的遥控按钮不一致。
4、Set类的intersection()函数花了很长时间。原因在于:本质算法没有一步一步的清晰搞懂,只靠模糊的思想写出来的程序必定会有bug!
如:set1与set2求intersection时(升序),思想:set2的每一个元素与set1的元素进行比较,只要比set1元素大,则set1的这个元素删除,同时继续与set1的下一个元素比较,直到不满足set2的这个元素大于set1的元素的情况。这种情况又有2中子情况:==或者<。“==”的时候删除set1的这个元素,set2的元素插入set1后边;“<”的时候set2的下一个元素与该元素进行比较,重复前边操作。注意点:为了防止访问invalidnode,分别对set1与set2的最后一个点进行单独处理,则加入while控制条件,使最后一个点不进入循环体(j>1 / i>1),则在循环体外检查并操作j==1/i==1的情况。j==1时,有3种情况:< 、==、 >。分别讨论。
5、在调用对象函数前,注意检查是否valid,用if来判断。这之后才能调用相关函数。
6、外部类Set使用DList时,最好用DList的父类类型List声明,以免后期需要使用List的其他子类,如SList类。
7、类DList需要用DListNode()构造函数来创建新节点时候,避免直接使用DListNode(),而是创建方法method newNode(),在方法中返回DListNode()。这样后期需要使用其他节点类型:如SListNode时候,不需要对DList类中换掉所有DListNode(),只需要在方法newNode中,返回SListNode()即可。
8、注意Exception的使用。try-catch-finally或者throw exception
更多图片 小图 大图
组图打开中,请稍候......

评分

1

查看全部评分

回复 支持 2 反对 0

使用道具 举报

gocong 发表于 2016-1-14 07:48:05 | 显示全部楼层
gocong 发表于 2016-1-9 05:10
您好,part II 我有个疑问。 set()构造函数怎么初始化呢? 我看了看github上code, 都是 new DList() ...

好吧,我来自己回答吧,做完以后,我发现,List没有构造函数的原因就是作者想让你在这步来决定你用哪个List;所以如果你在这用new SList(), 那么set就是用SList完成的,用DList就是用DList完成的,但是对于用Set的人完全没影响,他不在乎你真正实现的是SList还是DList。这是你自己选择用List实现了算法的优化。如果有新的developer想用一个更好的List结构,他要做的就是创造一个新的List和ListNode ADT,然后在Set构造函数中引用new 新List();
回复 支持 2 反对 0

使用道具 举报

althinking 发表于 2015-7-17 13:22:14 | 显示全部楼层
本帖最后由 althinking 于 2015-7-17 13:25 编辑

Homework 5Part 1
Screenshot from 2015-07-15 11:27:03.png
Part 2
Screenshot from 2015-07-17 13:10:38.png

part 2的intersect()要考虑多种边界条件。比如空集的情况;s1.intersect(s2)时,s2触发了exception,s1能不能继续把剩下的元素删掉。
下面是我的test cases,抛砖引玉。
  1.   public static void main(String[] argv) {
  2.     System.out.println("Testing insert()");
  3.     Set s = new Set();
  4.     s.insert(new Integer(3));
  5.     s.insert(new Integer(4));
  6.     s.insert(new Integer(3));
  7.     System.out.println("Set s should be { 3 4 }: " + s);

  8.     Set s2 = new Set();
  9.     s2.insert(new Integer(4));
  10.     s2.insert(new Integer(5));
  11.     s2.insert(new Integer(5));
  12.     System.out.println("Set s2 should be { 4 5 }: " + s2);

  13.     Set s3 = new Set();
  14.     s3.insert(new Integer(5));
  15.     s3.insert(new Integer(3));
  16.     s3.insert(new Integer(8));
  17.     System.out.println("Set s3 should be { 3 5 8 }: " + s3);

  18.     System.out.println();
  19.     System.out.println("Tesing union()");
  20.     s.union(s2);
  21.     System.out.println("After s.union(s2), s should be { 3 4 5 }: " + s);
  22.     s2.union(s3);
  23.     System.out.println("After s2.union(s3), s2 should be { 3 4 5 8 }: " + s2);
  24.     Set s4 = new Set();
  25.     System.out.println("Empty set s4 = " + s4);
  26.     s.union(s4);
  27.     System.out.println("After s.union(s4), s should be { 3 4 5 }: " + s);
  28.     s4.union(s);
  29.     System.out.println("After s4.union(s), s4 should be { 3 4 5 }: " + s4);

  30.     System.out.println();
  31.     System.out.println("Tesing intersect()");
  32.     Set s5 = new Set();
  33.     Set s6 = new Set();
  34.     s6.insert(new Integer(1));
  35.     s5.intersect(s6);
  36.     System.out.println("{}.intersect({1}) should be { }: " + s5);
  37.     s6.intersect(s5);
  38.     System.out.println("{1}.intersect({}) should be { }: " + s6);
  39.     s6.insert(new Integer(1));
  40.     Set s7 = new Set();
  41.     s7.insert(new Integer(1));
  42.     s7.insert(new Integer(2));
  43.     s6.intersect(s7);
  44.     System.out.println("{1}.intersect({1 2}) should be { 1 }: " + s6);
  45.     s6.insert(new Integer(2));
  46.     s6.insert(new Integer(3));
  47.     s6.intersect(s7);
  48.     System.out.println("{1 2 3}.intersect({1 2}) should be { 1 2 }: " + s6);
  49.     s6.insert(new Integer(3));
  50.     s6.insert(new Integer(5));
  51.     s7.insert(new Integer(4));
  52.     s7.insert(new Integer(7));
  53.     s7.intersect(s6);
  54.     System.out.println("{1 2 4 7}.intersect({1 2 3 5}) should be { 1 2 }: " + s7);

  55.     System.out.println();
  56.     System.out.println("Tesing cardinality()");
  57.     System.out.println("s.cardinality() should be 3: " + s.cardinality());
  58.     System.out.println("s4.cardinality() should be 3: " + s4.cardinality());
  59.     System.out.println("s5.cardinality() should be 0: " + s5.cardinality());
  60.     System.out.println("s6.cardinality() should be 4: " + s6.cardinality());
  61.     System.out.println("s7.cardinality() should be 2: " + s7.cardinality());
  62.   }
复制代码

评分

3

查看全部评分

回复 支持 2 反对 0

使用道具 举报

amyzen 发表于 2015-5-12 03:51:01 | 显示全部楼层
终于做完了,有两个难点,卡了好久:1.发现各种protected的 prev, head等都不能用,开始用next(),item()等方法都不习惯
2.时间复杂度要求是相加的关系,就不可以简单的调用insert()方法遍历this了


sort()可以实现相加的复杂度要求,但用sort()方前,还在DListnode写了实现comparable()接口,还是各种generics报错。。。。
后来union那考虑到s和this都已经是排好序的额,所以直接从s的list的front()开始比大小,插到合适位置后,再移到s的下一位时就不需要比较this中已比较过的那些节点了,所以复杂度可以达到相加关系,还是学到很多~~~

另外还有学到了comparable也是种可以cast的类型

HW5.1.1.png HW5.1.2.png HW5.1.3.png

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

zj45499 发表于 2015-1-9 13:52:17 | 显示全部楼层
增加几个空集的Test Case
  1.         Set s4 = new Set();
  2.         System.out.println("Empty Set s4 = " + s4);
  3.         
  4.         System.out.println("s4.cardinality() = " + s4.cardinality());
  5.         
  6.         s4.union(s4);
  7.         System.out.println("After s4.union(s4), s4 = " + s4);

  8.         s4.intersect(s4);
  9.         System.out.println("After s4.intersect(s4), s4 = " + s4);

  10.         s3.union(s4);
  11.         System.out.println("After s3.union(s4), s3 = " + s3);

  12.         s3.intersect(s4);
  13.         System.out.println("After s3.intersect(s4), s3 = " + s3);
复制代码
Screen Shot 2015-01-08 at 9.53.41 PM.jpg
Screen Shot 2015-01-09 at 1.34.00 PM.jpg


评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

windforce 发表于 2014-6-30 06:46:37 | 显示全部楼层
melissami 发表于 2014-6-28 22:54
你的测试好详细,赞!
不知道是否方便分享一下你的测试代码,我也想测试一下自己哪些细节不够完善
谢谢 ...

其实就是在自带test code 加了个空集的情况,没插入任何数据,直接进行intersect 和 union的测试。

我也不清楚这样算不算完备。 我自己之前的代码对空集的处理有点问题(明明空集交非空集应该为空,我之前运行时会莫名其妙多出一个数据),后来改过来了。
回复 支持 1 反对 0

使用道具 举报

Linzertorte 发表于 2014-6-9 08:53:57 | 显示全部楼层
不知道具体 内容。但是许多基本的class, compareTo都是有定义的。你inherit了而且 。
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2014-6-9 08:56:00 | 显示全部楼层
http://docs.oracle.com/javase/7/docs/api/java/lang/String.html

比如说String
All Implemented Interfaces:
Serializable, CharSequence, Comparable<String>
回复 支持 反对

使用道具 举报

joranson 发表于 2014-6-9 15:24:49 | 显示全部楼层
compareTo 是从Object里继承下来的
回复 支持 反对

使用道具 举报

windforce 发表于 2014-6-21 09:56:40 | 显示全部楼层
这个homework我也写了很久。 主要有两点,一个是对接口的 raw type 和 generic type还是没真正掌握
这次作业里我没用泛型,而是用的(Comparable)currentNode.item()).compareTo(c) 这种表达式,也能运行。。。

还有就是Set测试时对涉及空集的case,我改了很久才通过。光用作业里提供的测试数据我还真可能发现不了自己写的方法的缺陷
更多图片 小图 大图
组图打开中,请稍候......

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

melissami 发表于 2014-6-28 22:52:53 | 显示全部楼层
本帖最后由 melissami 于 2014-6-28 10:46 编辑

这次作业也改了很长时间,感觉这门课越来越难了,怎么破
在intersect的时候,为了不超过复杂度,想了很多种方法,代码越写越长,但其实最后真正运行成功的很短
union的时候,还因为一个低级错误,传入参数set s循环的时候,我忘记了写s.head,直接写head,然后陷入死循环,好长时间才找到错误
Part I partI-1.gif


partI-2.gif



Part II
hw5.jpg


评分

1

查看全部评分

回复 支持 反对

使用道具 举报

melissami 发表于 2014-6-28 22:54:20 | 显示全部楼层
windforce 发表于 2014-6-20 20:56
这个homework我也写了很久。 主要有两点,一个是对接口的 raw type 和 generic type还是没真正掌握
这次 ...

你的测试好详细,赞!
不知道是否方便分享一下你的测试代码,我也想测试一下自己哪些细节不够完善
谢谢~
回复 支持 反对

使用道具 举报

melissami 发表于 2014-7-3 23:33:03 | 显示全部楼层
话说lz开始写project2了吗,这个要求2-3个人的小组要怎么做,一个人亚历山大啊:/
回复 支持 反对

使用道具 举报

marshallou 发表于 2014-7-9 12:31:18 | 显示全部楼层
我也做了好久。。
更多图片 小图 大图
组图打开中,请稍候......

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

gougou9901 发表于 2014-7-10 23:04:15 | 显示全部楼层
hw5交作业    求学分~~
更多图片 小图 大图
组图打开中,请稍候......

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

krist 发表于 2014-7-17 17:15:09 | 显示全部楼层
回复 支持 反对

使用道具 举报

逃亡~ 发表于 2014-9-17 09:46:22 | 显示全部楼层
joranson 发表于 2014-6-9 15:24
compareTo 是从Object里继承下来的

Object没有implement Comparable。

真正能用compareTo的原因是,你真正传进去的是Integer,Integer implement了Comparable,同时Inherent了Object,所以Integer可以作为item传入ListNode,这个时候item就具有了使用compareTo的特性,可以强制转为Comparable,然后使用compareTo。
回复 支持 反对

使用道具 举报

逃亡~ 发表于 2014-9-17 09:46:52 | 显示全部楼层
windforce 发表于 2014-6-21 09:56
这个homework我也写了很久。 主要有两点,一个是对接口的 raw type 和 generic type还是没真正掌握
这次 ...

这次作业没让使用泛型吧
回复 支持 反对

使用道具 举报

joranson 发表于 2014-9-17 12:51:14 | 显示全部楼层
逃亡~ 发表于 2014-9-17 09:46
Object没有implement Comparable。

真正能用compareTo的原因是,你真正传进去的是Integer,Integer im ...

我不是说Object class。。。是泛指对象。。。每个Object都有compareTo method的。。。
回复 支持 反对

使用道具 举报

逃亡~ 发表于 2014-9-17 16:36:09 | 显示全部楼层
终于写完了,match时间复杂度实在是太恶心了
1.png 2.png 3.png 4.png

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

voiding 发表于 2014-9-24 06:46:41 | 显示全部楼层
谁能帮我看看往set里面 insert的code, 我觉得我写得太复杂了。可以运行出来结果,但是逻辑上好像太复杂。 setInsert.png
回复 支持 反对

使用道具 举报

voiding 发表于 2014-9-26 00:23:13 | 显示全部楼层
终于搞定了,hw主要学习到了protected key word的scope,还有comparable interface的用法,算法学习到了把two sorted set merge to one sorted list。继续努力!
更多图片 小图 大图
组图打开中,请稍候......

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

MCwong 发表于 2014-9-30 09:49:45 | 显示全部楼层
HW5 done,快开学了,坚持
屏幕快照 2014-09-29 18.16.10.png
屏幕快照 2014-09-29 18.47.09.png

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 06:50

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表