PLEASE HELP ME COMPLETE THIS #include #include #include \"H

PLEASE HELP ME COMPLETE THIS #include <cstring> #include <iostream> #include \"H

ID: 3680944 • Letter: P

Question

PLEASE HELP ME COMPLETE THIS

#include <cstring>
#include <iostream>

#include "Huffman.h"

using namespace std;

// createHuffmanCodec(htree)
// Pre: htree is a reference to a HuffmanTree
// Post: allocates a new HuffmanCodec record
// return: a reference to the Huffman codec

HuffmanCodec *createHuffmanCodec(HuffmanTree *t) {
HuffmanCodec *hcdc = new HuffmanCodec;
hcdc->huffTree = t;

//initialize codebook
for (int i = 0; i < ASCII_SIZE; i++){
hcdc->codebook[i] = NULL;
}

// build the codebook using the Tree
char *acode = new char[height(t->root)+1];
find_codes(hcdc, t->root, acode, 0);
return hcdc;
}

// find_codes(codec,tree,store,index)
// recursively find Huffman codes from a given tree
// pre: codec is a reference to Huffman Codec
// tree is a reference to a TreeNode in the HuffmanTree
// store is a character array used to store partial solutions
// index is the next unused index in store
// post: the Huffman codes have been printed.
void find_codes(HuffmanCodec *hcdc, TreeNode *t, char s[], int d){
if (t == NULL){
return;
}
else if (isLeaf(t)){
s[d] = '';
hcdc->codebook[(int) getData(getData(t))] = copy(s);
}
else {
s[d] = '0';
find_codes(hcdc, getLeft(t), s, d+1);
s[d] = '1';
find_codes(hcdc, getRight(t), s, d+1);
}
}

// delete_huffman_helper(t)
// deallocate the huffman tree and frequency records
// Pre: t::refToTreeNode
// Post: the tree t and its subtrees have been deleted
// as well as their contents.
void delete_huffman_helper(TreeNode *t){
if (t == NULL){
return;
}
delete_huffman_helper(getLeft(t));
delete_huffman_helper(getRight(t));
//delete the Frequency record
delete getData(t);
//delete the current Tree node
delete t;
}

// DESTRUCTOR
// destroyHuffmanTree(ht)
// Pre: ht is a reference to a HuffmanTree
// Post: memory for ht is deallocated
void destroyHuffmanTree(HuffmanTree *ht){
delete_huffman_helper(ht->root);
delete ht;
}

// destroyHuffmanCodec(hcdc)
// Pre: hcdc is a reference to a HuffmanCodec
// Post: memory for ht is deallocated
void destroyHuffmanCodec(HuffmanCodec *hcdc){
destroyHuffmanTree(hcdc->huffTree);
for (int i = 0; i < ASCII_SIZE; i++){
if (hcdc->codebook[i] != NULL){
delete [] hcdc->codebook[i];
}
}
}

// decode_char(tnode, message, d){
// decode one character from the message.
// Pre: tnode is a node in a huffman tree
// message:: cstring, the whole message to decode
// d:: a reference to an int containing the current
// index in the message
// Post: d has been increased by the number of 0s and 1s used to
// encode the character
// Return: the decoded character
char decode_char(TreeNode *t, char message[], int *d){
// TODO: complete this function
return '.'; // dot returned for no good reason
}

// decode(hcdc, message)
// decode the given message
// Pre: hcdc is a reference to a HuffmanCodec
// message:: cstring containing the coded message
// return: a reference to a cstring containing the decoded message
char *decode(HuffmanCodec *h, char message[]){
int d = 0; // index for the coded message
int i = 0; // index for the de-coded message

// Note: We've simplified by using a fixed size array
// we could estimate the length of the message
// more accurately than this by using the length
// of the message to decode and the tree height.
char *decoded_msg = new char[MESSAGE_LIMIT];

// go through the whole message
while (d < strlen(message)){
// decode one character using the Huffman Tree
decoded_msg[i] = decode_char(h->huffTree->root, message, &d);
i++;
}
// ensure the C-string is properly terminated
decoded_msg[i] = '';

// then make a copy
char *result = copy(decoded_msg);
delete [] decoded_msg;
return result;
}

