help me sort my array of structs 
Author Message
 help me sort my array of structs

OK, i need to sort an array of structs on a user selected struct
member.  i am having real trouble getting this to work correctly.

i tried    qsort(sarray.MEMBER, n, sizeof(struct datanode), compare);
MEMBER being any of the members in the struct of course.
this produced runtime errors on all members execpt lname, which mixed up

data  within  the structs.

so my question how do you sort an array of structs on a user defined
field, without mixing the struct's data with data from other struct's?
is it even possible (i believe it is, i just cannot figure it out!)?

thanks

here is some of my code:

struct datanode {
 char lname [26];
 char fname [21];
 char iname [26];
 char course [11];
 char date [21];
 char time [21];

Quote:
};

....
struct datanode *sarray;

sarray = malloc(n * sizeof(struct datanode));
/*...i fill the array with structs from FILE...*/

/*...here the user should select which member of the datanode struct to
sort on (using submenu, SELECT/CASE stmts)*/

qsort(sarray, n, sizeof(struct datanode), compare); /*this gives results

in ordering by first character in lname field only*/
...
int compare(const char *vp, const char *vq)
{
     const char *p = vp, *q = vq;
     return (*p - *q);

Quote:
}



Thu, 06 Dec 2001 03:00:00 GMT  
 help me sort my array of structs

Quote:

> OK, i need to sort an array of structs on a user selected struct
> member.  i am having real trouble getting this to work correctly.

> i tried    qsort(sarray.MEMBER, n, sizeof(struct datanode), compare);
> MEMBER being any of the members in the struct of course.
> this produced runtime errors on all members execpt lname, which mixed up
> data  within  the structs.

> so my question how do you sort an array of structs on a user defined
> field, without mixing the struct's data with data from other struct's?
> is it even possible (i believe it is, i just cannot figure it out!)?

> here is some of my code:

> struct datanode {
>  char lname [26];
>  char fname [21];
>  char iname [26];
>  char course [11];
>  char date [21];
>  char time [21];
> };

    unsigned displacement, length;    /* Global, for use by main() and
compare() */

Quote:
> ....
> struct datanode *sarray;

> sarray = malloc(n * sizeof(struct datanode));
> /*...i fill the array with structs from FILE...*/

> /*...here the user should select which member of the datanode struct to
> sort on (using submenu, SELECT/CASE stmts)*/

Here you need to convert the selection to a displacement into the struct of
the start of the field to be sorted and the length of that field:

    displacement = /* 0 for 1st field, ... */
    length = /* sizeof selected field */

Quote:
> qsort(sarray, n, sizeof(struct datanode), compare); /* sort array of
> datanodes on selected field */

Lets generalize to sort on an entire (char) field. qsort() will pass
compare() pointers to datanode structures. Compare takes void pointer
arguments, so...

Quote:
> int compare(const void *vp, const void *vq)
> {
>      const char *p = vp, *q = vq;
>      return strncmp(p+displacement,q+displacement,length);
> }

You were mighty close!

Morris Dovey
West Des Moines, Iowa USA



Thu, 06 Dec 2001 03:00:00 GMT  
 help me sort my array of structs
The array (of structs)  works well when sorted on last name, which is the most
important for this program.  But it still does not sort correctly on the
remaining fields, and I cannot "see" why it fials to do so.  Did I implement
the suggestions correctly?  Perhaps I screwed something up along the way!

I included the entire code for the precedure below.

Thanks for the suggestions..

Quote:
> > struct datanode {
> >  char lname [26];
> >  char fname [21];
> >  char iname [26];
> >  char course [11];
> >  char date [21];
> >  char time [21];
> > };

>     unsigned displacement, length;    /* Global, for use by main() and
> compare() */

