代写program编程、代做c++，Python程序设计、Java编程调试

日期：2021-04-26 11:23

Part II

60 points total

Preparing for Part II

Begin by downloading the following zip file: ps8.zip

Unzip this archive, and you should find a folder named ps8, and within it the files you will need for Part II.

Keep all of the files in the ps8 folder, and open that folder in VS Code using the File->Open Folder or File->Open menu option.

Problem 5: Binary tree iterator

25 points; pair-optional

This is the only problem of the assignment that you may complete with a partner. See the rules for working with a partner on pair-optional problems for details about how this type of collaboration must be structured.

The traversal methods that are part of the LinkedTree class are limited in two significant ways: (1) they always traverse the entire tree; and (2) the only functionality that they support is printing the keys in the nodes. Ideally, we would like to allow the users of the class to traverse only a portion of the tree, and to perform different types of functionality during the traversal. For example, users might want to compute the sum of all of the keys in the tree. In this problem, you will add support for more flexible tree traversals by implementing an iterator for our LinkedTree class.

You should use an inner class to implement the iterator, and it should implement the following interface:

public interface LinkedTreeIterator {

   // Are there other nodes to see in this traversal?

   boolean hasNext();

   // Return the value of the key in the next node in the

   // traversal, and advance the position of the iterator.

   int next();

}

There are a number of types of binary-tree iterators that we could implement. We have given you the implementation of a preorder iterator (the inner class PreorderIterator), and you will implement an inorder iterator for this problem.

Your inorder iterator class should implement the hasNext() and next() methods so that, given a reference named tree to an arbitrary LinkedTree object, the following code will perform a complete inorder traversal of the corresponding tree:

LinkedTreeIterator iter = tree.inorderIterator();

while (iter.hasNext()) {

   int key = iter.next();

   // do something with key

}

Important guidelines

?In theory, one approach to implementing a tree iterator would be to perform a full recursive traversal of the tree when the iterator is first created and to insert the visited nodes in an auxiliary data structure (e.g., a list). The iterator would then iterate over that data structure to perform the traversal. You should not use this approach. One problem with using an auxiliary data structure is that it gives your iterator a space complexity of O(n), where n is the number of nodes in the tree. Your iterator class should have a space complexity of O(1).

?Your iterator’s hasNext() method should have a time efficiency of O(1).

?Your iterator’s constructor and next() methods should be as efficient as possible, given the time efficiency requirement for hasNext() and the requirement that you use no more than O(1) space.

?We encourage you to consult our implementation of the PreorderIterator class when designing your class. It can also help to draw diagrams of example trees and use them to figure out what you need to do to go from one node to the next.

Here are the tasks that you should perform:

1.Review the code that we’ve given you in the PreorderIterator class and the preorderIterator() method, and understand how that iterator works. It’s worth noting that you can’t actually use a PreorderIterator object yet, because it will only work after you have completed the next task.

To assist you in the process of reviewing the PreorderIterator class, we have created an overview of that class that we encourage you to read.

2.In order for an iterator to work, it’s necessary for each node to maintain a reference to its parent in the tree. These parent references will allow the iterator to work its way back up the tree.

In the copy of LinkedTree.java that we’ve given you for this assignment, the inner Node class includes a field called parent, but the LinkedTree code does not actually maintain this field as the tree is updated over time. Rather, this parent field is assigned a value of null by the Node constructor, and its value remains null forever.

Before implementing the iterator, you should make whatever changes are needed to the existing LinkedTree methods so that they correctly maintain the parent fields in the Node objects.

?For example, when a Node object is first inserted in the tree, you should set its parent field to point to the appropriate parent node.

?Think about when the parent of a node can change, and update the necessary method(s) to modify the parent field in a Node object whenever its parent changes.

?The root of the entire tree should have a parent value of null.

3.Next, add a skeleton for your iterator class, which you should name InorderIterator (note that only the two Is are capitalized). It should be a private inner class of the LinkedTree class, and it should implement the LinkedTreeIterator interface. Include whatever private fields will be needed to keep track of the location of the iterator. Use our PreorderIterator class as a model.

4.Implement the constructor for your iterator class. Make sure that it performs whatever initialization is necessary to prepare for the initial calls to hasNext() and next().

In the PreorderIterator constructor that we’ve given you, this initialization is easy, because the first node that a preorder iterator visits is the root of the tree as a whole. For an inorder iterator, however, the first node visited is not necessarily the root of the tree as a whole, and thus you will need to perform whatever steps are needed to find the first node that the inorder iterator should visit, and initialize the iterator’s field(s) accordingly.

5.Implement the hasNext() method in your iterator class. Remember that it should execute in O(1) time.

6.Implement the next() method in your iterator class. Make sure that it includes support for situations in which it is necessary to follow one or more parent links back up the tree, as well as situations in which there are no additional nodes to visit. If the user calls the next() method when there are no remaining nodes to visit, the method should throw a NoSuchElementException.

7.Add an inorderIterator() method to the outer LinkedTree class. It should take no parameters, and it should have a return type of LinkedTreeIterator. It should create and return an instance of your new class.

8.Test everything! At a minimum, you must do the following: In the main() method, add a unit test that uses the while-loop template shown near the start of this problem to perform a full inorder traversal of a sample tree.

Problem 6: Implementing a hash table using separate chaining

35 points; individual-only

In lecture, we discussed the following interface for a hash table ADT:

public interface HashTable {

   boolean insert(Object key, Object value);

