c++ - 如何实现关联数组/映射/哈希表数据结构（一般和 C++ 中）

Question

好吧，我正在制作一个小型电话簿应用程序，我决定使用地图是最好的数据结构，但我不知道从哪里开始。（必须从头开始实现数据结构 - 学校作业）

Answer 1

尝试对于实现键是短字符串的映射非常有效。维基百科文章很好地解释了它。

处理重复，只需让树的每个节点存储一个重复匹配的链表

这是 trie 的基本结构

struct Trie {
   struct Trie* letter;
   struct List *matches;
};

malloc(26*sizeof(struct Trie)) 为字母，你有一个数组。如果要支持标点符号，请将它们添加到字母数组的末尾。

匹配项可以是匹配项的链接列表，可以随心所欲地实现，我不会为你定义结构列表。

Answer 2

最简单的解决方案：使用包含您的地址条目的向量并遍历该向量进行搜索。

映射通常实现为二叉树（寻找红/黑树进行平衡）或哈希映射。它们都不是微不足道的：树在组织、内存管理和平衡方面有一些开销，哈希映射需要良好的哈希函数，这也不是微不足道的。但是这两种结构都很有趣，通过实现其中一个（或者更好，两者都可以:-)），您将获得很多洞察力的理解。

还要考虑将数据保留在向量列表中，并让映射包含向量的索引（或指向条目的指针）：然后您可以轻松拥有多个索引，例如一个用于名称，一个用于电话号码，这样您就可以查找两者的条目。

也就是说，我只想强烈推荐使用标准库提供的数据结构来处理现实世界的任务:-)

Answer 3

一个简单的入门方法是创建一个使用两个向量的地图类——一个用于键，一个用于值。要添加一个项目，请在其中插入一个键，在另一个中插入一个值。要找到一个值，您只需遍历所有键。完成这项工作后，您可以考虑使用更复杂的数据结构。