一亩三分地论坛

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

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

Berkeley CS 61B Data Structures(in Java) Lab3 讨论帖

  [复制链接] |试试Instant~ |关注本帖
jaly50 发表于 2014-5-31 00:22:50 | 显示全部楼层 |阅读模式

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

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

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

x
本帖最后由 jaly50 于 2014-5-31 11:41 编辑

lab3 和lab4都是看完第八课 链表 就可以写的
实验室里要求2个小时完成的,所以都比较简单
作业链接:http://www.cs.berkeley.edu/~jrs/61b/lab/lab3/

lab就不加分

大家还是可以上传作业 mark一下自己做过了
或者做作业有什么问题
可在此帖讨论

lab3

lab3




相关链接:      

       【公开课讨论+加分总贴】:UC Berkeley CS 61B Data Structures(in Java)
       【课程网站】: 【spring2014】【fall2006
       【视频网站】:【Youtube(fall2006)】【Youtube(spring2014)】【Youku(fall 2006)】

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

评分

1

查看全部评分

enirinth 发表于 2015-5-14 22:01:43 | 显示全部楼层
先贴图:
1111.png


题目意思好绕,constant time就好了,后面说了一堆record, representation之类的, 感觉不如直接说keep track of the tail。。。
要改的三个是:加一个instance variable (tail),insertFront(),  insertEnd();

人认为有两种实现带tail的linkedlist的思路:
1. head和tail指向的都是首末的有意义的node:
    优点:代码简洁,节约了两个node;
    缺点:insertFront()和insertEnd()里都要把tail==0拎出来单独讨论;
2. head和tail分别指的首末的无意义的(不存item)node,专门作首尾节点:
    优点:是课堂上讲的标准linkedlist结构
    缺点:代码稍微复杂一点,又因为是单向linkedlist,没有prev,所以尾node的next要往回指,容易弄错。。(事实上1中的node本身也是往回指的。。)

贴一下1的代码:
  1. public void insertFront(Object obj) {
  2.   head = new SListNode(obj, head);
  3.   if (tail == null){
  4.     tail = head;
  5.   }
  6.   size++;
  7. }

  8. public void insertEnd(Object obj) {
  9.   if (tail==null){
  10.     insertFront(obj);
  11.   } else {
  12.     tail.next = new SListNode(obj, null);
  13.     tail = tail.next;
  14.     size++;
  15.   }
  16. }
复制代码
2的代码就是把一些head和tail改成head.next和tail.next,然后不用分情况讨论了,略了;




回复 支持 2 反对 0

使用道具 举报

pirateshadow 发表于 2016-3-24 20:02:04 | 显示全部楼层
第一次忘了在insertFront()里面添加tail == null的情况,应该想到对称性的。
Screen Shot 2016-03-24 at 8.00.20 PM.png
回复 支持 1 反对 0

使用道具 举报

m32jo4 发表于 2014-5-31 11:08:09 | 显示全部楼层
there is something wrong with youtube link?
回复 支持 反对

使用道具 举报

朝仓音梦 发表于 2014-6-3 01:48:46 | 显示全部楼层
本帖最后由 朝仓音梦 于 2014-6-3 01:51 编辑

老师讲的
public void removeBack(){
head.prev=head.prev.prev;
head.prev.next=head;
size--;
}
没有错误吗?第三句 head.prev.next不是本来就是head?
觉得应该是
head.prev.prev.next=head;
回复 支持 反对

使用道具 举报

