algorithm - 为什么要搜索链表？

Question

我正在阅读“算法设计手册”，它说基本列表上的三个操作是搜索、插入和删除。然后它继续在 C 中描述一种算法，一旦找到它正在寻找的节点（通过将节点的数据与搜索的数据进行比较），它就会返回该节点（以及因此连接在它下面的任何节点）。如果它没有找到它正在寻找的东西，它会返回NULL.

所以我的问题是，如果我们知道我们在寻找什么，我们为什么要寻找它？如果原因只是为了查看它是否包含在列表中，那么为什么布尔函数不“包含”我们真正想要的东西呢？

score 2 · Accepted Answer

一个节点可能包含比您要搜索的值更多的信息。想象一个模拟文件系统的列表。您按名称搜索文件，但您返回的节点可能包含文件名、文件大小、上次修改时间、文件所有者、访问权限和其他数据。

score 1 · Accepted Answer

通常，人们会搜索一个节点以对其进行处理。也许您想在现有节点中设置一个新值，删除该节点之后的所有内容，或者在该节点之后插入一些内容。如果您在列表中保持特定顺序，则搜索功能的语义可能会扩展为查找大于某个值的第一项，等等。

score 0 · Accepted Answer

有时，您需要该特定节点进行某些操作。请记住，节点本身及其内容是两个不同的逻辑实体。

score 0 · Accepted Answer

一个布尔函数“包含”可能就是我们想要的。如果我们想搜索一些我们没有但我们确实有标识号的数据集怎么办？

尝试将教科书中的示例视为一般示例。搜索布尔值和搜索基于其他值的记录都执行相同的操作，只是输出不同。

score 0 · Accepted Answer

考虑一个简单的例子......

你编写了一个程序，询问人们的年龄（以年为单位）并将他们存储在一个列表中，然后显示一个直方图（每个年龄有多少人），或者它可能显示过去一年有多少人年满 21 .

在这样的程序中，您可能事先不知道列表中最终会出现什么。这就是你搜索它的原因。

score 0 · Accepted Answer

链表结构的唯一入口是head节点。要到达列表中的特定节点，您必须遍历head节点到下一个节点，到下一个节点，......最后到目标节点，因此进行搜索。所以contains会做同样的事情 - 搜索equals你正在寻找的节点的节点。

6 回答 6