-1

我抽象出一个我需要保存在 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 ]

有谁知道在内存中表示这种数据结构的最有效方法是什么？

4

2 回答 2

3

如果我理解正确：

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

我还将假设数据键是稀疏的，因此直接的“[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。

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

  • 所有这些小数据块的 malloc 都是低效的。
  • 列表是 O(n) 访问。

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

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

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

于 2013-02-02T18:30:41.857 回答
1

处理您所询问的多个索引的一个很好的通用方法是使用对哈希表和可交换哈希函数，其中字母和数字键的顺序无关紧要：

typedef struct hash_node_s {
  struct hash_node_s *next;
  char *keyAlpha;
  unsigned keyNumeric;
  void *data
} HASH_NODE, *HASH_NODE_PTR;

#define HASH_TABLE_SIZE 997
typedef HASH_NODE_PTR HASH_TABLE[HASH_TABLE_SIZE];

// Hash a string and integer in one value.
unsigned hash(char *keyAlpha, unsigned keyNumeric) {
  unsigned h = 0;
  for (int i = 0; keyAlpha[i]; i++) {
    h = h * 31 ^ keyAlpha[i] ^ keyNumeric;
    keyNumeric *= 31;
  }
  return h;
}

static HASH_NODE *find_or_insert(HASH_TABLE tbl, char *keyAlpha, unsigned keyNumeric) {
  unsigned h = hash(keyAlpha, keyNumeric) % HASH_TABLE_SIZE;
  for (HASH_NODE *p = tbl[h]; p; p = p->next)
    if (strcmp(keyAlpha, p->keyAlpha) == 0 && keyNumeric == p->keyNumeric)
      return p;
  HASH_NODE *n = safe_malloc(sizeof *n);
  n->next = tbl[h];
  n->keyAlpha = safe_strdup(keyAlpha);
  n->keyNumeric = keyNumeric;
  n->data = NULL;
  tbl[h] = n;
  return n;
}

void insert(HASH_TABLE tbl, char *keyAlpha, unsigned keyNumeric, void *data) {
  find_or_insert(keyAlpha, keyNumeric)->data = data;
}

void write(HASH_TABLE tbl, unsigned keyNumeric, char *keyAlpha, void *data) {
  find_or_insert(keyAlpha, keyNumeric)->data = data;
}

void *read(HASH_TABLE tbl, char *keyAlpha, unsigned keyNumeric) {
  return find_or_insert(keyAlpha, keyNumeric)->data;
}

void delete(HASH_TABLE tbl, char *keyAlpha, unsigned keyNumeric)
{
  unsigned h = hash(keyAlpha, keyNumeric) % HASH_TABLE_SIZE;
  for (HASH_NODE *q = NULL, *p = tbl[h]; 
       p; 
       q = p, p = p->next)
    if (strcmp(keyAlpha, p->keyAlpha) == 0 && keyNumeric == p->keyNumeric) {
      if (q) 
        q->next = p->next;
      else 
        tbl[h] = p->next;
      safe_free(p->keyAlpha);
      safe_free(p);
      return;
    }
}

此代码未经测试，但除了轻微的拼写错误外，它应该是可靠的。

所有操作的成本大致相同。计算哈希函数取决于密钥长度。除此之外，所有操作的概率都是 O(1)，这意味着除非遇到哈希函数不会产生伪随机结果的坏情况，或者让表负载变得过高，否则这确实会非常快。

这段代码的弱点是它每个元素存储两个键，字符串键可能任意大。但这可以通过使用单独的字符串表（字符串的哈希表）来解决，以便重复的字符串由相同的指针表示。字符串表插入和删除（当引用计数达到零时）将替换safe_strdupandfree调用。在所有其他情况下，代码将保持不变。有了这个，存储开销是一个整数和每个数据项的指针。

于 2013-02-04T18:23:49.193 回答