Hi all,
Alright I will try to be as descriptive as possible, so here is the deal.
I am attempting to create a Huffman Encoding Tree. The input file is test.txt the characters of the file are read in and as each char is read in it is converted to is ASCII value that serves as the subscript of the array that holds the frequency for which each char is read. Then for each non-zero occuring char a LLNode is created and inserted into the list, called List, which are sorted by frequency which is stored in the data element of the LLNode, which is a pointer to a BinNode (program works up to this point). Once the List is built it is sent into BuildHuffTree which should build a huffman tree according the the huffman algorithm. The tree is then printed via PrintHuffTree() which calls PrintHuff(root, stack1, stack2) which should do a traversal like this
print tree (current)
if current node is a leaf, print leaf ASCII value, print stack in reverse and return
else
push (0)
print left subtree - recursive
pop()
push(1)
print right subtree - recursive
pop()
return
To print the stack in reverse I use a second stack that fills from the first top down, and then prints.
My problem comes when I attempt to run main, it runs and prints (I believe correctly) and then dies in horrible horrible agony.
If I could get another pair of eyes to look this over and let me know if they see anything super wrong I would appreciate it. I'll post all the relevant code here and I'll attach the source code and input file Ive been using
-Jake
template <class Type> InitialList<Type>::InitialList()
{
first = NULL;
last = NULL;
count = 0;
}
template <class Type> InitialList<Type>::~InitialList()
{
LLNode<Type> *temp;
while(first != NULL)
{
temp = first;
first=first->next;
delete temp;
}
last = NULL;
count = 0;
}
template <class Type> int InitialList<Type>::length() const
{
return count;
}
template <class Type> void InitialList<Type>::initializeList()
{
count = 0;
first = NULL;
last = NULL;
}
template <class Type> void InitialList<Type>::print() const
{
LLNode<Type> *current; //pointer to traverse the list
current = first; //start at beginning of list
while(current != NULL)
{
cout<<"Character: "<<current->data.ASCII_Char;
cout<<"Frequency: "<<current->data.frequency<<endl;
current=current->next;
}
}
template <class Type> void InitialList<Type>::insert(const Type insertItem)
{
LLNode<Type> *current;
LLNode<Type> *trailCurrent;
LLNode<Type> *newNode;
bool found;
newNode = new LLNode<Type>;
newNode->data = insertItem;
newNode->next = NULL;
newNode->prev = NULL;
if(first == NULL)
{
first = newNode;
last = newNode;
count++;
}
else
{
found = false;
current = first;
while(current != NULL && !found)
{
if(current->data.frequency >= insertItem.frequency)
found = true;
else
{
trailCurrent = current;
current = current->next;
}
}
if(current == first)
{
first->prev = newNode;
newNode->next = first;
first = newNode;
count++;
}
else
{
if(current != NULL)
{
trailCurrent->next = newNode;
newNode->prev = trailCurrent;
newNode->next = current;
current->prev = newNode;
}
else
{
trailCurrent->next = newNode;
newNode->prev = trailCurrent;
last = newNode;
}
count++;
}
}
}
template <class Type> void InitialList<Type>::deleteNode(const Type &deleteItem)
{
bool found = false;
LLNode<Type> *current; //pointer to traverse the list
LLNode<Type> *trailCurrent;
if(first == NULL)
cout<<"List is empty, no deletions for you!!!!!!"<<endl;
else if(first->data.ASCII_Char == deleteItem.ASCII_Char)
{
current = first;
first = first->next;
if(first != NULL)
first->prev = NULL;
else
last = NULL;
count--;
delete current;
}
else
{
found = false;
current = first;
while(current != NULL && !found)
{
if(current->data.ASCII_Char >= deleteItem.ASCII_Char)
found = true;
else
current=current->next;
}
if(current == NULL)
cout<<"Didnt find the item, try again"<<endl;
else if(current->data.ASCII_Char == deleteItem.ASCII_Char)
{
trailCurrent = current->prev;
trailCurrent->next = current->next;
if(current->next != NULL)
current->next->prev = trailCurrent;
if(current == last)
last = trailCurrent;
count--;
delete current;
}
}
}
template <class Type> Type* InitialList<Type>::returnXnode(int numNode)
{
LLNode<Type> *current;
BinNode *returnnode = new BinNode;
current = first;
for(int i=1;i<numNode;i++)
{
if(current->next != NULL)
{
current = current->next;
}
else
{
cout<<"Not that many nodes in the list"<<endl;
}
}
returnnode->ASCII_Char = current->data.ASCII_Char;
returnnode->frequency = current->data.frequency;
returnnode->LLink = current->data.LLink;
returnnode->RLink = current->data.RLink;
return returnnode;
}
template <class Type> class binaryTree
{
public:
void printHuffTree() const;
void BuildHuffTree(InitialList<Type> nodeList);
binaryTree();
~binaryTree();
protected:
BinNode *root;
private:
void printHuff(BinNode *p, stack<int> encoded1, stack<int> encoded2) const;
void destroy(BinNode* &p);
};
template <class Type> binaryTree<Type>::binaryTree()
{
root = NULL;
}
template <class Type> binaryTree<Type>::~binaryTree()
{
destroy(root);
}
template <class Type> void binaryTree<Type>::destroy(BinNode* &p)
{
if(p != NULL)
{
destroy(p->LLink);
destroy(p->RLink);
delete p;
p = NULL;
}
}
template <class Type> void binaryTree<Type>::printHuffTree() const
{
stack<int> a;
stack<int> b;
printHuff(root, a, b);
}
template <class Type> void binaryTree<Type>::printHuff(BinNode *p, stack<int> encoded1, stack<int> encoded2) const
{
if(p->LLink == NULL && p->RLink == NULL)
{
int temp;
cout<<p->ASCII_Char<<" - ";
while(!encoded1.empty())
{
encoded2.push(encoded1.top());
encoded1.pop();
}
while(!encoded2.empty())
{
cout<<encoded2.top();
encoded2.pop();
}
cout<<"\n";
return;
}
else
{
encoded1.push(0);
printHuff(p->LLink, encoded1, encoded2);
encoded1.pop();
encoded1.push(1);
printHuff(p->RLink, encoded1, encoded2);
encoded1.pop();
return;
}
}
template <class Type> void binaryTree<Type>::BuildHuffTree(InitialList<Type> nodeList)
{
int count;
int combinedfreqs;
count = nodeList.length();
BinNode* node1 = new BinNode;
BinNode* node2 = new BinNode;
BinNode* ParentNode = new BinNode;
for(int i=1;i<count;i++)
{
node1=nodeList.returnXnode(1);
node2=nodeList.returnXnode(2);
combinedfreqs = node1->frequency + node2->frequency;
ParentNode->frequency = combinedfreqs;
if(node1->frequency < node2->frequency)
{
ParentNode->LLink = node1;
ParentNode->RLink = node2;
}
else if(node1->frequency > node2->frequency)
{
ParentNode->RLink = node1;
ParentNode->LLink = node2;
}
else if(node1->frequency == node2->frequency)
{
if((node1->LLink == NULL && node1 == NULL) && (node2->LLink == NULL && node2 == NULL))
{
ParentNode->LLink = node1;
ParentNode->RLink = node2;
}
else if((node1->LLink == NULL && node1 == NULL) && (node2->LLink != NULL && node2 != NULL))
{
ParentNode->LLink = node1;
ParentNode->RLink = node2;
}
else if((node1->LLink != NULL && node1 != NULL) && (node2->LLink == NULL && node2 == NULL))
{
ParentNode->RLink = node1;
ParentNode->LLink = node2;
}
else
{
ParentNode->LLink = node1;
ParentNode->RLink = node2;
}
}
else
{
cout<<"Something went wrong with assigning ParentNode Links"<<endl;
}
nodeList.deleteNode(*node1);
nodeList.deleteNode(*node2);
root = ParentNode;
nodeList.insert(*ParentNode);
}
}
int main()
{
int chararray[num_chars];
int charnum;
char inchar;
char filename[31];
FILE *pFile;
InitialList<BinNode> List;
binaryTree<BinNode> Tree;
for(int i=0;i<256;i++)
{
chararray[i] = 0;
}
cout<<"Enter the file name to be processed: ";
cin>>filename;
pFile=fopen(filename,"r");
if(pFile==NULL)
cout<<"Error reading file"<<endl;
else
{
charnum = getc(pFile);
while(charnum != EOF)
{
chararray[charnum]++;
charnum = fgetc(pFile);
}
fclose (pFile);
BinNode temp;
temp.LLink = NULL;
temp.RLink = NULL;
for (int i=0;i<256;i++)
{
if(chararray[i]>0)
{
temp.frequency=chararray[i];
temp.ASCII_Char=static_cast<char>(i);
List.insert(temp);
}
}
List.print();
Tree.BuildHuffTree(List);
Tree.printHuffTree();
}
return 0;
}