3

因此,我在概念化以下问题的答案时遇到了很多困难。我不是在寻找答案,而是我可以采取的有用步骤,这将使我能够自己提出答案。注意:为了回答这些问题,我给出了引用的类和一个驱动程序。问题如下:

Q.1 为 ADT 包实现一个方法 replace,用给定的对象替换并返回当前在包中的任何对象。

Q.2. 编写一个 remove 方法来删​​除 ArrayBag 中元素的每个实例。

问题 3。至少给出两个适合使用固定包的情况的示例和两个适合使用可调整大小的包的情况的示例。

以下代码是我开始的,但不确定我的方向是否正确:

a.1 public T replace(T theItem) {
    Random generator = new Random();
    int randomPosition = generator.nextInt(numberOfEntries);

    T result = null;

    if (!isEmpty() && (randomPosition >= 0)) {
        result = bag[randomPosition]; // Entry to remove
        bag[randomPosition] = theItem; // Replace entry to remove with
                                // last entry

    }
    return result;
 a.2 public void clear(T theItem) {
    while (!this.isEmpty(ArrayBag))
        this.remove();

 a.3 not sure it should be related to coding examples or something else.

此外,ArrayBag 的类如下供参考:

import java.util.Arrays;
import java.util.Random;

public final class ArrayBag<T> implements  BagInterface<T> {
private final T[] bag;
private int numberOfEntries;
private boolean initialized = false;
private static final int DEFAULT_CAPACITY = 25;
private static final int MAX_CAPACITY = 10000;

/** Creates an empty bag whose initial capacity is 25. */
public ArrayBag() {
    this(DEFAULT_CAPACITY);
} // end default constructor

/**
 * Creates an empty bag having a given capacity.
 * 
 * @param desiredCapacity
 *            The integer capacity desired.
 */
public ArrayBag(int desiredCapacity) {
    if (desiredCapacity <= MAX_CAPACITY) {
        // The cast is safe because the new array contains null entries
        @SuppressWarnings("unchecked")
        T[] tempBag = (T[]) new Object[desiredCapacity]; // Unchecked cast
        bag = tempBag;
        numberOfEntries = 0;
        initialized = true;
    } else
        throw new IllegalStateException("Attempt to create a bag "
                + "whose capacity exceeds " + "allowed maximum.");
  } // end constructor

  /**
   * Adds a new entry to this bag.
   * 
   * @param newEntry
  *            The object to be added as a new entry.
  * @return True if the addition is successful, or false if not.
 * /
  public boolean add(T newEntry) {
    checkInitialization();
    boolean result = true;
    if (isArrayFull()) {
        result = false;
    } else { // Assertion: result is true here
        bag[numberOfEntries] = newEntry;
        numberOfEntries++;
    } // end if

    return result;
  } // end add

 /**
 * Retrieves all entries that are in this bag.
 * 
 * @return A newly allocated array of all the entries in this bag.
 */
public T[] toArray() {
    checkInitialization();

    // The cast is safe because the new array contains null entries.
    @SuppressWarnings("unchecked")
    T[] result = (T[]) new Object[numberOfEntries]; // Unchecked cast

    for (int index = 0; index < numberOfEntries; index++) {
        result[index] = bag[index];
    } // end for

    return result;
    // Note: The body of this method could consist of one return statement,
    // if you call Arrays.copyOf
} // end toArray

/**
 * Sees whether this bag is empty.
 * 
 * @return True if this bag is empty, or false if not.
 */
public boolean isEmpty() {
    return numberOfEntries == 0;
} // end isEmpty

/**
 * Gets the current number of entries in this bag.
 * 
 * @return The integer number of entries currently in this bag.
 */
public int getCurrentSize() {
    return numberOfEntries;
} // end getCurrentSize

/**
 * Counts the number of times a given entry appears in this bag.
 * 
 * @param anEntry
 *            The entry to be counted.
 * @return The number of times anEntry appears in this ba.
 */
public int getFrequencyOf(T anEntry) {
    checkInitialization();
    int counter = 0;

    for (int index = 0; index < numberOfEntries; index++) {
        if (anEntry.equals(bag[index])) {
            counter++;
        } // end if
    } // end for

    return counter;
} // end getFrequencyOf

/**
 * Tests whether this bag contains a given entry.
 * 
 * @param anEntry
 *            The entry to locate.
 * @return True if this bag contains anEntry, or false otherwise.
 */
public boolean contains(T anEntry) {
    checkInitialization();
    return getIndexOf(anEntry) > -1; // or >= 0
} // end contains

/** Removes all entries from this bag. */
public void clear() {
    while (!this.isEmpty())
        this.remove();
} // end clear

/**
 * Removes one unspecified entry from this bag, if possible.
 * 
 * @return Either the removed entry, if the removal was successful, or null.
 */
public T remove() {
    checkInitialization();
    T result = removeEntry(numberOfEntries - 1);
    return result;
} // end remove

/**
 * Removes one occurrence of a given entry from this bag.
 * 
 * @param anEntry
 *            The entry to be removed.
 * @return True if the removal was successful, or false if not.
 */
public boolean remove(T anEntry) {
    checkInitialization();
    int index = getIndexOf(anEntry);
    T result = removeEntry(index);
    return anEntry.equals(result);
} // end remove

public boolean removeRandom() {
    Random generator = new Random();
    int randomPosition = generator.nextInt(numberOfEntries);
    T result = removeEntry(randomPosition);
    if (result == null) {
        return false;
    } else {
        return true;
    }

}

@Override
public boolean equals(Object obj) {
    if (obj instanceof ArrayBag) {
        ArrayBag<T> otherArrayBag = (ArrayBag<T>) obj;

        if (numberOfEntries == otherArrayBag.numberOfEntries) {

            // I create new arrays so that I can manipulate them
            // and it will not alter this.bag or otherArrayBag.bag
            T[] currentBagTempArray = toArray();
            T[] otherBagTempArray = otherArrayBag.toArray();

            Arrays.sort(currentBagTempArray);
            Arrays.sort(otherBagTempArray);

            for (int i = 0; i < numberOfEntries; i++) {
                if (!currentBagTempArray[i].equals(otherBagTempArray[i])) {
                    return false;
                }
            }
            return true;
        } else {
            return false;
        }

    } else {
        return false;
    }
}

public ResizableArrayBag<T> createResizableArray() {
    T[] currentBagContents = toArray();
    ResizableArrayBag<T> newBag = new ResizableArrayBag<T>(currentBagContents);
    return newBag;
}

// Returns true if the array bag is full, or false if not.
private boolean isArrayFull() {
    return numberOfEntries >= bag.length;
} // end isArrayFull

// Locates a given entry within the array bag.
// Returns the index of the entry, if located,
// or -1 otherwise.
// Precondition: checkInitialization has been called.
private int getIndexOf(T anEntry) {
    int where = -1;
    boolean found = false;
    int index = 0;

    while (!found && (index < numberOfEntries)) {
        if (anEntry.equals(bag[index])) {
            found = true;
            where = index;
        } // end if
        index++;
    } // end while

    // Assertion: If where > -1, anEntry is in the array bag, and it
    // equals bag[where]; otherwise, anEntry is not in the array.

    return where;
} // end getIndexOf

// Removes and returns the entry at a given index within the array.
// If no such entry exists, returns null.
// Precondition: 0 <= givenIndex < numberOfEntries.
// Precondition: checkInitialization has been called.
private T removeEntry(int givenIndex) {
    T result = null;

    if (!isEmpty() && (givenIndex >= 0)) {
        result = bag[givenIndex]; // Entry to remove
        int lastIndex = numberOfEntries - 1;
        bag[givenIndex] = bag[lastIndex]; // Replace entry to remove with
                                            // last entry
        bag[lastIndex] = null; // Remove reference to last entry
        numberOfEntries--;
    } // end if

    return result;
} // end removeEntry

// Throws an exception if this object is not initialized.
private void checkInitialization() {
    if (!initialized)
        throw new SecurityException(
                "ArrayBag object is not initialized properly.");
} // end checkInitialization

} // 结束 ArrayBag

4

2 回答 2

1

其他人在Bag Class Implementation in Java/Using Array 中使用 Array 实现了 Bag。我只看了一眼代码,所以可能是鱼龙混杂。

我假设 Bag 就像一个 Set,除了 in 可以多次存储同一个对象。您可能希望实现某种私有集合(可能是上面的数组)。我们称之为myBag。由于您使用的是通用类型 T,因此您的 Bag 将仅包含 T 类型的对象

对于 Q1,您的 replace() 方法可能需要采用两个参数:要替换的对象(比如findMe)和要替换它的对象(比如replacement)。如果您的 Bag 可以容纳重复项,那么您可能需要替换第一个匹配的对象。而不是使用 Random(),您可能需要通过 myBag 逐个元素地遍历,并将找到的元素替换为您要替换的元素。findMe如果未找到,您可能想抛出错误。所以方法声明可能是这样的:

public boolean replace(T findMe, T replacement)

如果找到了 findMe ,则返回 true ,否则返回 false。

对于 Q2,您可以创建一个 while 循环,在 myBag 的大小大于 0 时删除 myBag 中的第一个元素。

对于第三季度,不涉及编码。这是一个思考问题。一般来说,当一开始就知道尺寸不会改变时,固定尺寸的 Bag 会很有帮助。

可调整大小的包在更多情况下是有意义的,在这些情况下,您一开始不知道大小,并且它可能会缩小或增长,例如上课的候补名单。

于 2015-02-05T21:44:14.803 回答
0

我查看了您的起始代码和类,但我没有运行它。但我可以说你的方向是正确的。

对于 Q2,您应该在数组中搜索给定元素并删除每个元素。因为问题清楚地表明“删除元素的每个实例”请检查 getIndexOf() 方法。你可以看到如何搜索和元素。如果你找到一个匹配的删除它。如果在迭代它时删除和元素,请小心。如果在迭代时删除一个元素,大小将会改变。我建议您将每个匹配项存储在一个数组中。迭代后对每个找到的元素使用 remove(index) 方法

Give at least two examples of a situation where a fixed bag is appropriate and two examples of a situation where a resizable bag is appropriate.

对于这个项目,您可以添加一些解释和一些示例代码或算法。我可以给你两件事:

1.  If the array is not getting full too fast fixed size is good. But if array is getting full too fast you should resize new array and copy all elements again and again. Overhead amount is important.
2. Amount of capacity is important. How you will decide initial size ? Big size or small size ? Think that

我希望这有帮助

于 2015-02-05T21:12:32.233 回答