C++代写：CMPT115 Huffman Tree Part3|留学生CS代写|代做Java编程|C作业|C++程序|Python代码

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:

Walk through the message, character by character, counting how many times each character is used. Use an integer array for this.
Once the whole message has been seen, use the array to build a Frequency record for each character seen at least once.
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.
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:

1	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:

1	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

Complete createFrequencyList() as indicated.
Build the testADT app, and run it.
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

Complete remove_smallest() as indicated.
Build the testADT app, and run it.
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

Complete createHuffmanTree() constructor as indicated.
Build the testADT app, and run it.
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.