Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 851
  • Last Modified:

Build Huffman Tree with Priority Queue in C

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
Karamelg11
Asked:
Karamelg11
  • 3
  • 3
  • 2
1 Solution
 
Karamelg11Author Commented:
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
 
ozoCommented:
are you able to implement deleteMin and pqInsert?
0
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
ozoCommented:
0
 
AlexNekCommented:
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
 
Karamelg11Author Commented:
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
 
AlexNekCommented:
>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
 
ozoCommented:
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

Free Tool: Subnet Calculator

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

  • 3
  • 3
  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now