Solved

Using a queue for Huffman code

Posted on 2009-04-09
6
2,974 Views
Last Modified: 2012-05-06
Hello,

I am working on creating a Huffman Code (tree).  I currently read all symbols and frequencies from a file into Nodes, stored in an array of node *'s, then I sort the array based on frequency and push the sorted nodes into a queue.  Now when I try to combine the Nodes I receive and error.  I pop the first to nodes from queue and have temp vairables for them, I create a new node and combine the frequencies and alpha characters.  However when I try to push the new node back into the queue I receive error message: "deque iteration not referencable".  
Please tell me how I can fix this, so that I can pop and push to the same queue?
I created another queue and I am able to push the node * to that queue, so I know it is a problem with accessing the same queue I am popping from.  Can someone tell me how I can push a node * back into the same queue?

// Proj 5 Huffman Code.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <iomanip>
#include <queue>
#define ARRAYSIZE 26
using namespace std;
struct treeNode
{
	char alpha[ARRAYSIZE];
	float freq;
	int level;
	struct treeNode *leftPtr, *rightPtr, *parent;
};
typedef struct treeNode TreeNode;
typedef TreeNode *TreeNodePtr; 
TreeNodePtr rootPtr = NULL; 
treeNode * node_position[ARRAYSIZE];
FILE *fp;
queue<treeNode*> q;
queue<treeNode*> huff;
void insertSymbols(); //creates leaf nodes and stores in pointer array
void sortArray(struct treeNode * node_position[]); //sort the array of node pointers
void printSortedArray(struct treeNode * node_position[]); //prints symbols and freq. read from symbol.txt file
void enQueue(struct treeNode * node_position[]); //insert nodes into queue
void createHuff();
int _tmain(int argc, _TCHAR* argv[])
{
	insertSymbols();
	sortArray(node_position);
	printSortedArray(node_position);
	//enQueue(node_position);
	createHuff();
	return 0;
}
void sortArray(struct treeNode * node_position[])//sort the array
{
	int pass; //pass counter
	int c; //comparison counter
	treeNode * hold;  //temp locaion to swap elements
	for(pass=0; pass<ARRAYSIZE; pass++)
	{
		for(c=0; c<ARRAYSIZE-1; c++)
		{
			if(node_position[c]->freq>node_position[c+1]->freq)
			{
				hold=node_position[c];
				node_position[c]=node_position[c+1];
				node_position[c+1]=hold;
			}
		}
	}
}
void printSortedArray(struct treeNode * node_position[])
{
	int i;
	for(i=0; i<ARRAYSIZE; i++)
	{
		cout<<"Symbol is:  "<<node_position[i]->alpha<<"\t"<<"Frequency is:  "<<node_position[i]->freq<<endl;
	}
}
void insertSymbols()
{
	int i;
	fp = fopen("N:\\symbol.txt", "r");
	for(i=0; i<ARRAYSIZE; i++)
	{		
		struct treeNode * treePtr;
		treePtr = (struct treeNode *) malloc (sizeof(treeNode));
		fscanf(fp, "%s", &treePtr->alpha);
		fscanf(fp, "%f", &treePtr->freq);
		node_position[i]=treePtr;
	}
}
void enQueue(struct treeNode * node_position[])
{
	int i;
	for(i=0; i<ARRAYSIZE; i++)
	{		
		q.push(node_position[i]);
	}
	return ;
}
void createHuff()
{
	treeNode *temp1, *temp2;
	treeNode *treePtr;
	
	while (!q.empty())
	{
		temp1=q.front();
		q.pop();
		temp2=q.front();
		q.pop();
		
		treePtr = (struct treeNode*) malloc (sizeof(treeNode));
 
		if(rootPtr==NULL)
			rootPtr=treePtr;
 
		temp1->parent=treePtr;
		temp2->parent=treePtr;
		treePtr->leftPtr=temp1;
		treePtr->rightPtr=temp2;
		strcpy(treePtr->alpha, temp1->alpha);
		strcat(treePtr->alpha,temp2->alpha);
		treePtr->freq=temp1->freq+temp2->freq;
		rootPtr=treePtr;
		q.push(treePtr); /*this causes a problem*/
	                      /*huff.push(treePtr); I can successfully push to this queue*/
	}
}

Open in new window

symbol.txt
0
Comment
Question by:Zorniac
  • 4
6 Comments
 
LVL 1

Author Comment

by:Zorniac
ID: 24111730
I had this function called commented out //enQueue(node_position);
but it shouldn't have been I was experimenting when I posted the question.  Please uncomment if you try to compile
0
 
LVL 84

Expert Comment

