c - 用 C 读/写多数组数据结构

Question

我抽象出了一个需要用 C 语言保存的排序列表。一种方法最适合阅读，另一种方法最适合写作。

WRITE: search KeyNumeric then KeyAlpha and write *Data

Key1 : [ KeyA, *Data1A, KeyB, *Data1B, KeyC, *Data1C ]
Key2 : [ KeyA, *Data2A, KeyB, *Data2B, KeyC, *Data2C ]
Key3 : [ KeyA, *Data3A, KeyB, *Data3B, KeyC, *Data3C ]


READ: search KeyAlpha then KeyNumeric and read *Data

KeyA : [ Key1, *Data1A, Key2, *Data2A, Key3, *Data3A ]
KeyB : [ Key1, *Data1B, Key2, *Data2B, Key3, *Data3B ]
KeyC : [ Key1, *Data1C, Key2, *Data2C, Key3, *Data3C ]

有人知道在内存中表示此数据结构的最有效方法是什么吗？

Answer 1

如果我理解正确的话:

• 您的数据有一个由数字和某种字母组成的复合键(您没有说明它是字符还是字符串)。
• 有时您有字母键，需要搜索数字，有时反之亦然(它恰好被读取和(覆盖)写入，但这可能不是重点)。
• 插入和删除很少见，但需要支持。

我还将假设数据键是稀疏的，因此直接的“[N][A]”数组不适合您。

由于您希望数据进行双重索引，因此我建议您需要某种链接结构:列表或树。

要使用链表来完成此操作，您的 C 结构可能如下所示:

struct stuff {
  int num_key;
  char alpha_key;

  /* The number-first lists.  */
  struct {
    struct stuff *next_num;
    struct stuff *next_alpha;
  } num_list;

  /* The alpha-first links.  */
  struct {
    struct stuff *next_alpha;
    struct stuff *next_num;
  } alpha_list;

  struct data Data;
};

因此，如果您有数据项1A、1B、1C、2A、2B、2C、3A、3B、3C，这些链接的工作方式如下:

• 1A num_list.next_num 指向 2A。
• 1A num_list.next_alpha 指向 1B。
• 1A num_alpha.next_alpha 指向 1B。
• 1A num_alpha.next_num 指向 2A。
• 2B num_list.next_num 为 NULL。
• 2B num_list.next_alpha 指向 2C。
• 2B num_alpha.next_alpha 为 NULL。
• 2B num_alpha.next_num 指向 3B。

因此，用文字来说，num_list.next_num 始终指向具有下一个数字的内容，但第一个 字母可用。同样，alpha_list.next_alpha 始终指向带有下一个字母的内容，但第一个数字可用。如果您不查看辅助列表的头部，则主列表的指针为 NULL，因为您永远不想以这种方式遍历数据，并且在那里维护真正的指针会导致错误，或导致插入或删除时额外的维护。

您可以将其视为两个列表列表:

• num_list.next_num 是 num_list.next_alpha 列表的头列表。
• aplha_list.next_alpha 是 alpha_list.next_num 列表的头列表。

要查找项目，您首先要在主列表之一上移动，num_list.next_num 或 aplha_list.next_alpha，然后向下移动到辅助列表之一，num_list.next_alpha或num_alpha.next_num。

<小时/>

因此，显然存在一些效率问题:

• 所有这些小数据 block 的 malloc 效率很低。
• 访问列表的时间复杂度为 O(n)。

如果您正在处理大量数据，我会做两件事:

1. 使用某种平衡树而不是平面列表。然后，“列表的头部”就成为“树的根”。

2. 分配了一个固定大小的struct stuff数组，并使用数组索引作为链接，而不是指针。然后只需维护一个未使用插槽的“空闲列表”即可。如果您的数据超出了数组，则使用 realloc 或分配第二个内存块并记住哪些索引位于哪个 block 中。