一亩三分地论坛

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

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

[CS61B_Spring 2015] Discussion3-Arrays vs. Linked Lists

[复制链接] |试试Instant~ |关注本帖
hurricane_e 发表于 2015-6-2 13:00:28 | 显示全部楼层 |阅读模式

[其他]CS61B Data Structures #14 - 2015-05-25@Berkeley

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

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

x
RT~
karte_polo 发表于 2015-6-4 10:17:49 | 显示全部楼层

public class Disc03 {

        public static void main(String[] args) {
                int[] x = {5,9,14,15};
                int[] r = insert(x,6,2);
                int[] expected = {5,9,6,14,15};
        org.junit.Assert.assertArrayEquals(expected, r);
        SList s = new SList(5);
        s.S_insert(6,3);
        s.S_insert(2,2);
        org.junit.Assert.assertEquals(6.0, s.head.next.val, 1e-10);
        s.S_insert(10,1);
        org.junit.Assert.assertEquals(10.0, s.head.next.val, 1e-10);
        SentinelSList s1 = new SentinelSList();
        s1.insert(5, 2);
        org.junit.Assert.assertEquals(5.0, s1.front.next.val, 1e-10);
        int[] test = {3,2,1};
        int[] xifys = xify(test);
        int[] expectedxy = {3,3,3,2,2,1};
        org.junit.Assert.assertArrayEquals(expectedxy, xifys);
        }
       
        public static int[] insert(int[] x, int val, int position) {
                int l = x.length;
                        int[] newArray = new int[l+1];
                        for(int n =0;n<position;n++){
                                newArray[n] = x[n];
                        }
                        newArray[position] = val;
                        for(int n =position+1;n<l+1;n++){
                                newArray[n] = x[n-1];
                        }
                        return newArray;
                }
        public static class SNode {
                public SNode next;
                public double val;
                public SNode(double val, SNode next) {
                this.next = next;
                this.val = val;
                }
        }
        public static class SList{
                private SNode head;
                public SList(){
                }
                public SList(int val){
                        head = new SNode(val,null);
                }
                public void S_insert(double val, int position){
                        SNode p = head;
                        if (p == null){
                                head = new SNode(val,null);
                        }else{
                        int n = 1;
                        while(p.next!=null && n<position){
                                p = p.next;
                                n++;
                        }
                        p.next = new SNode(val,p.next);
                        }       
                }
               
        }
       
       
        public static class SentinelSList {
                private SNode front;
                private SNode back;
                public SentinelSList() {
                this.back = new SNode(0, null);
                this.front = new SNode(0, back);
                }
                public void insert(double val, int position) {
                        SNode p = front;
                        int n = 0;
                        if (p.next!=back && n <position){
                                p = p.next;
                                n++;
                        }
                        p.next = new SNode(val,p.next);
                }
        }
        public static int[] xify(int[] x){
                int newl = 0 ;
                int count = 0;
                for(int i=0;i<x.length;i++){
                        newl+= x[i];
                }
                int[] res = new int[newl];
                for(int i=0;i<x.length;i++){
                        for(int n=0;n<x[i];n++){
                                res[count]=x[i];
                                count++;
                        }
                       
                }
                return res;
        }

}

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| hurricane_e 发表于 2015-6-4 15:21:43 | 显示全部楼层
回复 支持 反对

使用道具 举报

baiery 发表于 2015-6-5 15:00:31 | 显示全部楼层
1.Array Insertion

