Python 中的双向链表

Question

嘿伙计们，我真的很迷路。我正在为我的数据结构类编写一个双向链表程序，但我无法弄清楚。

更新：所以我完成了我的单链表作业。如何将其转换为双向链表，并使用提供的数据加载和打印？

目的

程序规格：

1. 从控制台读取 15 人的姓名和权重数据，其中一行上有一个名字，下一行上有一个权重， 就像名字一样.txt。

2. 您的程序将通过双向链表根据名称和权重为按升序维护的数据构建一个列表。

3. 此 dll 将使用一个指针将权重保持在排序顺序，并使用另一个链接将名称保持排序顺序。

4. 您需要在维护此排序时构建列表，因此在任何时候调用打印方法时，它都会打印相关字段 挨次。（这意味着节点按排序顺序添加到列表中， 元素不会添加到列表中，后跟在 列表。

例如，在为 （名称 – 重量） 添加 3 个元素后：迈克尔 – 275，汤姆 – 150，安倍 – 200。

输出：按名称排序（升序）的名称和权重：Abe – 200， 迈克尔 - 275，汤姆 - 150 姓名和重量按重量排序（升序）。 ： 汤姆 – 150， 安倍 – 200， 迈克尔 – 275

我要去的一小段代码

class LinkedList(object):
    __slots__ = 'prev', 'next', 'value'
ll1 = LinkedList()
ll2 = LinkedList()
if __name__=="__main__":
  f = open("Names.txt","r")
  ll1.value = f.readline()
  ll1.next = ll2
  ll1.prev = None

  ll2.value = f.readline()
  ll2.next = None
  ll2.prev = ll1
  f.close()
  print("Linearly: n")
  print(ll1.value)
  print(ll1.next.value)
  print("Reversely: n")
  print(ll2.value)
  print(ll2.prev.value)

我的单链表（排序）程序

#!/usr/bin/env python
class Node:
  def __init__(self):
    self.data = None
    self.next = None
class LinkedList:
  def __init__(self):
    self.head = None
  def addNode(self, data):
    curr = self.head
    if curr is None:
      n = Node()
      n.data = data
      self.head = n
      return
    if curr.data > data:
      n = Node()
      n.data = data
      n.next = curr
      self.head = n
      return
    while curr.next is not None:
      if curr.next.data > data:
        break
      curr = curr.next
    n = Node()
    n.data = data
    n.next = curr.next
    curr.next = n
    return
  def __str__(self):
    data = []
    curr = self.head
    while curr is not None:
      data.append(curr.data)
      curr = curr.next
    return "[%s]" %(', '.join(str(i) for i in data))
  def __repr__(self):
    return self.__str__()
if __name__=="__main__":
  ll = LinkedList()
  num = int(input("Enter a number: "))
  while num != -1:
    ll.addNode(num)
    num = int(input("Enter a number: "))
  c = ll.head
  while c is not None:
    print(c.data)
    c = c.next

数据：名称.txt

Jim
150
Tom
212
Michael
174
Abe
199
Richard
200
April
117
Claire
124
Bobby
109
Bob
156
Kevin
145
Jason
182
Brian
150
Chris
175
Steven
164
Annabelle
99

正如你所看到的，我没有做太多。我不确定如何正确加载数据，我只是总体上迷失了。我不知道从哪里开始。我在网上看了几个例子，但它们对我来说很神秘。

提前感谢您的任何帮助。我非常感谢。

Answer 1

鉴于问题定义指定了"指针"，python 不是实现这一点的合适语言。但是你可以使用 python 变量作为"指针"（或者更确切地说是引用），因为它们就是这样;python变量只是对象的名称或引用。

但是如果你想用python实现，我会使用一个列表ot元组。

第一个是（名称、权重）元组的列表。

In [1]: data = [("Michael", 275), ("Tom", 150), ("Abe", 200)]

此列表中的顺序无关紧要。只需在新元组到达时append新元组即可。

