help me sort my array of structs
Author |
Message |
arava #1 / 14
|
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 |
|
|
Morris Dove #2 / 14
|
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 |
|
|
arava #3 / 14
|
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 |
|
|
Kurt Watz #4 / 14
|
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 |
|
|
Lawrence Kir #5 / 14
|
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 |
|
|
Morris Dove #6 / 14
|
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 |
|
|
David & Cath #7 / 14
|
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 |
|
|
Lawrence Kir #8 / 14
|
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 |
|
|
Morris Dove #9 / 14
|
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 |
|
|
arava #10 / 14
|
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 |
|
|
Greg Marti #11 / 14
|
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 |
|
|
Joe Wrigh #12 / 14
|
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 |
|
|
rdiaz.. #13 / 14
|
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 |
|
|
Morris Dove #14 / 14
|
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 |
|
|
|