c-对包含字符串的链表进行排序

Question

所以我想做的是对只包含字符串的链表进行排序。为此，我有两个选择。

选项1-动态分配一个与链表大小相同的数组，并且包含该数组的字符串也具有相同的大小，将链表的内容复制到数组中，并使用qsort对其进行排序。

选项2-实现合并排序算法以便对其进行排序。

其中一个问题是，如果我选择选项2而不是选项1，它会花费更多的内存和时间吗？

我的第二个问题是，我正在尝试执行选项1，为此，我有一个包含链表代码的头文件。问题是在为字符串数组分配内存后，当我试图复制内容时，我会出现分段错误。

程序：

#include <stdlib.h> 
#include <stdio.h>
#include <string.h>
#include "Listas_ligadas_char.h"
int main() {
link_char head = NULL;
char **strings;
head = insertEnd_char(head, "fcb");
head = insertEnd_char(head, "bvb");
head = insertEnd_char(head, "slb");
head = insertEnd_char(head, "fcp");
int len = length_char(head);
int i = 0, j;
strings = (char **)malloc(sizeof(char *) * len);
link_char t;
t = head;
while (t != NULL && i <= len) {
strings[i] = (char *)malloc(sizeof(char) * (strlen(t->str) + 1));
strcpy(strings[i++], t->v.str)
t = t->next;
}
for (t = head; t != NULL; t = t->next) {
printf("* %sn", strings[i]);
}
}

头文件：

#ifndef _Listas_ligadas_char_
#define _Listas_ligadas_char_
#include <stdlib.h> 
#include <stdio.h>
#include <string.h>
typedef struct node_char {
char *str;
struct node_char *next;
} *link_char;
link_char lookup_str(link_char head, char *str) {
link_char t;
for (t = head; t != NULL; t = t->next)
if (strcmp(t->str, str) == 0)
return t;
return NULL;
}
link_char NEW_str(char *str) {
int i;
link_char x = (link_char)malloc(sizeof(struct node_char));
x->str = (char *)malloc(sizeof(char) * (strlen(str) + 1));
strcpy(x->str, str);
x->next = NULL;
return x;
}
link_char insertEnd_char(link_char head, char *str) {
link_char x;
if (head == NULL)
return NEW_str(str);
for (x = head; x->next != NULL; x = x->next)
;
x->next = NEW_str(str);
return head;
}
int length_char(link_char head) {
int count = 0;
link_char x;
for (x = head; x != NULL; x = x->next)
count++;
return count;
}
void print_lista_char(link_char head, int NL) {
link_char t;
for (t = head; t != NULL; t = t->next) {
printf("%d * %sn", NL, t->str);
}
}
void FREEnode_str(link_char t) {
free(t->str);
free(t);
}
link_char delete_el_char(link_char head, char *str) {
link_char t, prev;
for (t = head, prev = NULL; t != NULL;
prev = t, t = t->next) {
if (strcmp(t->str, str) == 0) {
if (t == head)
head = t->next;
else
prev->next = t->next;
FREEnode_str(t);
break;
}
}
return head;
}
#endif

顺便说一句，如果你想知道NL是什么，NL是一个计算stdin各行的变量，而我只想打印数组，我不想保留它的元素。

所以，如果你能说出你认为哪种选择是最好的，我会非常感激。

Answer 1

选项1-动态分配一个与链表大小相同的数组和包含该数组的字符串，并将链表的内容复制到数组中，然后使用qsort对其进行排序。

没有必要将链表转换为数组。快速排序算法也可以应用于链表。

然而，由于您的链表仅是单独链接的，因此您不能使用(通常更高效的)Hoare分区方案，而必须使用Lomuto分区方案。这是因为Hoare分区方案需要向后遍历链表的能力(这需要一个双链表)。

即使快速排序算法不需要将链表转换为数组，这可能仍然有意义，因为链表的空间局部性比数组差。无论哪种方式，算法的平均时间复杂度将是O(n*logn)，最坏情况下的时间复杂度为O(n^2)。

