Java代写:CSE274 Bags

ADT里面Array和List,实现Bag Class的方法。

Array

Outcomes

  • Implement an ADT (specifically a resizable array and Linked List based implementation of the Bag ADT)
  • Test a class

General requirements (not following any of these could result in a score of 0):

  • The Eclipse project name must be Project3
  • You will write exactly two source code files: ArrayBag.java, LinkedBag.java and BagTester.java
  • You will also need to include the Bag interface as specified in BagInterface.java. Do not modify this file. Your resizable array bag and Linked List bag must implement this interface.
  • You will use the default package (this means there should be no package statements in any of your files).

Specific requirements

For this homework, you will implement Bag ADT for String objects in two ways: using a resizable array, and using linked nodes. Bag is similar to Set except that duplicates are allowed. In fact, sometimes bags are referred to as “multisets”

Highlights of the Bag ADT:

  • Order is unimportant (and unpredictable)
  • Duplicates are allowed
  • We want to be able to:
    • Add items to the bag
    • Remove items (2 ways…remove a specific item, and remove an arbitrary item)
    • Find the size
    • Check if an item is in the bag
    • Count the number of times an item is in the bag
    • Remove duplicates from the bag
    • Check if this bag contains all the elements that are in another bag (ignoring duplicates)
    • Check if this bag contains exactly the same elements as those in another bag (since order is unimportant, if 2 bags contain the same elements but in a different order, they are considered the same).

Note: even though order is unimportant in a bag, you should not change the order of the elements except in methods that are supposed to add or remove items.

ArrayBag

  1. In a class named ArrayBag, implement the Bag interface found in BagInterface.java.
  2. Your implementation will use a resizable array that doubles in size any time an item is added when the array is already full. Do not use Java’s ArrayList or any other Java collections except arrays. You should simply work with an array, and handle the array resizing on your own. For this method, you should use your own resizing algorithm, rather than Arrays.copyOf().
  3. Any time the number of entries in the bag drops to less than half the size of the array, reduce the size of the array to half its size. So, for example, if the array has a size of 20, and there are 11 items in it, and one of those items is removed, the array should still be a size of 20. BUT, if another item is removed, there will be only 9 items remaining. Since 9 is less than half the size of the array, reduce the size of the array to 10. However, do not reduce the size of the array if it would cause the size of the array to be less than 5. For this method, use Arrays.copyOf() to handle the resizing.
  4. The only instance variables should be the array, and an int representing the size of the bag.
  5. There should be two constructors:
    • a. A constructor with no parameters. By default, this should use an array instance variable with a starting size of 10.
    • b. A constructor with an int parameter specifying the initial capacity of the array instance variable. If the parameter is less than 5, throw an IllegalArgumentException.
  6. The remove() method should remove some item from the bag (the client does not care which). So, you get to choose what to return. Choose so that your remove() method has O(1) time complexity.

LinkedBag

  1. In a class named LinkedBag, implement the Bag interface found in BagInterface.java.
  2. LinkedBag should not use any arrays, except when returning the array in toArray().
  3. LinkedBag class should contain a private inner Node class.
  4. The only instance variables should be a node representing the start, or head, of the nodes, and an int representing the size of the bag.
  5. There should be one constructor: A no-parameter constructor that creates an empty bag.
  6. The remove() method should remove some item from the bag (the client does not care which). So, you get to choose what to return. Choose so that your remove() method has O(1) time complexity.

Some notes

  1. Read over the interface comments carefully, especially for the containsAll() and sameItems() methods. These contain examples to help clarify what these methods do.
  2. Notice that the parameter type for containsAll() and sameItems() is BagInterface. You should use that type in your implementation. This is important to understand: the parameter will be a bag, but it could be a linked bag or an array bag or some other implementation. So, your solution to these methods should not rely on using the nodes or the array directly. Rather, you should be relying only on other methods in BagInterface to solve these methods.
  3. Since BagInterface is already well commented with Javadoc comments, it is not necessary to add Javadoc comments to those methods in your implementations. HOWEVER, you should still document each class with a description of your implementation, and your name, date, etc.

What you need to do

  • You are responsible for implementing and testing all the methods.

What to do when you are done

  • Submit a zip of the src folder containing your java files to the appropriate assignment on Canvas.

Deductions

  • Code not formatted using standard formatting guidelines: -3 (you can avoid this by using Eclipse’s built-in code formatting tool)
  • Code missing standard comments at the top: -3 (this should include your name, date, and a description of your implementation)