插入链表时获取频率计数

Question

为了这个单链表的实践，我创建了两个classes。我想在将新添加的单词添加到列表时计算它们的频率。但似乎每次函数运行时，它们的频率都只有 1？练习还指出我应该在节点 class.

中添加频率计数

class Node:
    def __init__(self, wordData, freq=1):
        self.next = None
        self.wordData = wordData
        self.freq = freq

class FreqLinkedList:
    def __init__(self):
        self.head = None


    def addWord(self, word):
        #appending
        new_node = Node(word)
        if self.head is None:
            self.head = new_node
            return

        current_node = self.head
        while current_node.next:
            current_node = current_node.next
        current_node.next = new_node


        while current_node.next is not None:
            if current_node.wordData == word:
                current_node.freq += 1
                current_node = current_node.next
            current_node.next = current_node.next
        return current_node.freq

    def printList(self):
        current_node = self.head
        while current_node is not None:
            print(current_node.wordData, current_node.freq)
            current_node = current_node.next

Answer 1

这里的问题是您正在创建频率为 1 的每个节点。当您遍历链表以更新频率时，您只需将它递增 1。因此，最早的条目将具有正确的计数，而每个后续条目的计数将比前一个条目少 1。检查以下代码段：

f = FreqLinkedList()
f.addWord("a")
f.addWord("a")
f.addWord("a")
f.addWord("a")
f.printList()

# output
# a 4
# a 3
# a 2
# a 1

修复当前设计

保持链表级别的频率。并使用它来创建新节点以及更新现有节点的频率。

from collections import Counter

class FreqLinkedList:
    def __init__(self):
        self.head = None
        self.freqs = Counter() # maintain freq of all words

    def addWord(self, word):

        # book keeping
        self.freqs.update([word]) # this will prevent splitting into characters
        current_word_freq = self.freqs.get(word)

        # appending
        if self.head is None:
            self.head = Node(word)
            return current_word_freq

        current_node = self.head
        while current_node.next:
            current_node = current_node.next
        current_node.next = Node(word, freq=current_word_freq) # freq != 1

        current_node = self.head
        while current_node.next is not None:
            if current_node.wordData == word:
                current_node.freq = current_word_freq # not freq += 1
            current_node = current_node.next
        return current_word_freq


# Test
f = FreqLinkedList()
f.addWord('a')
f.addWord('a')
f.addWord('a')
f.addWord('b')
f.addWord('b')
f.addWord('c')
f.addWord('d')
f.addWord('d')
f.printList()

# Output
# a 3
# a 3
# a 3
# b 2
# b 2
# c 1
# d 2
# d 2

但是，这种方法通常效率极低。

更好的设计

你不应该在 Node 中有频率。在链表中创建一个方法 get_freq 并像 FreqLinkedList().get_freq('a') 一样使用它：

def get_freq(self, word):
        return self.freqs.get(word)

插入链表时获取频率计数

Getting frequency count while inserting in linked list

python

linked-list

data-structures

python-3.x

singly-linked-list