使用 qsort 对列表进行排序？

Question

我正在编写一个程序，您可以在其中通过键盘或文件输入单词，然后将它们按长度排序。 有人告诉我应该使用链表，因为单词的长度和数量不固定。

我应该使用链表来表示单词吗？

struct node{
    char c;
    struct node *next;
};

那么如何使用 qsort 按长度对单词进行排序呢？ qsort 不适用于数组吗？

我对编程还很陌生。

谢谢。

Answer 1

我认为有一个比您应该选择的排序算法更大的问题。 第一个是您定义的结构实际上不会保存单词列表，而是保存单个字母（或单个单词）的列表。C 中的字符串表示为以 null 结尾的字符数组，布局如下：

| A | n | t | h | o | n | y | \0 |

这个数组理想地被声明为 char[8] - 每个字母一个插槽，加上一个空字节插槽（实际上是内存中的一个字节的零。）

现在我知道你可能知道这一点，但为了清楚起见，值得指出这一点。 当您操作数组时，您可以一次查看多个字节并加快速度。 使用链表，您只能以真正线性的时间查看事物：从一个字符走到下一个字符。 当您尝试在字符串上快速执行某些操作时，这一点很重要。

保存此信息的更合适的方法是采用非常类似于 C 的风格，并在 C++ 中用作向量：使用 malloc 和 realloc 自动调整连续内存块的大小。

首先，我们设置一个像这样的结构：

struct sstring {
    char *data;
    int logLen;
    int allocLen;
};
typedef struct string sstring;

我们为此提供了一些函数：

// mallocs a block of memory and holds its length in allocLen
string_create(string* input); 

// inserts a string and moves up the null character
// if running out of space, (logLen == allocLen), realloc 2x as much
string_addchar(string* input, char c);

string_delete(string* input);

现在，这不太好，因为您不能只使用 scanf 读入一个简单的缓冲区，但您可以使用类似 getchar() 的函数来获取单个字符并使用 string_addchar() 将它们放入字符串中以避免使用链表。 该字符串尽可能避免重新分配，每 2^n 插入一次，并且您仍然可以使用 C 字符串库中的字符串函数！！这对实现排序有很大帮助。

那么现在我该如何实际实现排序呢？ 您可以创建一个类似的类型，旨在以类似的方式保存整个字符串，并根据需要进行增长，以保存来自控制台的输入字符串。 无论哪种方式，您的所有数据现在都位于可以作为数组访问的连续内存块中 - 因为它是一个数组！ 例如，假设我们有这个：

struct stringarray {
    string *data;
    int logLen;
    int allocLen;
};
typedef struct stringarray cVector;
cVector myData;

以及与以前类似的功能：创建、删除、插入。

这里的关键是您可以在 string.data 元素上使用 strcmp() 来实现排序函数，因为它只是一个 C 字符串。 由于我们有一个使用函数指针的 qsort 内置实现，因此我们所要做的就是包装 strcmp() 以与这些类型一起使用并传入地址。

Answer 2

如果您知道如何对项目进行排序，则在读取数据时应该使用插入排序，这样一旦输入了所有输入，您所要做的就是写入输出。 使用链表就可以了，尽管您会发现它具有 O(N²) 性能。 如果您将输入存储在按长度排序的二叉树中（平衡树最好），那么您的算法将具有 O(NlogN) 性能。 如果您只想执行一次，那么就应该优先考虑实施的简单性而不是效率。

伪代码：

  list = new list
  read line
  while not end of file
      len = length(line)
      elem = head(list)
      while (len > length(elem->value))
          elem = elem->next
      end
      insert line in list before elem
      read line
  end

 // at this point the list's elements are sorted from shortest to longest
 // so just write it out in order
 elem = head(list)
 while (elem != null)
     output elem->value
     elem = elem->next
 end

Answer 3

是的，经典的“C”库函数 qsort() 只适用于数组。 这是内存中连续的值集合。

Tvanfosson 的建议非常好——当你构建链表时，你可以在正确的位置插入元素。 这样，列表始终是排序的。

我认为您被告知要使用链接列表的评论很有趣。 事实上，列表在许多情况下都是一种很好的数据结构，但它确实有缺点； 例如，必须遍历它才能找到元素。

根据您的应用程序，您可能需要使用哈希表。 在 C++ 中，您可以使用 hash_set 或 hash_map。

我建议您花一些时间学习基本数据结构。 在这里花费的时间将使您受益匪浅，并且更好地让您能够评估诸如“使用链接列表”之类的建议。

Answer 4

有很多方法可以处理它......如果您有足够的勇气尝试，您可以通过动态内存分配和 realloc 使用数组。

然而，qsort 的标准实现需要每个元素都是固定长度，这意味着有一个字符串指针数组。

不过，与使用指向指针的指针相比，实现链表应该很容易。

我认为您被告知要做的不是将字符串保存为列表；而是将字符串保存为列表。 但是在链表中：

struct node {
    char *string;
    node *next;
}

然后，您所要做的就是每次读取字符串时，将一个新节点添加到列表中的有序位置。 （遍历列表，直到当前字符串的长度大于您刚刚读取的字符串。）

单词长度不固定的问题很常见，通常通过将世界临时存储在缓冲区中，然后将其复制到适当长度的数组（当然是动态分配的）。

编辑：

在伪代码中：

array = malloc(sizeof(*char))
array_size = 1
array_count = 0

while (buffer = read != EOF):
    if(array_count == array_size)
        realloc(array, array_size * 2)
    array_count++
    sring_temp = malloc(strlen(buffer))
    array[array_count] = string_temp

qsort(array, array_count, sizeof(*char), comparison)

print array

当然，这需要大量的润色。 请记住，数组的类型为 char **array，即“指向 char 的指针的指针”（将其作为指针数组处理）； 由于您要传递指针，因此不能只将缓冲区传递到数组中。

Answer 5

您可以通过分配一个指针数组（每个列表元素一个）来对链表进行排序。

然后，您对该数组进行排序，在比较函数中，您当然会收到指向列表元素的指针。

然后，这将为您提供一个排序的指针列表。

然后，您可以通过遍历指针数组并依次调整每个元素来遍历列表。 重新排列其在列表中的顺序以匹配指针数组的顺序。