得分46.25
有一个点的bug不会修（希望大佬带我），style没有注意。
1.LinkedListDeque.java
public class LinkedListDeque <T>{ private class 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); } private T 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<T> { 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&&last<items.length) { items[last]=item; size++; last++; rate=size/items.length; s2++; } else { T[] a = (T[]) new Object[items.length*2]; if(s2>0) System.arraycopy(items, start, a, 0,s2); if(begin<items.length-1) System.arraycopy(items, begin+1, a, a.length-s1, s1); items = a; end=items.length; start=0; last=s2; begin=items.length-s1-1; items[last]=item; last++; size = size + 1; s2++; } } public void addFirst(T item) { 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&&begin<items.length) items[begin]=item; begin--; start=0; last=s2; size = size + 1; rate=(double) size/items.length; s1++; } } private T d; public T removeLast() { if(s2>0) { 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 return null; } 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 return null; } 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; } public T get(int index) { if(index<s1) return items[begin+index+1]; if(index>=s1&&index<size) return items[start+(index-s1)]; else return null; } public void printDeque() { for(int i=begin+1;i<end;i++) { System.out.print(items[i]); System.out.print(' '); } for(int j=start;j<last;j++) { System.out.print(items[j]); System.out.print(' '); } System.out.print("\n"); } public boolean isEmpty() { return size==0; } }
我的失误点总结：
LinkList题目第一次没有注意给设置的pre赋值。每一次改变链表都要注意first,last以及他们之前、之后的节点的pre,next的变化。get递归写法要注意。
第二题总是忘记更新start,end的值只关心了begin和last。
在给addFirst()修改的时候也要对应修改addLast()。
remove函数同理，介于这不是简单的数组，get()函数不能简单采用数组常用的直接返回对应下标的值的办法，要判断index是在哪一部分。
