如何使用qsort对结构数组进行排序? [英] How to sort an array of a structure using qsort?
问题描述
我和一个朋友正在尝试自学C，并决定去做一个最初被认为很容易的练习，在该练习中，我们创建了一个两个字符的结构，分别包含1.姓氏和2.姓氏.函数read_person获取用户输入，将其保存在结构中并返回.输入应保存在动态分配的数组中(到目前为止，据称所有这些都做对了).然后，使用qsort，数组在涉及到姓氏时应升序排列，在涉及姓氏时则降序排列，最后考虑姓氏的长度.如果前名等长，则应比较姓氏.我们俩都在努力地使qsort正常工作，但它却无法进行排序，因此我们想知道是否有人知道如何做?
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;
}
推荐答案
您在这里发生的许多事情虽然不正确，但也涉及到一些细微的问题，这些问题在尝试进行操作时不会很明显偶然发现如何填充您的结构.
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.
首先，您声明 struct details (其中5个)的全局数组.不要那样做虽然合法，但您只想在全局范围内声明 struct ，然后在 main()中声明每个实例，然后传递该结构的副本或指向的指针该结构作为代码中需要它的任何函数的参数.
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.
第二，您在 read_person 本地声明 d ，然后在最后将 d 返回给 main().很好，但是……了解为什么很好.当您声明 d 时， struct details 的所有成员都具有自动存储类型，并且每个成员的存储都已在此时完全定义.无需在函数中的任何地方调用 malloc .当您最后返回 d 时， struct assignment 允许函数返回该结构，并为所有赋值并在中可用main().
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().
最后在 main()中，您调用 read_person(); ，但无法分配返回值或使用 d 以任何方式.
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.
与其创建全局的struct数组，不如直接声明该struct本身，例如:
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];
};
然后使用您的 read_person(void)函数，消除对 malloc 的调用，只需执行以下操作:
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;
}
(注意:，您不希望在每个名称的末尾留下行尾'\ n'，因此您需要覆盖结尾的'\ n'和 nul-character '\ 0'(或等价的 0 ).做到这一点的方法，使用 strcspn 可能是最健壮，最简单的方法之一. strcspn 返回字符串中不包含的字符数 exclude set .因此，只需将您的 exclude set 包含行尾的"\ n" ，它就会返回字符串中最多的字符数到'\ n'，然后将其设置为 0 )
(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)
(也请注意::在结构详细信息read_person(void)中使用 void 来指定该 read_person 不接受任何参数.在C语言中，如果您只是将()保留为空，则该函数将接受不确定的个参数)
(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)
然后在 main()中分配返回值，并以某种方式使用它，例如
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;
}
您的另一种选择是在 main()中声明您的结构，然后将指针传递给您的 read_person 函数以进行填充.只需在 main()中声明一个结构，然后将其的地址传递给 read_person ，但请注意，使用了指向结构的指针-> 运算符来访问成员，而不是'.'.例如，您可以这样做:
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;
}
最后，由于您确实包含了 mailloc ，因此您还可以了解如何使用它为该结构以及每个 forename 和 surname (姓)，这样两者都使用正确的字节数来保存输入的名称，而不再使用.当为任何要分配的内存块分配3个职责的存储空间时:(1)在使用内存块之前，始终验证分配是否成功，(2)始终为内存块保留指向起始地址的指针，因此，(3)在不再需要时可以释放.
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.
这将在您动态分配存储的任何位置添加一些重复但重要的代码行.例如，在这种情况下，当您动态分配该结构以及该结构内的 forename 和 surname 时，您的结构声明和函数可以是:
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;
}
(注意:使用 memcpy 而不是 strcpy .您已经使用扫描了字符串结尾strcspn 来获取字符串中的字符数，然后在该位置处对字符串进行nul终止，无需使用 strcpy 再次扫描字符串的末尾，只需复制带有 memcpy 的字符数(+1也可以复制 nul-终止字符).
(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.
尝试看看您是否可以理解为什么上面的函数包含了 free()函数以及该函数的作用.
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.)
使用/输出示例
所有示例均产生相同的输出.一个例子是:
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
内存使用/错误检查
当务之急是使用一个内存错误检查程序来确保您不尝试访问内存或不在分配的块的边界之外/之外写，尝试读取或基于未初始化的值进行条件跳转，最后，以确认您释放了已分配的所有内存.
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.
对于Linux， valgrind 是通常的选择.每个平台都有类似的内存检查器.它们都很容易使用，只需通过它运行程序即可.
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.
处理结构详细信息数组的qsort
在处理了您使用 struct details 的所有最初问题之后，我差点忘了您原来的问题与 qsort 有关. qsort 使用简单，只需传递数组，要排序的成员数，每个成员的大小以及返回 -1、0、1 根据第一个元素是在传递给函数的第二个元素之前，等于还是之后进行排序.
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.
使用 qsort 的唯一责任是编写 compare 函数.当 qsort 的新用户通常在看到该函数的声明时会回头一想:
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) { ... }
实际上很简单. a 和 b 只是指向要比较的数组元素的指针.因此，如果您有一个包含 结构详细信息的数组. a 和 b 只是指向 结构详细信息的指针.您只需要编写您的 compare 函数即可将 a 和 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.
要对 forename 进行排序，您可以比较以下功能:
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);
}
然后在 main()中，您只需声明一个 struct details 数组，然后调用 qsort ，例如
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;
}
使用/输出示例
$ ./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
(注意:，因为 Mickey 和 Minnie 都姓氏 Mouse ，因此按>姓，然后按 forname 对其进行进一步排序，因此上面的列表中有正确的规范排序)
(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.
这篇关于如何使用qsort对结构数组进行排序?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
