17

摘自 Thomas Cormen 的算法简介：

"为简单起见，我们假设，就像我们对二叉搜索树和红黑树所做的那样，与密钥相关的任何“卫星信息”都存储在与密钥相同的节点中。实际上，人们可能会实际存储每个键只是指向另一个磁盘页面的指针，该磁盘页包含该键的卫星信息。本章中的伪代码隐含地假设与键关联的卫星信息或指向此类卫星信息的指针，无论何时移动键，都与键一起传播从一个节点到另一个节点。 ”

所以我一直在尝试用谷歌搜索卫星信息这个词的含义，但我找不到任何东西（被关于 NASA 的东西所涵盖）。我仅基于文本的理解是，“卫星信息”是指向实际键值位置的地址，例如指针？我是正确的还是我误解了它？

编辑：是什么使它与钥匙不同？

4

1 回答 1

26

卫星数据是指您想要存储在数据结构中并且不属于数据结构结构的任何“有效负载”数据。它可以是你想要的任何东西。它可以是单个值、大量值或指向保存该值的其他位置的指针。

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

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

换句话说，任何给定数据结构的全部价值在于它包含的数据，这就是你书中术语中的卫星数据。数据结构将额外消耗结构数据（如next示例中的指针）以执行定义它的算法，但从用户的角度来看，这些本质上是“开销”。

对于关联容器，“键”值具有双重作用：一方面是用户数据，另一方面也是容器结构的一部分。然而，一棵树可以配备额外的卫星数据，在这种情况下，它成为从关键数据到卫星数据的“地图”。

At one extreme you have a fixed-size array which has no overhead and only payload data, and on the other extreme you have complicated structures like multiindexes, tries, Judy arrays, or lockfree containers which maintain a comparably large amount of structural data.

于 2013-01-27T20:29:03.830 回答