Solved

Help sorting informations from an array of structs

Posted on 2004-10-26
301 Views
Last Modified: 2012-05-05
Hi everybody, I've started a project not far ago and I'm and now starting the last part.

I've previously programmed an array that contains structs, each structs containing different information. I must now take these informations and sort them to print a cute little list. The problem is that I need to print 2 differents lists, each using the quicksort method to sort the array on different record of a struct, but 1 ascending and the other decreasing.

Now the reason I'm posting this is to get some advices on the best way to understand and solve this problem. I don't have a large knowledge of C language so every help would be appreciated. Should I start by programming a quicksort function taking an array of struct or reading every struct of the array individually and  ? Which step should I take first ? Right now it's looking like a giantic task for me butonce I plan the correct steps I hopw it will get easier !

Here my main struct just for the record:
 struct book
 {
     char title[80];
     char autor[40];
     char editor[20];
     char ISBN[10];
     char subject[20];
     char releaseDate[10];
 };
typedef struct book bookInfo;

and here's my array of struct:
bookInfo *books = NULL;


Thanks all for your time.
Frank
0
Question by:The_Kingpin08
    25 Comments
     
    LVL 23

    Expert Comment

    by:brettmjohnson
    Why resort the array to get descending?  Once you sort the array in ascending order,
    simply traverse the array in reverse to display descending order:

    /* print the list in descending order */
    for (i = arrayCount-1; i >= 0; i--)
          printBook(&array[i]);

    0
     

    Author Comment

    by:The_Kingpin08
    One list has to be ascending based on the Subject record while the other list has to be descending based on the releaseDate record.
    besides that, any ideas on how to create the quicksort using informations from a struct's field inside an array ?
    0
     
    LVL 11

    Expert Comment

    by:lbertacco
    You can use the stdlib.h library function qsort().

    #include <stdlib.h>

    int relDatRevCmp(void *a, void *b)
    {
      return -strcmp(((bookInfo *)a)->releaseDate, ((bookInfo *)b)->releaseDate);
    }

    main()
    ...
    qsort(books, arrayCount, sizeof(bookInfo), relDatRevCmp);
    ...

    This is assuming that you want a lexicographical sort on the releaseDates and that these are zero terminated strings; but you can easily modify it for different situations.
    0
     

    Expert Comment

    by:hanhvansu
    Hi The_Kingpin08 !

    The simplest way to solve your problem is writting 2 functions,one for ascending the array based on Subject and the other for descending the array based on releaseDate! If you want to know the code of quicksort , just let me know !

    Have fun!
    0
     
    LVL 48

    Expert Comment

    by:Julian Hansen
    If I understand you correctly you want the following
     
    Field1    Field2
    A             3
    A             2
    A             1
    B             5
    B             1
    C             2
    C             1
    C             0

    In your compare function for qsort simply do the following

    if (s1.field1 < s2.field1 ) return -1 ;
    if (s1.field1 > s2.field1)  return 1 ;

    // If we get here s1.field1 == s2.field1 so compare on field2 remember to switch the return value around to do descending sort.

    if (s1.field2 < s2.field2) return 1;
    if (s2.field2 > s2.field2) return -1 ;

    // If we get here s1.field1 == s2.field1 and s1.field2 = s2.field2 so return 0 to indicate equal.

    return 0;

    Haven't tested it yet but give it a go.
    0
     
    LVL 48

    Accepted Solution

    by:
    Here is some sample code that demonstrates the point

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

    typedef struct
    {
          int field1 ;
          int field2 ;
    } S ;

    S ms[] = {
          {5,3},
          {4,1},
          {1,2},
          {3,3},
          {5,1},
          {2,2},
          {2,1},
          {2,3},
          {1,3},
          {4,2},
          {1,1},
          {3,2},
          {2,3},
          {1,4}
    } ;

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

    void main( int argc, char **argv )
    {
       int i;
       /* Eliminate argv[0] from sort: */
       argv++;
       argc--;

       /* Sort remaining args using Quicksort algorithm: */
       qsort( (void *)ms, 14, sizeof( int ) * 2, compare );

       /* Output sorted list: */
       for( i = 0; i < 14; ++i )
          printf( "%d %d \n", ms[i].field1, ms[i].field2 );
       printf( "\n" );
    }

    int compare( const void *arg1, const void *arg2 )
    {
          S *s1 = (S*)arg1;
          S *s2 = (S*)arg2;

          if ( s1->field1 < s2->field1 ) return -1 ;
          if ( s1->field1 > s2->field1 ) return 1 ;

          if ( s1->field2 < s2->field2 ) return 1 ;
          if ( s1->field2 > s2->field2 ) return -1 ;

          return 0 ;
    }
    0
     

    Author Comment

    by:The_Kingpin08
    Damn and me that already started programming a quicksort function not knowing the stdlib.h included one ! julianH, would it be possible to use your way but get the information from struct inside an array ? Here's what I think it would looks like with my function.

    BTW do we need to create a compare function to use the built-in qsort ?

     /* Struct containing the informations on a book */
     struct book
     {
         char title[80];
         char autor[40];
         char editor[20];
         char ISBN[10];
         char subject[20];
         char releaseDate[10];
     };
     typedef struct book bookInfo;

    int main()
     {
       FILE *file;                           // File containing the data
       bookInfo *books = NULL;     // Array of books, UNKNOWN size
       char buff[10000];                // Buffer to read in the file
       int i =0;
       int num_books = 0;             // Keep the count of number read in
       int line_number = 0;           /* Used to count the 6 lines required
                                               to create a new struct */
       argv++;                            /* Eliminate argv[0] from sort: */
       argc--;

     
       /* First step we open the file and see if it's correct */
       file = fopen("livres.txt", "r");
       if(file==NULL)
          {
          printf("Error: can't open file.\n");
          return 1;
          }
       else
          {
            /* First loop that goes through every line of the file */
          while(fgets(buff, sizeof(buff), file) != NULL)
            {
                      bookInfo BOOK; // Create a new book

                      /* Resize the array containing the structs */
                      parseline(&BOOK, buff, line_number);
                      if(line_number==5)
                      {
                            void *temp = realloc( books, (num_books + 1) * sizeof(bookInfo));
                            if ( temp != NULL )
                            {
                                  books = (bookInfo*)temp;
                            }
                            
                            /* Sort remaining args using Quicksort algorithm: */
                            qsort( (void *)BOOK, 14, sizeof( int ) * 2, compare );

                                   /* Output sorted list: */
                                  for( i = 0; i < 14; ++i )
                                  printf( "%d %d \n", books[i].title, books[i].autor);
                                  printf( "\n" );
    ...


    int compare( const void *arg1, const void *arg2 )
    {
         BOOK *book1 = (BOOK*)arg1;
         BOOK *book2 = (BOOK*)arg2;

         if ( book1 ->title< book2 ->title) return -1 ;
         if ( book1 ->title> book2 ->title) return 1 ;

         if ( book1 ->autor< book2 ->autor) return 1 ;
         if ( book1 ->autor> book2 ->autor) return -1 ;

         return 0 ;
    }


    Thanks, Frank

    0
     

    Author Comment

    by:The_Kingpin08
    I don't really understand how this built-in qsort function works... If someone could be kind enough to at least tell me the parameters it requires then I could discovr the rest :)

    Frank
    0
     
    LVL 11

    Expert Comment

    by:lbertacco
    You NEED to create a compare function unless the ones already in the library are fine for you (e.g. strcmp which just compare 2 strings)

    In your code above here, you cannot do:
     if ( book1 ->title< book2 ->title) return -1 ;
    since these are strings and you cannot compare strings with "<" in C, but you have to use strcmp.

    So you could do
    int compare( const void *arg1, const void *arg2 )
    {
         BOOK *book1 = (BOOK*)arg1;
         BOOK *book2 = (BOOK*)arg2;
         int t=strcmp(book1->title, book2->title);
         if(t) return t;
         return strcmp(book1->autor, book2->autor);
    }
    0
     
    LVL 11

    Expert Comment

    by:lbertacco
    Oops, I didn't check the rest of your code but there seem to be other issues there too.
    Why were you using BOOK *book1 ? Your book type is bookInfo, not BOOK, so:

    int compare( const void *arg1, const void *arg2 )
    {
         bookInfo *book1 = (bookInfo *)arg1;
         bookInfo *book2 = (bookInfo *)arg2;
         int t=strcmp(book1->title, book2->title);
         if(t) return t;
         return strcmp(book1->autor, book2->autor);
    }

    Also when you call qsort, the second argument is the number of elements in the array (num_books?), not 14; and the third element is the size of an element, that is sizeof(bookInfo), not sizeof(int)*2.
    0
     
    LVL 48

    Expert Comment

    by:Julian Hansen
    The_Kingpin08,

    To expand on what lbertacco says above.

    The compare function is necessary because the qsort algorithm does not know anything about the data you are trying to sort integers, strings etc. You need to provide a function that tells qsort how to elements relate to each other with respect to ranking. QSort will call your compare function each time it wants to know how two elements compare with each other and based on what the function returns qsort will make a decision about how to deal with the two elements.

    lbertacco's compare function above should do it except for one small error. You want to sort descending on the autor field so you need to swap the parameters arround in the strcmp i.e instead of

       return strcmp(book1->autor, book2->autor);

    do

       return strcmp(book2->autor, book1->autor);

    The strcmp function returns a value < 0 if str1 < str2, ==0 if they are the same and >0 if str1 > str2. This is what the compare function should return as well so it is a simple matter to just return the return value of strcmp - however the order you put the parameters in is important to determine the sort order.


    0
     

    Author Comment

    by:The_Kingpin08
    hey thanks a lot guys, your support is so precious.

    There's one other thing I don't understand and that's the use of "argv" I've already seen this in VB and Java I think but can't remember it's function and it's use in this case.

    Thanks again. Frank
    0
     
    LVL 48

    Expert Comment

    by:Julian Hansen
    Not sure what you are referring to. In C/C++ there is a convention for accessing command line parameters

    int main ( int argc, char* argv[])

    where argv is an array of strings storing the command line parameters with argv[0] being the path and filename of the executable and each element of the array corresponding to 1 space or "" delimited word entered on the command line.

    However this is just a convention and could just as easily be

    int main (int Fish, char* AndChips[])
    {
       int i ;
       for ( i = 0 ; i < Fish ; i++ ) printf ( "Argument[%d] = %s\n", i, AndChips[i] ) ;

       return 0;
    }

    Not elegant but syntactically correct ... ;)

    Don't know if that answers your question.
    0
     

    Author Comment

    by:The_Kingpin08
    yes thanks a lot julianH !
    0
     

    Author Comment

    by:The_Kingpin08
    When I tried calling the qsort function with my line

    qsort( (void *)BOOK, num_books, sizeof(bookInfo) * 2, compare );

    I get 2 errors:

    -Cannot convert from 'bookInfo' to 'void *'
    -too few arguments for call through pointer-to-function

    is the first parameter correct ? I still don't know what the first parameter refer to...

    Thanks a thousand time,

    Frank
    0
     

    Author Comment

    by:The_Kingpin08
    ok I found out that the first parameter is the list, so I changed it to

    qsort( (void *)BOOK, num_books, sizeof(bookInfo) * 2, compare );


    Thanks all for your support !

    Frank
    0
     

    Author Comment

    by:The_Kingpin08
    qsort(books, num_books, sizeof(bookInfo) * 2, compare );
    0
     
    LVL 48

    Expert Comment

    by:Julian Hansen
    No problem - glad to have been of help.
    0
     

    Author Comment

    by:The_Kingpin08
    Ok now I've ran into another proble :(  (can't wait until this project is over so I can sleep!)

    Looks like my Compare function isn't correct. It never does seem to find the second argument, the *book2. How could I specify that the 2nd item to read is the 2 value of the struct array named "books" which is a bookInfo type ? Is this possible ?

    int compare( const void *arg1, const void *arg2 )
    {
         bookInfo *book1 = (bookInfo *)arg1;
         bookInfo *book2 = (bookInfo *)arg2;
         int t=strcmp(book1->title, book2->title);
         if(t) return t;
         return strcmp(book1->autor, book2->autor);
    }
    0
     
    LVL 48

    Expert Comment

    by:Julian Hansen
    Hi Kingpin,

    I am not sure what you are asking here - the compare function does appear to be correct when you say it is not finding the second argument - what exactly do you mean?

    The only problem with the compare function is the last line which should be corrected as per my earlier post to ensure the descending sort on the autor field.

    Ok, just took a look at your code. You are looping reading records from the file into the variable BOOK - 1 instance of the structure. You are then reallocing a pointer variable (your array) and setting book equal to this array. Here is the problem

    Firstly you are passing BOOK to the qsort function which will never work because it will always only contain 1 record.
    Secondly, after parsing the record into BOOK and reallocating the book pointer you are never copying the new record into the array.

    You should be doing something along the lines of


    bookinfo * bookarray ;
    bookinfo * pBook ;
    int cp = 0 ;
    int size = 10 ;

    bookarray = malloc ( sizeof(bookinfo*) * size ) ; // Make provision for a 10 element array
    // open the file here
    while (fgets (buffer,BUFFSIZE,file) )
    {
       if ( cp == size )
       {
           size = size + 10 ;
           bookarray = realloc ( bookarray, sizeof(bookinfo*) * size ) ;
       }

       bookarray[cp] = malloc ( sizeof ( bookinfo ) );
       parseline (bookarray[cp], buff ) ;
    }

    // close file here
    qsort ( ( void *) bookarray, cp, sizeof(bookinfo), compare ) ;

    for ( int i = 0 ; i < cp; i++ ) printf ...

    // free memory here

    I have not tested the code but that is the gist of it.
    0
     
    LVL 48

    Expert Comment

    by:Julian Hansen
    Oops - mistake - you can loose the second line
     bookinfo * pBook
    it is not needed
    0
     
    LVL 48

    Expert Comment

    by:Julian Hansen
    Oops nuther error - cp not being incremented - see revised code

    bookinfo * bookarray ;
    int cp = 0 ;
    int size = 10 ;

    bookarray = malloc ( sizeof(bookinfo*) * size ) ; // Make provision for a 10 element array

    // open the file here

    while (fgets (buffer,BUFFSIZE,file) )
    {
       // check to see if array is full ...
       if ( cp == size )
       {
           size = size + 10 ; // make provision for another 10 elements - arbitary selection
           bookarray = realloc ( bookarray, sizeof(bookinfo*) * size ) ; // resize the array keeping existing elements
       }

       bookarray[cp] = malloc ( sizeof ( bookinfo ) ); // create a new record in the next available position in the array for the new record
       parseline (bookarray[cp], buff ) ;   // fill in the record data
       cp++ ;   // increment your array pointer and go around again
    }

    // close file here
    qsort ( ( void *) bookarray, cp, sizeof(bookinfo), compare ) ;

    for ( int i = 0 ; i < cp; i++ ) printf ...

    // free memory here
    0
     

    Author Comment

    by:The_Kingpin08
    Alright, thhanks a lot julianH, your last reply help me solve my problem. I didn't use your code but understod it to correct some mistakes I made in my code...

    Thanks a thousand time again, now I can almost see the rest coming !

    Frank
    0
     
    LVL 48

    Expert Comment

    by:Julian Hansen
    My pleasure - glad to have been of help
    0
     
    LVL 11

    Expert Comment

    by:lbertacco
    Note that in the 3rd paramter to qsort you have to use
     sizeof(bookInfo)
    and not
     sizeof(bookInfo) * 2
    0

    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone.

    Featured Post

    Shellfire Box VPN + Lifetime Subscription

    The Shellfire Box easily connects all of your devices, even those that don't offer the possibility to establish a safe vpn connection. Access blocked content and surf safely, no matter where in the world you are located.

    Suggested Solutions

    Whether you’re a college noob or a soon-to-be pro, these tips are sure to help you in your journey to becoming a programming ninja and stand out from the crowd.
    If you’re thinking to yourself “That description sounds a lot like two people doing the work that one could accomplish,” you’re not alone.
    An introduction to basic programming syntax in Java by creating a simple program. Viewers can follow the tutorial as they create their first class in Java. Definitions and explanations about each element are given to help prepare viewers for future …
    In this fifth video of the Xpdf series, we discuss and demonstrate the PDFdetach utility, which is able to list and, more importantly, extract attachments that are embedded in PDF files. It does this via a command line interface, making it suitable …

    846 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    6 Experts available now in Live!

    Get 1:1 Help Now