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

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

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!

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.