// eof

Explanation / Answer

main.cpp

#include <iostream>
#include "Huffman.h"

using namespace std;

// function to make testing a little neater
// Pre: passed is a boolean which is true if the test passed, and false if it didn't
void testDecider(int *number, int *nFailed, bool passed,
                 const char *testannounce, const char *iffailed) {
*number += 1;
cout << "Test " << *number << ": " << testannounce;
if (passed) {
    cout << "Passed!";
}
else {
    *nFailed += 1;
    cout << "Error: " << iffailed << " **** ";
}
cout << endl;
}

int testall(){
// ----------------------------------------------
// Testing Frequency ADT
// Try to create a frequency record
Frequency *freq_for_testing = createFrequency('f',5);
// test the frequency record
int testNumber = 0;
int testFailed = 0;
testDecider(&testNumber, &testFailed,
              getData(freq_for_testing) == 'f',
              "Frequency getData() ",
              "inconsistent character stored in Frequency record");
setData(freq_for_testing,'g');
testDecider(&testNumber, &testFailed,
              getData(freq_for_testing) == 'g',
              "Frequency setData() ",
              "setData() seemed to have no effect!");
testDecider(&testNumber, &testFailed,
              getCount(freq_for_testing) == 5,
              "Frequency getCount(): ",
              "inconsistent count stored in Frequency record");
setCount(freq_for_testing,6);
testDecider(&testNumber, &testFailed,
              getCount(freq_for_testing) == 6,
              "Frequency setCount(): ",
              "setCount() seemed to have no effect!");

if (testFailed > 10) return testFailed;

// ----------------------------------------------
// Testing TreeNode ADT
// Try to create a tree using the frequency record
TreeNode *tree_for_testing = createTreeNode(freq_for_testing);
testDecider(&testNumber, &testFailed,
              isLeaf(tree_for_testing),
              "TreeNode isLeaf(): ",
              "tree record should be a leaf, but isn't");
testDecider(&testNumber, &testFailed,
              getData(tree_for_testing) == freq_for_testing,
              "TreeNode getData(): ",
              "tree record should contain the frequency object, but doesn't");
testDecider(&testNumber, &testFailed,
              height(tree_for_testing) == 1,
              "TreeNode height(): ",
              "tree record should have height 1, but doesn't");
testDecider(&testNumber, &testFailed,
              getLeft(tree_for_testing) == NULL,
              "TreeNode getLeft(): ",
              "Unexpected left subtree not NULL");
testDecider(&testNumber, &testFailed,
              getRight(tree_for_testing) == NULL,
              "TreeNode getRight(): ",
              "Unexpected right subtree not NULL");

if (testFailed > 10) return testFailed;
TreeNode *another_tree = createTreeNode(createFrequency('x',12));
setRight(tree_for_testing, another_tree);
testDecider(&testNumber, &testFailed,
              getRight(tree_for_testing) == another_tree,
              "TreeNode setRight(): ",
              "set right subtree failed");
another_tree = createTreeNode(createFrequency('q',314));
setLeft(tree_for_testing, another_tree);
testDecider(&testNumber, &testFailed,
              getLeft(tree_for_testing) == another_tree,
              "TreeNode setLeft(): ",
              "set left subtree failed");
testDecider(&testNumber, &testFailed,
              !isLeaf(tree_for_testing),
              "TreeNode isLeaf(): ",
              "tree record seems to be a leaf, but shouldn't be!");
testDecider(&testNumber, &testFailed,
              height(tree_for_testing) == 2,
              "TreeNode height(): ",
              "tree record should have height 2, but doesn't");

if (testFailed > 10) return testFailed;
another_tree = getRight(tree_for_testing);
testDecider(&testNumber, &testFailed,
              height(another_tree) == 1,
              "TreeNode height(): ",
              "tree record should have height 1, but doesn't");
setRight(tree_for_testing,NULL);
testDecider(&testNumber, &testFailed,
              getRight(tree_for_testing) == NULL,
              "TreeNode setRight(): ",
              "tree record should have NULL right subtree, but doesn't");
testDecider(&testNumber, &testFailed,
              height(tree_for_testing) == 2,
              "TreeNode height(): ",
              "tree record should still have height 2, but doesn't");

if (testFailed > 10) return testFailed;
// ----------------------------------------------
// Testing List ADT
// Try to create a List record using the tree object
List *list_for_testing = createList();
// check is empty?
testDecider(&testNumber, &testFailed,
              isEmpty(list_for_testing),
              "List isEmpty(): ",
              "new list record should be empty, but isn't");

// check for zero elements
testDecider(&testNumber, &testFailed,
              getNumElements(list_for_testing) == 0,
              "List getNumElements(): ",
              "new list record shold have zero elements, but doesn't");

// add tree to the list
testDecider(&testNumber, &testFailed,
              insert(list_for_testing,tree_for_testing),
              "List insert(): ",
              "should have succeeded, but didn't!");
// test the tree record again
testDecider(&testNumber, &testFailed,
              getNumElements(list_for_testing) == 1,
              "List getNumElements(): ",
              "new list record should have one element, but doesn't");
testDecider(&testNumber, &testFailed,
              remove(list_for_testing, tree_for_testing),
              "List remove(): ",
              "remove() failed! ");
testDecider(&testNumber, &testFailed,
              insert(list_for_testing,tree_for_testing),
              "List insert(): ",
              "should have succeeded, but didn't!");
// add another tree to the list
testDecider(&testNumber, &testFailed,
              insert(list_for_testing,another_tree),
              "List insert(): ",
              "should have succeeded, but didn't!");
// test the tree record again
testDecider(&testNumber, &testFailed,
              getNumElements(list_for_testing) == 2,
              "List getNumElements(): ",
              "new list record should have one element, but doesn't");
testDecider(&testNumber, &testFailed,
              remove(list_for_testing, another_tree),
              "List remove(): ",
              "remove() failed! ");
testDecider(&testNumber, &testFailed,
              insert(list_for_testing,another_tree),
              "List insert(): ",
              "should have succeeded, but didn't!");
// test the tree record again
testDecider(&testNumber, &testFailed,
              getNumElements(list_for_testing) == 2,
              "List getNumElements(): ",
              "new list record should have one element, but doesn't");

if (testFailed > 10) return testFailed;
// ----------------------------------------------
// Testing Iterator ADT
// Try to create a Iterator record using the list object
Iterator *lTrav_for_testing = createIterator(list_for_testing);
testDecider(&testNumber, &testFailed,
              hasNext(lTrav_for_testing),
              "Iterator hasNext(): ",
              "there should be something in the list to look at, but isn't");
testDecider(&testNumber, &testFailed,
              next(lTrav_for_testing) == tree_for_testing,
              "Iterator next(): ",
              "should have gotten the tree record, but didn't");
testDecider(&testNumber, &testFailed,
              hasNext(lTrav_for_testing),
              "Iterator hasNext(): ",
              "there should be something in the list to look at, but isn't");
testDecider(&testNumber, &testFailed,
              next(lTrav_for_testing) == another_tree,
              "Iterator next(): ",
              "should have gotten a tree record, but didn't");
testDecider(&testNumber, &testFailed,
              !hasNext(lTrav_for_testing),
              "Iterator hasNext(): ",
              "there shouldn't be anything in the list to look at, but there is");

if (testFailed > 10) return testFailed;
// ----------------------------------------------
// Testing FrequencyList ADT
FrequencyList *flist = createFrequencyList("122333");
// check is empty?
testDecider(&testNumber, &testFailed,
              !isEmpty(flist),
              "FrequencyList isEmpty(): ",
              "new frequency list record should not be empty, but seems to be");
testDecider(&testNumber, &testFailed,
              getNumElements(flist) == 3,
              "FrequencyList getNumElements(): ",
              "new frequency list record should have 3 elements, but doesn't");

TreeNode *smallest = remove_smallest(flist);
testDecider(&testNumber, &testFailed,
              getData(getData(smallest)) == '1',
              "FrequencyList remove_smallest(): ",
              "tried to find the smallest Frequency in the list, but didn't");
testDecider(&testNumber, &testFailed,
              getNumElements(flist) == 2,
              "FrequencyList getNumElements(): ",
              "new frequency list record should have 2 elements, but doesn't");
TreeNode *middlest = remove_smallest(flist);
testDecider(&testNumber, &testFailed,
              getData(getData(middlest)) == '2',
              "FrequencyList remove_smallest(): ",
              "tried to find the smallest Frequency in the list, but didn't");
testDecider(&testNumber, &testFailed,
              getNumElements(flist) == 1,
              "FrequencyList getNumElements(): ",
              "new frequency list record should have 1 element, but doesn't");
testDecider(&testNumber, &testFailed,
              insert(flist,middlest),
              "FrequencyList insert(): ",
              "couldn't insert a treenode");
testDecider(&testNumber, &testFailed,
              getNumElements(flist) == 2,
              "FrequencyList getNumElements(): ",
              "new frequency list record should have 2 elements, but doesn't");
testDecider(&testNumber, &testFailed,
              insert(flist,smallest),
              "FrequencyList insert(): ",
              "couldn't insert a treenode");

if (testFailed > 10) return testFailed;
// ----------------------------------------------
// Testing HuffmanTree ADT

HuffmanTree *hufft = createHuffmanTree(flist);
testDecider(&testNumber, &testFailed,
              hufft != NULL,
              "HuffmanTree createHuffmanTree(): ",
              "couldn't create a HuffmanTree");

// this test violates the ADT
testDecider(&testNumber, &testFailed,
              height(hufft->root) == 3,
              "HuffmanTree createHuffmanTree(): ",
              "HuffmanTree is the wrong size!");
// this test violates the ADT
testDecider(&testNumber, &testFailed,
              getCount(getData(hufft->root)) == 6,
              "HuffmanTree createHuffmanTree(): ",
              "HuffmanTree calculated the wrong frequency at the root!");

if (testFailed > 10) return testFailed;
// ----------------------------------------------
// Testing HuffmanCodec ADT
HuffmanCodec *huffcdc = createHuffmanCodec(hufft);
testDecider(&testNumber, &testFailed,
              huffcdc != NULL,
              "HuffmanCodec createHuffmanTree(): ",
              "HuffmanCodec returned a NULL Codec!");
char *one, *two, *three;
> cout << "Test " << testNumber << ": Code for '1' is " << one
       << " (should be 2 bits long)" << endl;
testNumber++;
two = huffcdc->codebook[(int)'2'];
cout << "Test " << testNumber << ": Code for '2' is " << two
       << " (should be 2 bits long)" << endl;
testNumber++;
three = huffcdc->codebook[(int)'3'];
cout << "Test " << testNumber << ": Code for '3' is " << three
       << " (should be 1 bit long)" << endl;

char *coded = encode(huffcdc, "123");
testDecider(&testNumber, &testFailed,
              coded != NULL,
              "HuffmanCodec encode(): ",
              "HuffmanCodec returned a NULL string as a code!");
cout << "Test " << testNumber << ": Code for "123" is " << coded
       << " (should be : " << one << two << three << ")" << endl;

char *decoded = decode(huffcdc, one);
testDecider(&testNumber, &testFailed,
              decoded != NULL,
              "HuffmanCodec decode(): ",
              "returned a NULL string for 1!");
cout << "Test " << testNumber << ": Decoding "" << one << "" gives "
       << decoded
       << " (should be : 1)" << endl;

delete [] decoded;
decoded = decode(huffcdc, two);
testDecider(&testNumber, &testFailed,
              decoded != NULL,
              "HuffmanCodec decode(): ",
              "returned a NULL string for 2!");
cout << "Test " << testNumber << ": Decoding "" << two << "" gives "
       << decoded
       << " (should be : 2)" << endl;

delete [] decoded;
decoded = decode(huffcdc, three);
testDecider(&testNumber, &testFailed,
              decoded != NULL,
              "HuffmanCodec decode(): ",
              "returned a NULL string for 3!");
cout << "Test " << testNumber << ": Decoding "" << three << "" gives "
       << decoded
       << " (should be : 3)" << endl;

delete [] decoded;
decoded = decode(huffcdc, coded);
testDecider(&testNumber, &testFailed,
              decoded != NULL,
              "HuffmanCodec decode(): ",
              "returned a NULL string for 123!");
cout << "Test " << testNumber << ": Decoding "" << coded << "" gives "
       << decoded
       << " (should be : 123)" << endl;

cout << "No more tests!" << endl;

// tidy up
destroyFrequency( freq_for_testing );
destroyTreeNode( tree_for_testing );
destroyList( list_for_testing );
destroyIterator( lTrav_for_testing );
destroyHuffmanCodec( huffcdc );
return testFailed;

}

