1

Node と LinkedList の 2 つのクラスを持つ単一リンク リストは、簡単に実装できます。ただし、私の問題は、最初のノード アクセスのみ (保存された長さなし、最後のノード アクセスなし、ダミー ノードを使用しない) の単一リンク リストの場合です。私が頭を抱えたり、オンラインについて多くを見つけることができない特別なメソッドは、次のような O(1) の複雑さを持つ python の組み込みリスト操作に似ています。

aa = LinkedList()  --  creates empty list
aa.first()  --  similar to aa[0]
aa.rest()  --  similar to aa[1:]
aa.cons(item)  --  similar to aa[item:]
[item] + aa  --  similar to aa.insert(0, item)

あらゆる種類のリード、ヘルプ、ガイダンスをいただければ幸いです。何らかの理由で、ダミーノードまたは格納された長さとイテレータなしで、Python の組み込みリスト演算子を LinkedList の独自のメソッドに解釈することはできません。それを見ると、私はとても近くにいるように見えますが、私が行ったり見つけたりすることは何も役に立たないようです. ありがとうございました。

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

  def getData(self):
    return self.data

  def getNext(self):
    return self.next

  def setData(self, newdata):
    self.data = newdata

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

  def __str__(self):
    return str(self.data)

  def __repr__(self):
    return "Node(%s, %s)" % (repr(self.data), repr(self.next))

  def __eq__(self, other):
    return self.data == other.data and self.next == other.next

class myList:
  def __init__(self):
    self.first = Node()

  def add(self, data):
    newNode = Node() # create a new node
    newNode.data = data
    newNode.next = self.first # link the new node to the 'previous' node.
    self.first = newNode #  set the current node to the new one

  def first(self):
    return self.first.data


  def __repr__(self):
    plist = []
    for i in self:
        plist.append(i)
    return "LinkedList(%s)" % str(plist)
4

2 に答える 2

1

あなたのコードを見なくても、私が与えることができる基本的なヒントは、Linked List ベースの操作を行っている場合、多くの反復が必要になるということだと思います。aa.cons(item)配列ベースのリストとは異なり、特定のインデックスの項目にジャンプできないため、次のようなものを使用すると非効率的で反復に基づいてしまいます。

次の例では、リストの最初の項目を指すLinkedListという変数がクラスにあり、それぞれにリストの次の項目を指す という変数と、データを保持するという変数があると仮定します。そのノード。firstNodenextdata

の場合、最初の項目を指すaa.first()変数が既にあるので、これは簡単なはずです。headそれを返すだけです。

他の方法については、繰り返しが必要です。これは、リストをループして印刷する方法の例です。

current = list.first
while current is not None:
    print current.data
    current = current.next

の場合aa.rest()、最初の項目をスキップしてから、リストの残りをループする必要があります。リストの一歩を踏み出すには、基本的に現在の場所を追跡して繰り返します。list[1:] を返すには、新しいリストを作成してから、1 から最後までのすべての項目を追加して繰り返すのが最も簡単だと思います。

aa.rest()の特殊なケースですaa.cons(item)。現在のポインターが到達するまでリストを反復処理し、itemその後のすべてを含む新しいリストを作成します。

rest()andから返される新しいリストを必ずしも作成する必要はありませんcons(...)。実装方法によって異なります。私はあなたが考えるためにインサートを残しておきます.

LinkedListへのポインタしか持たない a では、headリストの先頭に追加するか最初の項目にアクセスする以外は O(1) を取得しません。それ以外はすべてほぼ O(N) になります。

それが少し役立つことを願っています！

于 2012-04-17T02:03:13.220 に答える
0

@sgusc は、これまでのところ、関数firstの名前付けとデータ属性の名前付けにも大きな問題があることを発見しましたfirst。後者は前者をオーバーライドしてしまいます (関数は実際にはclassインスタンスではなくにあるため)。

これを修正すると、動作に近いものが得られます。いくつかのことを単純化し、小さなテスト ドライバーを追加__iter__し、ジェネレーターを使用して各ノードのデータを順番に生成する を追加したので、for i in self(in myList.__repr__) が機能します。違い:

--- a/user1337598.py
+++ b/user1337598.py
@@ -1,4 +1,4 @@
-class Node:
+class Node(object):
   def __init__(self, data=None, next=None):
     self.data = data
     self.next = next
@@ -19,27 +19,36 @@ class Node:
     return str(self.data)

   def __repr__(self):
-    return "Node(%s, %s)" % (repr(self.data), repr(self.next))
+    return "Node(%r, %r)" % (self.data, self.next)

   def __eq__(self, other):
     return self.data == other.data and self.next == other.next

-class myList:
+class myList(object):
   def __init__(self):
-    self.first = Node()
+    self.first = None

   def add(self, data):
-    newNode = Node() # create a new node
-    newNode.data = data
-    newNode.next = self.first # link the new node to the 'previous' node.
+    newNode = Node(data, self.first) # create a new node
     self.first = newNode #  set the current node to the new one

-  def first(self):
+  def getFirst(self):
     return self.first.data

+  def __iter__(self):
+      node = self.first
+      while node is not None:
+          yield node.data
+          node = node.next

   def __repr__(self):
     plist = []
     for i in self:
         plist.append(i)
     return "LinkedList(%s)" % str(plist)
+
+if __name__ == '__main__':
+    lst = myList()
+    lst.add(1)
+    lst.add(2)
+    print repr(lst)

クラス名が であってもrepr、名前を使用することに注意してください。私は通常、使用する関数を作成します。たとえば、次のようになります。LinkedListmyListreprself.__class__.__name__

def __repr__(self):
    return '%s(%r, %r)' % (self.__class__.__name__, self.item1, self.item2)

これにより、基本クラス__repr__が派生クラスで機能することもできます (派生クラスからの少しの支援が必要な場合もあります)。

于 2012-04-17T04:41:24.863 に答える