Questions about qsort( ) to sort pointer to struct.

Discussion in 'C Programming' started by PCHOME, Jun 15, 2005.

  1. PCHOME

    PCHOME Guest

    Hi!

    I have questions about qsort( ). Is anyone be willing to help?

    I use the following struct:
    struct Struct_A{
    double value;
    ...
    } *AA, **pAA;

    After allocating memory, I have pAA[n], and AA[n].
    For all i, 0 <= i < n, pAA = &AA ;

    I want to retrieve all the AA.value's according to the
    value(decending order). So I want to sort.
    Instead of sorting the whole AA[n](size_of(struct Struct_A) is very
    large),
    I use pAA as a handle and sort pAA according to pAA->value.
    pAA[0]->value should be the biggest one.

    I triied:
    qsort( (void **) pAA, n, sizeof(struct Struct_A * ), comp);
    and
    int comp(const void * row1, const void * row2)

    struct Struct_A * Arow1
    = (struct Struct_A *) row1;

    struct Struct_A * Arow2
    = (struct Struct_A *) row2;

    if ( Arow1->value < Arow2->value) return (1);
    elseif if if ( Arow1->value > Arow2->value) return (-1);
    else return(0);


    }
    The code can run, but not in the way I need.

    before sort:
    pAA[0]->value = 0.688875
    pAA[1]->value = 0.580136
    pAA[2]->value = 0.379049
    pAA[3]->value = 0.606478
    pAA[4]->value = 0.742888
    pAA[5]->value = 0.908687
    pAA[6]->value = 0.969579
    after sort
    pAA[0]->value = 0.969579
    pAA[1]->value = 0.908687
    pAA[2]->value = 0.742888
    pAA[3]->value = 0.606478
    pAA[4]->value = 0.688875
    pAA[5]->value = 0.379049
    pAA[6]->value = 0.580136

    and the following one works.
    int comp(const void * row1, const void * row2)
    {

    struct Struct_A * Arow1
    = *((struct Struct_A **) row1);

    struct Struct_A * Arow2
    = *((struct Struct_A **) row2);

    if ( Arow1->value < Arow2->value) return (1);

    else if ( Arow1->value > Arow2->value) return (-1);

    else return 0;

    }

    Why does "*((struct Struct_A **) row1)" work? but not "(struct Struct_A
    *) row1"?
    To me, Both row1 point to the same location "&AA".
    I am confused why the (struct Struct_A *) row1 version can not lead to
    the correct result?

    Is anyone able to use PLAIN English explain what is the difference?
    and why dose the 2nd can not sort by "value"?

    A sorting need to swap data.
    The first one swap pAA and pAA[j] if necessary.
    What data will the (struct Struct_A *) row1 version indeed swap?

    Thanks!
    PCHOME, Jun 15, 2005
    #1
    1. Advertising

  2. PCHOME

    Eric Sosman Guest

    PCHOME wrote:
    > Hi!
    >
    > I have questions about qsort( ). Is anyone be willing to help?
    >
    > I use the following struct:
    > struct Struct_A{
    > double value;
    > ...
    > } *AA, **pAA;
    >
    > After allocating memory, I have pAA[n], and AA[n].
    > For all i, 0 <= i < n, pAA = &AA ;
    >
    > I want to retrieve all the AA.value's according to the
    > value(decending order). So I want to sort.
    > Instead of sorting the whole AA[n](size_of(struct Struct_A) is very
    > large),
    > I use pAA as a handle and sort pAA according to pAA->value.
    > pAA[0]->value should be the biggest one.
    >
    > I triied:
    > qsort( (void **) pAA, n, sizeof(struct Struct_A * ), comp);


    It would be better to use

    qsort (pAA, n, sizeof *pAA, comp);

    First, the `(void**)pAA' cast is wrong -- you will get
    away with it on many machines, but it is wrong nonetheless
    and there's no benefit in taking unnecessary risks. The
    correct cast would be `(void*)pAA' but even that much is
    unnecessary (assuming a prototype for qsort() is in scope,
    which it certainly should be). In fact, with the prototype
    the compiler will treat your original as equivalent to
    `(void*)(void**)pAA'.

    Second, `sizeof *pAA' is preferable to your original.
    The original you wrote was correct, but `sizeof *pAA' offers
    fewer opportunities to make silly errors. The compiler knows
    what type `pAA' points to; let the compiler do the work of
    figuring out the size.

    > and
    > int comp(const void * row1, const void * row2)
    >
    > struct Struct_A * Arow1
    > = (struct Struct_A *) row1;


    This would be right if you were sorting an array of
    `struct Struct_A' objects, but you're not: you're sorting an
    array of pointers to such objects. `row1' does not point
    to a struct; it points to a pointer to a struct. Here's
    what you need:

    struct Struct_A * Arow1
    = * (struct Struct_A **)row1;

    That is: You convert `row1' from `void*' to a pointer to an
    element of the array. Then since the array element is itself
    a pointer to the ultimate struct, you apply `*' to the converted
    array pointer to fetch the struct pointer.

    Here's a simple rule: The type of the first argument to
    qsort() is the type to which the comparison function's
    arguments should be converted, give or take a `const'.

    > [...]
    > and the following one works.
    > int comp(const void * row1, const void * row2)
    > {
    >
    > struct Struct_A * Arow1
    > = *((struct Struct_A **) row1);


    Right. The things being sorted are pointers, and comp()
    receives pointers to two of those things, hence the double
    `**': comp() receives pointers to pointers.

    > Why does "*((struct Struct_A **) row1)" work? but not "(struct Struct_A
    > *) row1"?
    > To me, Both row1 point to the same location "&AA".


    No, `row1' points to an element in the `pAA' array and
    not to a struct at all. The array element points to a struct
    in the `AA' array, but `row1' does not point there.

    | | | |
    +------+ +-------------+
    row1 ---> |pAA----> | AA[j] |
    +------+ +-------------+
    | | | |
    +------+ +-------------+
    | | | |


    (You say that i==j when the sort begins, but that will not
    remain true when qsort() rearranges the `pAA' array.)

    --
    Eric Sosman, Jun 15, 2005
    #2
    1. Advertising

  3. PCHOME

    pete Guest

    PCHOME wrote:
    >
    > Hi!
    >
    > I have questions about qsort( ). Is anyone be willing to help?
    >
    > I use the following struct:
    > struct Struct_A{
    > double value;
    > ...
    > } *AA, **pAA;
    >
    > After allocating memory, I have pAA[n], and AA[n].
    > For all i, 0 <= i < n, pAA = &AA ;
    >
    > I want to retrieve all the AA.value's according to the
    > value(decending order). So I want to sort.
    > Instead of sorting the whole AA[n](size_of(struct Struct_A) is very
    > large),
    > I use pAA as a handle and sort pAA according to pAA->value.
    > pAA[0]->value should be the biggest one.
    >
    > I triied:
    > qsort( (void **) pAA, n, sizeof(struct Struct_A * ), comp);
    > and
    > int comp(const void * row1, const void * row2)
    >
    > struct Struct_A * Arow1
    > = (struct Struct_A *) row1;
    >
    > struct Struct_A * Arow2
    > = (struct Struct_A *) row2;
    >
    > if ( Arow1->value < Arow2->value) return (1);
    > elseif if if ( Arow1->value > Arow2->value) return (-1);
    > else return(0);
    >
    > }
    > The code can run, but not in the way I need.
    >
    > before sort:
    > pAA[0]->value = 0.688875
    > pAA[1]->value = 0.580136
    > pAA[2]->value = 0.379049
    > pAA[3]->value = 0.606478
    > pAA[4]->value = 0.742888
    > pAA[5]->value = 0.908687
    > pAA[6]->value = 0.969579
    > after sort
    > pAA[0]->value = 0.969579
    > pAA[1]->value = 0.908687
    > pAA[2]->value = 0.742888
    > pAA[3]->value = 0.606478
    > pAA[4]->value = 0.688875
    > pAA[5]->value = 0.379049
    > pAA[6]->value = 0.580136
    >
    > and the following one works.
    > int comp(const void * row1, const void * row2)
    > {
    >
    > struct Struct_A * Arow1
    > = *((struct Struct_A **) row1);
    >
    > struct Struct_A * Arow2
    > = *((struct Struct_A **) row2);
    >
    > if ( Arow1->value < Arow2->value) return (1);
    >
    > else if ( Arow1->value > Arow2->value) return (-1);
    >
    > else return 0;
    >
    > }
    >
    > Why does "*((struct Struct_A **) row1)" work?
    > but not "(struct Struct_A *) row1"?
    > To me, Both row1 point to the same location "&AA".
    > I am confused why the (struct Struct_A *) row1 version can not lead to
    > the correct result?
    >
    > Is anyone able to use PLAIN English explain what is the difference?


    I wish I could.

    > and why dose the 2nd can not sort by "value"?
    >
    > A sorting need to swap data.
    > The first one swap pAA and pAA[j] if necessary.
    > What data will the (struct Struct_A *) row1 version indeed swap?


    /* BEGIN output new.c */

    AA[0].value is 0.688875
    AA[1].value is 0.580136
    AA[2].value is 0.379049
    AA[3].value is 0.606478
    AA[4].value is 0.742888
    AA[5].value is 0.908687
    AA[6].value is 0.969579

    pAA[0]->value is 0.969579
    pAA[1]->value is 0.908687
    pAA[2]->value is 0.742888
    pAA[3]->value is 0.688875
    pAA[4]->value is 0.606478
    pAA[5]->value is 0.580136
    pAA[6]->value is 0.379049

    /* END output new.c */

    /* BEGIN new.c */

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

    #define NELEM 7

    struct Struct_A {
    double value;
    struct Struct_A *next;
    };

    int comp(const void *arg1, const void *arg2);

    int main(void)
    {
    struct Struct_A *AA, **pAA;
    unsigned index;

    AA = malloc(NELEM * sizeof *AA);
    pAA = malloc(NELEM * sizeof *pAA);
    if (AA == NULL || pAA == NULL) {
    exit(EXIT_FAILURE);
    }
    AA[0].value = 0.688875;
    AA[1].value = 0.580136;
    AA[2].value = 0.379049;
    AA[3].value = 0.606478;
    AA[4].value = 0.742888;
    AA[5].value = 0.908687;
    AA[6].value = 0.969579;
    puts("/* BEGIN output new.c */\n");
    for (index = 0; index != NELEM; ++index) {
    pAA[index] = AA + index;
    printf("AA[%u].value is %f\n", index, AA[index] .value);
    }
    putchar('\n');
    qsort(pAA, NELEM, sizeof *pAA, comp);
    for (index = 0; index != NELEM; ++index) {
    printf("pAA[%u]->value is %f\n", index, pAA[index]->value);
    }
    free(AA);
    free(pAA);
    puts("\n/* END output new.c */");
    return 0;
    }

    int comp(const void *arg1, const void *arg2)
    {
    double value_1 = (**(struct Struct_A**)arg1).value;
    double value_2 = (**(struct Struct_A**)arg2).value;

    return value_1 > value_2 ? -1 : value_1 != value_2;
    }

    /* END new.c */


    --
    pete
    pete, Jun 16, 2005
    #3
  4. Re: Questions about qsort( ) to sort pointer to struct.

    Nice job!
    I_have_nothing, Jul 8, 2005
    #4
  5. Re: Questions about qsort( ) to sort pointer to struct.

    "I_have_nothing" <> writes:
    > Nice job!


    What?

    Don't assume that your readers have access to the article to which
    you're replying. (It appears to have expired on my server.)

    If you've been following this newsgroup, you've seen the following
    many times:

    If you want to post a followup via groups.google.com, don't use
    the broken "Reply" link at the bottom of the article. Click on
    "show options" at the top of the article, then click on the
    "Reply" at the bottom of the article headers.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
    We must do something. This is something. Therefore, we must do this.
    Keith Thompson, Jul 8, 2005
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Angus Comber
    Replies:
    7
    Views:
    1,153
    Richard Heathfield
    Feb 5, 2004
  2. beetle
    Replies:
    2
    Views:
    902
    beetle
    Jan 25, 2005
  3. Zero
    Replies:
    16
    Views:
    651
    Barry Schwarz
    Nov 19, 2005
  4. Maria Mela

    qsort wiht struct and pointers

    Maria Mela, Jan 25, 2007, in forum: C Programming
    Replies:
    10
    Views:
    713
    Dave Thompson
    Feb 6, 2007
  5. aleksa

    Struct pointer vs. struct array pointer

    aleksa, Feb 20, 2013, in forum: C Programming
    Replies:
    16
    Views:
    465
    Shao Miller
    Feb 20, 2013
Loading...

Share This Page