现在，最简单的方法是制作浅副本（引用相同的元组），并在打印它们之前对它们进行适当的排序;

In [2]: namelist = [d for d in data]
In [3]: namelist.sort(key=lambda x: x[0])
In [4]: namelist
Out[4]: [('Abe', 200), ('Michael', 275), ('Tom', 150)]

和

In [5]: weightlist = [d for d in data]
In [6]: weightlist.sort(key=lambda x: x[1])
In [7]: weightlist
Out[7]: [('Tom', 150), ('Abe', 200), ('Michael', 275)]

现在，以正确的顺序打印这些内容变得微不足道。

但这在练习中是明确禁止的。所以你要做的是这样的事情;

• 创建一个新的（name，weight）元组
• 浏览按权重排序的元组列表，并将新元组中的权重与现有元组中的权重进行比较（提示：使用 enumerate 以便获得列表中元组的索引）。一旦发现权重大于列出的元组的权重，请在权重排序列表中insert新元组。
• 与名称排序列表类似，但随后使用该名称作为比较值。

像这样的东西;

In [10]: newvalue = ("Eric", 225)
In [11]: for index, (name, weight) in enumerate(weightlist):
   ....:     if newvalue[1] < weight:
   ....:         weightlist.insert(index, newvalue)
   ....:         break
   ....:     
In [12]: weightlist
Out[12]: [('Tom', 150), ('Abe', 200), ('Eric', 225), ('Michael', 275)]

请注意，此算法假定weightlist已经按排序顺序排列！

---

另一个更符合任务的解决方案是为每个人使用字典;

In [37]: newvalue = {"name": "Eric", "weight": 225, "nextname": None, "nextweight": None}

您还需要data列表来保存所有词典。您将需要两个变量startname和startweight分别保存名字和最低权重。

在你做了一个newvalue之后，你首先将newvalue["weight"]与startweight["weight"]进行比较。如果新权重小于起始权重，则newvalue将成为新startweight，并且newvalue["nextweight"]应设置为旧的起始权重。如果没有，则移至列表中的下一项并再次进行比较。请注意，如果要插入链中，则必须更改两个nextweight属性！

这是一个双单链表。从startweight和startname开始，您可以通过走两条链来按顺序打印两者。

Answer 2

这是我的做法。 我建议您创建一个新问题或搜索如何从文本文件中读取数据。

class Node:
  def __init__(self, name, weight):
    self.name = name
    self.weight = weight
    self.prev_name = None
    self.next_name = None
    self.prev_weight = None
    self.next_weight = None

class DLL:
  def __init__(self):
    self.head = Node(None, None)
    self.tail = Node(None, None)
    self.head.next_name = self.tail
    self.head.next_weight = self.tail
    self.tail.prev_name = self.head
    self.tail.prev_weight = self.head
  def add(self, name, weight):
    node = Node(name, weight)
    # add by name
    p = self.head
    while (p.next_name != self.tail) and (p.next_name.name < name):
      p = p.next_name
    node.next_name = p.next_name
    node.prev_name = p
    p.next_name = node
    node.next_name.prev_name = node
    # add by weight
    p = self.head
    while (p.next_weight != self.tail) and (p.next_weight.weight < weight):
      p = p.next_weight
    node.next_weight = p.next_weight
    node.prev_weight = p
    p.next_weight = node
    node.next_weight.prev_weight = node
  def printByName(self):
    p = self.head
    while p.next_name != self.tail:
      print(p.next_name.name, p.next_name.weight)
      p = p.next_name
  def printByWeight(self):
    p = self.head
    while p.next_weight != self.tail:
      print(p.next_weight.name, p.next_weight.weight)
      p = p.next_weight
    return

和一些结果：

D = DLL()
D.add("Jim",150)
D.add("Tom",212)
D.add("Michael",174)
D.add("Abe",199)
D.printByName()
  Abe 199
  Jim 150
  Michael 174
  Tom 212
D.printByWeight()
  Jim 150
  Michael 174
  Abe 199
  Tom 212