1

嘿伙计们，我真的迷路了。我正在为我的数据结构类编写一个双向链表程序，但我就是想不通。

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

客观的

节目规格：

  1. 从控制台读取 15 个人的姓名和体重数据，其中一行是姓名，下一行是体重，例如 names.txt。

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

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

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

例如，为（姓名 - 体重）添加 3 个元素后：Michael - 275、Tom - 150、Abe - 200。

输出：按名称排序（升序）的名称和权重。: Abe – 200, Michael – 275, Tom – 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

数据：Names.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

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

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

4

2 回答 2

2

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

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

第一个是 (name, weight) 元组的列表。

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"]newvaluestartweightnewvalue["nextweight"] nextweight

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

于 2015-01-03T23:08:42.903 回答
1

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

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
于 2015-01-03T18:53:05.523 回答