插入到有序链表 Python 中并对重复项求和

Question

我正在尝试将项目对(字母，频率(插入有序链表中。 到目前为止，我能够创建排序的链表，但是如果一个字母出现两次，我无法弄清楚如何更新频率并重新排列列表。

到目前为止，我有：

def add(self, letter, frequency):
    temp = Frequency(letter, frequency)
    curr = self.head
    prev = None
    stop = False
    while curr != None and not stop:
        if curr.frequency < temp.frequency:
            stop = True
        else:
            prev = curr
            curr = curr.next
    if prev == None:
        temp.set_next(self.head)
        self.head = temp
    else:
        temp.set_next(curr)
        prev.set_next(temp)
f = SortedFrequencyList()
f.add('a', 3)
f.add('b', 5)
f.add('g' 1)

返回

({b: 5}, {a: 3}, {g: 1})

但如果我要做

f = SortedFrequencyList()
f.add('a', 3)
f.add('b', 5)
f.add('g', 1)
f.add('a', 3)

我得到

({b: 5}, {a: 3}, {a: 3}, {g: 1})

而不是

({a: 6}, {b: 5}, {g: 1})

Answer 1

我们无法在

编码帮助方面做太多事情，因为您还没有发布您的支持代码：我们没有足够的资源来重现问题。 您也没有给我们任何编码尝试。

您需要建立更多的链接列表支持。 到目前为止，您只有一个在列表中插入新条目的方法。 我建议您编写一个按名称(字母(查找现有元素的 find 方法，以及一个将查找它、增加频率并将其排序回列表的更新。

执行更新的构建块方法是编写删除例程。 找到该项目，保留副本，将其从列表中删除，然后添加具有更新频率的新项目。

更好的更新方法是在一个例程中执行删除和重新插入，备份列表。 这表明要么是递归记忆，要么是双向链表。 一种更快的方法是实现某种索引树结构，以便搜索更快。

这会让你朝着正确的方向前进吗？