c++ - "Guessing"从双向链表的哪一侧开始

Question

有点难以解释我的计划，但就是这样。我有一个双向链接的对象列表，这些对象按名为 name 的成员属性的字母顺序排序。我希望删除一个具有特定名称的节点，但我希望以这样一种方式删除它，即它更有可能在靠近它的列表一侧开始寻找它。

所以我想我必须找到第一个节点的 name 和最后一个节点的 name 之间的“中点”。然后我将检查该中点是否小于节点的名称。如果少，我就从尾部开始，否则我就从头开始。

我遇到的问题是我无法将字符串直接转换为 int。我的潜在解决方案是:

1. 将头部和尾部的每个单独字符转换为 int
2. 将每次转换放入一个int数组，一个数组为头，一个为尾
3. 将每个int再次转换成字符串，放入一个新的数组
4. 如果每个转换后的字符串长度小于 3，则通过在其中插入 0 来使它们的长度为 3
5. 将每个数组中的字符串相加
6. 再次将字符串转换为 int，找出两个 int 之间的差异并将其除以 2
7. 将新值添加到第一个节点的转换名称
8. 查找这个“中点”是否小于我要删除的节点的名称
9. 如果是，从尾部开始搜索
10. 否则，从头开始搜索

有没有更简单的方法可以做到这一点？

Answer 1

Alf 的评论实际上就是您想要的。为了决定在哪一端，您只需找到第一个不同的字符，然后根据中点进行选择，即可获得最大分辨率。

算法思路

list = ["apple", "banana", "orange"]
word_to_search_for = ["banana"]

index = 0
while list[0][index] == list[last][index]:
    if word_to_search_for[index] != list[0][index]:
        return "word not in list"
    ++index

spread = list[last][index] - list[0][index]
if (word_to_search_for[index] - list[0][index])> spread/2:
    start at last
else:
    start at 0