void SortRecs()
{
     FILE *fileptr;
     FILE *prntptr;
     char  ans;
     int count, rec_cnt = 0, sort_cnt = 1;
     struct datanode student;
     int test, i = 0, n;
     struct datanode *sarray;
     int flag = YES;
     f ileptr = fopen("DailyLoginFile.txt", "rb");
     prntptr = fopen("DailyPrintFile.txt", "ab");

     while((test = getc(fileptr) ) != EOF)
     {
           ungetc(test, fileptr);
           fread(&student, sizeof student, 1, fileptr);
           rec_cnt++;
     }

      fclose(fileptr);
      count = rec_cnt;
      n = rec_cnt;
      rec_cnt = 0;

      sarray = malloc(n * sizeof(struct datanode)); /*make graceful?*/

      fileptr = fopen("DailyLoginFile.txt", "rb");

      while((test = getc(fileptr) ) != EOF)
      {
       ungetc(test, fileptr);
       fread(&student, sizeof(struct datanode), 1, fileptr);
       sarray[i] = student;
       i++;
       rec_cnt++;
      }
      i = 0;
     do{
              SortMenu();
              ans = getchar();
              fflush(stdin);
              ans = toupper(ans);
              switch(ans)
               {
                    case ('F'):             /*FIRST NAME*/
                    {
                         displacement = 1;/* 0 for 1st field, ... */
                         length = 21;/* sizeof selected field */
                         qsort(sarray, n, sizeof(struct datanode), compare);
                         flag = NO;
                         break;
                    }
                    case ('L'):  /*LAST NAME WORKS!*/
                    {
                         displacement = 0;/* 0 for 1st field, ... */
                         length = 26;/* sizeof selected field */
                         qsort(sarray, n, sizeof(struct datanode), compare);
                         flag = NO;
                         break;
                    }
                    case ('I'): /*INSTRUCTOR NAME*/
                    {
                         displacement = 2;/* 0 for 1st field, ... */
                         length = 26;/* sizeof selected field */
                         qsort(sarray, n, sizeof(struct datanode), compare);
                         flag = NO;
                         break;
                    }
                    case ('C'):     /*COURSE*/
                    {
                         displacement = 3;/* 0 for 1st field, ... */
                         length = 11;/* sizeof selected field */
                         qsort(sarray, n, sizeof(struct datanode), compare);
                         flag = NO;
                         break;
                    }
                  case ('D'): /*DATE*/
                    {
                         displacement = 4;/* 0 for 1st field, ... */
                         length = 21;/* sizeof selected field */
                         qsort(sarray, n, sizeof(struct datanode), compare);
                         flag = NO;
                         break;
                    }
                case ('T'): /*TIME*/
                    {
                         displacement = 5;/* 0 for 1st field, ... */
                         length = 21;/* sizeof selected field */
                         qsort(sarray, n, sizeof(struct datanode), compare);
                         flag = NO;
                         break;
                    }
                default: /*default case, list available options*/
                    {
                         printf("\nPlease Enter F, L, I, C, D, or T.\n");
                         flag = YES;
                         break;
                    }
       }
  }while(flag == YES);

  while (i < count)
  {
       printf("%3d %s ", sort_cnt++, &sarray[i].fname);
       printf("%s ", &sarray[i].lname);
       printf("%s ", &sarray[i].iname);
       printf("%s ", &srray[i].course);
       printf("%s ", &sarray[i].date);
       printf("%s\n", &sarray[i].time);
       i++;
  }

      free(charray);
      fclose(fileptr);
      fclose(prntptr);

Quote:
}

int compare(const void *vp, const void *vq)
{
 const char *p = vp, *q = vq;
 return strncmp(p+displacement,q+displacement,length);
Quote:
}



Thu, 06 Dec 2001 03:00:00 GMT  
 help me sort my array of structs

Quote:

>OK, i need to sort an array of structs on a user selected struct
>member.  i am having real trouble getting this to work correctly.

What you want do do seems to be a "user selected" compare function.

Quote:
>i tried    qsort(sarray.MEMBER, n, sizeof(struct datanode), compare);

You should use the base address of the array you want to sort, not
some address close to the base address. The base address seems to
be "sarray" in your case.

