0

Actually i have to create huffman tree for that i need to sort the frequency and i am using qsort() function for that. But when i try to display the frequency it show still the same pattern (Not the sorted one). Here is my code:-

        struct node
        {
            int value;
            char letter;                 /* symbol */
            struct node *left,*right;    /* left and right subtrees */
        };
    typedef struct node Node;
//Given below is the frequency of all 27 alphabets
int englishLetterFrequencies [27] = {81, 15, 28, 43, 128, 23, 20, 61, 71, 2, 1, 40, 24, 69, 76, 20, 1, 61, 64, 91, 28, 10, 24, 1, 20, 1, 130};

here is my function where i try to build huffman (its inside the main() ):

/*builds the huffman tree and returns its address by reference*/

    void buildHuffmanTree(Node **tree){
        Node *temp;
        Node *array[27];
        int i, subTrees = 27;
        int smallOne;

        for (i=0;i<27;i++)
        {
            array[i] = malloc(sizeof(Node));
            array[i]->value = englishLetterFrequencies[i];
            array[i]->letter = i;
            array[i]->left = NULL;
            array[i]->right = NULL;
        }
         smallOne=sorting(array); //this function is responsible for sorting. I HAVE QSORT() CALL IN THIS FUNCTION

    return;
}

see its function definition :

int sorting(Node *array[])
{
    int smaller;
    int i = 0; int d,p;
    printf("the array frequency is \n");
    for(d=0;d < 27;d++)
    printf("%d  ",*array[d]);
    // sorting of arrays
    qsort(array,27,sizeof(*array),&cmpfunc); 
    //////////////////////////
    printf("\n the sorted array frequency is \n");
        for(p=0;p < 27;p++)
    printf("%d  ",*array[p]);

    return smaller;
}

whereas the cmpfunc() is here like this //PROBABLY MISTAKE IS HERE

 int cmpfunc (const void * a, const void * b)
    {
          return ( ((Node *)a)->value - ((Node *)b)->value );
    }

Any idea why it don't sort the arrays ?

Improve this question
2
  • 1
    Should qsort(*array be qsort(array ? And cmpfunc gets a lot more readable (and less error-prone) if it contains actual Node* variables that you initialize from the void* args, IMHO. Commented Jan 6, 2014 at 23:21
  • IF I PUT "*array" (instead of "array") at the place of first argument (in order to make some changes and then if i see output,Its shows that in the first two position is 0 but list is still unsorted) and when i put just "array" it again shows the same list of frequency Commented Jan 6, 2014 at 23:28

2 Answers 2

Reset to default
2 
 return ( (*(int**)a) - (*(int**)b ));

This is casting a and b as "pointer-to-pointer-to-int", so by dereferencing them only once you then calculate the difference between two pointers. What you mean is:

 return ( (*(Node **)a)->value - (*(Node **)b)->value );

because whilst **(int**)a might work in this case it is massively confusing to anyone trying to understand the code.

Edit: sorry, I ended up missing a dereference there myself - fixed.

Also:

printf("%d  ",*array[d]);

should be

printf("%d  ",array[d]->value);

for the same reason.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

are you sure that my qsort() is correct ?? Last argument with &cmpfun ?? because i have done the changes you asked me to do..Its still showing the same frequecies and I DON'T KNOW WHY IT GIVES 0 AT THE PLACE OF FIRST TWO FREQUENCIES ?? any idea ?
@user3085082 sorry, my mistake. I literally confused myself with the struct-aliasing-int business and ending up missing out the indirection from qsort() itself.
1

Your comparator is wrong, and your assumption of how qsort works isn't far behind it.

For sorting a pointer array of Node* you need a comparator like this:

int cmpfunc (const void * a, const void * b)
{
    const Node **lhs = (const Node **)a;
    const Node **rhs = (const Node **)b;
    return (*lhs)->value < (*rhs)->value ? -1
        : ((*rhs)->value < (*lhs)->value);
}

Stripping all the extraneous junk out, including the sorting() call and invoking qsort directly...

#include <stdio.h>
#include <stdlib.h>

struct node
{
    int value;
    char letter;                 /* symbol */
    struct node *left,*right;    /* left and right subtrees */
};
typedef struct node Node;

static const int englishLetterFrequencies [27] =
{
    81, 15, 28, 43, 128, 23,
    20, 61, 71, 2, 1, 40, 24,
    69, 76, 20, 1, 61, 64, 91,
    28, 10, 24, 1, 20, 1, 130
};

int cmpfunc (const void * a, const void * b)
{
    const Node **lhs = (const Node **)a;
    const Node **rhs = (const Node **)b;
    return (*lhs)->value < (*rhs)->value ? -1
        : ((*rhs)->value < (*lhs)->value);
}

void buildHuffmanTree(Node **tree)
{
    Node *array[27];
    int i;
    
    for (i=0;i<27;i++)
    {
        array[i] = malloc(sizeof(*array[i]));
        array[i]->value = englishLetterFrequencies[i];
        array[i]->letter = (char)i;
        array[i]->left = NULL;
        array[i]->right = NULL;
    }
    
    qsort(array, 27, sizeof(*array), cmpfunc);
    
    for (i=0; i<27; ++i)
        printf("array[%d]->value = %d\n", i, array[i]->value);
    
    return;
}

int main()
{
    buildHuffmanTree(NULL);
    return 0;
}

Output

array[0]->value = 1
array[1]->value = 1
array[2]->value = 1
array[3]->value = 1
array[4]->value = 2
array[5]->value = 10
array[6]->value = 15
array[7]->value = 20
array[8]->value = 20
array[9]->value = 20
array[10]->value = 23
array[11]->value = 24
array[12]->value = 24
array[13]->value = 28
array[14]->value = 28
array[15]->value = 40
array[16]->value = 43
array[17]->value = 61
array[18]->value = 61
array[19]->value = 64
array[20]->value = 69
array[21]->value = 71
array[22]->value = 76
array[23]->value = 81
array[24]->value = 91
array[25]->value = 128
array[26]->value = 130

Spend some time learning how the algorithm works, and don't take shortcuts. You're going to need two comparator functions for what it looks like you're ultimately going to do (assuming I understand how you're planning on building your huffman tree).

Improve this answer

4 Comments

that was a big help Whoz ..But i am not able to understand the return part,I mean:- "return (*lhs)->value < (*rhs)->value ? -1 : ((*rhs)->value < (*lhs)->value ? 1 : 0);" and also why we use 2 ** here :- "const Node **lhs = (const Node **)a;" THANKS FOR THE EXPLANATION
The Node** is because of how qsort works. it passes you the address of each item in your sequence being compared. In this case that is the address of a pointer, i.e. a Node*. The return statement in the comparator could be made significantly simpler since you stand no chance of an underflow with your static data, but I prefer to do it the same way without that assumption.
The comparator only need return negative, zero, or positive, so the subtraction itself is fine - nested ternaries are going to earn a massively confusing, too ;)
@Notlikethat The subtraction is fine for the OP only because of the value-domain. It would not be fine as a general solution; Such an example would be the first operand being at or near INT_MIN and a resulting subtraction of the second operand triggering underflow. That is the sole reason I use that comparator as a cookie-cutter. If ternaries aren't someone's cup of tea, a if-duo with inline returns would work equally as well, or an if-else-if-else quad if single-return is also desired to reduce the massive confusion overload.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.