C++代写：CMPT115 Huffman Tree Part2

发表于   |   分类于

Introduction

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

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:

1
2
3
4
5
6
7
8
9
// 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:

1
2
3
4
5
6
7
8
// 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:

1
2
3
4
5
6
7
// 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.
  4. 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.

Grading

  • 5 marks: createTreeNode() builds a TreeNode record and correctly initializes it with the given data.
  • 5 marks: height() correctly calculates the height of a Tree.

Exercise 3 Warmup: Completing List.cc

The file List.cc contains the implementations for Lists and Iterators. We’ve combined them into one file so that there would be fewer files to manage. They are also very strongly coupled ADTs, so having them in one file is not really a design problem. The List ADT uses a simple ListNode chain to store Elements.
All the List and Iterator implementations are complete, except for the remove() operation.
The purpose of the remove() is to remove the given element from the list. If the removal was successful, return true.
The remove() operation is as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// remove(l,d)
// pre: l is a reference to a List
// d is a an Element
// post: removes the given element d if it was in the list
// return: true if the element was successfully removed,
//         false otherwise
bool remove(List *l, Element toRemove){
  // check error condition first
  if (l == NULL) {
    cerr << "Error in remove(List): given a NULL list!"
    << " Returning false, but anything could happen!"
    << endl;
  return false;
}
  // TODO: complete this function
  return false;
}

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 false. That’s where you put the code to remove the given Element from the chain of List nodes. Assume that the Elements can be compared for equality using ==. We’ll be storing references as Elements, so this will work. Don’t try to deallocate the removed Element. In a later exercise, we’ll see how remove() is called.

Exercise Summary

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

What to hand in:

The file List.cc containing your code for the remove() operation described above.

Grading

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