THE FINAL programming project for this term is a rather large, two-part assignment. The first part, a short exercise involving binary sort trees, will count for five points. The second part, a long exercise involving lists and some advanced aspects of C++ classes, will count for 15 points. The project is due on the last day of class, Monday, April 28. Please turn in printouts of your solutions to both parts of the project on that day. We will talk about both parts of the project in class before you start work on them.
In Assignment 4, you wrote a program that used arrays to decode a Morse code message. You should re-do that assignment, using a binary sort tree to store the code, rather than an array. A solution to the original problem is available in the file /home/cs225/showMessage.cc. You can use that solution as a starting point, instead of your own solution, if you like. You will also find useful the sample program /home/cs225/wordlist_tree.cc. This program uses a binary sort tree to store information about words and word frequencies. What you have to do is very similar: Use a binary sort tree to store code words and the encoded characters that they represent. Note that you will also need the files /home/cs225/code.dat and /home/cs225/message.dat, which hold the code and the encoded message. You can use the following type to represent nodes in your tree:
struct TreeNode {
string code; // The code string for a character.
char ch; // The un-encoded character.
TreeNode *left, *right; // Standard tree pointers.
};
You will need a function to insert a given code string and its corresponing char into the tree, and you will need a function to search the tree for a given code string.
The second part of the project is to write an implementation file for the header file /home/cs225/Polynomials.h. This file defines a class named Polynomial. An object belonging to this class represents a polynomial, such as 3*x^4+2*x^2-7. The class includes a copy constructor and various overloaded operators. Some of the operators are members of the class, while others are friend functions. The polynomials themselves are represented as linked lists. Each node in the linked list represents one term of the polynomial. A node is defined by the type:
struct TermNode { // Represents a term of the form k*x^n
double coefficient; // The coefficient, k, in this term.
unsigned int exponent; // The exponent, n, in this term.
TermNode *next; // Pointer to the next term.
};
You will need to use this definition in your implementation file. The hardest thing to implement will be the addTerm() function, but once you have that done you can use it as a basis for writing many of the other functions and operators. (The input operator << can also be tough, depending on how fancy you make it.) I suggest that you start by writing the basic constructor, the output operator >>, and the addTerm() function. Test them thoroughly before you try to do anything else! Then implement as many other features as you have time for. You will also need to write a main program to test your work. You might find some ideas from the sample program /home/cs225/wordlist_list.cc to be useful as you struggle to work with linked lists. You can get partial credit for a partially complete implementation.