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，因此您将递归到root->children[3]电话号码的剩余位11000（即向右移动 2）。下一个索引是0,10然后是1（所以你会指向root->children[3]->children[0]->children[2]->children[1]）。此时，您的电话号码中没有任何设置位，因此您找到了正确的插入位置。

（您也可以考虑使用Patricia trie，但这很难实现。）