Связанные списки и рекурсия в python

Я новичок в программировании и начинаю в 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')
3 2
python recursion linked-list

3 ответа:

Рекурсия-это функциональное наследие, и поэтому использование ее с функциональным стилем даст наилучшие результаты. В вашей программе реализован связанный список с использованием императивного стиляизменяемых узлов - то есть значения 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

Теперь использование node полностью абстрагировано, и мы можем написать список более высокого уровня поведение с помощью наших новых свойств 

class linked_list:
  ... 

  def length (self):
    if self.is_empty:
      return 0
    else:
      return 1 + self.tail.length ()
Выше мы видим, что очень легко говорить о нашем списке через использование его свойств. Прежде чем мы пойдем дальше, давайте посмотрим, как мы можем построить списки и визуализировать их с помощью print. Для преобразования объекта в строку мы используем __str__ 
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

Помните, поскольку мы построили неизменяемый связанный список, add_first не изменяет список, который был вызван 

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

Прежде чем мы двинемся дальше, давайте сделаем это проще. постройте наши связанные списки. Мы добавляем статический build функция, которая позволяет нам построить список из переменного числа входов 

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
Теперь давайте посмотрим на ваши функции remove_first и remove_last теперь 
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

И node_number 

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

И A add_last халява 

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

1

Я бы установил его там, где функция длины на самом деле является частью класса Node, а не Класса Linked_List. Класс Linked_List также будет иметь функцию length, но все, что он будет делать, - это вызывать функцию length узла head списка.

Тогда каждый узел просто вернет length своего экземпляра next плюс 1.

1

Рекурсия должна иметь базовый случай, в котором код проверяет, является ли атрибут next None. Если да, то функция возвращает текущий счетчик. Если нет, счетчик увеличивается и функция length вызывается как метод атрибута next, чтобы иметь возможность продолжить прогрессию рекурсии по ссылкам, которые могут быть записаны как: 

|val1|pointer| -> |val2|pointer| -> |val3|pointer| -> |val4|pointer| -> |val5|None|

Во-первых, Ниже приведена более простая конструкция класса связанного списка для демонстрации: 

class Node:
   def __init__(self, val=None):
      self.head = val
      self.next = None 
   def length(self, count = 0):
      if self.next is None:
         return count + 1 if self.next is None and self.head else count
      return self.next.length(count + 1)
   def insert(self, v):
      if self.head is None:
         self.head = v
      else:
         if self.next is None:
           self.next = Node(v)
         else:
           self.next.insert(v)
   @classmethod
   def regular_transform(cls, node, nodes = []):
      '''for easier visulization'''
      return nodes+[node.head] if not node.next else cls.regular_transform(node.next, nodes+[node.head])

n = Node()
for i in [56, 232, 424, 2, 11]:
  n.insert(i)
print(Node.regular_transform(n))
print(n.length())

Вывод: 

[56, 232, 424, 2, 11]
5
0