聯系方式

您當前位置:首頁 >> Python編程Python編程

日期:2019-07-30 10:04

CSE 274

Summer 2019

Project #5

Hash Table with Separate Chaining and Trees

There are 2 parts to this assignment: Complete the set that uses a hash table implementation using separate chaining

Implement several tree processing algorithms

1. (70 pts) HashTable Implementation. Do not use any standard Java collection classes (e.g., TreeSet,

TreeMap, HashSet, etc.) for this work.

Submit a HashedSetSC.java and Car.java.

a. (5 pts) Create a class to represent a car - Car - that year (int), make (String), model (String), and color

(String). Car should override the equals and hashCode methods.

b. (65 pts) Create a class - HashedSetSC - that implement a set using a hash table. Assume that the

data type being stored has proper equals and hashCode methods defined. HashedSetSC class

will be similar to the HashedDictionary class presented in the textbook but will use separate

chaining to resolve collisions. Another difference is that your class will not be a dictionary (i.e., key-value

pairs), instead it will be used to represent a set.

The individual buckets must be implemented using your list implementation other than a Java standard

list. It is suggested that you use LinkedListWithIterator class defined in the

ListImplementation project.

Notes:

● Your hashed set implementations must implement the SetInterface used in a previous

project.

● Allocating and using the hashTable array will differ from the textbook’s examples. This is

because of Java’s peculiar behavior with arrays of generic structures. The rough outline of the

class will be:

public class HashedSetSC<T> implements HashedSetSC {

private LinkedListWithIterator<T> [] hashTable;

private final int INIT_CAPACITY = 71;

@SuppressWarnings("unchecked")

public HashedSetSC() {

hashTable = (LinkedListWithIterator <T>[])new LinkedListWithIterator<?>[INIT_CAPACITY ];

...

}

}

2. (30 pts) Tree Processing. In the TreeImplementation project, add and implement the following methods to the

BinaryTree class.

a. (10) public T getMaxLeaf() // returns largest leaf value

b. (10) public Set<T> getLeaves() // returns all leaf values

c. (10) public boolean isBalanced()


版權所有:編程輔導網 2018 All Rights Reserved 聯系方式:QQ:99515681 電子信箱:[email protected]
免責聲明:本站部分內容從網絡整理而來,只供參考!如有版權問題可聯系本站刪除。

黑龙江体彩22选5