锐客网

  1. 首页 > it技术 > >

CS61b|CS61b proj1a

CS61bproj1a

得分46.25
有一个点的bug不会修（希望大佬带我），style没有注意。
1.LinkedListDeque.java

public class LinkedListDeque { privateclass staffnode{ private T item; private staffnode pre; private staffnode next; private staffnode(T x) { item=x; } } private int size=1; private staffnode first; private staffnode last; private staffnode standf; private LinkedListDeque(T x) { first=new staffnode(x); standf=new staffnode(x); first.next=standf; first.pre=standf; standf.next=first; standf.pre=first; last=first; size=1; }public LinkedListDeque() { standf=new staffnode(null); first=standf; last=first; size=0; }public void addFirst(T x) {if(size==0) { first=new staffnode(x); standf.next=first; standf.pre=first; first.pre=standf; first.next=standf; last.pre=standf; last.next=standf; last=first; size++; } else { size++; if(size==2) { last.pre=first; } staffnode first1=new staffnode(x); standf.next=first1; first1.next=first; first1.pre=standf; first.pre=first1; first=first1; first.pre=first1.pre; first.next=first1.next; }} public void addLast(T x) {if(isEmpty()) { last=new staffnode(x); standf.pre=last; standf.next=last; last.next=standf; last.pre=standf; first=last; first.next=standf; first.pre=standf; size++; }else { staffnode v=last; last=new staffnode(x); last.pre=v; v.next=last; last.next=standf; standf.pre=last; size++; }} public T removeFirst() { if(size>=1) { T e=first.item; first=first.next; standf.next=first; size--; return e; } else return null; }public T getRecursive(int index){ if (index>=size) return null; else return getRecursive(first,index,0); }privateT getRecursive(staffnode p,int index,int t){ if(t==index) return p.item; else { return getRecursive(p.next,index,t+1); } } public T removeLast() { if(size>=1) {T r=last.item; last=last.pre; last.next=standf; size--; return r; }else return null; }public boolean isEmpty() {if(size==0) return true; else return false; } public T get(int index) { int t=0; staffnode a=first; while(a!=standf) {if(index==t) return a.item; a=a.next; t++; } return null; } public void printDeque() { staffnode p=first; while(p!=standf) { System.out.print(p.item); System.out.print(" "); p=p.next; } System.out.print("\n"); } public int size() { return size; }}




2.ArrayDeque

public class ArrayDeque { private T[] items; private int begin; private int size; private int last; private double rate; private int start; private int s1; private int s2; private int end; public ArrayDeque() { items = (T[]) new Object[8]; begin=items.length-1; size=0; rate=0; start=0; last=0; end=items.length; s1=0; s2=0; }public void addLast(T item) {if(last<=begin&&last0) System.arraycopy(items, start, a, 0,s2); if(begin=0&&begin>=last) { items[begin]=item; begin--; size++; s1++; rate=(double) size/items.length; } else { T[] a = (T[]) new Object[items.length*2]; if(s2>0) System.arraycopy(items, start, a, 0, s2); if(s1>0) System.arraycopy(items, begin+1, a, a.length-s1, s1); items = a; end=items.length; begin=items.length-s1-1; if(begin>=0&&begin0) { s2--; size--; last--; d=items[last]; rate=(double) size/items.length; if(rate<0.25&&items.length>16) { recycle(); } return d; } else if(s1>0){ s1--; end--; size--; d=items[end]; rate=(double) size/items.length; if(rate<0.25&&items.length>16) { recycle(); } return d; } else returnnull; } private int c; public T removeFirst() { if(s1>0) { s1--; size--; begin++; d=items[begin]; rate=(double) size/items.length; if(rate<0.25&&items.length>16) { recycle(); } return d; } else if(s2>0) { s2--; d=items[start]; start=start+1; size--; rate=(double) size/items.length; if(rate<0.25&&items.length>16) { recycle(); } return d; } else returnnull; } private void recycle() { if (size > 0) { T[] a = (T[]) new Object[size]; if (s1 > 0) System.arraycopy(items, begin + 1, a, 0, s1); if (s2 > 0) System.arraycopy(items, start, a, s1, s2); items = a; s2 = size; s1 = 0; begin = items.length - 1; end = items.length; start = 0; last = s2; } else { T[] a = (T[]) new Object[1]; //if(begin+1<=items.length-1) if (s1 > 0) System.arraycopy(items, begin + 1, a, 0, s1); if (s2 > 0) System.arraycopy(items, start, a, s1, s2); items = a; s2 = size; s1 = 0; begin = items.length - 1; end = items.length; start = 0; last = s2; } } public int size() { return size; } publicT get(int index) { if(index=s1&&index


我的失误点总结：
LinkList题目第一次没有注意给设置的pre赋值。每一次改变链表都要注意first,last以及他们之前、之后的节点的pre,next的变化。get递归写法要注意。
第二题总是忘记更新start,end的值只关心了begin和last。
在给addFirst()修改的时候也要对应修改addLast()。
remove函数同理，介于这不是简单的数组，get()函数不能简单采用数组常用的直接返回对应下标的值的办法，要判断index是在哪一部分。

【CS61b|CS61b proj1a】

    推荐阅读


      上一篇：Actor|Actor model 的理解与 protoactor-go 的分析

      下一篇：Angular依赖注入（全面讲解（翻译中））