by:ozo
ID: 24111990
I don't think you want to push the new node into a queue,
you want the  nodes in order of size, so a heap may be a more appropriate data structure than  a queue
0
 
LVL 1

Author Comment

by:Zorniac
ID: 24112296
I found the problem on line 97, when i only had one element in the queue, I was attempted to do two pops.  this was caused by the while loop logic being set to while( !q.empty()), I changed this to
while(q.size>1). I am able to consolidate all nodes into one tree and all alpha symbols to my rootPtr.
0
Microsoft Certification Exam 74-409

Veeam® is happy to provide the Microsoft community with a study guide prepared by MVP and MCT, Orin Thomas. This guide will take you through each of the exam objectives, helping you to prepare for and pass the examination.

 
LVL 1

Author Comment

by:Zorniac
ID: 24112323
I think they may be out of order, I need to make a drawing and then see how the tree comes out by hand
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 24135822
Just a note about this :

>>                 strcpy(treePtr->alpha, temp1->alpha);
>>                 strcat(treePtr->alpha,temp2->alpha);

Are you sure that the alpha field's size (25 characters) is big enough to hold these concatenations ? Be careful to avoid buffer overflows.
0
 
LVL 1

Accepted Solution

by:
Zorniac earned 0 total points
ID: 24197771
I fixed the initial problem by changing the while loop logic.  I corrected the tree's nodes being out of order, by sorting the queue until there was only one node left in the queue.  popped two elements, combined them, push new node to the queue, moved queue elements to the array, sorted the array and requed all elements in the array, started pops over again.

