数据结构中的卫星信息是什么？

Question

18

摘自Thomas Cormen的《算法导论》：

为了简化问题，我们假设与键相关联的任何“卫星信息”都存储在同一节点中，就像二叉搜索树和红黑树一样。实际上，一个人可能会仅将每个键与指向包含该键卫星信息的另一个磁盘页面的指针一起存储。本章中的伪代码默认假定与键相关联的卫星信息或指向这种卫星信息的指针随着键从节点移动而传递。

所以我一直在尝试谷歌术语“卫星信息”的含义，但我找不到（被NASA的事情覆盖）。基于文本本身，我的理解是“卫星信息”是指向实际键值位置的地址，例如指针？我是正确的还是我误解了它？

编辑：它与键有何不同之处？

- jantristanmilan

你最后一个问题的答案肯定是“是”。 - Kerrek SB

1

@KerrekSB "我有误解吗？" 那个.. - jantristanmilan

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Kerrek SB · Accepted Answer

卫星数据是指您想要存储在数据结构中的任何“有效载荷”数据，它不是数据结构的一部分。它可以是任何您想要的东西。它可以是单个值、大量值的集合或指向保存值的其他位置的指针。

例如，这里是一个单链表的列表节点，其卫星数据是一个整数：

struct node
{
    node * next;
    int satellite;
};

换句话说，任何给定数据结构的整个价值在于它所包含的数据，即你书中所称的卫星数据。数据结构还将消耗结构数据（例如示例中的next指针）来执行定义它的算法，但从用户的角度来看，这些基本上是“开销”。

对于关联容器，“键”值扮演着双重角色：一方面它是用户数据，另一方面它也是容器结构的一部分。然而，树可以配备额外的卫星数据，这样它就成为从键数据到卫星数据的“映射”。

在一个极端，你有一个固定大小的数组，它没有任何开销，只有有效载荷数据；在另一个极端，你有复杂的结构，如多索引、tries、Judy数组或无锁容器，它们维护着相当大量的结构数据。