How to sort an array of a structure using qsort?

2019-08-28 17:38发布

问题:

A friend and I are trying to teach ourselves C and have decided to do, a what was first thought to be easy, an exercise, where we create a struct of two char containing 1. the forename and 2. the surname. A function read_person gets the users input, saves it in the structure and returns it. The input should be saved in a dynamically allocated array (all of which we have allegedly done correct so far). Then, using qsort, the array should be sorted ascendingly when it comes to the forename, descendingly when it comes to the surname and lastly, considering the length of the forename. if the forenames are equally long, the surnames should be compared. Both of us were trying really hard to make the qsort work but it just wouldn't sort, therefore we were wondering whether anyone has an idea how to do it?

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

struct details{
  char forename[10];
  char surname[10];
}[5];

struct details read_person(){
struct details d;
printf("Enter your forename: ");
fgets(d.forename, 10, stdin);
printf("Enter your surname: ");
fgets(d.surname, 10, stdin);
struct details *arr_dt=malloc(5 * sizeof(struct details));
free(arr_dt);
return d;
}



int main(){
read_person();
return 0;
}

回答1:

You have a number of things going on here that are just not right, but that also touch on a few subtle issues that won't be apparent in attempting to stumble though how to fill your struct.

First, you declare a global array of struct details (5 of them). Don't do that. While legal, instead you simply want to declare the struct at global scope and then declare each instance within main() and pass either a copy of the struct, or a pointer to the struct as parameters to any function within your code that needs it.

Second, you declare d local to read_person and then return d at the end for assignment back in main(). This is fine, ... but ... understand why it is fine. When you declare d all members of struct details all have automatic storage type and storage for each member is fully defined at that point. There is no need to call malloc anywhere in your function. When you return d at the end, struct assignment allows the function to return the struct and have all values assigned and available back in main().

Finally in main(), you call read_person(); but fail to assign the return or make use of the stored values in d in any way.

Instead of creating a global array of struct, simply declare the struct itself, e.g.:

#define MAXNM  32   /* if you need a constant, #define one (or more) */
                    /* (don't skimp on buffer size) */
struct details {
    char forename[MAXNM];
    char surname[MAXNM];
};

Then for your read_person(void) function, eliminate the calls to malloc and simply do:

struct details read_person (void)
{
    struct details d;

    printf ("Enter your forename: ");
    fgets (d.forename, MAXNM, stdin);
    d.forename[strcspn(d.forename, "\n")] = 0;  /* trim \n from end */

    printf("Enter your surname : ");
    fgets(d.surname, MAXNM, stdin);
    d.surname[strcspn(d.surname, "\n")] = 0;    /* trim \n from end */

    return d;
}

(note: you do not want the line-ending '\n' left at the end of each of the names, so you need to overwrite the trailing '\n' with the nul-character '\0' (or equivalently 0). While there are several ways to do this, the use of strcspn is probably one of the most robust and simplest ways to do this. strcspn returns the number of characters in the string NOT included in the exclude set. So simply have your exclude set include the line-ending "\n" and it returns the number of characters in the string up to the '\n' which you then simply set to 0)

(also note: the use of void in struct details read_person (void) to specify that read_person takes no arguments. In C if you simply leave empty (), then the function takes an indeterminate number of arguments)

Then in main() assign the return and use it in some fashion, e.g.

int main (void) {

    struct details person = read_person();

    printf ("\nname: %s, %s\n", person.forename, person.surname);

    return 0;
}

You other alternative is to declare your struct in main() and pass a pointer to your read_person function for filling. Simply declare a struct in main() and then pass the address of the struct to read_person, but note that with a pointer to struct you use the -> operator to access members rather than '.'. For example you could do:

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

#define MAXNM  32   /* if you need a constant, #define one (or more) */
                    /* (don't skimp on buffer size) */
struct details {
    char forename[MAXNM];
    char surname[MAXNM];
};

void read_person (struct details *d)
{
    printf ("Enter your forename: ");
    fgets (d->forename, MAXNM, stdin);
    d->forename[strcspn(d->forename, "\n")] = 0;  /* trim \n from end */

    printf("Enter your surname : ");
    fgets(d->surname, MAXNM, stdin);
    d->surname[strcspn(d->surname, "\n")] = 0;    /* trim \n from end */
}

int main (void) {

    struct details person;

    read_person (&person);

    printf ("\nname: %s, %s\n", person.forename, person.surname);

    return 0;
}

And finally, since you did include mailloc, you may as well learn how you could have used it to allocate storage for the struct, as well as each forename and surname so that both use exactly the correct number of bytes to hold the names entered and no more. When allocating storage for anything you have 3 responsibilities regarding any block of memory allocated: (1) always validate the allocations succeeds before making use of the block of memory, (2) always preserve a pointer to the starting address for the block of memory so, (3) it can be freed when it is no longer needed.