Infininty, yes, you are right, seems like I should have been one character short, however when all nodes are combined I am able to hold the string concatenation.  I am not sure why this worked.
In case anyone is interested here is my completed code
3/11/2009
Project 5 Huffman Code Tree*/
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <queue>
#define ARRAYSIZE 26
#define NUMNODES 51
#define MAXPATH 10
using namespace std;
char outFile[40];
char symbolFile[40];
char bitFile[40];
struct treeNode
{
	char alpha[ARRAYSIZE];
	int path[9];
	float freq;
	int level;
	struct treeNode *leftPtr, *rightPtr, *parent;
};
typedef struct treeNode TreeNode;
typedef TreeNode *TreeNodePtr; 
TreeNodePtr rootPtr = NULL;
TreeNodePtr treePtr=NULL;
treeNode * node_position[ARRAYSIZE];
treeNode * levelArray[NUMNODES];
treeNode * leafArray[ARRAYSIZE];
FILE *fp;
queue<treeNode*> q;
queue<treeNode*> levelQ;
void insertSymbols(); //creates leaf nodes and stores in pointer array
void sortArray(struct treeNode * a[]); //sort the array of node pointers
void printSortedArray(struct treeNode * a[]); //prints symbols and freq. read from symbol.txt file
void enQueue(struct treeNode * a[]); //insert nodes into queue
void createHuff(); //combines leaf nodes into Huffman Tree
void moveToArray(); //moves queue to array after every two pops; called from createHuff
void inOrder(TreeNodePtr treePtr); //prints huffman tree inOrder
void bfs(treeNode* pNode); //gets all nodes from tree and copies mem addr to array
void setLevel(treeNode * levelArray[]); //sets nodes level and prints nodes in level order
void readBitFile(); //reads binary pattern from file and outputs text
void startGetLeaves(treeNode* node);
void getLeavesRecur(treeNode* node, int path[], int pathLen);//
void goRight(treeNode * node, int path[], int pathLen);//tracks huff code
void goLeft(treeNode * node, int path[], int pathLen);//tracks huff code
void getLeaves(treeNode * node, int ints[], int len);//captures leafs to * array
void alphabetizeArray(treeNode *leafArray[]);//sorts leafs in alpha order
void printHuffCode(treeNode * leafArray[]);//prints symbols and code
int _tmain(int argc, _TCHAR* argv[])
{
	ofstream myout;
	cout<<"Enter FULL path to OUTPUT file."<<endl;
	cin>>outFile;
	cout<<"Enter FULL path to SYMBOL file."<<endl;
	cin>>symbolFile;
	cout<<"Enter FULL path to bit file."<<endl;
	cin>>bitFile;
	myout.open(outFile, ios::app);
	insertSymbols();
	sortArray(node_position);
	printSortedArray(node_position);
	enQueue(node_position);
	createHuff();
	myout<<endl<<"The inOrder traversal is:"<<endl;
	cout<<endl<<"The inOrder traversal is:"<<endl;
	inOrder( rootPtr);
	bfs(rootPtr);
	myout<<endl<<"Printing the tree in levelOrderTraversal"<<endl;
	cout<<endl<<"Printing the tree in levelOrderTraversal"<<endl;
	setLevel(levelArray);
	startGetLeaves(rootPtr);
	alphabetizeArray(leafArray);
	printHuffCode(leafArray);
	readBitFile();	
	myout.close();
	return 0;
}
void sortArray(struct treeNode * a[])//sort the array
{
	int pass; //pass counter
	static int count = 0;
	int c; //comparison counter
	treeNode * hold;  //temp locaion to swap elements
	for(pass=0; pass<ARRAYSIZE-count; pass++)
	{
		for(c=0; c<ARRAYSIZE-count-1; c++)
		{
			if(a[c]->freq>a[c+1]->freq)
			{
				hold=a[c];
				a[c]=a[c+1];
				a[c+1]=hold;
			}
		}
	}
	count++;
}
void printSortedArray(struct treeNode * a[])
{
	int i;
	ofstream myout;
	myout.open(outFile, ios::app);
	for(i=0; i<ARRAYSIZE; i++)
	{
		if(a[i]!=NULL)
		{			
			myout<<"Symbol is:  "<<a[i]->alpha<<"\t"<<"Frequency is:  "<<a[i]->freq<<endl;
			cout<<"Symbol is:  "<<a[i]->alpha<<"\t"<<"Frequency is:  "<<a[i]->freq<<endl;
		}
	}
	myout.close();
}
void insertSymbols()
{
	int i;
	fp = fopen(symbolFile, "r");
	for(i=0; i<ARRAYSIZE; i++)
	{	
		treePtr = new treeNode;
		treePtr->leftPtr=treePtr->rightPtr=treePtr->parent=NULL;
		fscanf(fp, "%s", &treePtr->alpha);
		fscanf(fp, "%f", &treePtr->freq);
		node_position[i]=treePtr;
	}
	fclose(fp);
}
void enQueue(struct treeNode * a[])
{
	int i;
	for(i=0; i<ARRAYSIZE; i++)
	{	
		if(a[i]!=NULL)
		{
			q.push(a[i]);
			a[i]=NULL;
		}
	}
}
void createHuff()
{
	treeNode *temp1, *temp2;
	while(q.size()>1)
	{
		temp1=q.front();
		q.pop();
		temp2=q.front();
		q.pop();
		treePtr = new treeNode;	
		treePtr->leftPtr=treePtr->rightPtr=treePtr->parent=NULL;
		temp1->parent=temp2->parent=treePtr;
		treePtr->leftPtr=temp1;
		treePtr->rightPtr=temp2;
		strcpy(treePtr->alpha, temp1->alpha);
		strcat(treePtr->alpha,temp2->alpha);
		treePtr->freq=temp1->freq+temp2->freq;
		q.push(treePtr);
		moveToArray();
		sortArray(node_position);
		printSortedArray(node_position);
		enQueue(node_position);		
	}
	rootPtr=treePtr;
	rootPtr->level=0;
}
void moveToArray()
{
	int i;
	for(i=0; i<ARRAYSIZE; i++)
	{
		if(!q.empty())
		{
			node_position[i]=q.front();
			q.pop();
		}
		else
			node_position[i]=NULL;
	}
}
void inOrder( TreeNodePtr treePtr )
{
	ofstream myout;
	myout.open(outFile, ios::app);
	if ( treePtr != NULL ) 
	{
		inOrder( treePtr->leftPtr );
		myout<<"Frequency:    "<<treePtr->freq<<"  Symbol:  "<<treePtr->alpha<<endl;
		cout<<"Frequency:    "<<treePtr->freq<<"  Symbol:  "<<treePtr->alpha<<endl;
		inOrder( treePtr->rightPtr );
   } 
	myout.close();
}
void bfs(treeNode* pNode)
{  
	int inc=0;
	levelQ.push(pNode);
	while (!levelQ.empty())
	{
		pNode = levelQ.front();
		if (pNode->leftPtr)
			levelQ.push(pNode->leftPtr);
		if (pNode->rightPtr)
			levelQ.push(pNode->rightPtr);
		levelArray[inc]=levelQ.front();
		inc++;
		levelQ.pop();
	}
}
void setLevel(treeNode * levelArray[])
{
	int i;
	ofstream myout;
	myout.open(outFile, ios::app);
	for(i=0; i<NUMNODES; i++)
	{		
		if(levelArray[i]->parent!=NULL)
			levelArray[i]->level=levelArray[i]->parent->level+1;
		myout<<"At level "<<levelArray[i]->level<<":   Symbol:  "<<levelArray[i]->alpha<<endl;		
		cout<<"At level "<<levelArray[i]->level<<":   Symbol:  "<<levelArray[i]->alpha<<endl;
	}
	myout<<endl;
	myout.close();
	cout<<endl;
}
void startGetLeaves(treeNode* node) { 
  int path[MAXPATH]; 
  getLeavesRecur(node, path, 0); 
} 
void getLeavesRecur(treeNode* node, int path[], int pathLen) { 
  if (node==NULL) return; 
  
  // it's a leaf, so print the path that led to here 
  if (node->leftPtr==NULL && node->rightPtr==NULL) 
	  getLeaves(node, path, pathLen); 
 
  else 
  { 
	  // otherwise try both subtrees
	  goLeft(node, path, pathLen);
	  goRight(node, path, pathLen);
  } 
} 
void getLeaves(treeNode * node, int ints[], int len) { 
  int i;
  static int c=0;  
  leafArray[c]=node;
  c++;
  for (i=0; i<len; i++) 
  {
	  node->path[i]=ints[i];
  } 
} 
void goLeft(treeNode * node, int path[], int pathLen)
{
	path[pathLen]=0;
	pathLen++;
	getLeavesRecur(node->leftPtr, path, pathLen);
}
void goRight(treeNode * node, int path[], int pathLen)
{
	path[pathLen]=1;
	pathLen++;
	getLeavesRecur(node->rightPtr, path, pathLen);
}
void alphabetizeArray(treeNode *leafArray[])
{
	int pass; //pass counter
	static int count = 0;
	int c; //comparison counter
	treeNode * hold;  //temp locaion to swap elements
	for(pass=0; pass<ARRAYSIZE; pass++)
	{
		for(c=0; c<ARRAYSIZE-1; c++)
		{
			if(leafArray[c]->alpha>leafArray[c+1]->alpha)
			{
				hold=leafArray[c];
				leafArray[c]=leafArray[c+1];
				leafArray[c+1]=hold;
			}
		}
	}	
}
void printHuffCode(treeNode * leafArray[])
{			
	int i, j;
	ofstream myout;
	myout.open(outFile, ios::app);
	for(i=0; i<ARRAYSIZE; i++)
	{
		myout<<"symbol:  "<<leafArray[i]->alpha<<" "<<"HuffmanCode:  ";
		cout<<"symbol:  "<<leafArray[i]->alpha<<" "<<"HuffmanCode:  ";
		
		for(j=0; j<9; j++)
		{
			if((leafArray[i]->path[j]==1)|(leafArray[i]->path[j]==0))
			{
				myout<<leafArray[i]->path[j];
				cout<<leafArray[i]->path[j];
			}
		}
		myout<<endl;
		cout<<endl;
	}
	myout<<"symbol:  "<<rootPtr->alpha<<" "<<"HuffmanCode:  "<<endl;
	cout<<"symbol:  "<<rootPtr->alpha<<" "<<"HuffmanCode:  "<<endl;	
	myout.close();
}
void readBitFile()
{
	char item;
	treePtr=rootPtr;
	fp = fopen(bitFile, "r");
	ofstream myout;
	myout.open(outFile, ios::app);
	myout<<endl;
	cout<<endl;
	while(!feof((fp)))
	{
		fscanf(fp, "%c", &item);
		if(item=='0')
		{
			treePtr=treePtr->leftPtr;
			if((treePtr->leftPtr==NULL)&&(treePtr->rightPtr==NULL))
			{
				myout<<treePtr->alpha;
				cout<<treePtr->alpha;
				treePtr=rootPtr;
			}
		}
		if(item=='1')
		{
			treePtr=treePtr->rightPtr;
			if((treePtr->rightPtr==NULL)&&(treePtr->leftPtr==NULL))
			{
				myout<<treePtr->alpha;
				cout<<treePtr->alpha;
				treePtr=rootPtr;
			}
		}
		if(item=='.')
		{
			myout<<".  ";
			cout<<".  ";
			treePtr=rootPtr;
		}
		if(item==' ')
		{
			myout<<" ";
			cout<<" ";
			treePtr=rootPtr;
		}
		if(item=='-')
		{
			myout<<"-";
			cout<<"-";
			treePtr=rootPtr;
		}
		if(item==',')
		{
			myout<<", ";
			cout<<", ";
			treePtr=rootPtr;
		}	
	}
	myout<<endl;
	myout.close();
	fclose(fp);
	cout<<endl;
}

Open in new window

0

Featured Post

Master Your Team's Linux and Cloud Stack

Come see why top tech companies like Mailchimp and Media Temple use Linux Academy to build their employee training programs.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
The goal of this video is to provide viewers with basic examples to understand and use structures in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use for-loops in the C programming language.

772 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question