0

我正在尝试在 C 中开发一个网络资源管理器组件，它通过 TCP/UDP 套接字跟踪各种网络元素。为此，我使用三个值：

  1. 硬件位置编号
  2. 服务组号
  3. 节点号

规则是网络上的任何两个元素都不能具有相同的这三个数字的集合。因此，每个位置的身份在网络上都是唯一的。此信息需要以某种方式（非持久性）保存在程序中，以便给定任何参数（可能只是一个数字，或任何两个的组合，或全部三个），程序通过以下方式返回合格的候选人执行快速搜索。

添加和删​​除也应该是高效的，但是考虑到在初始瞬态阶段之后插入或删除会很少，如果它们比搜索慢一点，应该没问题。使用树是一种选择，但答案是“使用哪一个？” 仍然让我望而却步（不是我知道很多，但如果它们符合我的目的，我期待学习新的）。

为此，我可以分别维护三个不同的树，其中相似的节点指向内存中的相同结构，但我觉得这效率低且不紧凑。我正在寻找一个统一的数据集，它可以像多个键一样处理这些变化。

或者我可以有一个带有多个键的 AVL 树（如果允许的话）。

网络中的元素数量是动态的，因此无法选择使用 3D 数组。

一个朋友也建议散列，但我不太确定。

请帮忙。

4

1 回答 1

1

散列似乎是一个愚蠢的选择。也许最重要的原因是您似乎对近似查找感兴趣。散列您的值可能意味着遍历整个集合以找到一组具有共同前缀或类似前缀的节点。

PATRICIA 常用于路由表中，它使自己非常适合搜索具有相似键的项目。请注意，我发现了很多关于 PATRICIA 尝试的误导性信息，我在这里写过这些信息。我发现这个资源特别有用。

与 AVL 树类似，您需要将三个键组合成一个（最好不要散列）。

unsigned int key[3] = { hardware_location_number, service_group_number, node_number };
           /* ^------- Use something like this as your key */
于 2013-05-01T11:58:02.950 回答