Quote:
>MEMBER being any of the members in the struct of course.
>this produced runtime errors on all members execpt lname, which mixed up
>data  within  the structs.

Did it?

Quote:
>so my question how do you sort an array of structs on a user defined
>field, without mixing the struct's data with data from other struct's?

With a "user defined" compare function.

Quote:
>is it even possible (i believe it is, i just cannot figure it out!)?

Yes it is.

Quote:
>thanks
>here is some of my code:
>struct datanode {
> char lname [26];
> char fname [21];
> char iname [26];
> char course [11];
> char date [21];
> char time [21];
>};
>....
>struct datanode *sarray;
>sarray = malloc(n * sizeof(struct datanode));
>/*...i fill the array with structs from FILE...*/
>/*...here the user should select which member of the datanode struct to
>sort on (using submenu, SELECT/CASE stmts)*/
>qsort(sarray, n, sizeof(struct datanode), compare); /*this gives results
>in ordering by first character in lname field only*/
>...
>int compare(const char *vp, const char *vq)

You don't want to compare "char"s, you want to compare "struct datanode"s.
The signature of a compare function passed to qsort is not subject to
your choice. It's "int compare(const void *, const void *)".

Have a look at FAQ 13.9 for details.

Kurt

--
| Kurt Watzka                            



Thu, 06 Dec 2001 03:00:00 GMT  
 help me sort my array of structs


Quote:
>The array (of structs)  works well when sorted on last name, which is the most
>important for this program.  But it still does not sort correctly on the
>remaining fields, and I cannot "see" why it fials to do so.  Did I implement
>the suggestions correctly?  Perhaps I screwed something up along the way!

>I included the entire code for the precedure below.

>Thanks for the suggestions..

>> > struct datanode {
>> >  char lname [26];
>> >  char fname [21];
>> >  char iname [26];
>> >  char course [11];
>> >  char date [21];
>> >  char time [21];
>> > };

>>     unsigned displacement, length;    /* Global, for use by main() and
>> compare() */

