python中的链表和递归

Question

我是编程新手，从Python开始。我的问题是关于链表，我为链表写了一个类，我需要做的是有一个函数，一个输入作为指向列表头部的引用。据我所知，'linked_list.Head'，其中linked_list是有问题的列表的名称。具体使用递归，我试图找到列表的长度作为这个函数的输出。下面是我的代码，我不太明白如何移动到下一个节点，并在本例中使用递归返回节点数。

import re
def special_match(strg, search=re.compile(r'[^A-Za-z.]').search):
    return not bool(search(strg))

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

    def get_data(self):
        return self.data

    def set_data(self,value):
        self.data = value

    def get_next_node(self):
        return self.next

    def set_next_node(self,val):
        self.next = val

class linked_list:

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

    def add_first(self,e):
        newest = node(e,None)
        newest.next = self.head
        self.head = newest
        self.size = self.size+1
        if self.size == 1:
            self.tail = newest

    def add_last(self,e):
        newest = node(e,None)
        if self.size > 0:
            self.tail.next = newest
        else:
            self.head = newest
        self.tail = newest
        self.size = self.size+1

    def remove_first(self):
        if self.size == 0:
            print('The linked list is empty')
        elif self.size == 1:
            answer = self.head.data
            self.head = None
            self.tail = None
            self.size -= 1
            return answer
        else:
            answer = self.head.data
            self.head = self.head.next
            self.size = self.size - 1
            return answer

    def remove_last(self):
        if self.size == 0:
            print('The linked list is empty')
        elif self.size == 1:
            answer = self.tail.data
            self.head = None
            self.tail = None
            self.size -= 1
            return answer
        else:
            temp  = self.head
            while(temp.next is not None):
                temp = temp.next
            temp.next = None


    def node_number(self,reference):
        reference = str(reference)
        count = 0
        temp = self.head
        if special_match(reference) == True:
            count =+ 1
            temp = temp.next
            return self.node_number  
        else:
            print('You have made wrong input')

    def printe(self):
        curr = self.head
        while curr:
            print(curr.data)
            curr = curr.get_next_node()
        if self.size == 0:
            print('The list is empty')

Answer 1

递归是函数式的遗产，因此将它与函数式一起使用将产生最好的结果。在您的程序中，您已经使用命令样式的可变节点实现了一个链表，也就是说，data和next的值可以随着时间的推移而改变。虽然这可能感觉像是一种直观的方法，但我想集中讨论一个不变的实现，它将我们从严重的状态复杂性中解放出来。在这个答案中，我们将使用函数样式表示的递归形式实现所有链表函数。

我们从简单的node和Linked_List类开始。这一次，我们跳过创建get_*和set_*函数的步骤。在Python中还有其他方法来完成这类事情，我们稍后会看到

class node:
  def __init__ (self, left, right):
    self.left = left
    self.right = right


class linked_list:
  def __init__ (self, node = None):
    self.node = node

接下来，我们为列表定义基本属性:is_empty、head和tail

class linked_list:
  def __init__ (self, node = None):
    self.node = node

  @property
  def is_empty (self):
    return self.node is None

  @property
  def head (self):
    if self.is_empty:
      raise Exception ("cannot get head of an empty list")
    else:
      return self.node.left

  @property
  def tail (self):
    if self.is_empty:
      raise Exception ("cannot get tail of an empty list")
    else:
      return self.node.right

class linked_list:
  ... 

  def length (self):
    if self.is_empty:
      return 0
    else:
      return 1 + self.tail.length ()

class linked_list:
  ... 

  def add_first (self, x):
    return linked_list (node (x, self))

  def __str__ (self):
    if self.is_empty:
      return "None"
    else:
      return str (self.head) + " -> " + str (self.tail)

ls = linked_list().add_first(3).add_first(2).add_first(1)
print (ls)
# 1 -> 2 -> 3 -> None

print (ls.length ())
# 3

ls = linked_list().add_first(3).add_first(2).add_first(1)
print (ls)
# 1 -> 2 -> 3 -> None

print (ls.add_first (0))
# 0 -> 1 -> 2 -> 3 -> None

print (ls)
# 1 -> 2 -> 3 -> None

class linked_list:
  ...

  @staticmethod
  def build (x = None, *rest):
    if x is None:
      return linked_list ()
    else:
      return linked_list (node (x, linked_list.build (*rest)))

print (linked_list.build (1,2,3))
# 1 -> 2 -> 3 -> None

class linked_list:
  ...

  def remove_first (self):
    if self.is_empty:
      raise Exception ("cannot remove first element of an empty list")
    else:
      return self.tail

  def remove_last (self):
    if self.is_empty:
      raise Exception ("cannot remove last element of an empty list")
    elif self.tail.is_empty:
      return self.tail
    else:
      return linked_list (node (self.head, self.tail.remove_last ()))

ls = linked_list.build (1,2,3)
print (ls)
# 1 -> 2 -> 3 -> None

print (ls.remove_first ())
# 2 -> 3 -> None

print (ls.remove_last ())
# 1 -> 2 -> None

print (ls)
# 1 -> 2 -> 3 -> None

class linked_list:
  ...

  def node_number (self, index = 0):
    if self.is_empty:
      raise Exception ("index out of bounds")
    elif index is 0:
      return self.head
    else:
      return self.tail.node_number (index - 1)

ls = linked_list.build ("a", "b", "c")

print (ls.node_number (0))
# "a"

print (ls.node_number (1))
# "b"

print (ls.node_number (10))
# Exception: index out of bounds

class linked_list:
  ...

  def add_last (self, x):
    if self.is_empty:
      return self.add_first (x)
    else:
      return linked_list (node (self.head, self.tail.add_last (x)))

ls = linked_list.build (1, 2, 3)
print (ls)
# 1 -> 2 -> 3 -> None

print (ls.add_last (4))
# 1 -> 2 -> 3 -> 4 -> None

print (ls)
# 1 -> 2 -> 3 -> None

完整的程序演示在repl.it