int main() {

int failed = testall();
if (failed == 0) {
    cout << "Congratulations! You passed all the tests!" << endl;
}
else if (failed >= 10) {
    cout << "You failed at least 10 tests, skipped the rest." << endl;
}
else {
    cout << "You failed less than 10 tests. Getting pretty close!" << endl;
}

return 0;
}

Huffman.cpp

#include "Huffman.h"

#include <cstring>
#include <iostream>

using namespace std;

// 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
   TreeNode *addLeft, *addRight ,*addMid;
   //TreeNode *addMid = new TreeNode;
   while (getNumElements(frequencies) > 1) {
       addLeft = remove_smallest(frequencies);
       addRight = remove_smallest(frequencies);
       addMid = new TreeNode;
       addMid->data = createFrequency('$',addLeft->data->count + addRight->data->count);
       addMid->left = addLeft;
       addMid->right = addRight;
       insert(frequencies, addMid);
   }
   HuffmanTree *huffmanTree = new HuffmanTree;
   huffmanTree->root = addMid;
cout <<"hufftestData "<<huffmanTree->root->data->data<<endl;
   cout <<"hufftestCount "<<huffmanTree->root->data->count<<endl;
   cout <<"testHeight "<< height(addMid)<<endl;
   return huffmanTree;


return NULL;
}

