C++代写：CMPT115HuffmanTreePart3

Introduction

这是Huffman作业的第三部分，同样分为三个小练习。

Exercise 4 Constructor for FrequencyList

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.
   In the lecture slides on Huffman trees, the character and frequency data were
   attributes of the Tree record itself.
   In this assignment, we are using Frequency records to store the character and
   frequency values. This adds another ADT to think about, but it allows us to
   reuse the ordinary tree that simply stores a single Element. This is good
   software reuse (of Trees) and adaptability: if we want to store other data in
   the Tree, we can change the Frequency ADT, and most if not all of the rest of
   the application would not need to change.

Hints on counting characters

Each character you can type or use on a computer has an integer value; for
letters and digits and normal keyboard symbols, this is called the ASCII
value. For example, the letter ‘c’ has an ASCII value of 99. Because of this,
we can use a character as an index into a characeter count array like this:
counts[‘c’]. We can do this for any character, whether it’s ‘c’ or ‘&’.
To calculate the frequency of each letter in a message, we use an array of
counts (initialized to 0). Each time we observe a character in a message, we
can increase its count. For example to increase the count for the letter ‘c’,
we would do the following:
counts[‘c’] += 1;
—|—
This will increase the count of the integer at index 99 (the one corresponding
to the letter ‘c’). The letter ‘c’ is the 99th character in the ASCII
character set, and its counter is the 100th in our counts array. To initialize
the counts array, we have the following:
int counts[ASCII_SIZE]; // ASCII_SIZE is defined in LOCALE.h
for (int i = 0; i < ASCII_SIZE; i++) {
counts[i] = 0;
}
—|—
Here we’re using integers, not characters, to index into the array. This is
okay, because in a sense, characters are integers. Characters have special
status when we want to think of them as characters, but they also have integer
values which we use when that’s handy.
One problem remains: with compiler flags -Wall and -pedantic, the compiler may
complain when you use a character as an array index:
warning: array subscript has type ‘char’ [-Wchar-subscripts]
To get rid of these warnings, we can use a technique called typecasting.
Typecasting tells the compiler to treat a variable of one type as though it
has a different type. For example, we can typecast a character to an integer
as follows:
counts[(int) ‘c’] += 1;
—|—
The use of (int) in brackets in front of a value tells the compiler that it’s
not a mistake to try to use the value ‘c’ as an integer (99). Typecasting can
also be done when you want to force a float to be truncated into a integer, or
something like that. We’ll only use it for characters in this asignment.

Exercise Summary

1. Complete createFrequencyList() as indicated.
2. Build the testADT app, and run it.
3. If your code does the right things, tests 33-34 should all report “Passed.”

What to hand in:

The file FrequencyList.cc containing your code for the createFrequencyList()
constructor described above.

Grading

• 4 marks: createFrequencyList() correctly counts characters in the given C-string.
• 2 marks: createFrequencyList() correctly creates a Frequency record for each character appearing 1 or more times in the given C-string.
• 2 marks: createFrequencyList() correctly creates a TreeNode for each Frequency record
• 2 marks: createFrequencyList() correctly creates a List to store these TreeNodes
• 2 marks: createFrequencyList() correctly puts all the TreeNodes into the List
• 2 marks: createFrequencyList() correctly returns the FrequencyList.

Exercise 5 Completing FrequencyList.cc

The FrequencyList ADT is a wrapper for the List ADT, because it does
specialized things that normal lists don’t do. One of the things we want
FrequencyList to do is to remove the smallest TreeElement in its list.
The operation remove_smallest() appears in the implementation, but it is
incomplete.
// remove the smallest frequency tree from the list
// Pre: l is a list containing Trees of Frequencies.
// Post: the tree with smallest frequency has been removed
// from the list.
// return: the Tree with smallest frequency in List l.
// Will return NULL if the list was empty.
TreeNode *remove_smallest(FrequencyList *l) {
if (l == NULL) {
cerr << “Error in remove_smallest: given NULL list”
<< “ Returning NULL, but anything could happen.”
<< endl;
return NULL;
}
// TODO: complete this function
return NULL;
}
—|—
Notice the “TODO” in the comment near the bottom. Right now, the operation
checks if the given list is NULL. After the TODO, it does nothing except
return NULL.
Your job is to complete this function. It will remove and return a tree record
that has the smallest frequency. You’ll use this function repeatedly in your
Huffman tree algorithm, in a later exercise.

Hints

• Use an Iterator to find the Tree record with the smallest frequency in it. If there is more than one Tree with the smallest value, it doesn’t matter which one you return.
• Once you find the Tree with the smallest frequency, you should remove it from the list (In an previous exercise, you implemented is a List operation called remove() for exactly this purpose).
• Remember that the List record stores TreeNode records, and the TreeNode record contains a Frequency record; it’s the Frequency record that knows the frequency that you should be looking at to see which tree is smallest. You’ll have to dig into these records; use the ADT operations!

Exercise Summary

1. Complete remove_smallest() as indicated.
2. Build the testADT app, and run it.
3. If your code does the right things, tests 35-41 should all report “Passed.”

What to hand in:

The file FrequencyList.cc containing your code for the remove_smallest()
operation described above.

Grading

• 10 marks: remove_smallest() correctly removes the given TreeElement from the List.

Exercise 6 Building a Huffman Tree

In the file Huffman.cc, there are two ADTs defined. The first is the Huffman
Tree. The Huffman Tree has a very simple interface: there is only a
constructor, but no other operations.
The Huffman Tree constructor take a FrequencyList as input. As we saw in
lecture, the algorithm for building a Huffman Tree is discussed in the Hints
below. Here’s the current constructor:
// createHuffmanTree(frequencies)
// Pre: frequencies is a reference to a FrequencyList
// Post: allocates a new HuffmanTree record
// return: a reference to the Huffman tree, if the list is not empty
HuffmanTree *createHuffmanTree(FrequencyList *frequencies) {
// TODO: complete this function
return NULL;
}
—|—
Your job is to complete this function.

Hints

The Huffman algorithm removes the two smallest trees in the list, and you can
call remove_smallest() twice in a row. You have to create a new TreeNode
record with these two tree records as subtrees, and put it into the list.
Remember that each TreeNode stores a Frequency record. Each time you take two
Treenodes out of the FrequencyList, you have to create a new Trenode with a
new Frequency record; the new Frequency record needs a character, but the
character is not important (use any character). Note: the frequency has to be
the sum of the frequencies of the two TreeNodes you removed (the two
smallest). When there is exactly record left in the list, it is the final
tree, and you should return it.
There is an example of the algorithm visually on the Moodle page. There may be
ties when seeking the two smallest trees; using any of the smallest trees is
correct. The new TreeNode you create has 2 subtrees, but it doesn’t matter
which one is left or right. For these reasons, there may be many correct
Huffman trees for any given message.

Exercise Summary

1. Complete createHuffmanTree() constructor as indicated.
2. Build the testADT app, and run it.
3. If your code does the right things, tests 42-45 should all report “Passed.”

What to hand in:

The file Huffman.cc containing your code for the constructor described above.

Grading

• 4 marks: createHuffmanTree() repeatedly removes the two smallest subtrees in the FrequencyList.
• 4 marks: createHuffmanTree() correctly builds a new TreeNode from these two subtrees.
• 2 marks: createHuffmanTree() correctly puts the new TreeNode into the FrequencyList.
• 2 marks: createHuffmanTree() correctly terminates when there is exactly 1 TreeNode in the FrequencyList.
• 2 marks: createHuffmanTree() correctly returns a newly allocated HuffmanTree record containing the TreeNode.