如何使用 Python 正确实例化 MultiSet（我自己创建的）

Question

我想学习数据结构，所以我决定使用 Python 创建它们。我首先创建了一个单链表（由两个 class 组成：实际列表和节点）。列表由节点组成（或者可以为空）。每个节点都有一个“下一个”值。当我实例化一个列表时，它看起来像这样：

l = LinkedList([1,2])

这是 init 的 sudocode:

def __init__(self, item=None):
    head = None

    if a single item was given
        head = Node(item)
        head.next = None
    else if multiple items were given
        for i in item
            if head: # i is not the first item in the list
                new_head = Node(i)
                new_head.next = head
                head = new_head
            else: # i is the first item in the list
                head = Node(i)
                head.next = None

也许上面的逻辑有缺陷，但希望你能或多或少地理解它是如何工作的。我在这里注意到的关键是我没有使用任何列表 ([]) 或数组 ({})，因为我不需要。

现在，我正在尝试创建一个 MultiSet，但我卡在了 init 部分。 Linked List 很简单，因为我看 Linked List 的文章时，所有的文章都立即提到了一个 List class 和一个 Node class （一个 List 由一个 Node 组成。一个 List 有一个 head和尾巴。一个节点有一个 'next' 值）。但是当我阅读有关 MultiSets 的文章时，他们只是提到 multisets 是允许相同数据的多个实例的数据集（或包）。

到目前为止，这是我的多重集的 init：

def __init__(self, items=None):
    self.multiset = []
    if items: # if items is not None
        try:
            for i in items: # iterate through multiple items (assuming items is a list of items)
                self.multiset.append(i)
        except: # items is only one item
            self.multiset.append(items)

我不认为我走在正确的轨道上，因为我使用的是 Python 列表 ([]) 而不是实现我自己的列表（就像我使用节点对链表所做的那样， list.head、list.tail 和 node.next).

有人可以指出我如何使用 Python（不使用现有的 Python 列表/数组）创建和实例化我自己的 MultiSet 的正确方向吗？还是我已经在正确的轨道上，我是否应该在创建自己的 MultiSet 数据结构时使用 Python 列表/数组？

Answer 1

您似乎将两件事混为一谈：

数据结构——使用Python（或任何其他语言，基本上），你可以实现链表、平衡树、哈希表等
映射语义 - 任何容器，尤其是关联容器，都有一个协议：当您插入一个已经在其中的键时，它会做什么？它是否具有使用给定密钥访问所有项目的操作？等等

因此，根据您的链表，您当然可以实现多重集（尽管性能不佳），因为这主要取决于您的决定。一种可能的方法是：

插入后，使用键追加一个新节点
对于查找，遍历节点； return 您找到的第一个密钥，或者 None 如果没有
对于 find_all，遍历节点，return 一个列表（或你自己的链表），所有匹配它的键.

同样，链表本身并没有规定您是否必须将它用作集合或字典（或其他任何东西）。这些是正交决策。

如何使用 Python 正确实例化 MultiSet（我自己创建的）

How to properly instantiate a MultiSet (created on my own) using Python

python

data-structures

multiset