That will add a few repetitive, but important, lines of code wherever you dynamically allocate storage. For example in this case where you dynamically allocate for the struct and for forename and surname within the struct, your struct declaration and function, could be:

struct details {
    char *forename;
    char *surname;
};

struct details *read_person (void)
{
    char buf[MAXNM];
    size_t len;
    struct details *d = malloc (sizeof *d);  /* allocate storage */

    if (d == NULL) {                         /* validate allocation succeeds */
        perror ("malloc-d");
        return NULL;
    }

    printf ("Enter your forename: ");
    fgets (buf, MAXNM, stdin);
    len = strcspn(buf, "\n");
    buf[len] = 0;
    d->forename = malloc (len + 1);      /* allocate */
    if (d->forename == NULL) {           /* validate */
        perror ("malloc-d->forename");
        free (d);
        return NULL;
    }
    memcpy (d->forename, buf, len + 1);

    printf ("Enter your surname : ");
    fgets (buf, MAXNM, stdin);
    len = strcspn(buf, "\n");
    buf[len] = 0;
    d->surname = malloc (len + 1);       /* allocate */
    if (d->surname == NULL) {            /* validate */
        perror ("malloc-d->surname");
        free (d->forename);
        free (d);
        return NULL;
    }
    memcpy (d->surname, buf, len + 1);

    return d;
}

