Python中的單個鏈接列表搜索

我想搜索鏈接列表中的值/字符並返回值/字符在鏈接列表中的次數。如果我只是使用遞歸而不是尾遞歸，這也會更容易嗎？Python中的單個鏈接列表搜索

class MyList(): 
    __slots__=('head','size') 

class Empty(): 
    __slots__=() 

class NonEmpty(): 
    __slots__=('data','next') 

def mkMyList(): 
    lst = MyList() 
    lst.head = mkEmpty() 
    lst.size = 0 
    return lst 

def mkEmpty(): 
    return Empty() 

def mkNonEmpty(data,lst): 
    node = NonEmpty() 
    node.data = data 
    node.next = lst 
    return node 

def count(l, value, c = 0): 
    l = mkMyList() 
    if l.head != value: 
     l.head = l.head.next 
    if l.head == value: 
     return count(l.head.next, value, c + 1) 
    if l.size == 0: 
     return c

當我嘗試測試它，我得到這個：

count(s,'s',c= 0) 
Traceback (most recent call last): 
    File "<pyshell#2>", line 1, in <module> 
    count(s,'s',c= 0) 
    File "C:\Users\Qasim\Desktop\Linked Lists.py", line 30, in count 
    l.head = l.head.next 
AttributeError: 'Empty' object has no attribute 'next'

來源

2014-04-05 user3404012

你可以發佈你的整個測試？ – BorrajaX

而不是使用遞歸，我會使用迭代器模式。這裏是做在你的問題的情況下的一種方法：

class LinkedList(object): 

    class Node(object): 
     __slots__ = ('prev', 'next', 'value') 

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

    def __init__(self, iterable=[]): 
     self.head = LinkedList.Node() # dummy node 
     self.tail = self.head 
     self.size = 0 
     for item in iterable: 
      self.append(item) 

    def __iter__(self): 
     current = self.head 
     while True: 
      if current.next is not None: 
       current = current.next 
       yield current.value 
      else: 
       raise StopIteration 

    def append(self, value): 
     self.tail.next = LinkedList.Node(prev=self.tail, value=value) 
     self.tail = self.tail.next 
     self.size += 1 

    def pop(self): 
     if self.size > 0: 
      value = self.tail.value 
      self.tail = self.tail.prev 
      self.tail.next = None 
      self.size -= 1 
      return value 
     else: 
      raise IndexError('pop from empty list') 

    def count(self, value): 
     cumsum = 0 
     for item in self: 
      if item == value: 
       cumsum += 1 
     return cumsum

通過我的定義Python special method__iter__，可以順序訪問一個LinkedList在以下方式中的元素：

l = LinkedList([1, 2, 3, 3, 3, 4, 5]) 
for value in l: 
    print(value)

這然後使期望的方法count直接實施。

請注意，我已經使用Python生成器語法來實現__iter__，您可以閱讀關於生成器和yield語句here。

來源

2014-04-05 19:32:04 jstarr

跟蹤代碼：

l = mkMyList() # => head = Empty() 
if l.head != value: # True since head is Empty() 
    l.head = l.head.next # Empty does not have a ".next" attribute

這就是回溯告訴你的。編輯：另外兩件事：（1）我不知道爲什麼計數甚至調用mkMyList時，似乎你的意圖是要通過它列表，l，在函數參數。（2）我猜你想放的尺寸檢查if語句在這個函數的頂部：

if l.size == 0: 
    return c

來源

2014-04-05 17:07:33

我看到的問題是，在count列表中從來沒有正確初始化。在mkMyList()中，head元素設置爲和Empty，它沒有next屬性。在count()中，您只能使用mkMyList()。這意味着l.head是Empty，並且它不可能具有next屬性。爲了解決這個問題，我建議使用給定的輸入實例化列表l。

關於遞歸問題：不，在構成尾遞歸函數和定期遞歸函數方面幾乎沒有什麼區別。

來源

2014-04-05 17:11:01

Python中的單個鏈接列表搜索

回答

相關問題