辅导program编程、讲解c++，Python程序设计、Java编程调试
- 首页 >> Matlab编程 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
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