public static int[] insert(int[] x, int val, int position){
                int[] y = new int[x.length+1];
                for (int i=x.length-1;i > position-1; i-- ){
                y[i+1] = x[i];
                }
                y[position] = val;
                for (int j = 0;j<position;j++){
                        y[j] = x[j];
                }
                return y;

2. Singly Linked Lists
public void insert(double val, int position){
                SNode p = head;
                if (head == null || position == 0){
                        head = new SNode(val, head);
                        return;
                }else{

                        while(p.next != null && position > 1){
                                p = p.next;
                                position -- ;
                        }
                        SNode temp = p;
                        temp = new SNode(val,temp.next);
                        p.next = temp;

                }
        }

3.  Sentinel Nodes

public void insert(double val, int position) {
                SNode p = front;
                if (front == null || position == 0){
                        front = new SNode(val, front);
                        return;
                }else{

                        while(p.next != back && position > 1){
                                p = p.next;
                                position -- ;
                        }
                        SNode temp = p;
                        temp = new SNode(val,temp.next);
                        p.next = temp;
                        if (position > 1){
                                back = temp;
                        }
                }
        }

三个程序全都test过,应该是对的

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

baiery 发表于 2015-6-5 15:01:56 | 显示全部楼层
karte_polo 发表于 2015-6-4 10:17
public class Disc03 {

        public static void main(String[] args) {

你的SentinelSList貌似有点问题,应该是while循环,不是if吧?另外你没有处理back啊,如果是在list尾巴上添加元素,那back也要移到尾巴去才对吧?
回复 支持 反对

使用道具 举报

baiery 发表于 2015-6-5 15:02:18 | 显示全部楼层

我觉得你的SentinelSList貌似也没有考虑back需要移动的情况,你觉得呢?
回复 支持 反对

使用道具 举报

karte_polo 发表于 2015-6-5 20:04:47 | 显示全部楼层
baiery 发表于 2015-6-5 15:01
你的SentinelSList貌似有点问题,应该是while循环,不是if吧?另外你没有处理back啊,如果是在list尾巴上 ...

谢谢提醒!那时候只用了一个测试用例,没有发现while写成if了

我的BACK 是会移动的;当指针P指向BACK前一个NODE的时候,会把这个NODE的NEXT指针指向新节点,而新节点的NEXT指针指向BACK ,你看一下是不是这样
回复 支持 反对

使用道具 举报

baiery 发表于 2015-6-6 13:46:28 | 显示全部楼层
karte_polo 发表于 2015-6-5 20:04
谢谢提醒!那时候只用了一个测试用例,没有发现while写成if了

我的BACK 是会移动的;当指针P指向BACK ...

哦对的,没错!其实我的写法倒是麻烦了!学习了!
回复 支持 反对

使用道具 举报

a0106660 发表于 2015-6-14 11:43:36 | 显示全部楼层
感觉你们插入的循环方法和我不一样。我是先求出SIZE  然后用SIZE 判断插入位置合不合法,再用for 循环插入。 操作次数是比你们多一些。
对了,你们的back 是设置的(0,null),初始化就没变过。还是设置成真正的尾节点?  假如一直是(0,null) 那不是变成 two sentinelnodes 了? SList.PNG SentinelSList.PNG SentinelSList2.PNG

ArrayInsertion.PNG

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

xiaobai024 发表于 2015-6-16 01:22:29 | 显示全部楼层
求问一下 2015 的视频是在哪里呢? 我看到YouTube上面还是2014的
回复 支持 反对

使用道具 举报

 楼主| hurricane_e 发表于 2015-6-16 04:47:56 | 显示全部楼层
xiaobai024 发表于 2015-6-16 01:22
求问一下 2015 的视频是在哪里呢? 我看到YouTube上面还是2014的

https://berkeley-cs61b.github.io/public_html/index.html 课程主帖里有链接~
回复 支持 反对

使用道具 举报

xiaobai024 发表于 2015-6-16 04:53:33 | 显示全部楼层
hurricane_e 发表于 2015-6-16 04:47
https://berkeley-cs61b.github.io/public_html/index.html 课程主帖里有链接~

谢谢咯~~~不知道61A 是不是也有类似的链接?
回复 支持 反对

使用道具 举报

Casualet 发表于 2015-6-17 23:56:04 | 显示全部楼层
1:

1

1


Only if thecapacity is larger than the size of the array.


2:

2

2


3:
public class SentinelSList {
  private SNode front;
  private SNode back;

  public SentinelSList() {
    this.back = new SNode(0, null);
    this.front = new SNode(0, back);
}

  public void insert(double val, int position) {
        int i=0;
        SNode temp=new SNode(val,null);
        SNode next=front;
        while(next.next!=back){
             if(i==position){
                SNode t=next.next;
                next.next=temp;
                temp.next=t;
                return ;
             }else{
            next=next.next;
            i++;
         }      

       }
       SNode tBack=back;
       back=new SNode(0,null);
       tBack.val=val;
       tBack.next=back;        
}

  public static int []  xify(int [] x){

       int sum=0;
      for(int i=0;i<x.length;i++){
             sum+=x;
      }

      int [] re=new int[sum];

      int i=0;
      int j=0;
      int temp=0;
      for(;i<x.length;i++){
        for(temp=0;temp<x;temp++){
             re[j++]=x;
         }

     }
   return re;
  }


  public void printList(){
       SNode s=front.next;
       while(s!=back){
          System.out.println(s.val+" ");   
          s=s.next;
      }


   }

  public static void main(String args[] ){
       SentinelSList s=new SentinelSList();

       s.insert(1,0);
       s.insert(2,1);
       s.insert(3,2);
       s.insert(4,3);
       s.insert(5,4);
       s.insert(6,-1);
       s.insert(7,10);
       s.printList();
       int [] input={3,2,1};
       input=xify(input);
       for(int i=0;i<input.length;i++){
         System.out.print(input+" ");
      }
  }
}

测试结果

测试结果



每天一题,先赶上进度再来看大家的代码吧...


评分

1

查看全部评分

回复 支持 反对

使用道具 举报

whosays 发表于 2015-6-18 00:27:29 | 显示全部楼层
Array Insertion:
public class arrayOp {
        public static int[] insert(int[] x, int val, int position) {
                int[] y = new int[x.length + 1];
                int i = 0;
                y[position] = val;
                while (i < y.length) {
                        if (i > position) {
                                y = x[i-1];

                        } else if (i < position) {  
                                y = x;
                        }
                        i += 1;
                }
                return y;
        } // close insert method
}

SList:
public class SList {
        // instantiation
        private SNode head;
        public SList (double item) {
                head = new SNode(item, null);
        }

        // insert val to the indexed position
        public void insert(double val, int position){
        // my own codes start here                
                if ((head == null) || (position == 0)) {
                        head = new SNode (val, head); // invalid insert position & reach the right position
                } else {
                        while ((position != 0) && (head != null)){
                                head = head.next;
                                position -= 1;
                        } // close while loop
                        SNode oldHead = head;
                        head = new SNode(val, oldHead);
                }
        } // close insert method
SentinelList:
public class SList {
        // instantiation
        private SNode head;
        public SList (double item) {
                head = new SNode(item, null);
        }

        // insert val to the indexed position
        public void insert(double val, int position){
        // my own codes start here                
                if ((head == null) || (position == 0)) {
                        head = new SNode (val, head); // invalid insert position & reach the right position
                } else {
                        while ((position != 0) && (head != null)){
                                head = head.next;
                                position -= 1;
                        } // close while loop
                        SNode oldHead = head;
                        head = new SNode(val, oldHead);
                }
        } // close insert method

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

whosays 发表于 2015-6-18 00:31:00 | 显示全部楼层
本帖最后由 whosays 于 2015-6-18 00:35 编辑
a0106660 发表于 2015-6-14 11:43
感觉你们插入的循环方法和我不一样。我是先求出SIZE  然后用SIZE 判断插入位置合不合法,再用for 循环插入 ...

我也引入了size,个人理解这题就是两个sentinel node。如果再做细点就跟老师课上的例子一样,可以在前插或在后插,并分别get前后的新元素,我觉得只做这题只要实现前、后插的一种就够了。欢迎讨论
回复 支持 反对

使用道具 举报

西风吹草 发表于 2015-6-20 12:01:50 | 显示全部楼层
本帖最后由 西风吹草 于 2015-6-20 12:09 编辑

1.
        public static int[] insert(int[] x, int val, int position){
                int[] y = new int[x.length + 1];
                System.arraycopy(x, 0, y, 0, position);
                y[position] = val;
                System.arraycopy(x, position, y, position + 1, x.length - position);
                return y;
        }

2.
public class SList {
        private SNode head;
        public void insert(double val, int position){
                for (int i = 0; i < position && head != null; i ++){
                        head = head.next;
                }
                head = new SNode(val, head);
        }
}

3b.
Capture.PNG

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

Kengo 发表于 2015-10-16 10:23:34 | 显示全部楼层
  1. /** Singly linked lists
  2. */

  3. public class SNode {
  4.     public SNode next;
  5.     public double val;
  6.     public SNode(double val, SNode next) {
  7.         this.next = next;
  8.         this.val = val;
  9.     }
  10.    
  11. }

  12. /** Singly linked list
  13. */

  14. public class SList {
  15.     public SNode head;
  16.     public int size;
  17.     /** insert a value val at position
  18.      *  destructive approach
  19.      *  if the position is invalid, insert the node at the end
  20.      */
  21.    
  22.     public SList(double val) {
  23.         head = new SNode(val, null);
  24.         size = 1;
  25.     }

  26.     public SList() {
  27.         this.head = null;
  28.         size = 0;
  29.     }

  30.     public void insertBack(double val) {
  31.         SNode p = head;

  32.         if (head == null) {
  33.             head = new SNode(val, null);
  34.         
  35.         } else {
  36.             while(p.next != null) {
  37.                 p = p.next;
  38.             }
  39.             p.next = new SNode(val, p.next);
  40.             size += 1;
  41.         }
  42.     }


  43.     public void insert(double val, int position) {
  44.         SNode p = head;
  45.         if (position < 0 || position >= size){
  46.             insertBack(val);
  47.         } else if (position == 0) {
  48.             head = new SNode(val, head);
  49.             size += 1;
  50.         } else {

  51.             for(int i = 0; i < position - 1; i++) {
  52.                 p = p.next;
  53.             }
  54.             p.next = new SNode(val, p.next);
  55.             size += 1;
  56.         }
  57.     }


  58.     public void printList() {
  59.         SNode p = head;
  60.         while( p != null) {
  61.             System.out.println(p.val);
  62.             p = p.next;
  63.         }

  64.     }



  65.     public static void main(String[] args) {
  66.         SList list = new SList(5.0);

  67.         list.insert(6, 1);
  68.         list.insert(2, 2);
  69.         list.insert(10, 1);
  70.         list.insert(10, 0);

  71.         int inValidPos1 = -1;
  72.         int inValidPos2 = 5;

  73.         list.insert(11, inValidPos1);
  74.         list.insert(12, inValidPos2);

  75.         list.printList();
  76.     }
  77. }

  78. /** Insert elements into a SentinelList.
  79. * if the posiiton is invalid, insert the node at the end
  80. */

  81. public class SentinelSList {
  82.     private SNode front;
  83.     private SNode back;
  84.     private int size;

  85.     public SentinelSList() {
  86.         this.back = new SNode(0, null);
  87.         this.front = new SNode(0, back);
  88.         this.size = 0;
  89.     }

  90.     public void printList() {
  91.         SNode p = front.next;
  92.         while( p != back) {
  93.             System.out.println(p.val);
  94.             p = p.next;
  95.         }

  96.     }

  97.     public void insertBack(double val) {
  98.         SNode p = front.next;

  99.         if (p == back){
  100.             front.next = new SNode(val, back);

  101.         } else {
  102.             while(p.next != back) {
  103.                 p = p.next;
  104.             }
  105.             p.next = new SNode(val, p.next);
  106.             size += 1;
  107.         }
  108.     }

  109.     public void insert(double val, int position) {
  110.         SNode p = front.next;
  111.         if (position < 0 || position >= size){
  112.             insertBack(val);
  113.         } else if (position == 0) {
  114.             front.next = new SNode(val, front.next);
  115.             size += 1;
  116.         } else {

  117.             for(int i = 0; i < position - 1; i++) {
  118.                 p = p.next;
  119.             }
  120.             p.next = new SNode(val, p.next);
  121.             size += 1;
  122.         }
  123.     }

  124.     public static void main(String[] args) {
  125.         SentinelSList list = new SentinelSList();

  126.         list.insert(6, 0);
  127.         list.insert(2, 1);
  128.         list.insert(10, 1);
  129.         list.insert(10, 0);

  130.         int inValidPos1 = -1;
  131.         int inValidPos2 = 5;

  132.         list.insert(11, inValidPos1);
  133.         list.insert(12, inValidPos2);

  134.         list.printList();
  135.     }

  136. }
复制代码

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

HNAKXR 发表于 2016-1-31 21:34:48 | 显示全部楼层
本帖最后由 HNAKXR 于 2016-1-31 21:37 编辑

1 Array Insertion
  1. import java.util.Arrays;

  2. public class Insert {
  3.         public static int[] insert(int[] x, int val, int position) {
  4.                 int[] result = new int[x.length + 1];
  5.                 for (int i = 0; i < x.length + 1; i++) {
  6.                         if (i < position) {
  7.                                 result[i] = x[i];
  8.                         } else if (i == position) {
  9.                                 result[i] = val;
  10.                         } else {
  11.                                 result[i] = x[i - 1];
  12.                         }
  13.                 }
  14.                 return result;
  15.         }

  16.         public static void main(String[] args) {
  17.                 int[] x = {5, 9, 14, 15};
  18.                 int[] y = insert(x, 6, 2);
  19.                 System.out.println(Arrays.toString(y));
  20.         }
  21. }
复制代码
2 Singly Linked Lists
  1. public class SList {
  2.         private SNode front;

  3.         public void insert(double val, int position) {
  4.                 int i = 0;
  5.                 SNode p = front;

  6.                 if (p == null || position == 0) {
  7.                         front = new SNode(val, front);
  8.                 } else {
  9.                         while (p.next != null && i < position - 1) {
  10.                                 p = p.next;
  11.                                 i++;
  12.                         }
  13.                         p.next = new SNode(val, p.next);
  14.                 }
  15.                 size = size + 1;
  16.         }
  17. }
复制代码
3 Sentinel Nodes
  1. public class SentinelSList {
  2.         private SNode front;
  3.         private SNode back;

  4.          public void insert(double val, int position) {
  5.                 SNode p = front;
  6.                 int i = 0;
  7.                 while (p.next != back && i < position) {
  8.                         p = p.next;
  9.                         i++;
  10.                 }
  11.                 if (i == position) {
  12.                         p.next = new SNode(val, p.next);
  13.                 } else {
  14.                         back.next = new SNode(val, null);
  15.                 }
  16.         }
  17. }
复制代码

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 14:08

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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