c - 使用 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++ 中用作 vector :使用 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() 以用于这些类型并传入地址。