Solved

Build Huffman Tree with Priority Queue in C

Posted on 2007-04-08
8
761 Views
Last Modified: 2011-09-20
Hi,

I am working on the Huffman Algorithm in C for my class project.  I am having trouble building the huffman tree to start.  This is what I have so far:

TreeNode * buildHuffmanTree(int freqs[256])
{
  int i;
  PriorityQueue forest;
  TreeNode* leftP, *rightP, *tmp;
  TreeEntry* top;
 
  CreatePQueue(&forest);
 
  /* YOU FILL IN THE REST OF THIS CODE */
  for (i = 0; i < 256; i++)
  {
      if (freqs[i] > 0)
        {
          leftP = malloc (sizeof(TreeNode));
          leftP->left = NULL;
          leftP->right = NULL;
          pqInsert(leftP, &forest);
      }
   }

        while (freqs[i] > 1)
      {
         
          leftP = deleteMin(&forest);
          rightP = deleteMin(&forest);
          tmp->left = leftP;
          tmp->right = rightP;
          tmp = MakeNode(top->symbol, top->weight, tmp->left, tmp->right);
          pqInsert(tmp, &forest);
      }
      return tmp;
{

If anyone has any advice I would appreciate it.  Thanks.
0
Comment
Question by:Karamelg11
  • 3
  • 3
  • 2
8 Comments
 
LVL 16

Expert Comment

by:AlexNek
ID: 18873408
0
 

Author Comment

by:Karamelg11
ID: 18873454
I am familiar with all those web pages, and it doesn't really help me with implementing the actual code to create a tree using a priority queue.
0
 
LVL 84

Expert Comment

by:ozo
ID: 18873511
are you able to implement deleteMin and pqInsert?
0
Problems using Powershell and Active Directory?

Managing Active Directory does not always have to be complicated.  If you are spending more time trying instead of doing, then it's time to look at something else. For nearly 20 years, AD admins around the world have used one tool for day-to-day AD management: Hyena. Discover why

 
LVL 84

Expert Comment

by:ozo
ID: 18873515
0
 
LVL 16

Expert Comment

by:AlexNek
ID: 18873521
What is then your troubles? If you know algorithm very well then try to write pseudo code and then convert it to C
Here is one sample
http://www.codeproject.com/cpp/Huffman_coding.asp
0
 

Author Comment

by:Karamelg11
ID: 18873596
ozo - I am able to implement deleteMin and pqInsert and  I have in the following code.  AlexNek, converting it to C is where I am having the problem.  I had posted the code I had written in hopes of getting criticism on what I may be doing wrong.


TreeNode * buildHuffmanTree(int freqs[256])
{
  int i;
  PriorityQueue forest;
  TreeNode* leftP, *rightP, *tmp;
  TreeEntry* top;
 
  CreatePQueue(&forest);
 
  /* YOU FILL IN THE REST OF THIS CODE */
  for (i = 0; i < 256; i++)
  {
      if (freqs[i] > 0)
        {
          leftP = malloc (sizeof(TreeNode));
          leftP->left = NULL;
          leftP->right = NULL;
          top->weight = freqs[i];
          top->symbol = (char) i;
          leftP = MakeNode(top->symbol, top->weight, leftP->left, leftP->right);
          pqInsert(leftP, &forest);
      }
   }

        while (tmp->left&&tmp->right != NULL)
      {
         
          leftP = deleteMin(&forest);
          rightP = deleteMin(&forest);
          tmp->left = leftP;
          tmp->right = rightP;
          tmp = MakeNode(top->symbol, top->weight, tmp->left, tmp->right);
          pqInsert(tmp, &forest);
      }
      return tmp;
{
0
 
LVL 16

Accepted Solution

by:
AlexNek earned 500 total points
ID: 18873653
>converting it to C is where I am having the problem.
It can't be a big problem. Post the pseudo code and notice the parts with troubles.

>...in hopes of getting criticism
This lines look not so good for me.
          tmp->left = leftP;
          tmp->right = rightP;

          tmp = MakeNode(top->symbol, top->weight, tmp->left, tmp->right);
You assign unassigned variable /at least I can't see where it was/, fill the fields and then assign variable.

I have a small notices in addition. I don't like:
- function parameters like int freqs[256
- variables declaration in one line TreeNode* leftP, *rightP, *tmp;
- such a logical expression while (tmp->left&&...
0
 
LVL 84

Expert Comment

by:ozo
ID: 18880541
top->weight and top->symbol also seem to be referencing an undefined pointer
what is MakeNode, and how  are TreeNode and TreeEntry defined?
0

Featured Post

What is SQL Server and how does it work?

The purpose of this paper is to provide you background on SQL Server. It’s your self-study guide for learning fundamentals. It includes both the history of SQL and its technical basics. Concepts and definitions will form the solid foundation of your future DBA expertise.

Question has a verified solution.

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

Suggested Solutions

Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
This is an explanation of a simple data model to help parse a JSON feed
In this fourth video of the Xpdf series, we discuss and demonstrate the PDFinfo utility, which retrieves the contents of a PDF's Info Dictionary, as well as some other information, including the page count. We show how to isolate the page count in a…
In this seventh video of the Xpdf series, we discuss and demonstrate the PDFfonts utility, which lists all the fonts used in a PDF file. It does this via a command line interface, making it suitable for use in programs, scripts, batch files — any pl…

770 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