但是，由于节点只包含指向字符串的指针，所以在取消引用这些指针时，空间局部性无论如何都会很差。因此，在这种情况下，将链表转换为数组可能没有太大帮助，因为这只会提高指向字符串的指针的空间位置，而不会提高字符串本身的空间位置。

---

问题之一是，如果我选择选项2而不是选项1，它会花费更多的内存和时间吗？

合并排序是链表的理想选择。

合并排序的另一个优点是其最坏情况下的时间复杂性，即O(n*logn)，而使用快速排序时为O(n^2)。

对于链表，合并排序的空间复杂度为O(1)，而快速排序的空间复杂性为O(logn)。但是，如果您决定将列表转换为用于快速排序的数组，则算法的空间复杂性将增加到O(n))。

---

我的第二个问题是，我试图执行选项1，为此我有一个包含链表代码的头文件。问题是在为字符串数组分配内存后，当我试图复制内容时，我会出现分段错误。

只有当你提供一个关于你的问题的最小可重复的例子时，我才能帮助你。您发布的代码没有重现问题。它甚至不编译。以下行包含几个错误：

strcpy(strings[i++],t->v.str)

Answer 2

您确实有两个明智的选择：

• 选项1通常会提供最佳性能，但需要额外的sizeof(link_char) * N空间。

• 选项2对于使用自底向上合并排序的挂起子列表只需要O(log(N))堆栈空间，或者对于递归自上而下合并排序只需要类似的空间复杂性。缺点是你必须自己编写排序函数，而且很容易出错。

请注意，对于选项1，您不应该复制字符串，而应该只分配一个指针数组并初始化它以指向节点本身。通过这种方式，您可以保留可能包含其他信息的节点结构，并避免额外的分配。

还要注意的是，一旦有了节点指针数组和比较函数，就可以使用qsort或其他排序函数，如timsort或mergesort，这在最坏情况下的时间复杂性方面可能更合适。

在您的实现中存在多个问题：

• 回路测试while (t != NULL && i <= len)不正确。测试应该是冗余的，但如果您坚持测试i，它应该是i < len，或者如果length_char返回了不正确的计数，您可能会访问超出string数组末尾的内容
• strcpy(strings[i++], t->v.str)有语法错误，您可能是指strcpy(strings[i++], t->str);

• 打印循环具有未定义的行为，因为您没有将i重置为0，也没有在循环体中增加i，所以您为所有对printf的调用传递strings[i]，并且i应该是len，所以strings[i]访问分配的数组的末尾之外。您可能会得到崩溃或无效指针，或者printf可能忽略的空指针。。。应该是：

  for (i = 0; i < len; i++) {
  printf("* %sn", strings[i]);
  }
  

这是一个修改后的版本：

#include <stdio.h>
#include <stdlib.h>
#include "Listas_ligadas_char.h"
int cmp_char(const void *aa, const void *bb) {
link_char a = *(const link_char *)aa;
link_char b = *(const link_char *)bb;
return strcmp(a->str, b->str);
}
link_char sort_char(link_char head) {
if (head != NULL && head->next != NULL) {
size_t i, len = length_char(head);
link_char *array = malloc(sizeof(*array) * len);
link_char t = head;
for (i = 0; i < len; i++, t = t->next)
array[i] = t;
qsort(array, len, sizeof(*array), cmp_char);
head = t = array[0];
for (i = 1; i < len; i++)
t = t->next = array[i];
t->next = NULL;
free(array);
}
return head;
}
int main() {
link_char head = NULL;
head = insertEnd_char(head, "fcb");
head = insertEnd_char(head, "bvb");
head = insertEnd_char(head, "slb");
head = insertEnd_char(head, "fcp");
head = sort_char(head);
for (link_char t = head; t != NULL; t = t->next) {
printf("* %sn", strings[i]);
}
return 0;
}

注：

• 将指针隐藏在typedef后面很容易出错。您应该将node_char定义为typedef struct node_char node_char，并在任何地方使用node_char *
• 在头文件中定义列表函数是非常规的。您可以对static inline函数执行此操作，但不应在头文件中定义全局函数，因为如果多个模块包含此头文件并链接在一起，则会导致名称冲突