The Huffman tree algorithm uses a list of trees, each tree storing a number of F
ID: 3681010 • Letter: T
Question
The Huffman tree algorithm uses a list of trees, each tree storing a number of Frequency records. The way we’ll manage this list is to build a “wrapper” ADT around the List ADT. The file FrequencyList.cc contains the implementation of this wrapper ADT. Notice that most of the List operations are simply delegations to the contained List. We want to give the wrapper a new constructor operation, and a new operation called remove_smallest(), which is the next exercise. Because these are very specific operations for the Huffman tree algorithm, it is better to build a wrapper ADT than to put these special purpose operations in the List ADT. The FrequencyList constructor currently looks like this:
// createFrequencyList(message)
// Pre: message:: refToChar, the message to be encoded
// Return: a reference to the generated list.
// post: a new list is allocated
// return: reference to the new list
FrequencyList *createFrequencyList(const char* message){
if (message == NULL) {
cerr << "Error in createFrequencyList(): NULL message!" << endl;
return NULL; } // TODO: complete this function return NULL; }
The constructor should do the following:
1. Walk through the message, character by character, counting how many times each character is used. Use an integer array for this.
2. Once the whole message has been seen, use the array to build a Frequency record for each character seen at least once.
3. Build a TreeNode for each Frequency record, and then store the TreeNode in the List. Each Tree will be a leaf node for now. We’ll use the initialized list in a later exercise.
4. Return the FrequencyList full of TreeNodes.
Explanation / Answer
****************************************************************************** * Compilation: javac Huffman.java * Execution: java Huffman -Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.