CS 215 - Fundamentals of Programming IISpring 2010 - Project 730 pointsOut: April 14, 2010Due: April 26, 2010 (Monday, last day of class)This project is to build a Morse code tree and use it to encode and decode messages. Morse CodeMorse code was developed for sending messages across telegraphic wires. The code consists of patterns of short and long elements often called dots and dashes, respectively. Each letter, digit, and symbol is assigned a specific pattern of dots and dashes. The Morse code can be represented using a binary tree where the left branches represent a dot and the right branches represent a dash.For example, here is a portion of the Morse code tree:The code for each character is a string formed by appending a '.' when taking a left branch and a '-' for a right branch when traversing the path from the root to the node containing the letter. In the codetree above, the code for 'r' is ".-." (left, right, left), the code for 'm' is "--" (right, right), and the code for 'a' is ".-" (left, right). A message is encoded by giving a sequence of codes for the letters in the message. Since Morse code does not have a prefix property (that is, a sequence of elements that represents one character may be a prefix of a longer sequence for some other character, e.g., the codes for 'm' and 'g'), there is a space between each character code. For example, the Morse code for the message "ram" is ".-. .- --", which is formed by listing the codes for 'r', 'a', and 'm' separated by spaces. Since a space is used to separate character codes, an actual space between words will be represented in the code as '|'. Likewise a newline will be represented in the code as "||". (In actual Morse code, words and sentences are separated by longer silences than the silence between characters, but we do not want to count spaces for this project.) Thus if the message "garment ten" is followed by a newline, our Morse code for the message would be --. .- .-. -- . -. - | - . -. ||For this project, you will be given codefiles containing the Morse code. Your assignment is to write a MorseTree class (specification given below) that can read a codefile and construct a codetree for use in encoding and decoding messages, and write a (main) program to encode and decode messages using a MorseTree object. 04/13/2010 Page 1 of 6e ta n mr gTnode struct This project assumes the Tnode<T> structure definition of Chapter 10 of the textbook (page 511) as used in lecture. Since it is a template, the definition should be placed outside and before the MorseTree class definition in the morse.h header file. Specifications for MorseTree Class Note: this is not a template class, though it does use the Tnode structure template from the textbook. Attributes There is only one attribute of this class, a single Tnode<char> pointer variable that points to the root of the constructed codetree. Operations Explicit-value constructor - builds the codetree from an input stream connected to a codefile. Assumes that the stream is valid.● Analysis Objects Type Kind Movement Nameinput stream connected to codefile istream variable received & passed back codeFileThe codefile will consist of an integer n, followed by n lines of the form letter code where code is the Morse encoding for letter. The constructor is to read the codefile and build the codetree. For example, the codefile for the codetree above would be:7a .-e .g --.m --n -.r .-.t -The basic algorithm is to read each letter (as a character) and its code (as a string) and use the code to traverse the tree (starting with the root) as one would do when decoding. If an interior node does not exist, create it and continue. When the end of the code is reached, you are at the node that stores the letter.Copy constructor - creates a copy of the original MorseTree using the CopyTree function ● Analysis Objects Type Kind Movement Nameoriginal tree MorseTree variable received originalCopyTree - private recursive helper function to copy a tree (page 529 of textbook) that returns the root of the copy. ● Analysis04/13/2010 Page 2 of 6Objects Type Kind Movement Nameroot of tree to copy Tnode<char>* variable received rootroot of copy Tnode<char>* variable returned copyRootDestructor - deletes MorseTree nodes using DeleteTree function ● Analysis - no objects DeleteTree - private recursive helper function to delete tree nodes (page 530 of textbook) ● Analysis Objects Type Kind Movement Nameroot of tree to delete Tnode<char>* variable received rootoperator= - assignment operator, make this MorseTree the same as the original MorseTree using both DeleteTree and CopyTree, returns a reference to this object ● Analysis Objects Type Kind Movement Nameoriginal tree MorseTree variable received originalthis tree MorseTree & variable returned *thisWriteTree - writes out the codetree "sideways" to an output stream using WriteTreeHelper function. Assumes the stream is valid. ● Analysis Objects Type Kind Movement Nameoutput stream ostream variable received & passed back outWriteTreeHelper - private recursive helper function to write out the codetree to an output stream using RNL traversal (right, visit node, left).● Analysis Objects Type Kind Movement Nameoutput stream ostream variable received & passed back outroot of tree to write Tnode<char>* variable received rootnumber of spaces to indent int variable received indent04/13/2010 Page 3 of 6By using a RNL traversal with indenting, the tree will be written "sideways" with the root on the left side of the output. Each node value should be written on a separate line in a field of indent number of spaces. (Use setw() from <iomanip> to do this.) In order for the tree to "look right" on the screen, an extra newline should be output before the first recursive call and after the second recursive call when the indent number is less than or equal to 16. The recursive calls to WriteTreeHelper should increase the indenting by 8 spaces. For example, the codetree above would print out as follows (the * marks the root of the tree and left edge of the display, and there are three blank lines before and after the tree). m g t n* a r eEncode - encodes message from an input stream, writing results to an output stream, using CharToCode. Assumes the streams are valid. ● Analysis Objects Type Kind Movement Nameinput stream connected to message
View Full Document
Unlocking...