Use qsort() to sort array of pointers to struct

This is a discussion on Use qsort() to sort array of pointers to struct within the C Programming forums, part of the General Programming Boards category; Hey Everyone, I'm fairly new to C and am having trouble sorting a linked list. To do this I decided ...

  1. #1
    Registered User
    Join Date
    Apr 2012
    Posts
    3

    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.
    Last edited by VIgnotam; 04-03-2012 at 07:44 PM.

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  3. #3
    Registered User
    Join Date
    Apr 2012
    Posts
    3
    I realize that and I've tried taking away the asterisk with no luck. The reason why I put it in was because qsort() passes a pointer to another pointer in this case. But you're right, it's wrong, but taking it away doesn't work either. Garbage just gets printed, but if I use the array directly, before it gets passed to cmpAge(), like tmp[3]->d.age, it works fine so the problem is not in the values stored in the array but in the way I'm accessing them within cmpAge().

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,417
    > LINK ia = (LINK)a;
    These should be
    LINK *ia = (LINK*)a;

    And in the body of the code, use
    (*ia)->member
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    Registered User
    Join Date
    Apr 2012
    Posts
    3
    Thanks Salem. That worked.

    I feel really stupid because I'm 95% sure I tried that. When I was testing I was only changing the first argument after the control string in the printf() and I got an error, as it did today, until my brain decided to return and I realized the errors were coming from the other references. What can you do?

    Thanks again

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 1
    Last Post: 07-30-2011, 12:49 PM
  2. Array of Struct sort
    By fukki in forum C++ Programming
    Replies: 1
    Last Post: 10-07-2010, 06:08 AM
  3. Using qsort to sort an array of strings
    By MSF1981 in forum C Programming
    Replies: 31
    Last Post: 05-17-2009, 01:31 AM
  4. How to sort an array of pointers to structure
    By broli86 in forum C Programming
    Replies: 3
    Last Post: 06-30-2008, 02:52 PM
  5. using qsort to sort an array of strings
    By bobthebullet990 in forum C Programming
    Replies: 6
    Last Post: 11-25-2005, 07:31 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21