2

在 C 中，我需要存储一个可能相对较大（数千个项目）的短字符串 (char*) 列表。
字符串可以删除或插入但不能修改，顺序并不重要。
我不知道什么是更有效的数据结构来做到这一点。
我可以使用 struct ：

struct node_s {
  char *str;
  node_s *next;
}

或 char * 数组：

char **strings;

我不需要直接访问字符串，我只需要它们存在，因为旁边的另一个数据结构（radix trie）维护字符串某些部分的指针。

4

6 回答 6

2

当您在初始化时不知道确切的条目数时，使用链表通常比使用数组更好。

数组具有固定大小。当您不知道将拥有多少条目并且想要使用数组时，您有两种选择。要么你分配一个比你需要的任何东西都大得多的数组，这是对内存的巨大浪费（而且，通常很难事先知道合理的上限应该是多少）。或者你从一个小数组开始，等到它满了。然后分配一个更大的新数组，将所有条目复制到新数组并释放旧数组，这是对 CPU 周期的巨大浪费。

但是使用链表，您就没有这个问题，因为它们可以动态增长和收缩。

但请注意各种操作的运行时间差异。

在数组中，通过索引获取元素非常快。但是删除具有特定索引的元素而不留下空条目是非常昂贵的，因为后面的每个元素都必须向后移动一个索引。在中间插入一个条目而不覆盖现有条目同样昂贵，因为您必须将后面的所有内容向前移动一个。

使用链表，删除或插入中间的节点很快（当您已经有了它的前导节点时），因为除了插入的节点及其前导节点之外没有其他节点需要被触及。但是找到必须执行此操作的节点可能会很昂贵，因为您必须通过之前的所有节点跟踪链接。

当您需要快速查找和快速插入/删除时，使用二叉树是一个很好的折衷方案。

于 2012-12-11T14:52:49.843 回答
1

这取决于你的程序。

如果你知道字符串的数量。我建议你使用数组

如果您不知道字符串的数量，我建议您使用链表

如果字符串将在 C 中定义为常量。你可以这样使用：

char *strings[1000] = {
  "string 0",
  "string 1",
  "string 2",
  "string 3",
   .
   .
   .
  "string 999"
}
于 2012-12-11T14:47:15.573 回答
1

实际上，char **strings只是一个字符串数组。数组≠链表。那么node_s绝对是解决方案。

于 2012-12-11T14:47:17.743 回答
1

这取决于你想用它们做什么。

如果顺序不重要，我认为大多数操作将是添加\删除。如果是这样，您需要选择列表数据结构（第一个变体）。

如果您需要对元素进行恒定时间访问，则数组很好，但在无序数组中，这将不起作用.. 搜索某些字符串将花费 O(n) 时间，就像在列表中一样。

于 2012-12-11T14:50:40.887 回答
1

所以，如果我理解正确的话，字符串列表不是访问数据的主要方式，它只是一个指针的“清理列表”，必须释放这些指针，而不必遍历所有其他现已过时的数据。

在这种情况下，我会使用链表，但不是以正常方式。您的node_s上述要求，对于每个字符串，您malloc为结构执行一个，为字符串本身执行一个。

相反，我会定义一个这样的结构：

struct string_list {
  struct string_list *next;
  char data[0];
};

零长度数组在结构中不占用空间，但为您提供了一个可以使用的类型化地址。然后，您可以为结构和实际字符串分配内存：

struct string_list *newstr = malloc (sizeof(struct string_list) + my_desired_size);

然后将数据放在newstr->data，并链接next指针：

newstr->next = list_head;
strcpy (newstr->data, my_data, my_desired_size);
list_head = newstr;

当需要释放字符串时，只free需要一个即可。哦，当然还有修复链接。

于 2012-12-11T15:59:18.460 回答
0

当您有大量项目并且想要频繁添加/删除项目时，同时访问时间接近随机访问 O(log n)，您应该考虑使用哈希表。

如果在节点上添加数千个，则链表的访问时间会非常慢，并且数组不适合频繁添加/删除。

于 2012-12-11T15:41:08.027 回答