Musfanzy 发表于 2014-6-3 07:33:50 | 显示全部楼层
朝仓音梦 发表于 2014-6-3 01:48
老师讲的
public void removeBack(){
head.prev=head.prev.prev;

没有错误 因为已经把head.prev.prev 赋值给了 head.prev
第一句话是 从 后往前 建立链接
第二句话是 从 前往后 建立链接
回复 支持 反对

使用道具 举报

gloria_wwj 发表于 2014-6-12 22:48:20 | 显示全部楼层
字数字数字数字数!
Lab3.png
回复 支持 反对

使用道具 举报

galaxy2 发表于 2014-6-21 20:25:31 | 显示全部楼层
lab3.png
                                
lab3.png
回复 支持 反对

使用道具 举报

漫漫琳游的鱼 发表于 2014-6-28 13:50:15 | 显示全部楼层
QQ截图20140628134753.png insertEnd()方法的修改是不是添加一个结点时刻指向尾结点就可以了?
回复 支持 反对

使用道具 举报

ginrain 发表于 2014-6-28 23:44:46 | 显示全部楼层
回ls,
我是加了一个tail 然后在insertend和insertfront里做判断,为head == null时,tail = head = 新元素;当insertend不为null时候,把tail.next装上去,再更新tail;
QQ20140628-1.png
回复 支持 反对

使用道具 举报

dsqx71 发表于 2014-6-30 19:40:27 | 显示全部楼层
希望能坚持跟上。。。。。

lab3

lab3
回复 支持 反对

使用道具 举报

南方的狼 发表于 2014-8-9 16:38:19 | 显示全部楼层
晒一下答案~
result.jpg
回复 支持 反对

使用道具 举报

awksu 发表于 2014-8-13 17:07:45 | 显示全部楼层
lab3.png




回复 支持 反对

使用道具 举报

donal 发表于 2014-8-21 11:48:02 | 显示全部楼层
Lab比较easy
Lab3.PNG
回复 支持 反对

使用道具 举报

voiding 发表于 2014-9-5 06:01:13 | 显示全部楼层
lab3.jpg

回复 支持 反对

使用道具 举报

dwl1222 发表于 2014-9-9 10:44:36 | 显示全部楼层
加分加分叶
Lab3.PNG
回复 支持 反对

使用道具 举报

lvtongyun 发表于 2014-10-15 23:05:48 | 显示全部楼层
ginrain 发表于 2014-6-28 23:44
回ls,
我是加了一个tail 然后在insertend和insertfront里做判断,为head == null时,tail = head = 新元 ...

我是这样写的   public void insertEnd(Object obj) {
      if (head == null) {
      head = new SListNode(obj);
      tail = head;
    } else {
      tail.next = new SListNode(obj);
      tail = new SListNode(obj);
    }
    size++;
  }
为什么出现run-time error了呢?
回复 支持 反对

使用道具 举报

chendanlan 发表于 2014-11-14 11:09:52 | 显示全部楼层
lab3.PNG lab3 error.PNG

为什么我用eclipse能运行,用cmd不能运行阿?难道是三个class文件一起运行的问题吗?求解决方案。
回复 支持 反对

使用道具 举报

chendanlan 发表于 2014-11-14 11:11:49 | 显示全部楼层
lvtongyun 发表于 2014-10-15 23:05
我是这样写的   public void insertEnd(Object obj) {
      if (head == null) {
      head = new SL ...

accoding to online resource,
you should write like this,
if (tail == null){
                tail = new SListNode(obj);
                head=tail;
        }else{
        tail.next = new SListNode(obj);
        tail=tail.next;
        }
        size ++;
回复 支持 反对

使用道具 举报

chendanlan 发表于 2014-11-14 11:13:15 | 显示全部楼层
lvtongyun 发表于 2014-10-15 23:05
我是这样写的   public void insertEnd(Object obj) {
      if (head == null) {
      head = new SL ...

或者最后一行是tal=tai.next
回复 支持 反对

使用道具 举报

chendanlan 发表于 2014-11-14 11:16:03 | 显示全部楼层
lvtongyun 发表于 2014-10-15 23:05
我是这样写的   public void insertEnd(Object obj) {
      if (head == null) {
      head = new SL ...

wow,sorry,回复这么多,都没答对。。我复制粘贴了你的代码,能在我的eclipse运行耶。。。可能其它部分有问题吧。你看看你的insetfront,有没有跟新tail的信息。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 10:17

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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