(note: the use of memcpy rather than strcpy. You have already scanned for the end-of-string with strcspn to obtain the number of characters in the string and then nul-termianted the string at that point. There is no need to scan for end-of-string again with strcpy, just copy the number of characters (+1 to also copy the nul-terminating character) with memcpy.

Try to see if you can understand why the free() function is include in the function above and what purpose it is serving.

Putting a complete example together that dynamically allocates, you could do something similar to the following:

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

#define MAXNM  1024

struct details {
    char *forename;
    char *surname;
};

struct details *read_person (void)
{
    char buf[MAXNM];
    size_t len;
    struct details *d = malloc (sizeof *d);

    if (d == NULL) {
        perror ("malloc-d");
        return NULL;
    }

    printf ("Enter your forename: ");
    fgets (buf, MAXNM, stdin);
    len = strcspn(buf, "\n");
    buf[len] = 0;
    d->forename = malloc (len + 1);
    if (d->forename == NULL) {
        perror ("malloc-d->forename");
        free (d);
        return NULL;
    }
    memcpy (d->forename, buf, len + 1);

    printf ("Enter your surname : ");
    fgets (buf, MAXNM, stdin);
    len = strcspn(buf, "\n");
    buf[len] = 0;
    d->surname = malloc (len + 1);
    if (d->surname == NULL) {
        perror ("malloc-d->surname");
        free (d->forename);
        free (d);
        return NULL;
    }
    memcpy (d->surname, buf, len + 1);

    return d;
}

int main (void) {

    struct details *person = read_person();

    if (person != NULL) {   /* validate the function succeeded */
        printf ("\nname: %s, %s\n", person->forename, person->surname);

        free (person->forename);
        free (person->surname);
        free (person);
    }

    return 0;
}

(note: all memory is freed before the program exits. Understand that the memory would be freed automatically on exit, but if you make a habit of always taking care of your 3-responsibilities concerning dynamically allocated memory, you will never have problems leaking memory later on as your code size grows.)

Example Use/Output

All of the examples produce the same output. An example would be:

$ ./bin/struct_name3
Enter your forename: Samuel
Enter your surname : Clemens

name: Samuel, Clemens

Memory Use/Error Check

It is imperative that you use a memory error checking program to insure you do not attempt to access memory or write beyond/outside the bounds of your allocated block, attempt to read or base a conditional jump on an uninitialized value, and finally, to confirm that you free all the memory you have allocated.

For Linux valgrind is the normal choice. There are similar memory checkers for every platform. They are all simple to use, just run your program through it.

$ valgrind ./bin/struct_name3
==14430== Memcheck, a memory error detector
==14430== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==14430== Using Valgrind-3.12.0 and LibVEX; rerun with -h for copyright info
==14430== Command: ./bin/struct_name3
==14430==
Enter your forename: Samuel
Enter your surname : Clemens

name: Samuel, Clemens
==14430==
==14430== HEAP SUMMARY:
==14430==     in use at exit: 0 bytes in 0 blocks
==14430==   total heap usage: 3 allocs, 3 frees, 31 bytes allocated
==14430==
==14430== All heap blocks were freed -- no leaks are possible
==14430==
==14430== For counts of detected and suppressed errors, rerun with: -v
==14430== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Always confirm that you have freed all memory you have allocated and that there are no memory errors.

Handling qsort of Array of struct details

After handling all of the initial problems with your use of struct details, I came close to forgetting that your original question related to qsort. qsort is simple to use, you just pass the array, the number of members to sort, the size of each member, and a compare function that returns -1, 0, 1 based on whether the first element sorts before, is equal to, or sorts after the second element passed to the function.

Your only responsibility using qsort is to write the compare function. While new users to qsort usually have their eyes roll back in their heads when they see the declaration for the function:

int compare (const void *a, const void *b) { ... }

It's actually quite simple. a and b are simply pointers to elements of the array to compare. So if you have an array of struct details. The a and b are just pointers to struct details. You simply need to write your compare function to cast a and b to the appropriate type.

To sort on forename, you compare function could be:

int compare_fore (const void *a, const void *b)
{
    const struct details *name1 = a,
                         *name2 = b;
    int rtn = strcmp (name1->forename, name2->forename); /* compare forename */

    if (rtn != 0)       /* if forenames are different */
        return rtn;     /* return result of strcmp */

    /* otherwise return result of strcmp of surname */
    return strcmp (name1->surname, name2->surname);      /* compare surname */
}

To sort on surname, you would have:

int compare_sur (const void *a, const void *b)
{
    const struct details *name1 = a,
                         *name2 = b;
    int rtn = strcmp (name1->surname, name2->surname);

    if (rtn != 0)
        return rtn;

    return strcmp (name1->forename, name2->forename);
}

Then within main() you simply declare an array of struct details and call qsort, e.g.

int main (void) {

    struct details person[MAXS];

    for (int i = 0; i < MAXS; i++)
        person[i] = read_person();

    qsort (person, MAXS, sizeof *person, compare_fore);

    puts ("\nSorted by forename:\n");
    for (int i = 0; i < MAXS; i++)
        printf ("  %s, %s\n", person[i].forename, person[i].surname);

    qsort (person, MAXS, sizeof *person, compare_sur);

    puts ("\nSorted by surname:\n");
    for (int i = 0; i < MAXS; i++)
        printf ("  %s, %s\n", person[i].forename, person[i].surname);

    return 0;
}

Or, putting it altogether in a full example you would have:

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

#define MAXS    5   /* if you need a constant, #define one (or more) */
#define MAXNM  32   /* (don't skimp on buffer size) */

struct details {
    char forename[MAXNM];
    char surname[MAXNM];
};

int compare_fore (const void *a, const void *b)
{
    const struct details *name1 = a,
                         *name2 = b;
    int rtn = strcmp (name1->forename, name2->forename); /* compare forename */

    if (rtn != 0)       /* if forenames are different */
        return rtn;     /* return result of strcmp */

    /* otherwise return result of strcmp of surname */
    return strcmp (name1->surname, name2->surname);      /* compare surname */
}

int compare_sur (const void *a, const void *b)
{
    const struct details *name1 = a,
                         *name2 = b;
    int rtn = strcmp (name1->surname, name2->surname);

    if (rtn != 0)
        return rtn;

    return strcmp (name1->forename, name2->forename);
}

struct details read_person (void)
{
    struct details d;

    printf ("\nEnter your forename: ");
    fgets (d.forename, MAXNM, stdin);
    d.forename[strcspn(d.forename, "\n")] = 0;  /* trim \n from end */

    printf("Enter your surname : ");
    fgets(d.surname, MAXNM, stdin);
    d.surname[strcspn(d.surname, "\n")] = 0;    /* trim \n from end */

    return d;
}

int main (void) {

    struct details person[MAXS];

    for (int i = 0; i < MAXS; i++)
        person[i] = read_person();

    qsort (person, MAXS, sizeof *person, compare_fore);

    puts ("\nSorted by forename:\n");
    for (int i = 0; i < MAXS; i++)
        printf ("  %s, %s\n", person[i].forename, person[i].surname);

    qsort (person, MAXS, sizeof *person, compare_sur);

    puts ("\nSorted by surname:\n");
    for (int i = 0; i < MAXS; i++)
        printf ("  %s, %s\n", person[i].forename, person[i].surname);

    return 0;
}

Example Use/Output

$ ./bin/struct_name4

Enter your forename: Mickey
Enter your surname : Mouse

Enter your forename: Minnie
Enter your surname : Mouse

Enter your forename: Samuel
Enter your surname : Clemens

Enter your forename: Mark
Enter your surname : Twain

Enter your forename: Walt
Enter your surname : Disney

Sorted by forename:

  Mark, Twain
  Mickey, Mouse
  Minnie, Mouse
  Samuel, Clemens
  Walt, Disney

Sorted by surname:

  Samuel, Clemens
  Walt, Disney
  Mickey, Mouse
  Minnie, Mouse
  Mark, Twain

(note: since Mickey and Minnie both have last name Mouse, for the sort by surname they are then further sorted by forname so there is a correct cannonical sort in the list above)

Now, hopefully, we have address all the aspects of your question. Look things over and let me know if you have further questions.