// createHuffmanCodec(htree)
// Pre: htree is a reference to a HuffmanTree
// Post: allocates a new HuffmanCodec record
// return: a reference to the Huffman codec

HuffmanCodec *createHuffmanCodec(HuffmanTree *t) {
HuffmanCodec *hcdc = new HuffmanCodec;
hcdc->huffTree = t;

//initialize codebook
for (int i = 0; i < ASCII_SIZE; i++){
hcdc->codebook[i] = NULL;
}

// build the codebook using the Tree
char *acode = new char[height(t->root)+1];
find_codes(hcdc, t->root, acode, 0);
return hcdc;
}

// find_codes(codec,tree,store,index)
// recursively find Huffman codes from a given tree
// pre: codec is a reference to Huffman Codec
//      tree is a reference to a TreeNode in the HuffmanTree
//      store is a character array used to store partial solutions
//      index is the next unused index in store
// post: the Huffman codes have been printed.
void find_codes(HuffmanCodec *hcdc, TreeNode *t, char s[], int d){
if (t == NULL){
    return;
}
else if (isLeaf(t)){
    s[d] = '';
    hcdc->codebook[(int) getData(getData(t))] = copy(s);
}
else {
    s[d] = '0';
    find_codes(hcdc, getLeft(t), s, d+1);
    s[d] = '1';
    find_codes(hcdc, getRight(t), s, d+1);
}
}

