Huffman Encoding Tree Fatal Error after print

Question

jaker29902 0 Newbie Poster

13 Years Ago

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;
}

c++

Main.cpp (8.69 KB)

#include <iostream>
#include <iomanip>
#include <fstream>
#include <string>
#include <stack>

using namespace std;

const int num_chars = 256;

struct BinNode
{
	int frequency;
	char ASCII_Char;
	BinNode * LLink;
	BinNode * RLink;
};


template <class Type>struct LLNode
{
	LLNode<Type> *next;
	LLNode<Type> *prev;
	Type data;	
};


template <class Type> class InitialList
{
public:
	const InitialList<Type>& operator= 
		(const InitialList<Type> &); //Overload the assignment operator

	bool isEmptyList() const; //Returns boolean indicating whether list is empty or not

	int length() const; //Returns the number of nodes in the list

	void initializeList();//function to initialize the list to an empty state
	void destroy();//Deletes all the nodes from the list
	void print() const;//Prints the info contained in each node
	void insert(const Type insertItem);//Inserts a node into the list
	void deleteNode(const Type &deleteItem);//Function to delete a node from the list
	Type* returnXnode(int numNode); //Function to return the specifed node in the list

	InitialList();//default constructor
	~InitialList();//destructor

protected:
	int count;
	LLNode<Type> *first; //head pointer
	LLNode<Type> *last;  //tail pointer
};



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> bool InitialList<Type>::isEmptyList() const
{
	return (first == 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;
}

test.txt (0.04 KB)

aaaa
bbb
cc
d
e
!!!!
@@@
##
$

1 Contributor
2 Replies
133 Views
1 Day Discussion Span
Latest Post 13 Years Ago Latest Post by jaker29902

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

jaker29902 0 Newbie Poster · Answer 1 · 2010-04-28T00:24:03+00:00

Hey all,

So I went through the debugging again and found it is triggering a break point here

_ASSERTE(_CrtIsValidHeapPointer(pUserData));

and am told that this means I have a bad pointer somewhere but when I try to trace the program out by hand it seems like it should work for me, any ideas?

-Jake

jaker29902 0 Newbie Poster · Answer 2 · 2010-04-28T01:55:57+00:00

Found it! After putting break points at each destructor and each delete function, I traced the problem to ~InitialList() something went wrong when it tried to loop through and delete the list, not sure what happened but I commeted out the destructor and everything works!

I am so awesome!