如何为Bag（或Multiset）ADT编写实现类？

Question

我有一个作业，我需要为Bag（或Multiset）ADT编写一个实现类。问题是，作业的措辞难以理解，我不确定到底需要做什么。

Here是作业描述，here是我提供的界面。到目前为止，This是我的实现类。我还没有编写任何方法，因为我不确定从哪里开始，特别是关于3种不同的构造函数。

package Bags;


import java.io.*;


public class ConBag implements Bag, Serializable {


  private String[]  items;     // The items in the bag
  private int       itemCount; // The number of items
  private int       size;      // The size of the bag



  // This constructor creates a new empty bag able to hold 100 items.
  public ConBag ( ) {

    this(100);

  }; // Constructor



  // This constructor creates a new bag with a specified capacity.
  public ConBag ( int size ) {

    items = new String[size];

  }; // Constructor



  // This constructor takes an array of Strings and copies them into a bag of 100 or fewer items.
  public ConBag ( String[] items ) {



  }; // Constructor



  public void add ( String item ) {

    try{
      if(!contains(item) && (!(size == items.length))){
        items[itemCount] = item;
        itemCount++;
      }
    }catch (NoSpaceException exception) {
      System.out.println("Bag is full.");
    }    
  }; // Add



  public void remove ( String item ) {

    for (int i=0; i<size; i++) {
      if (contains(item)) {
        items[i] = items[itemCount-1];
      }else {
        NoItemException exception; 
        System.out.println("Item not in bag.");
      }
    }    
  };



  public int cardinality ( ) {

    return itemCount;    
  };



  public boolean contains ( String item ) {

    for (int i=0; i<itemCount; i++) {
      if(items[i].equals(item))
        return true;
    }
    return false;   
  };



  public int count ( String item ) {

    int count;

    return count;    
  };



  public String draw ( ) {



  };

}

我觉得我错过了一些重要的东西，但我不知道是什么。我已经有NoItemException和NoSpaceException，但我认为我不需要在这篇文章中包含它们，因为它们非常基本。任何正确方向的帮助或推动都会很棒。谢谢！

Answer 1

您需要允许复制，因此使用String数组作为数据结构会使事情变得困难。最好使用键是String的映射，值是Integer。

目前还不清楚房间的限制是什么，因此，现在你可以定义一个名为room的私有成员，它将是int，每当你打算添加一个字符串时，都要检查房间的基数。如果它更小，则增加映射条目的值（如果存在）。如果没有，那么只需使用值1创建它。

删除应检查包含。如果您拥有的Map不包含该项，则抛出异常。否则，如果映射条目的值高于1，则递减它。如果它是1，则只需将其从映射中删除。

要计算基数，请遍历地图并计算值的总和。

包含应该很简单，你只需要调用你的地图的方法。伯爵也应该很简单。

画画很有意思。首先，计算基数，将其用作随机化的无法到达的上限，并初始化一个总和并开始遍历地图。在每次迭代时，使用map条目的值增加sum（在循环之前为0）。如果随机数小于sum，则调用remove传递项的键并退出循环。

编辑

如果你需要使用一个String项数组来执行此操作，那么你可以这样做，但是你还需要为每个String存储一个整数，这将是另一个数组，最简单的表示是确保每个项目中的每个项目。字符串数组将与同一索引处的int数组中的int值相关联。不太优雅，但可以使用。现在，在这种情况下，您无法使用Map方法，但需要自己实现。