作爲Java中的數組實現Bag實現

Question

我應該爲一個項目實現一個bag數據結構（也稱爲multiset），一個無序的 齊次值集合（任何Java對象，不包括null）。我在互聯網上進行了大量的搜索，但是我很難用數組代替List之類的東西，也不太瞭解在類中使用數組的語法。

我需要實現所有的java.util.Collection，除非拋出一個UnsupportedOperationException異常。是的，我必須使用一個數組，當我添加到它時，容量必須增加10.我的問題是，我不知道如何處理包含方法，明確方法， addAll方法，第二個構造函數。希望我添加的其他東西也能順利運行。我已經在註釋塊中包含了API定義。任何輸入都可以幫助我。

正如Mark在下面問到的，我不明白如何通過包搜索特定元素。

import java.util.Collection; 
import java.util.Iterator; 

class Bag<T> implements Collection<T>{ 
private T[] array; 
public int bagSize; 


public Bag(){ 
    array=(T[])new Object[10]; 
} 
public Bag(Collection<T> other){ 
    //Not sure what to put here 
    //creates a bag containing all of the items passed to it as a Collection<T> 
} 

public int size() { 
    return bagSize; 
} 

public boolean isEmpty() { 
    if(size()==0) 
     return true; 
    else 
     return false; 
} 


public boolean contains(Object o) { 
    //Not sure what to put here 
    /*Returns true if this collection contains the specified element. More formally, 
    returns true if and only if this collection contains at least one element e such 
    that (o==null ? e==null : o.equals(e)). */ 
    return (o.toArray()==null ? this.toArray()==null : o.toArray() == this.toArray()); 
    } 

} 


public Iterator<T> iterator() { 
    throw new UnsupportedOperationException("not implemented."); 
} 

public Object[] toArray() { 
    return array; 

} 

public <T> T[] toArray(T[] a) { 
    throw new UnsupportedOperationException("not implemented."); 
} 

public boolean add(T e) { 
    if(bagSize>=array.length) 
     return false; 
    else 
    { 
     ensureCapacity(bagSize+10); 
     array[bagSize]=e; 
     bagSize++; 
     return true; 
    } 

} 

public boolean remove(Object o) { 
    for(int i=0; i<bagSize; i++) 
     if(array[i].equals(o)){ 
      for(int j=i; j<bagSize-1; j++) 
       array[j]=array[j+1]; 
      bagSize--; 
      return true; 
     } 
    return false; 

} 

public boolean containsAll(Collection<?> c) { 
    throw new UnsupportedOperationException("not implemented."); 
} 

public boolean addAll(Collection<? extends T> c) { 
    //Not sure what to put here 
    /*Adds all of the elements in the specified collection to this collection 
    (optional operation). The behavior of this operation is undefined if the specified 
    collection is modified while the operation is in progress. (This implies that the 
    behavior of this call is undefined if the specified collection is this collection, 
    and this collection is nonempty.) */ 
} 

public boolean removeAll(Collection<?> c) { 
    throw new UnsupportedOperationException("not implemented."); 
} 

public boolean retainAll(Collection<?> c) { 
    throw new UnsupportedOperationException("not implemented."); 
} 

public void clear() { 
    //Not sure what to put here 
    /*Removes all of the elements from this collection (optional operation). The 
    collection will be empty after this call returns (unless it throws an exception).*/ 
} 

@Override 
public int hashCode(){ 
    throw new UnsupportedOperationException("not implemented."); 
} 

@Override 
public boolean equals(Object e) { 
    if (e == null) { 
     return false; 
    } 
    if (getClass() != e.getClass()) { 
     return false; 
    } 
    final Bag<T> other = (Bag<T>) e; 
    return true; 
} 

public void ensureCapacity(int minCapacity){ 
    T[] biggerArray; 
    if(array.length<minCapacity){ 
     biggerArray=(T[]) new Object[minCapacity]; 
     System.arraycopy(array, 0, biggerArray, 0, bagSize); 
     array=biggerArray; 
    } 
} 

Answer 1

我感到困惑，你裏面有什麼contains ...你在一個Object，它不具有toArray()方法調用toArray()。這表明對你想要做的事情有一些基本的誤解。儘管如此，實際上你確實似乎知道如何檢查集合是否包含給定的對象，因爲你必須找到它的對象才能到remove它。您的remove方法返回的值與contains使用相同對象調用時的值完全相同boolean值。我認爲你可以從中工作。

（您的remove方法有一個可能導致內存泄漏的錯誤，順便說一句......當它將陣列中的對象向左移1時，它不會將陣列插槽設置爲不再包括集合null英寸）

addAll是很簡單的......你給所有需要添加元素的Collection，和你有一個add方法，可以添加元素。這些一起。 （addAll是你真的需要實現你的第二個構造函數。）

clear也很簡單。在調用它之後，你的數組不需要引用任何對象，並且你的包的大小需要爲0.請考慮如何做到這一點。

的iterator()一個工作的實施將幫助你不少多達Collection方法（包括clear）能夠利用收集的Iterator（方便的抽象類AbstractCollection做到這一點）來實現，但實現該是多一點很難，而不僅僅是實現一個基本不使用它的基本clear。

另外，一個小紙條。

public boolean isEmpty() { 
    if(size()==0) 
     return true; 
    else 
     return false; 
} 

會更好寫爲：

public boolean isEmpty() { 
    return size() == 0; 
} 

由於size() == 0已經是boolean表達，將if/else是多餘的。

Answer 2

您可以使用番石榴的Multiset實現作爲參考。這將會給你一些想法 http://guava-libraries.googlecode.com/svn/trunk/src/com/google/common/collect/