2

我应该为一个项目实现一个包数据结构(也称为多重集),一个可能有重复的同类值(任何 Java 对象,不包括 null)的无序集合。我已经在互联网上进行了广泛的搜索,但是很难将我的思想包裹在使用数组而不是 List 之类的东西上,并且不太了解在类中使用数组的语法。

我需要实现所有 java.util.Collection,除非通过抛出 UnsupportedOperationException 进行说明。是的,我必须使用一个数组,当我添加它时,容量必须增加 10。我的问题是我不确定如何处理contains方法、clear方法、addAll方法和第二个构造函数。希望我添加的所有其他内容也能顺利运行。我已将 API 定义包含在注释块中。任何输入都会真正帮助我。

正如马克在下面问的那样,我不明白如何通过包来搜索特定元素。

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; 
    }
}
4

2 回答 2

3

我对你里面的东西感到困惑contains......你正在调用toArray()一个Object没有toArray()方法的 。这表明您对您正在尝试做的事情存在一些基本的误解。尽管如此,您实际上似乎确实知道如何检查集合是否包含给定对象,因为您必须找到该对象才能找到remove它。您的remove方法返回与使用相同对象调用时完全相同的boolean值。contains我认为你可以从中工作。

(顺便说一句,您的remove方法有一个可能导致内存泄漏的错误......当它将数组中的对象向左移动 1 时,它不会将不再包含在集合中的数组槽设置为null.)

addAll很简单……你得到了一个Collection需要添加的元素,并且你有一个add可以添加元素的方法。这些一起去。(addAll这也是实现第二个构造函数所真正需要的。)

clear也很简单。调用它之后,你的数组需要没有对任何对象的引用,并且你的包的大小需要为 0。想想你怎么能做到这一点。

的工作实现将帮助您通过使用集合来实现许多iterator()方法Collection(包括t 可能使用它。clearIteratorAbstractCollectionclear

另外,一个小笔记。

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

最好写成:

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

因为size() == 0已经是一个boolean表达式,所以if/else是多余的。

于 2010-11-04T03:43:36.043 回答
0

您可以使用 guava 的 Multiset 实现作为参考。这会给你一些想法 http://guava-libraries.googlecode.com/svn/trunk/src/com/google/common/collect/

于 2010-11-04T01:50:35.263 回答