The_Kingpin08
asked on
Help sorting informations from an array of structs
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
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
ASKER
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 ?
besides that, any ideas on how to create the quicksort using informations from a struct's field inside an array ?
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.
#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.
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!
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!
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.
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.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
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
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
ASKER
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
Frank
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);
}
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);
}
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.
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.
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.
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.
ASKER
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
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
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.
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.
ASKER
yes thanks a lot julianH !
ASKER
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
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
ASKER
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
qsort( (void *)BOOK, num_books, sizeof(bookInfo) * 2, compare );
Thanks all for your support !
Frank
ASKER
qsort(books, num_books, sizeof(bookInfo) * 2, compare );
No problem - glad to have been of help.
ASKER
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);
}
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);
}
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.
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.
Oops - mistake - you can loose the second line
bookinfo * pBook
it is not needed
bookinfo * pBook
it is not needed
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
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
ASKER
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
Thanks a thousand time again, now I can almost see the rest coming !
Frank
My pleasure - glad to have been of help
Note that in the 3rd paramter to qsort you have to use
sizeof(bookInfo)
and not
sizeof(bookInfo) * 2
sizeof(bookInfo)
and not
sizeof(bookInfo) * 2
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]);