0

CLRSの本に従って、歩哨を持つリンクリストを作成しようとしています。私の削除機能は、何らかの理由で、削除するノードまでの LL のチャンクを削除します。添付は私のコードです。どんな提案でも大歓迎です。

class Node():
    def __init__(self,v):
        self.value = v
        self.next = None
        self.prev = None

    def getValue(self):
        return self.value

    def changeValue(self,v):
        self.value = v

    def getNext(self):
        return self.next

    def getPrev(self):
        return self.prev

    def setNext(self,newNext):
        self.next = newNext

    def setPrev(self,newPrev):
        self.prev = newPrev

class List(Node):
    def __init__(self):
        self.nil = Node(None)

    def addNode(self,v):
        a = Node(v)
        a.setNext(self.nil.next)
        a.setPrev(self.nil)
        self.nil.next = a

    def length(self):
        count = 0
        a = self.nil
        while(a.next != None):
            count += 1
            a = a.getNext()
        return count

    def search(self,v):
        a = self.nil
        while(a.next != None):
            if (a.value == v):
                return True
            a = a.getNext()
        return False

    def remove(self,v):
        a = self.nil.next
        breakloop = 0
        while((a.next != None) and (breakloop == 0)):
            if (a.value == v):
                a.prev.next = a.next
                a.next.prev = a.prev
                breakloop = 1
            a = a.getNext()

    def printList(self):
        a = self.nil.next
        while(a.next != None):
            print(a.value)
            a =a.getNext()
        print(a.value)


a = List()
a.addNode(4)
a.addNode(7)
a.addNode(2)
a.addNode(6)
a.addNode(5)
a.addNode(8)
a.addNode(1)
a.addNode(14)
a.addNode(13)
a.addNode(17)
a.addNode(18)
a.printList()
a.remove(13)
a.printList()

出力は
18 17 13 14 1 8 5 6 2 7 4
14 1 8 5 6 2 7 4 になります。

4

2 に答える 2

2

@tcaswell はコードの問題を正しく診断しました。以前は正しく設定prevされていたノードにリンクを設定していませself.nil.nextん。しかし、彼の解決策は理想的ではないと思います。代わりに私が提案するのは次のとおりです。

問題の即時修正は次のとおりです。

def addNode(self, v):
    a = Node(v)

    a.setNext(self.nil.next)
    self.nil.next.setPrev(a) # this is the link that was previously missing

    a.setPrev(self.nil)
    self.nil.setNext(a)

self.nil.nextただし、リストが最初にあるため、リストが空の場合は正しく機能しませんNone。ただし、コンストラクターself.nilで作成するときにそれ自体へのリンクを作成することで、これを修正できます。List

def __init__(self):
    self.nil = Node(None)
    self.nil.next = self.nil.prev = self.nil # set up circular links!

これで、self.nil常に有効なノードが値として保持されnextますprev。

ではなくfor をチェックするようにremoveNodeandループを変更する必要があります。printListself.nilNone

于 2013-02-16T05:11:58.163 に答える
1

バグはaddNode関数にあり、すべて.prevのノードのノードはself.nil

以下を使用します。

def addNode(self,v):
    a = Node(v)
    a.setNext(self.nil.next)
    if self.nil.next is not None:
        self.nil.next.setPrev(a)
    a.setPrev(self.nil)
    self.nil.next = a

あなたの問題を解決します。setPrevおそらく、このロジックをand関数に入れたいと思うでしょう(最後を除いて常にsetNext確実にするためa == a.next.prev) 。a == a.prev.nexta

于 2013-02-16T04:50:20.887 に答える