时间戳

首页 > 解决方案 > 如何将我的第一个节点的 prev 设置为我的最后一个节点的下一个以创建循环双向链表？

python - 如何将我的第一个节点的 prev 设置为我的最后一个节点的下一个以创建循环双向链表？

问题描述

我正在使用循环双向链表创建约瑟夫斯问题。我收到一个属性错误，我认为这是因为我的 current_node（第一个节点）还没有 .prev。

我知道我的第一个节点的 prev 应该指向我的最后一个节点的下一个以创建循环双向链表。

有人可以指导我是否正确识别错误？如果是，我该如何纠正？

如果不是，那么我可以纠正错误的其他方法是什么？

#Initialize the node
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None
        
    def remove(self, n):
        print("Student " +str(n)+ " was removed")
        
class Circle:
# Initializing the DLL
    def __init__(self):
        self.head = None
        self.tail = None
#Inserting elements 2 to n in the dll              
    def insert_after(self, x, data):          
        y = Student(data) # make a new Node object.
        z = Student(data)
        z = x.next
        
        y.prev = x
        y.next = z
        x.next = y
        
        z.prev = y       
    
    def josephus_solution(self, dllist, n, k):
            no_of_active_nodes = n
            current_node = Student(1)
            #last_node = Student(n)
            #print(current_node.prev)
            for i in range(2, n + 1):
                dllist.insert_after(current_node, i)
                count = 0
            #print(current_node.data)
            while (current_node.next != current_node.prev):
                #print(current_node.next.prev)
                current_node = current_node.next
                count += 1
                #print(current_node.data)
                if (count == k):
                    current_node.remove(current_node.data)
                    current_node.prev.next = current_node.next
                    current_node.next.prev = current_node.prev
                    count = 0 
                    no_of_active_nodes -= 1
                    #print(no_of_active_nodes)
                if (no_of_active_nodes == 1):
                    print("Student" + str(current_node.data) + "Recieves the scholarship")
            return current_node.data

dllist = Circle()
n = 5 #int(input('Input number of people (n): '))
k = 2 #int(input('The nth person will be executed. Input k: '))
ans = dllist.josephus_solution(dllist, n, k)

错误

---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
/tmp/ipykernel_24/3762059582.py in <module>
     54 n = 5 #int(input('Input number of people (n): '))
     55 k = 2 #int(input('The nth person will be executed. Input k: '))
---> 56 ans = dllist.josephus_solution(dllist, n, k)

/tmp/ipykernel_24/3762059582.py in josephus_solution(self, dllist, n, k)
     32             #print(current_node.prev)
     33             for i in range(2, n + 1):
---> 34                 dllist.insert_after(current_node, i)
     35                 count = 0
     36             #print(current_node.data)

/tmp/ipykernel_24/3762059582.py in insert_after(self, x, data)
     24         x.next = y
     25 
---> 26         z.prev = y
     27 
     28     def josephus_solution(self, dllist, n, k):

AttributeError: 'NoneType' object has no attribute 'prev'

标签： pythonlinked-listdoubly-linked-listcircular-listjosephus

解决方案

错误的直接原因z是None，您的代码因此无法访问prev该行中的任何属性z.prev = y。原因是当第一个节点被创建时，它的prev和next属性被初始化为None，并且当这个节点作为x参数传递给 时insert_after，然后z = x.next一个None值被分配给z。

您的方法有几个问题：

  • insert_after调用两次是没有意义的Student，因为你想插入一个节点，而不是两个
  • 尽管您的Circle类具有 ahead和 atail属性，但它们在初始化为 之后从未使用过None，因此 Circle 实例中实际上没有任何内容可以帮助您维护列表。Student您不妨在类上定义所有方法。
  • 中的while条件josephus_solution可能是为了测试列表中只剩下一个节点，但它实际上验证是否还剩下两个。诚然，当current_node是刚刚被删除的节点，但是返回的数据是被删除节点的数据而不是剩余的活动节点，并且current_node不是刚刚删除的节点时，这个条件会导致循环退出它仍然有两个活动节点。

其他一些评论：

  • 当您josephus_solution作为方法调用时，不必也将实例作为参数传递。self已经可用于该方法
  • 我会将节点的创建拆分为一个单独的通用方法，并让我们josephus_solution处理现有的链表。
  • 就像在循环列表中一样，任何next或prev属性都不应该是None，当将它们初始化为self而不是None.
  • 该remove方法不应该负责打印消息，但另一方面应该负责重新连接prev和next引用。无论如何，这个方法不需要获取参数，因为它通过self.
  • 在原始约瑟夫斯问题中，第一个节点编号为 1，因此当 k=2 时，要删除的第一个节点是编号为 2 的节点。您的代码将首先删除编号为 3 的节点。要与原始问题保持一致，请移动该current_node = current_node.next语句将成为循环体中的最后一行。这也有助于确保在评估条件current_node时它永远不是刚刚删除的节点。while
  • 由于您的while条件已经考虑到何时停止，因此没有理由跟踪no_of_active_nodes变量。

还有很多话要说，但我认为这些是最重要的。

考虑到上述所有因素，这是对您的代码的更正：

class Student:
    def __init__(self, data):
        self.data = data
        # Better make prev/next self references to avoid None:
        self.next = self
        self.prev = self
        
    def remove(self):
        # Perform the remove here
        self.prev.next = self.next
        self.next.prev = self.prev
        
    def insert(self, data):          
        # Should only create one node, not two
        node = Student(data)
        node.next = self
        node.prev = self.prev
        self.prev = node.prev.next = node

    # Handy method to create a circular list from values
    @classmethod
    def fromiterator(cls, iterator):
        head = cls(next(iterator))
        for value in iterator:
            head.insert(value)
        return head

    def josephus_solution(self, k):
        count = 0
        current_node = self
        while current_node.next is not current_node:  # This is how to test for 1 node
            count += 1
            if count == k:
                current_node.remove()  # No argument
                print("Student " +str(current_node.data) + " was removed")
                count = 0
            current_node = current_node.next # do this at the end of the iteration
            # No need to keep track of active nodes ...
        return current_node

# These are the parameters of the "original" problem (see Wikipedia)
n = 41
k = 3
dllist = Student.fromiterator(iter(range(1, n+1)))
# Don't pass the list as argument: it already is available as `self`
dllist = dllist.josephus_solution(k)
# Perform output in the main code, not inside method
print("Student " + str(dllist.data) + " recieves the scholarship")

推荐阅读