0

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

它本质上是一个字符串数组，但具有包含该数组的结构。

例如：

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);

我得到一个分段错误（核心转储）。

我知道我在这段代码中遇到了分段错误，因为没有它，我可以很好地打印名称列表。当然没有排序。

有人可以帮忙吗？

4

1 回答 1

1

您的比较函数不适合您的数组格式。

这是一个简单的清单，您可以按照以下方式在使用 qsort 时获得正确的类型和大小：

  1. qsort 的第三个参数应该sizeof *x是x第一个参数的位置。
  2. qsort 函数内部的第一件事应该是声明一对通过复制函数参数初始化的指针。不应该有任何演员表。void *不需要演员表。
  3. 你可能认为你需要一个演员因为const，但如果你这样做，那是因为你把 放在const了错误的地方。要在不进行强制转换的情况下成功分配const void *，目标类型应该在关键字*之后正好有一个。并且都可以（并且彼此等效）；也可以（并且不同）；是错的。如果你不能把 a 放在the 之前，因为你没有 a因为你 typedef'ed 指针类型，这就是你不应该这样做的原因。constconst char *char const *const char *const *const char **const**
  4. 除了添加 之外const，如果 qsort 的第一个参数应用“数组衰减到指针”规则后，比较函数开头声明的指针的类型应该与 qsort 的第一个参数的类型完全相同是数组的名称。

在您的情况下， qsort 的第一个参数nodes_List是 的数组Node，因此应用衰减到指针规则并获得 a Node *，然后添加 aconst并获得：

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

现在，您通过 qsort 传递此内存块的起始地址（第一个 arg, nodes_list, 0x1000）加上关于其内部结构的 2 条信息：元素数（第二个 arg, size, 8）和元素数（第三个 arg, sizeof Node, 16)。有了这些信息，它就知道数组的元素位于地址 0x1000、0x1010、0x1020、... 0x1070。它选择其中一对——它选择哪一对取决于它使用的排序算法——为了简单起见，它是一个愚蠢的冒泡排序，它首先比较前两个元素。

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

您的比较函数接收a=0x1000和b=0x1010。它们是指向 16 字节对象的指针——具体来说，它们每个都指向一个struct Node. 如果您做错了事情，并将它们强制转换为char **，会发生什么？好吧，你得到一个char **值为 0x1000 的 a，你必须取消引用它char **才能让 achar *传递给strcmp，所以你做了那个取消引用，并最终将字节'H', 'o', 't', 'e'作为指针值加载（假设你的指针是 4 个字节长）。在以 ASCII 作为字符集的大端机器上，这是指向内存地址 0x486f7465 的指针，您将其传递给strcmp. strcmp崩溃。尝试的结果struct Node **基本相同。

另一个要知道的好事情是 qsort 如何在对数组重新排序时使用成员大小信息。第三个参数不仅仅是比较作用的对象的大小，它也是在重新排序数组时作为一个单元移动的对象的大小。在您的比较函数返回 1 (strcmp("Hotel", "Foxtrot")) 后，我们假设的 qsort 冒泡排序实现将交换 0x1000 和 0x1010 处的对象以将它们按正确的顺序排列。它将使用一系列 3 个每个 16 字节的 memcpy 来执行此操作。它必须移动所有这些额外\0的 '，因为它不知道它们是无用的。那些 16 字节的对象对 qsort 是不透明的。这可能是考虑构建一个二级指针数组并对其进行 qsorting 而不是主数组的原因，

于 2013-10-15T02:50:34.417 回答