Solved

Using a queue for Huffman code

Posted on 2009-04-09
6
2,972 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
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 
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

How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

Join & Write a Comment

The following diagram presents a diamond class hierarchy: As depicted, diamond inheritance denotes when two classes (e.g., CDerived1 and CDerived2), separately extending a common base class (e.g., CBase), are sub classed simultaneously by a fourt…
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…
The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use conditional statements in the C programming language.

743 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

Need Help in Real-Time?

Connect with top rated Experts

11 Experts available now in Live!

Get 1:1 Help Now