qsort按字母顺序比较字符串

Question

我使用stdlib.h库附带的qsort()对字符串结构数组进行排序。

它本质上是一个字符串数组，但其结构包含数组。

例如：

typedef struct node { 
    char name[MAX_SIZE + 1]; 
} Node; 

然后我节点的数组，包含名称是：

Node nodes_list[MAX_SIZE + 1]; 

我的问题是，我希望当我打印以下排序nodes_list这样：

for (i = 0; i < size; i++) { 
    printf("%s\n", nodes_list[i].name); 
} 

它按字母顺序打印所有名称。

我愿做排序使用qsort和我的比较器功能的列表是这样的：

int compare(const void *a, const void *b) { 
    const char **ia = (const char **)a; 
    const char **ib = (const char **)b; 
    return strcmp(*ia, *ib); 
} 

当我运行qsort功能：

qsort(nodes_list, size, sizeof(Node), compare); 

我得到一个分段错误（核心倾倒）。

我知道我得到了这段代码的段错误，因为没有它，我可以打印正确的名单。当然没有排序。

有人可以帮忙吗？

Answer 1

您的比较函数对于您的数组格式是错误的。

这里有一个简单的清单，你可以按照获得的种类和使用的qsort大小时右：

1. 的第三个参数快速排序应该是sizeof *x其中x是第一个参数。
2. qsort函数内的第一件事情应该是通过复制函数参数初始化的一对指针的声明。 不应该有任何演员。从void *铸件是没有必要的。
3. 由于const，你可能认为你需要演员，但如果你这样做，那是因为你已经把const放在了错误的地方。要在没有强制转换的情况下成功分配const void *，目标类型在const关键字后应该只有一个*。 const char *和char const *都可以（并且相互等价）; const char *const *也行（不同）; const char **是错误的。如果因为您没有*因为您键入了指针类型而无法在*之前放置const，这就是您不应该这样做的原因。
4. 除了增加const之外，在比较函数的开始处声明的指针的类型应该与qsort的第一个参数的类型完全相同，在将“array decays to pointer”规则应用之后if qsort的第一个参数是数组的名称。

在你的情况下，快速排序的第一个参数是nodes_List这是Node数组，因此应用衰减到指针的规则，你会得到一个Node *，然后添加一个const，你会得到：

const Node *a_node = a; 
const Node *b_node = b; 

现在你有一双漂亮的正确类型的指针，你只需在明显的方式对它们进行比较：

return strcmp(a_node->name, b_node->name); 

要解释为什么规则＃4的作品，你有仔细观察内存布局。假设MAX_SIZE是15，所以MAX_SIZE + 1是一个不错的第16轮，您的Node类型包含一个16字节的char数组，而您的nodes_list包含16个总数为16 * 16 = 256个字节的数组。假设nodes_list位于内存地址0x1000处。那么布局是：

+---------------+---------------+    +---------------+ 
| nodes_list[0] | nodes_list[1] |...............| nodes_list[15]| 
+---------------+---------------+    +---------------+ 
^    ^       ^   ^
0x1000   0x1010       0x10f0   0x1100 

地址0x1000到0x10ff实际上是对象的一部分。 0x1100是后沿 - 结束后一个字节。

进一步假设该阵列是半满（size是8），它填充有这些8个字符串：

Hotel Foxtrot Echo Charlie Golf Delta Bravo Alpha 

并且所述未使用的部分填充有0。对象是由这些256个字节（我添加空格和换行用于说明目的）

H o t e l \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 
F o x t r o t \0 \0 \0 \0 \0 \0 \0 \0 \0 
E c h o \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 
C h a r l i e \0 \0 \0 \0 \0 \0 \0 \0 \0 
G o l f \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 
D e l t a \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 
B r a v o \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 
A l p h a \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 
... 128 more \0's 

现在，你通过快速排序的内存此块的起始地址（第一个参数，nodes_list，为0x1000）加上2条有关其内部结构的信息：元素数（第2个参数，size，8）和元素数（第3个参数，sizeof Node,16）。有了这些信息，它知道数组的元素位于地址0x1000,0x1010,0x1020，... 0x1070。它挑选了一对 - 它选择哪一对取决于它使用的排序算法 - 让我们假设为简单起见，它是一个愚蠢的泡泡排序，通过比较前两个元素开始。

qsort使用元素地址0x1000和0x1010调用您的比较函数。它不知道它们的类型，但它知道它们的大小。每一个都是占用16个字节的数组元素。

您的比较功能收到a=0x1000和b=0x1010。它们是指向16字节对象的指针 - 具体地说，它们都指向struct Node。如果你做错了什么，并将它们投射到char **，会发生什么？那么，你得到一个值为0x1000的char **，并且你必须解除char **的取消引用才能将char *传递给strcmp，所以你做了这个解引用，并最终将字节'H', 'o', 't', 'e'加载为一个指针值（假设你的指针是4个字节长）。在以ASCII作为字符集的big-endian机器上，这是一个指向内存地址0x486f7465的指针，您将其传递给strcmp。 strcmp崩溃。尝试struct Node **的结果基本相同。

另一件好事就是知道qsort如何在重新排序数组时使用成员大小信息。第三个参数不仅仅是比较作用的对象的大小，它还是重新排序数组时移动的对象的大小。在您的比较函数返回1（strcmp（“Hotel”，“Foxtrot”））后，我们假设的qsort气泡排序实现将交换0x1000和0x1010处的对象，以使它们按正确的顺序排列。它将通过一系列3个每个16字节的memcpy执行此操作。它必须移动所有那些额外的\0，因为它不知道它们是无用的。那些16字节的对象对于qsort是不透明的。这可能是考虑构建辅助数组指针并将其排列而不是主数组的原因，当您的主数组具有非常大的对象时。