我是编程新手,从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')
递归是函数式的遗产,因此将它与函数式一起使用将产生最好的结果。在您的程序中,您已经使用命令样式的可变节点实现了一个链表,也就是说,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
最后一个函数返回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的有序集配方中使用了双向链接列表,但单链接列表在