c - 如何存储联系信息

Question

存储联系信息[姓名、电话号码]的最佳数据结构是什么？

Trie 可用于在给出姓名时搜索电话号码。
如果我想根据电话号码查找一个人的姓名该怎么办？即当我知道电话号码时如何找到姓名？
trie 对于此类搜索有效吗？

Answer 1

是的，特里结构很好。您可以使用电话号码中的位(如果将它们存储为整数)，而不是使用字符串中的字符作为每个级别的键。出于速度原因，您可能决定一次使用 3 或 4 位。

这可以通过一个存储当前身份信息的 trie 结构和一个指向子 trie 结构的指针数组来实现。

struct phone_number_trie {
   struct contact_info *info;
   struct phone_number_trie *children[4]; //  or 2, 8 or 16 etc.
};

例如将电话号码“83”(二进制为 1100011)存储在根为 root 的树中，您可以屏蔽较低的 2 位(例如 & 3)，即 11，因此您可以使用电话号码 11000 的剩余位递归到 root->children[3] (即右移 2)。下一个索引将是 0，然后是 10，然后是 1(因此您将指向 root->children[3 ]-> child [0]-> child [2]-> child [1])。此时，您的电话号码中已没有剩余的设置位，因此您已找到正确的插入位置。

(您也可以考虑使用 Patricia trie ，但这明显更难实现。)