C++代写：CMPT115-Huffman-Tree-Part2

Exercise 1 Warmup: Completing Frequency.cc

We’ll use the Frequency ADT to store a character, e.g., ‘a’, and a count of how many times it appears in some text, e.g., 7. The frequency record will be stored in the Huffman trees.

The Frequency interface is complete, and defined in Frequency.h. It’s basically a storage unit for characters and integers. The implementation is almost complete, but the constructor, createFrequency() is incomplete. Here’s what is in the Frequency.cc file:

// CONSTRUCTOR
// pre: d is the character data being counted,
//      c is the count.
// post: allocates memory for a new frequency record
// return: a reference to the new record
Frequency *createFrequency(char d, int c) {
  // TODO: complete this function
  return NULL;
}

It currently does nothing. Complete this operation, by allocating a record, and storing the appropriate data.

Exercise Summary

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

What to hand in:

The file Frequency.cc containing your code for createFrequency() described above.

Grading

5 marks: createFrequency() builds a Frequency record and correctly initializes it with the given data.

Exercise 2 Warmup: Completing TreeNode.cc

We’ll use the TreeNode ADT to help us build Huffman trees. In our application, a TreeNode will store a reference to a Frequency record; see TreeNode.h and TreeElement.h. Most of the TreeNode implementation is complete. There are two operations that are currently incomplete: the constructor, createTreeNode(), and the operation height().

The constructor currently looks like this:

// CONSTRUCTOR
// pre: d is a reference to a TreeElement
// post: allocates memory for the TreeNode
// return: reference to the TreeNode record
TreeNode *createTreeNode(TreeElement d){
  // TODO: complete this function
  return NULL;
}

Complete it so that it allocates a correctly initialize TreeNode record.
The height operation currently looks like this:

// height(n)
// pre: n is a reference to a TreeNode
// return: the height of the tree
int height(TreeNode *n){
  // TODO: complete this function
  return 0;
}

Complete this function so that it returns the height of a tree whose root is given as the parameter n.
Hints:

• This function must be recursive.
• The height of a NULL tree is 0.
• There is a function called max(a,b) you can use. It returns the larger of a or b. This function is defined in a C++ library called “algorithm” which we’ve already #included for you.

Exercise Summary

1. Complete createTreeNode() as indicated.
2. Complete height() as indicated.
3. Build the testADT app, and run it.

If your code does the right things, tests 5-16 should all report “Passed.”

What to hand in:

The file TreeNode.cc containing your code for the two operations described above.