Thread: Use qsort() to sort array of pointers to struct

Hey Everyone,

I'm fairly new to C and am having trouble sorting a linked list. To do this I decided to put the element pointers in an array and use qsort() to do the actual sorting by referencing the list data in my compare function used by qsort().


Here's the relevent bits of code so you can get an idea of what I'm trying to do.

Code:

struct data {
    char    name[20];
    int    age;
    int    weight;
};


typedef struct data        DATA;


struct linked_list {
    DATA                   d;
    struct linked_list    *next
};


typedef struct linked_list     ELEMENT;
typedef ELEMENT *             LINK;




/* This next function is where I'm having problems. It's my understanding, and perhaps I'm wrong, that 
qsort() passes a pointer to element in the given array to the compare function, so in this case it would 
be a pointer to a pointer. Below is what I originally tried (*ia->d.age), but this produced a few warnings 
about %s in the printf() expecting char* not an int. I then took away the asterisks and it compiled without 
warnings but used garbage values, so no luck there either. After that I tried a whole whack of things, 
none of which worked. */
int cmpAge(const void *a, const void *b)
{
    LINK ia = (LINK)a;
    LINK ib = (LINK)b;
    
    /* This is a quick/dirty printf() I'm using to help me debug */
    printf("%s & %s (%d - %d) = %d\n", *ia->d.name, *ib->d.name, *ia->d.age, *ib->d.age, (*ia->d.age - *ib->d.age));
    
    /* If working, compare ages and return value <, =, >, 0 */
    return (*ia->d.age - *ib->d.age);
}


LINK sortByAge(LINK a)
{
    int i, size = countem(a)        /* countem = simple function to count members in linked list */
    LINK tmp[size];                   /* create array of type LINK to hold pointers to elements of linked list*/
    
    /* Fill LINK array */
    for (i = 0; a != NULL; ++i, a = a->next) 
        tmp[i] = a;
        
    /* sort array by using cmpAge() */
    qsort(tmp, size, sizeof(LINK), cmpAge);
    
    /* change pointers in linked list to the order resulting from qsort() */
    for (i = 0; i < size; ++i) {
        if (i = (size - 1))
            tmp[i]->next = NULL;
        else
            tmp[i]->next = tmp[i+1];
    }
    
    /* return head address of list */
    return tmp[0];
}

It seems to me, I'm obviously not referencing the struct data correctly.


Does anyone have any suggestions?


Thanks.

If you have a node pointer:

Code:

struct node *ptr;

Then you use this to get its members:

Code:

ptr->member

Not this:

Code:

*ptr->member

. The only reason you'd use that would be if you had a pointer to a pointer to a node. You don't.

Your compiler should be complaining at you, telling you what lines you have wrong.


Quzah.

> LINK ia = (LINK)a;
These should be
LINK *ia = (LINK*)a;

And in the body of the code, use
(*ia)->member