Click here to Skip to main content
15,913,773 members
Home / Discussions / C / C++ / MFC
   

C / C++ / MFC

 
GeneralRe: Writing to the console only (without re-direction) Pin
Member 385202428-Apr-11 12:52
Member 385202428-Apr-11 12:52 
GeneralRe: Writing to the console only (without re-direction) Pin
Member 385202428-Apr-11 13:08
Member 385202428-Apr-11 13:08 
AnswerRe: Writing to the console only (without re-direction) Pin
Hans Dietrich28-Apr-11 13:12
mentorHans Dietrich28-Apr-11 13:12 
GeneralRe: Writing to the console only (without re-direction) Pin
Member 385202428-Apr-11 13:29
Member 385202428-Apr-11 13:29 
QuestionXML Parsing using Tiny XML Pin
pix_programmer28-Apr-11 3:55
pix_programmer28-Apr-11 3:55 
AnswerRe: XML Parsing using Tiny XML Pin
Code-o-mat28-Apr-11 4:10
Code-o-mat28-Apr-11 4:10 
AnswerRe: XML Parsing using Tiny XML Pin
jschell28-Apr-11 8:24
jschell28-Apr-11 8:24 
QuestionGenerating Huffman Coding using Two Queues and a Cursor Pin
Francis Paran28-Apr-11 3:45
Francis Paran28-Apr-11 3:45 
Hey everybody,

I just want to know what you think of a Huffman coding implemented using two queues and a cursor instead of using a binary tree or a priority. Please feel free to post your thoughts about it or what can be done to improve its performance. Basically, the algorithm has two queues as arguments where it first reads the first one (which has to be sorted BTW),and then creates the second queue by adding the values of the two lowest nodes in the first queue. The cursors serve as pointers of each nodes in the second queue to its left and right children in the first one (it can also be reference to the previous nodes in the second one). I think with the whole process, the algorithm has an O(n) number of operations but you be the critic.
void generateHuffman(Queue& q1, Queue& q2)
{/*
input - an initial sorted queue q1 of the frequencies of each character
output - a sorted list q2 composed where every node is the sum of two elements 
         in q1 and has cursors in each one of these.
*/

QueueNode *leftChild, *rightChild, *tempNode;

q1.enqueue(q1.dequeue());
q2.enqueue(q1.front()+q1.back());
rightChild = q1.backNode();
q1.enqueue(q1.dequeue());
leftChild = q1.backNode();

q2.setCursor(leftChild, rightChild);


while (q1.back() <= q1.front())
{//@pre: q1 has all the elements sorted
//@post: all elements in q1 will be back in place with each of them referenced
//       by elements in q2
	q2.enqueue( q1.front()+q2.front() );
	tempNode = q2.backNode();
	q2.enqueue(q2.dequeue());
	tempNode->rightCursor = q2.backNode();
	
	q1.enqueue(q1.dequeue());
	tempNode->leftCursor = q1.backNode();

	while( q2.frontNode() != tempNode)
		q2.enqueue(q2.dequeue());
	tempNode = NULL;
}

}

/**Queue.h*/

#include "QueueException.h"
typedef int QueueItemType;

struct QueueNode
          {
                 QueueItemType item;
                 QueueNode *leftCursor;
                 QueueNode *rightCursor;
                 QueueNode *next;
          };
          
class Queue
{
public: 
        Queue();
        ~Queue();
        
        bool isEmpty() const;
        QueueItemType front() const throw(QueueException);
        QueueItemType back() const throw(QueueException);
        QueueItemType dequeue() throw(QueueException);
        QueueNode *frontNode() const throw(QueueException);
        QueueNode *backNode() const throw(QueueException);
        
        //void sortQueue(Queue& q)  throw(QueueException);
        void dequeue(QueueItemType& queueFront)       throw(QueueException);
        void enqueue(const QueueItemType& newItem)  throw(QueueException);
        void setCursor(QueueNode *l, QueueNode *r)  throw(QueueException);
        
private:  
          QueueNode *backPtr;
          QueueNode *frontPtr;
};


Hope this helps to give me some advice. Thanks
QuestionRe: Generating Huffman Coding using Two Queues and a Cursor Pin
David Crow28-Apr-11 9:04
David Crow28-Apr-11 9:04 
AnswerRe: Generating Huffman Coding using Two Queues and a Cursor Pin
Francis Paran28-Apr-11 12:17
Francis Paran28-Apr-11 12:17 
GeneralRe: Generating Huffman Coding using Two Queues and a Cursor Pin
David Crow29-Apr-11 4:01
David Crow29-Apr-11 4:01 
GeneralRe: Generating Huffman Coding using Two Queues and a Cursor Pin
Francis Paran29-Apr-11 6:25
Francis Paran29-Apr-11 6:25 
GeneralRe: Generating Huffman Coding using Two Queues and a Cursor Pin
David Crow29-Apr-11 8:20
David Crow29-Apr-11 8:20 
GeneralRe: Generating Huffman Coding using Two Queues and a Cursor Pin
Francis Paran29-Apr-11 10:31
Francis Paran29-Apr-11 10:31 
GeneralRe: Generating Huffman Coding using Two Queues and a Cursor Pin
David Crow2-May-11 2:51
David Crow2-May-11 2:51 
QuestionWindows 7 compatible code in VC++ MFC Pin
Janaiko28-Apr-11 3:34
Janaiko28-Apr-11 3:34 
AnswerRe: Windows 7 compatible code in VC++ MFC Pin
Hans Dietrich28-Apr-11 4:10
mentorHans Dietrich28-Apr-11 4:10 
AnswerRe: Windows 7 compatible code in VC++ MFC Pin
Albert Holguin28-Apr-11 8:41
professionalAlbert Holguin28-Apr-11 8:41 
AnswerRe: Windows 7 compatible code in VC++ MFC Pin
Andrew Phillips30-Apr-11 6:16
Andrew Phillips30-Apr-11 6:16 
QuestionIs PnP Device ID unique Pin
champ2328-Apr-11 2:42
champ2328-Apr-11 2:42 
AnswerRe: Is PnP Device ID unique Pin
Hans Dietrich28-Apr-11 4:12
mentorHans Dietrich28-Apr-11 4:12 
QuestionBitmap in List control Pin
Anu_Bala28-Apr-11 0:28
Anu_Bala28-Apr-11 0:28 
QuestionRe: Bitmap in List control Pin
David Crow28-Apr-11 3:16
David Crow28-Apr-11 3:16 
QuestionC++ program and my __asm Pin
francesco.s27-Apr-11 23:51
francesco.s27-Apr-11 23:51 
AnswerRe: C++ program and my __asm Pin
Richard MacCutchan28-Apr-11 1:27
mveRichard MacCutchan28-Apr-11 1:27 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.