// destroyHuffmanCodec(hcdc)
// Pre: hcdc is a reference to a HuffmanCodec
// Post: memory for ht is deallocated
void destroyHuffmanCodec(HuffmanCodec *hcdc){
destroyHuffmanTree(hcdc->huffTree);
for (int i = 0; i < ASCII_SIZE; i++){
    if (hcdc->codebook[i] != NULL){
      delete [] hcdc->codebook[i];
    }
}
}

// encode(hcdc, message)
// encode a message using the Huffman Codec
// Pre: hcdc is a referene to a HuffmanCodec
//      message:: a cstring to encode
// Return a cstring containing the encoded message
char *encode(HuffmanCodec *h, const char message[]){
// TODO: complete this function
   FrequencyList *freqList = createFrequencyList(message);
   HuffmanTree *huffTree = createHuffmanTree(freqList);
   h = createHuffmanCodec(huffTree);
   size_t mesLen = strlen(message);
   char * encodedStr = new char[10*mesLen];
   char *temp;
   for (size_t i = 0; i < mesLen; i++) {
       temp = h->codebook[(int)message[i]];
       strcat(encodedStr, temp);
   }
   return encodedStr;
}

// decode_char(tnode, message, d){
// decode one character from the message.
// Pre: tnode is a node in a huffman tree
//      message:: cstring, the whole message to decode
//      d:: a reference to an int containing the current
//          index in the message
// Post: d has been increased by the number of 0s and 1s used to
//       encode the character
// Return: the decoded character
char decode_char(TreeNode *t, char message[], int *d){

// TODO: complete this function
   //if (t == NULL) exit(1);
   if (height(t) == 1){
       d++;
       return getData(getData(t));
   }
   if (isLeaf(t)){
       return getData(getData(t));
   }
   if (message[*d] == '0') {
       (*d)++;
       return decode_char(t->left, message, d);
   }
   if (message[*d] == '1') {
       (*d)++;
       return decode_char(t->right, message, d);
   }

return '.'; // dot returned for no good reason
}

