1

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

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

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

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

我对编程很陌生。

谢谢你。

4

5 回答 5

3

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

| 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() 以用于这些类型并传入地址。

于 2009-04-25T23:35:09.137 回答
1

如果您知道如何对项目进行排序，则在读取数据时应该使用插入排序，这样一旦输入了所有输入，您所要做的就是编写输出。使用链表是可以的，尽管您会发现它具有 O(N 2 ) 的性能。如果您将输入存储在按长度排序的二叉树中（平衡树最好），那么您的算法将具有 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
于 2009-04-25T23:22:15.377 回答
0

您可以通过分配一组指针来对链表进行 qsort，每个列表元素一个。

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

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

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

于 2009-04-26T07:43:04.473 回答
0

有很多方法可以处理它...如果您有足够的勇气尝试，您可以通过动态内存分配和 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 的指针的指针”（您将其作为指针数组处理）；由于您要传递指针，因此不能只将缓冲区传递到数组中。

于 2009-04-25T23:30:32.223 回答
0

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

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

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

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

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

于 2009-04-25T23:31:43.700 回答