电话簿的数据结构

Question

可能的重复：
存储 100 万个电话号码

如何设计包含 3 个电话地址簿的数据结构领域 姓名、电话号码、地址

必须能够在 3 个字段中的任何一个上搜索此电话簿

哈希表不起作用，因为所有三个字段都应哈希为相同的值，我认为这是不可能的。我也考虑过 trie 和其他数据结构，但想不出正确的答案。

Answer 1

您应该使用 TRIE 数据结构来实现电话簿。 TRIE 是一种使用字符串作为键的有序树数据结构。与二叉树不同，TRIE不存储与节点关联的键。

很好的例子

Answer 2

您可以使用单个哈希表或其他类型的关联数组（如果您愿意）来完成此操作。对于每个人，表中只有三个键（姓名、地址、电话），全部指向同一条记录。

Answer 3

我认为 trie （每个电话簿条目都是一片叶子）和两个 跳过列表（每个姓名和地址一个）可能会很有效。

只需为每个节点分配一组指针以沿名称轴移动，并分配一组指针以沿地址轴移动（即遍历跳跃列表）。

Answer 4

你不能同时用三种方式对某件事进行精确排序。您也不可能构建一个允许仅使用三分之一的键进行查找的哈希表。

您可能想要做的基本上就是数据库所做的事情：

• 存储所有记录的一个（可能未排序的）主列表。
• 对于您希望能够搜索的每一列，构建某种查找结构，该结构将指针/索引返回到主列表中。

因此，例如，您可以按照所需的顺序构建一个由 {name,phone,address} 结构组成的平面数组，然后对于每一行，将 (phone -> row#) 映射放入哈希表中。非唯一列可以散列到行号列表，或者您可以将它们放入二叉树中，其中重复键不成问题。

就空间要求而言，您基本上最终会将每个元素存储两次，因此您的空间要求至少会增加一倍。除此之外，您还获得了数据结构本身的开销；保持三个哈希表以约 70% 的容量加载，您的存储需求至少会增加 2.4 倍。

您可以通过保持主表在其中一列上排序来取消这些辅助查找结构之一，这样您就可以直接在 O(logN) 中搜索它。然而，这使得插入/删除行的成本非常昂贵（O(N)），但如果您的数据相当静态，那么这不是什么大问题。如果是这种情况，排序数组也将是辅助查找最节省空间的选择。

Answer 5

在电话簿中，电话号码应该是唯一的，地址是唯一的，但姓名可以重复。

所以也许你可以使用哈希表和链表结合来解决这个问题。

您可以使用“姓名、地址、电话号码”中的任何一个或组合作为哈希键，如果您仅使用姓名作为哈希键，则需要链表来存储重复的条目。

在这种方法中，基于哈希键的搜索效率为 O(1)，但基于其他两个的搜索效率为 O(n)。

Answer 6

C、C++ 还是 C#？

使用课程列表

    public class PhoneBook
{
    public string name;
    public string phoneNumber;
    public string address;
}

将其放入列表中，您就有了电话簿

Answer 7

在 C 中，我认为结构体是最好的选择。

typedef struct _Contact Contact;

struct _Contact
{
    char* name;
    char* number;
    char* address;
};

Contact* add_new_contact( char* name, char* number, char* address )
{
    Contact* c = (Contact*) malloc( sizeof( Contact ) );
    c->name = name;
    c->number = number;
    c->address = address;
    return c;
}

Contact* phone_book [ 20 ];  /* An array of Contacts */

使用标准字符串函数（ 或者如果使用 C++ 编译器，则 ）或类似 glib 的函数用于搜索姓名、数字等。

这是一个简单的示例：

Contact* search_for_number( Contact* phone_book[], const char* number )
{
    register int i;
    for( i = 0; i < sizeof( phone_book ); i++)
    {
       if ( strcmp( phone_book[i]->number, number ) == 0 ) return phone_book[i];
    }
    return NULL;
}

还有一个很好的、有用的代码示例 此处。

或者，

您也许可以使用链表，但由于 C 或 C 标准库不提供链表，您要么需要自己实现，要么使用第三方库。

我建议使用glib中的g_linked_list。