2

循環単方向リストを作成しようとしています。1 人だけが好きなリストのコードを変更できるようにしたいのですが、問題があります。

リンクされたリストには、次のものがあります。

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


class LinkedList(object):
  def __init__(self):
    self.first = None

  def __str__(self):
    a = "["
    current = self.first
    while current != None:
      a += str(current.data) + ', ' 
      current = current.next
    a = a[:-2] + ']'  
    return a  

  def __iter__(self):
    current = self.first
    a = []
    while current != None:
      a += [current.data]
      current = current.next
    return iter(a)

  def __len__ (self):
    current = self.first
    a = []
    while current != None:
      a += [current.data]
      current = current.next
    return len(a)

  def InsertFirst(self, item):
    NewLink = Link(item, self.first)
    self.first = NewLink

  def InsertLast(self, item):
    NewLink = Link(item)
    current = self.first

    if current == None:
      self.first = NewLink  
      return 

    while current.next != None:
      current = current.next
    current.next = NewLink 

  def Search(self, item):
    count = 0
    current = self.first
    while current != None:
      count += 1
      if current.data == item:
        return count
      else:
        pass
        current = current.next
    return -1

  def Delete(self, item):
    current = self.first
    previous = self.first

    if (current == None):
      return None

    while (current.data != item):
      if (current.next == None):
        return None
      else:
        previous = current
        current = current.next

    if (current == self.first):
      self.first = self.first.next
    else:
      previous.next = current.next

    return current

これまでのところ、循環リストについては次のとおりです。

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


class CircularList(object):
  def __init__(self):
    self.first = Link(None, None)
    self.head = Link(None, self.first)

  def __str__(self):
    a = "["
    current = self.first
    while current != None:
      a += str(current.data) + ', ' 
      current = current.next
    a = a[:-2] + ']'  
    return a  

  def InsertLast(self, item):
    NewLink = Link(item)
    current = self.first

    if current == None:
      self.first = NewLink  
      return 

    while current.next != None:
      current = current.next
    current.next = Link(item)

私の質問は、横断できるように最後の要素を最初の要素にリンクするにはどうすればよいですか?

4

5 に答える 5

7

循環リンク リストのポイントは、「次が None でない場合」のロジックをすべてスキップすることです。先頭では、head はそれ自体を指しており、リストが空であることを示しています。空の「最初」を作成する必要はありません。最初に次のようにします。

self.head = Link(None, None)
self.head.next = self.head

次に、他のノードの後に​​ノードを挿入するには、次のようにします。

def insert_after(insert_node, after_node):
    insert_node.next = after_node.next
    after_node.next = insert_node

リストの先頭に挿入するには、次のようにします。

insert_after(node, head)

リストは単独でリンクされているだけなので、「前に」ノードを見つけるために繰り返し挿入する必要があります。

def insert_before(node, before_node):
    loc = head
    while loc.next is not before_node:
        loc = loc.next
    insert_after(insert_node, loc)

リストの最後に挿入するには、次のようにします。

insert_before(node, head)

リストのすべての要素を取得するには、次のようにします。

current = self.head.next
while current is not self.head:
    # do something with current.data

    # advance to next element
    current = current.next

しかし、循環リストの真の力は、それを二重にリンクすることです。そのため、反復せずに前に挿入できます。

于 2011-03-27T19:22:20.357 に答える
2

last.next =作成時に最初ですか？

class Link (object):
  def __init__ (self, data, next = None):
    self.data = data
    self.next = self.first

有効なコードではない可能性があります。ただし、作成時にリストの最後の部分にいることが保証されているので、そうすることもできます。

于 2011-03-27T19:02:18.180 に答える
0 
class cirlist(list):
    def __init__(self,*arg):
        super(cirlist,self).__init__(*arg)
        self.m=super(cirlist,self).__getitem__(0)
        self.Index=0
    def next(self):
        if self.Index>=super(cirlist,self).__len__()-1:
            self.m=super(cirlist,self).__getitem__(0)
        else:
            self.m=super(cirlist,self).__getitem__(self.Index+1)
        if self.Index>super(cirlist,self).__len__()-1:    
            self.Index=super(cirlist,self).index(self.m)+1
        else:
            self.Index=super(cirlist,self).index(self.m)
        return self.m
于 2015-07-20T11:12:06.813 に答える
0 
class Link (object):

def __init__(self, first=None, rest=None):
    self.first = first
    self.rest = rest
def get_data(self):
    return self.first
def get_next(self):
    return self.rest
def __getitem__(self, i):
    if i ==  0:
        return self.first
    get = self
    while i > 0:
        get = get.rest
        i -= 1
    if get == None:
        raise IndexError('The Sentence Index is Out of Range.')
    return get.first

クラス Circular_Link (オブジェクト):

def __init__(self, things):
    assert len(things) > 2
    last = Link(things[len(things)-1])
    first = Link(things[len(things)-2], last)
    index = len(things)-2
    while index > 0:
        index -= 1
        first = Link(things[index], first)
    last.rest = first
    self.circle = first
def __getitem__(self, i):
    return self.circle[i]

この例では、通常のリストから循環リストを初期化します。

于 2015-08-22T06:12:02.067 に答える