// go through the whole message
while (d < (int)strlen(message)){
    // decode one character using the Huffman Tree
    decoded_msg[i] = decode_char(h->huffTree->root, message, &d);
    i++;
}
// ensure the C-string is properly terminated
decoded_msg[i] = '';

// then make a copy
char *result = copy(decoded_msg);
delete [] decoded_msg;
return result;
}

// eof

Huffman.h

#ifndef _HUFFMAN_H_
#define _HUFFMAN_H_

struct HuffmanTree {
TreeNode *root;
};

struct HuffmanCodec {
HuffmanTree *huffTree;
char *codebook[ASCII_SIZE];
};

// createHuffmanCodec(htree)
// Pre: htree is a reference to a HuffmanTree
// Post: allocates a new HuffmanCodec record
// return: a reference to the Huffman codec

HuffmanCodec *createHuffmanCodec(HuffmanTree *t) ;

// find_codes(codec,tree,store,index)
// recursively find and print Huffman codes from a given tree
// pre: codec is a reference to Huffman Codec
//      tree is a reference to a TreeNode in the HuffmanTree
//      store is a character array used to store partial solutions
//      index is the next unused index in store
// post: the Huffman codes have been printed.
void find_codes(HuffmanCodec *hcdc, TreeNode *t, char s[], int d);

// encode(hcdc, message)
// encode a message using the Huffman Codec
// Pre: hcdc is a referene to a HuffmanCodec
// message:: a cstring to encode
// return a cstring containing the encoded message
char *encode(HuffmanCodec *h, const char message[]);

// DESTRUCTOR

// destroyHuffmanTree(ht)
// Pre: ht is a reference to a HuffmanTree
// Post: memory for ht is deallocated
void destroyHuffmanTree(HuffmanTree *ht);

// destroyHuffmanCodec(hcdc)
// Pre: hcdc is a reference to a HuffmanCodec
// Post: memory for ht is deallocated
void destroyHuffmanCodec(HuffmanCodec *hcdc);

#endif

Navigate

PLEASE HELP ME BY ANSWERING CORRECTLY I WILL RATE YOU HIGH Calculate the current

PLEASE HELP ME CORRECT MY ANSWERS. 1. In the figure below, four equidistant para

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

PLEASE HELP ME COMPLETE THIS #include <cstring> #include <iostream> #include \"H

Question

Explanation / Answer

Related Questions

Navigate