>void SortRecs()
>{
>     FILE *fileptr;
>     FILE *prntptr;
>     char  ans;
>     int count, rec_cnt = 0, sort_cnt = 1;
>     struct datanode student;
>     int test, i = 0, n;
>     struct datanode *sarray;
>     int flag = YES;
>     f ileptr = fopen("DailyLoginFile.txt", "rb");
>     prntptr = fopen("DailyPrintFile.txt", "ab");

You need to check whether these calls to fopen() failed.

Quote:

>     while((test = getc(fileptr) ) != EOF)
>     {
>           ungetc(test, fileptr);
>           fread(&student, sizeof student, 1, fileptr);
>           rec_cnt++;
>     }

This is a very strange way of testing for the end of the file. Also
you're not checking the return value of fread() so your count may be
wrong. A simple rule of thimb is to test the return value of
every file read operation. Try

      while (fread(&student, sizeof student, 1, fileptr) == 1)
            rec_cnt++;

Incidentally why do you need this loop at all, you set up rec_cnt in
the next loop and you don't appear to need count until after that.

Quote:
>      fclose(fileptr);
>      count = rec_cnt;
>      n = rec_cnt;
>      rec_cnt = 0;

>      sarray = malloc(n * sizeof(struct datanode)); /*make graceful?*/

Consider making that

       sarray = malloc(n * sizeof *sarray); /*make graceful?*/

Then you don't worry about precisely what type is concerned, you will
always specify n units of the type that sarray points to. Don't forget to
test the return value for failure.

Quote:
>      fileptr = fopen("DailyLoginFile.txt", "rb");

Your initialisation of i is a long way away from where it is used.

Quote:
>      while((test = getc(fileptr) ) != EOF)
>      {
>       ungetc(test, fileptr);
>       fread(&student, sizeof(struct datanode), 1, fileptr);
>       sarray[i] = student;
>       i++;
>       rec_cnt++;
>      }

You can change this loop in the same way as the previous one. Also what
is the difference between i and rec_cnt?

Quote:
>      i = 0;
>     do{
>              SortMenu();
>              ans = getchar();
>              fflush(stdin);
>              ans = toupper(ans);
>              switch(ans)
>               {
>                    case ('F'):             /*FIRST NAME*/
>                    {
>                         displacement = 1;/* 0 for 1st field, ... */

Looking below you are using displacement as a byte offset. However you
aren't setting it up as a byte offset here, it seems to be some sort
of field number.  Try

                          displacement = offsetof(struct datanode, fname);

offsetof() is a standard C macro defined in <stddef.h> so you need to
include that header.It gives the byte offset of a specific member in a
structure.

Quote:
>                         length = 21;/* sizeof selected field */

Avoid "magic" constants like this where possible. There isn't a macro
like offsetof() to get the size of a structure member (although you could
make your own using the technique below). What you can do however is
this

                          length = sizeof(((struct datanode *)0)->fname);

While this appears to be dereferencing a null pointer it isn't a problem
here since sizeof does not evaluate its operand, it merely determines its
type. The construct is valid C.

--
-----------------------------------------


-----------------------------------------



Thu, 06 Dec 2001 03:00:00 GMT  
 help me sort my array of structs
Aravan...

I've made a few changes. Note how displacement differs from subscript and that I'm
reading data directly into the structure elements (no structure-to-structure
assignments) - see if this isn't closer to what you wanted:

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

#define YES 1
#define NO 0

struct datanode
{ char lname [26];
 char fname [21];
 char iname [26];
 char course [11];
 char date [21];
 char time [21];

Quote:
};

unsigned displacement, length; /* Global, for use by main() and compare() */

int compare(const void *vp, const void *vq) /* Used by qsort() */
{ const char *p = vp, *q = vq;
 return strncmp(p+displacement,q+displacement,length);

Quote:
}

void SortRecs()
{ FILE *fileptr;
 FILE *prntptr;
 char  ans;
 int count, rec_cnt = 0, sort_cnt = 1;
 struct datanode student;
 int test, i = 0, n;
 struct datanode *sarray;
 int flag = YES;
 void SortMenu(void);

 fileptr = fopen("DailyLoginFile.txt", "rb");
 prntptr = fopen("DailyPrintFile.txt", "ab");

 while((test = getc(fileptr) ) != EOF)
 { ungetc(test, fileptr);
  fread(&student, sizeof student, 1, fileptr);
   rec_cnt++;
 }
 fclose(fileptr);
 count = rec_cnt;
 n = rec_cnt;
 rec_cnt = 0;

 sarray = malloc(n * sizeof(struct datanode)); /* Check for malloc() error! */

 fileptr = fopen("DailyLoginFile.txt", "rb"); /* Check for fopen() error! */

 while((test = getc(fileptr)) != EOF)
 { ungetc(test, fileptr);
  fread(&sarray[i++], sizeof(struct datanode), 1, fileptr); /* Check return value!
*/
  rec_cnt++;
 }
 i = 0;
 do
 { SortMenu();
  ans = getchar();
  fflush(stdin);
  ans = toupper(ans);
  switch(ans)
  { case ('F'): /*FIRST NAME*/
   { displacement = &sarray[0].fname - &sarray[0];
    length = 21;
            flag = NO;
    break;
   }
   case ('L'): /*LAST NAME */
   { displacement = &sarray[0].lname - &sarray[0];
    length = 26;
            flag = NO;
    break;
   }
   case ('I'): /*INSTRUCTOR NAME*/
   { displacement = &sarray[0].iname - &sarray[0];
    length = 26;
            flag = NO;
    break;
   }
   case ('C'): /*COURSE*/
   { displacement = &sarray[0].course - &sarray[0];
    length = 11;
    flag = NO;
    break;
   }
   case ('D'): /*DATE*/
   { displacement = &sarray[0].date - &sarray[0];
    length = 21;
    flag = NO;
    break;
   }
   case ('T'): /*TIME*/
   { displacement = &sarray[0].time - &sarray[0];
    length = 21;
    flag = NO;
    break;
   }
   default: /*default case, list available options*/
   { printf("\nPlease Enter F, L, I, C, D, or T.\n");
          flag = YES;
    break;
   }
      }
 } while (flag == YES);

 qsort(sarray, n, sizeof(struct datanode), compare);

 while (i < count)
 { printf("%3d %s ", sort_cnt++, &sarray[i].fname);
  printf("%s ", &sarray[i].lname);
  printf("%s ", &sarray[i].iname);
  printf("%s ", &sarray[i].course);
  printf("%s ", &sarray[i].date);
  printf("%s\n",&sarray[i].time);
  i++;
 }
 free(sarray);
  fclose(fileptr);
 fclose(prntptr);

Quote:
}

Morris Dovey
West Des Moines, Iowa USA



Thu, 06 Dec 2001 03:00:00 GMT  
 help me sort my array of structs
Aravan,

Not sure what your over all need is but if you are interested I have a
library that implements a Red/Black Binary Tree.

keyinsert()
keydelete()
keylocate()
keynext()
keyprevious
keyfirst()
keylast()

written in plain jane ANSI C.

David Norton

Quote:

>OK, i need to sort an array of structs on a user selected struct
>member.  i am having real trouble getting this to work correctly.

>i tried    qsort(sarray.MEMBER, n, sizeof(struct datanode), compare);
>MEMBER being any of the members in the struct of course.
>this produced runtime errors on all members execpt lname, which mixed up

>data  within  the structs.

>so my question how do you sort an array of structs on a user defined
>field, without mixing the struct's data with data from other struct's?
>is it even possible (i believe it is, i just cannot figure it out!)?

>thanks

>here is some of my code:

>struct datanode {
> char lname [26];
> char fname [21];
> char iname [26];
> char course [11];
> char date [21];
> char time [21];
>};
>....
>struct datanode *sarray;

>sarray = malloc(n * sizeof(struct datanode));
>/*...i fill the array with structs from FILE...*/

>/*...here the user should select which member of the datanode struct to
>sort on (using submenu, SELECT/CASE stmts)*/

>qsort(sarray, n, sizeof(struct datanode), compare); /*this gives results

>in ordering by first character in lname field only*/
>...
>int compare(const char *vp, const char *vq)
>{
>     const char *p = vp, *q = vq;
>     return (*p - *q);
>}



Fri, 07 Dec 2001 03:00:00 GMT  
 help me sort my array of structs

...

Quote:
>   { displacement = &sarray[0].fname - &sarray[0];

This is not valid since &sarray[0].fname and &sarray[0] have different
and incompatible pointer types. Use offsetof().

--
-----------------------------------------


-----------------------------------------



Fri, 07 Dec 2001 03:00:00 GMT  
 help me sort my array of structs

Quote:

> >   { displacement = &sarray[0].fname - &sarray[0];

> This is not valid since &sarray[0].fname and &sarray[0] have different
> and incompatible pointer types. Use offsetof().

Exactly so, given that the compiler used did not provide offsetof(), both address
references should have been cast to (char *). That change passed the (weak) test of
compiling with both -ansi and -pedantic options turned on (with a modern compiler
that /does/ provide offsetof().)

offsetof() is new (and /most/ welcome!) to me. There have been a fair number of
times when it could have saved me a decent amount of keyboard work (and rework).

Thanks, Lawrence

[BTW, this time I did compile before posting; but didn't test because I was too
lazy to write a calling application /and/ gen up the test data file   8-]

Morris Dovey
West Des Moines, Iowa USA



Fri, 07 Dec 2001 03:00:00 GMT  
 help me sort my array of structs
thaks guys!!  using suggestions from all the postings, i now have it working
great!  thanks a lot!

i do have one more question though. :)

what is the best way/correct way to test for the return value of a malloc call?
perhaps something like:

    if(sarray = malloc(n * sizeof(struct datanode))) == NULL)
            ...
    else
            /*do its thing*/

Quote:

> >     sarray = malloc(n * sizeof(struct datanode)) ; /*make graceful?*/

> Consider making that
>    sarray = malloc(n * sizeof *sarray); /*make graceful?*/

> Then you don't worry about precisely what type is concerned, you will
> always specify n units of the type that sarray points to. Don't forget to
> test the return value for failure.



Sat, 08 Dec 2001 03:00:00 GMT  
 help me sort my array of structs

Quote:

>thaks guys!!  using suggestions from all the postings, i now have it
working
>great!  thanks a lot!

>i do have one more question though. :)

>what is the best way/correct way to test for the return value of a malloc
call?
>perhaps something like:

>    if(sarray = malloc(n * sizeof(struct datanode))) == NULL)

This is where your compiler spits out a million errors and you know it must
be wrong (you left out a '( ').
if((sarray = malloc(n*sizeof(struct datanode))) == NULL)
{
    puts("What do mean you want MORE!!"); /* I have a rude computer  ;-) */
    exit(EXIT_FAILURE);

Quote:
}

Regards,
Greg Martin


Sat, 08 Dec 2001 03:00:00 GMT  
 help me sort my array of structs
Quote:

> thaks guys!!  using suggestions from all the postings, i now have it working
> great!  thanks a lot!

> i do have one more question though. :)

> what is the best way/correct way to test for the return value of a malloc call?
> perhaps something like:

>     if(sarray = malloc(n * sizeof(struct datanode))) == NULL)
>             ...
>     else
>             /*do its thing*/

