Сторнирование одного связанного списка с помощью рекурсии - PullRequest
Новая
       35

Сторнирование одного связанного списка с помощью рекурсии

0 голосов
/ 12 сентября 2018

Я сделал функцию, которая переворачивает односвязный список, используя рекурсивный метод. Однако у меня возникли некоторые трудности при выполнении кода ниже: 

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

class linked_list:
    def __init__(self):
        self.head=node()

def append(self,data):
    new_node=node(data)
    cur_node=self.head
    while (cur_node.next!=None):
        cur_node=cur_node.next
    cur_node.next=new_node
    return cur_node.data

def display(self):
    elements=[]
    cur_node=self.head
    while(cur_node.next!=None):
        cur_node=cur_node.next
        elements.append(cur_node.data)
    print(elements)

def reverseRecursive(self,prev_code,cur_node):
    if cur_node.next!=None:
        reverseRecursive(cur_node,cur_node.next)
        cur_node.next=prev_node
    else:
        self.head=cur_node
    return
lst1=linked_list()
lst1.display()
lst1.append(1)
lst1.append(3)
lst1.append(5)
lst1.append(7)
lst1.display()
lst1.reverseRecursive(None,_____)
lst1.display()

Что я должен передать второй аргумент в функции / метода reverseRecursive, чтобы я мог его выполнить?

В качестве второго аргумента я хочу просто передать узел head связанного списка. Но я не знаю, как получить головной узел из метода init класса connected_list

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

1 Ответ

0 голосов
/ 12 сентября 2018

Связанный список является рекурсивной структурой, поэтому использование его с функциональным стилем даст наилучшие результаты. В вашей программе вы реализовали связанный список, используя процедурный стиль и изменяемые узлы - вы изменяете значения data и next с течением времени. Хотя это может показаться интуитивным подходом, я бы хотел сосредоточиться на неизменной дисциплине, которая освобождает нас от нанесения вреда сложности состояния.

Сначала мы исправим функцию конструктора node. Мы устанавливаем оба свойства при создании новых узлов, потому что они не изменятся позже в программе - 

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

Тогда linked_list - это просто один узел, построенный по определенному соглашению:

  • node.data удерживать данные узла
  • node.next это либо:
    • другой linked_list
    • или , None, обозначая конец списка

Начнем с конструктора для linked_list - 

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

  # ...

И реализуем is_empty, head и tail свойства для отвода node - 

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.data

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

Теперь использование 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 (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('A').add('B').add('C')
print (ls)
# C -> B -> A -> None

print (ls.length())
# 3

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

ls = linked_list().add('A').add('B').add('C')
print (ls)
# C -> B -> A -> None

print (ls.add('D'))
# D -> C -> B -> A -> None

print (ls)
# C -> B -> A -> None

Наконец, мы можем реализовать reverse - 

class linked_list:

  # ...

  def reverse (self):
    def loop (ls, acc):
      if ls.is_empty:
        return acc
      else:
        return loop (ls.tail, acc.add(ls.head))
    return loop (self, linked_list())

ls = linked_list().add('A').add('B').add('C')
print (ls)
# C -> B -> A -> None

print (ls.reverse())
# A -> B -> C -> None

Изменение списка не изменяет его 

print (ls)
# C -> B -> A -> None

print (ls.reverse())
# A -> B -> C -> None

print (ls)
# C -> B -> A -> None
...