   Queue<Object> search(Object key);

   Queue<Object> remove(Object key);

}

We also examined one implementation of this interface that uses open addressing (the OpenHashTable class that we’ve included in the ps8 folder).

In this problem, you will complete another implementation of this interface – one that uses separate chaining instead of open addressing. Its class will be called ChainedHashTable.

We have given you a skeleton for this class in the ps8 folder. It includes two private fields:

?one called numKeys for the number of keys in the hash table

?one called table that holds a reference to the array that you will use for the hash table. However, rather than having each element of the array store a single entry as we do in open addressing, each element of the array must serve as a bucket or chain of entries.

We have given you a private inner class called Node for the nodes in each chain. Each element of the table array must hold a reference to the first node in its linked list of nodes, and you will need to create and manipulate these nodes within your hash table methods.

Each Node object has fields that allow it to store:

?a single key

?the collection of values associated with that key, using an instance of our LLQueue class

?a reference to the next node in the linked list (if any).

We have also given you:

?a copy the h1() method from our OpenHashTable class, which you must use as the hash function of your implementation (Note: Because separate chaining allows all entries whose keys are hashed to a given position in the table to stay in that position, you will not need to perform any probing. As a result, you won’t need the second hash function h2() from OpenHashTable.)

?a toString() method that will allow you to see the current contents of the table. It returns a string of the form

?[table[0], table[1], ..., table[size - 1]]

where each position of the table is represented by either:

?the key or keys in that position’s chain of entries, separated by semi-colons and surrounded by curly braces.

?the word null if there are no keys in that position.

Your tasks

1.Review all of the provided code, and make sure that you understand it.

2.Add a constructor that takes the size of the hash table as its only parameter and initializes the hash table accordingly. It should throw an IllegalArgumentException if the size is not positive.

3.Implement each method from the HashTable interface as efficiently as possible. Make sure that each of these methods has the same basic functionality as the corresponding method from the OpenHashTable class discussed in lecture. In particular, they should throw exceptions for the same reasons that the OpenHashTable methods do.

As you add or remove items from the table, make sure that you update numKeys accordingly.

Because a given chain can grow to an arbitrary length, the hash table will never overflow, and thus your insert method can always return true.

For example, if you run this test code:

ChainedHashTable table = new ChainedHashTable(5);

table.insert("howdy", 15);

table.insert("goodbye", 10);

System.out.println(table.insert("apple", 5));

System.out.println(table);

you should see:

true

[{apple; howdy}, null, null, {goodbye}, null]

Note that:

?Position 0 has a chain with two keys, because both "howdy" and "apple" are assigned a hash code of 0 by h1() when the table size is 5.

?Position 3 has a chain with one key, because "goodbye" is assigned a hash code of 3 by h1() when the table size is 5.

4.Define an accessor method for the number of keys. Call this method getNumKeys(). For example, this test code:

5.ChainedHashTable table = new ChainedHashTable(5);

6.table.insert("howdy", 15);

7.table.insert("goodbye", 10);

8.table.insert("apple", 5);

9.System.out.println(table.getNumKeys());

10.table.insert("howdy", 25);     // insert a duplicate

11.System.out.println(table.getNumKeys());

should print:

3

3

because inserting a duplicate does not change the number of keys.

12.Although a hash table that uses separate chaining won’t overflow, it can become too full to offer decent performance. To allow clients to measure the degree of fullness, add a method called load() that takes no parameters and that returns a value of type double that represents the load factor of the table: the number of keys in the table divided by the size of the table.

For example, this test code:

ChainedHashTable table = new ChainedHashTable(5);

table.insert("howdy", 15);

table.insert("goodbye", 10);

table.insert("apple", 5);

System.out.println(table.load());

table.insert("pear", 6);

System.out.println(table.load());

should print:

0.6

0.8

13.To allow clients to obtain all of the keys in the hash table, add a method called getAllKeys() that takes no parameters and that returns an array of type Object containing all of the keys in the hash table.

For example, the following test code:

import java.util.*;

ChainedHashTable table = new ChainedHashTable(5);

table.insert("howdy", 15);

table.insert("goodbye", 10);

table.insert("apple", 5);

table.insert("howdy", 25);    // insert a duplicate

Object[] keys = table.getAllKeys();

System.out.println(Arrays.toString(keys));

should print:

[apple, howdy, goodbye]

14.To deal with situations in which the table becomes too full, add a method called resize() that takes an integer representing the new size, and that grows the table to have that new size. It should not return a value.

As discussed in lecture, it is not possible to simply copy every element of the current table into a new, larger table. This is because a given key may belong in a different position in the larger table. As a result, you will need to rehash the current keys in the hash table to ensure that they end up in the correct position in the resized table.

For example, the following test code:

ChainedHashTable table = new ChainedHashTable(5);

table.insert("howdy", 15);

table.insert("goodbye", 10);

table.insert("apple", 5);

System.out.println(table);

table.resize(7);

System.out.println(table);

should print:

[{apple; howdy}, null, null, {goodbye}, null]

[null, {apple}, null, null, null, {howdy}, {goodbye}]

Note that in this case, resizing the table causes all three keys to end up in different positions!

Special cases:

?The method should throw an IllegalArgumentException if the specified new size is less than the table’s current size.

?If the specified new size is the same as the table’s current size, the method should return without doing anything.

15.Add a main() method that performs at least two unit tests for each of the methods in the class. Use the same unit-test format that we specified in Problem 8 of Problem Set 7.