To the extent that malloc() returns NULL and that, at that point there
is nothing else to do except exit the program, consider a 'wrapper' like
this:

void * m_alloc(size_t size) {
  void *ret;
  if ((ret = malloc(size)) == NULL)
    fputs("Malloc Error!\n", stderr), exit(EXIT_FAILURE);
  return ret;

Quote:
}

In the body of your program you call "ptr = m_alloc(size_of_x);" and be
done with it.
--

"Everything should be made as simple as possible, but not simpler."
                    --- Albert Einstein ---


Sat, 08 Dec 2001 03:00:00 GMT  
 help me sort my array of structs

Quote:


>> int compare(const void *vp, const void *vq)
>> {
>>      const char *p = vp, *q = vq;
>>      return strncmp(p+displacement,q+displacement,length);
>> }

umm.... I cant figure out very well what are you trying to do, since your
comparision function must recieve pointers to your structures.. and you are
not posting how your structures look like.

--

Saludos


http://www.linuxfocus.org/developer/Roberto



Sun, 16 Dec 2001 03:00:00 GMT  
 help me sort my array of structs

Quote:

> >> int compare(const void *vp, const void *vq)
> >> {
> >>      const char *p = vp, *q = vq;
> >>      return strncmp(p+displacement,q+displacement,length);
> >> }

> umm.... I cant figure out very well what are you trying to do, since your
> comparision function must recieve pointers to your structures.. and you are
> not posting how your structures look like.

Roberto...

The comparison function does indeed receive pointers to structures. The
displacement of the (text) structure member from the start of the structure is
assigned to the "displacement" variable; and the length of the data field to
compare for sorting purposes is assigned to the "length" variable. The
compare() function uses these two global variables to provide strncmp() with
pointers to the appropriate (text) members.

Morris Dovey
West Des Moines, Iowa USA



Sun, 16 Dec 2001 03:00:00 GMT  
 
 [ 14 post ] 

 Relevant Pages 

1. help: how to use qsort to sort an array of struct

2. Sort array of struct

3. sorting an array of structs

4. Question About Sorting an Array of Structs

5. Problem sorting an array of struct

6. Sorting Array of Structs

7. Sorting a struct? Help ne

8. Need help Sorting Arrays with an insert function.

9. Need help sorting text into arrays. ASAP thx :)

10. HELP: Sorting arrays

11. Problems with sorting arrays-Please Help

12. Still sorting arrays-help

 

 
Powered by phpBB® Forum Software