6

二重連結リストを作成していますが、 PYTHONで二重連結リスト反復子メソッドを作成するのに苦労しています。

これはこれまでの私のコードです

class DoubleListNode:
    def __init__(self,data):
        self.data=data
        self.prev = None
        self.next= None

class ListIterator:
    def __init__(self):
        self._current = self.head

    def __iter__(self):
        return self

    def next(self):
        if self.size == 0 :
            raise StopIteration
        else:
            item = self._current.data
            self._current=self._current.next
            return item

class DoublyLinkedList:
    def __init__(self):
        self.head= None
        self.tail= None
        self.size = 0

    def add(self,data):
        newnode= DoubleListNode(data)
        self.size+=1
        if self.head is None:
            self.head = newnode
            self.tail = self.head
        elif data < self.head.data: # before head
            newnode.next = self.head
            self.head.prev= newnode
            self.head= newnode
        elif data > self.tail.data: # at the end
            newnode.prev= self.tail
            self.tail.next= newnode
            self.tail=newnode
        else:
            curNode = self.head
            while curNode is not None and curNode.data < data:
                curNode=curNode.next            
            newnode.next= curNode
            newnode.prev=curNode.prev
            curNode.prev.next= newnode
            curNode.prev=newnode

    def remove(self,data):
        curNode=self.head
        while curNode is not None and curNode.data!= data:
            curNode= curNode.next
        if curNode is not None:
            self.size -= 1
            if curNode is self.head:
                self.head= curNode.next
            else:
                curNode.prev.next=curNode.next
            if curNode is self.tail:
                self.tail=curNode.prev
            else:
                curNode.next.prev=curNode.prev

テストを実行すると、 と表示されTypeError: iteration over non-sequenceました。私は何か間違ったことをしましたか？

4

4 に答える 4

4

投稿されたように、コードは初期化されません (つまり、self.headが定義されていません)。

しかし、全体として、あなたは正しい軌道に乗っています。Python のcollections.OrderedDictのソースを見て、双方向にリンクされたリストをトラバースする実際の例を確認してください。

簡単な例を次に示します。

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

    def __iter__(self):
        here = self
        while here:
            yield here.value
            here = here.next

    def __reversed__(self):
        here = self
        while here:
            yield here.value
            here = here.prev

if __name__ == '__main__':
    a = Link('raymond')
    b = Link('rachel', prev=a);  a.next=b
    c = Link('matthew', prev=b); b.next=c

    print 'Forwards:'
    for name in a:
        print name
    print
    print 'Backwards:'
    for name in reversed(c):
        print name
于 2013-03-29T20:30:36.110 に答える
2

修正すべき重要な点が 2 つあります。

まず、DoublyLinkedListクラスにメソッドがありません__iter__。ListIteratorおそらく、インスタンスを返すものを作成したいと思うでしょう。これを手動で行おうとしているのかもしれませんが、これが通常の方法です。

ListIterator次に、正しく動作するようにコードを修正する必要があります。現在、__init__メソッドは正しく初期化されておらず、メソッドは存在しないnextようなメンバー変数にアクセスしようとしsizeています。

うまくいくと思う実装は次のとおりです。

def ListIterator(object):
    def __init__(self, node):
        self.current = node

    def __iter__(self):
        return self

    def next(self):
        if self.current is None:
            raise StopIteration()

        result = self.current.data
        self.current = self.current.next

        return result

class DoublyLinkedList(object):

    # all your current stuff, plus:

    def __iter__(self):
        return ListIterator(self.head)

補足として、現在のコードでは、ベースのないクラスを定義しています。これは Python 3 では問題ありませんが (objectデフォルトでは がベースになります)、Python 2 では「古いスタイル」のクラスが取得されます。古いスタイルのクラスは推奨されておらず、一部の言語機能が適切に動作しないことがわかります (ただし、私の知る限り、反復に関連する機能はありません)。一方、既に Python 3 を使用している場合は、(アンダースコアなしで)__next__ではなく、反復子クラスでメソッドを定義する必要がありますnext。

于 2013-03-31T02:57:17.587 に答える
0

あなたが投稿した内容に基づいて、次のことをお勧めします。

class ListIterator:
    # other stuff ...
    def __iter__(self):
        while self._current:
            yield self._current.data
            self._current = self._current.next
        self._current = self.head # Reset the current pointer

next() を実装する必要はありません

アップデート

使用例を次に示します。

for data in myListIterator:
    print data

# Without reset, the second time around won't work:
for data in myListIterator:
    print data
于 2013-03-29T21:15:18.737 に答える