当前位置: 首页 > 知识库问答 >
问题:

python中的链表和递归

仉峻
2023-03-14

我是编程新手,从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')

共有1个答案

方宜
2023-03-14

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

我们从简单的nodeLinked_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_emptyheadtail

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

 类似资料:
  • 最后一个函数返回15->20,然后组合为root.next->temp,但是在返回temp的步骤之后,为什么会返回根值。即10->15->20,而我希望只返回temp。 请找到代码,

  • 我需要为链表队列实现一个toString()递归方法。我知道我的toString方法在我上周做的一个链表实现中工作得很好,所以我在处理它的队列方面出了问题。 我的QueueList的toString方法: 以及我的构造函数,例如QueueList: 我试图用这个测试看看里面发生了什么: 与输出 我意识到这是因为我说的是前面的在方法的递归部分,但即使我将其更改为,我的输出是 这可能与我的排队和退队方

  • 问题内容: 我已经在一个类的Java项目上工作了一段时间。它是链表(此处称为,包含称为的简单节点)的实现。问题是,一切都必须使用递归算法来完成。我可以用一种方法来做所有的事情: 现在,我的函数只是调用一个带有参数以允许递归的辅助函数。 我的助手功能具有的签名。 目前,我使用堆栈来迭代工作,但这不是规范所要求的。我在C语言中找到了一种算法,该算法可以递归地将其递归逆转并将其转换为Java代码,并且可

  • 问题内容: 我被要求反转一个以head为参数的参数,其中head是一个链表,例如:1-> 2-> 3这是从已经定义的函数返回的,我试图以这种方式实现函数reverse_linked_list: 称为:。我编写的用于反转列表的函数具有给定的功能,并且仅适用于长度为3的列表。如何将其概括为长度为列表的? 问题答案: U可以使用mod函数获取每次迭代的余数,并且显然可以帮助反转列表。我想你是R和D团的学

  • 我正在学习数据结构,并试图理解Java中的链接列表。我的问题是,我有麻烦与删除节点在给定的索引递归。我的目标是得到O(log n),而不是使用循环,最后得到O(n)。 因此,当我试图删除索引2的条目时,它会删除该索引之前的所有数字,但不会删除该索引-因此它会删除[0]和[1],但不会删除[2]。 例如,在此代码中,删除前的数组填充为:。调用后,它有以下条目: 我只想删除13,这样数组就会像这样:

  • 问题内容: 在python中使用链表的最简单方法是什么?在方案中,链表仅由定义’。实际上,Python的和不是链接列表,而链接列表具有一些不错的属性,例如恒定时间串联,并且能够引用其中的单独部分。使它们一成不变,并且它们真的很容易使用! 问题答案: 以下是一些基于Martin诉Löwis陈述的列表函数: 哪里 尽管在Raymond Hettinger的有序集配方中使用了双向链接列表,但单链接列表在