Tôi đang cố gắng tìm ra làm thế nào tôi có thể đi qua danh sách được liên kết trong Python bằng cách sử dụng đệ quy.Recursion.
Tôi biết cách đi qua danh sách liên kết bằng cách sử dụng các vòng lặp chung như:
item_cur = my_linked_list.first
while item_cur is not None:
print[item_cur.item]
item_cur = item_cur.next
Tôi đã tự hỏi làm thế nào tôi có thể biến vòng lặp này thành một bước đệ quy.
Cảm ơn
Hỏi ngày 18 tháng 10 năm 2014 lúc 23:33Oct 18, 2014 at 23:33
5
Bạn có thể làm điều gì đó như thế này:
def print_linked_list[item]:
# base case
if item == None:
return
# lets print the current node
print[item.item]
# print the next nodes
print_linked_list[item.next]
Đã trả lời ngày 19 tháng 10 năm 2014 lúc 3:31Oct 19, 2014 at 3:31
Aviaviavi
8.95610 Huy hiệu vàng45 Huy hiệu bạc82 Huy hiệu Đồng10 gold badges45 silver badges82 bronze badges
Có vẻ như danh sách được liên kết của bạn có hai loại. Bạn có các nút danh sách, với các thuộc tính
def print_linked_list[item]:
# base case
if item == None:
return
# lets print the current node
print[item.item]
# print the next nodes
print_linked_list[item.next]
5 và def print_linked_list[item]:
# base case
if item == None:
return
# lets print the current node
print[item.item]
# print the next nodes
print_linked_list[item.next]
6 và một đối tượng trình bao có thuộc tính trỏ đến nút def print_linked_list[item]:
# base case
if item == None:
return
# lets print the current node
print[item.item]
# print the next nodes
print_linked_list[item.next]
7. Để in đệ quy danh sách, bạn sẽ muốn có hai chức năng, một để xử lý chức năng trình bao bọc và hàm trợ giúp để thực hiện xử lý đệ quy của các nút.def print_list[linked_list]: # Non-recursive outer function. You might want
_print_list_helper[linked_list.first] # to update it to handle empty lists nicely!
def _print_list_helper[node]: # Recursive helper function, gets passed a
if node is not None: # "node", rather than the list wrapper object.
print[node.item]
_print_list_helper[node.next] # Base case, when None is passed, does nothing
Đã trả lời ngày 19 tháng 10 năm 2014 lúc 5:04Oct 19, 2014 at 5:04
BlckknghtblckknghtBlckknght
96.4K11 Huy hiệu vàng112 Huy hiệu bạc162 Huy hiệu đồng11 gold badges112 silver badges162 bronze badges
Thử cái này.
class Node:
def __init__[self,val,nxt]:
self.val = val
self.nxt = nxt
def reverse[node]:
if not node.nxt:
print node.val
return
reverse[node.nxt]
print node.val
n0 = Node[4,None]
n1 = Node[3,n0]
n2 = Node[2,n1]
n3 = Node[1,n2]
reverse[n3]
Vijay
1231 Huy hiệu vàng1 Huy hiệu bạc10 Huy hiệu đồng1 gold badge1 silver badge10 bronze badges
Đã trả lời ngày 19 tháng 10 năm 2014 lúc 3:15Oct 19, 2014 at 3:15
KipikipiKipi
1652 Huy hiệu bạc10 Huy hiệu đồng2 silver badges10 bronze badges
Một danh sách được liên kết là một chuỗi các yếu tố dữ liệu, được kết nối với nhau thông qua các liên kết. Mỗi phần tử dữ liệu chứa một kết nối với phần tử dữ liệu khác dưới dạng con trỏ. Python không có danh sách liên kết trong thư viện tiêu chuẩn của nó. Chúng tôi thực hiện khái niệm danh sách được liên kết bằng cách sử dụng khái niệm các nút như được thảo luận trong chương trước.
Chúng tôi đã thấy cách chúng tôi tạo một lớp nút và cách đi qua các yếu tố của một nút. Trong chương này, chúng tôi sẽ nghiên cứu các loại danh sách được liên kết được gọi là danh sách liên kết đơn lẻ. Trong loại cấu trúc dữ liệu này, chỉ có một liên kết giữa bất kỳ hai phần tử dữ liệu nào. Chúng tôi tạo một danh sách như vậy và tạo các phương thức bổ sung để chèn, cập nhật và xóa các yếu tố khỏi danh sách.
Tạo danh sách được liên kết
Một danh sách được liên kết được tạo bằng cách sử dụng lớp nút mà chúng tôi đã nghiên cứu trong chương trước. Chúng tôi tạo một đối tượng nút và tạo một lớp khác để sử dụng đối tượng ODE này. Chúng tôi chuyển các giá trị thích hợp thông qua đối tượng nút để trỏ đến các phần tử dữ liệu tiếp theo. Chương trình dưới đây tạo ra danh sách được liên kết với ba yếu tố dữ liệu. Trong phần tiếp theo, chúng ta sẽ thấy cách đi qua danh sách được liên kết.
class Node: def __init__[self, dataval=None]: self.dataval = dataval self.nextval = None class SLinkedList: def __init__[self]: self.headval = None list1 = SLinkedList[] list1.headval = Node["Mon"] e2 = Node["Tue"] e3 = Node["Wed"] # Link first Node to second node list1.headval.nextval = e2 # Link second Node to third node e2.nextval = e3
Đi qua một danh sách được liên kết
Danh sách liên kết đơn lẻ có thể được đi qua chỉ theo hướng bắt đầu hình thức phần tử dữ liệu đầu tiên. Chúng tôi chỉ cần in giá trị của phần tử dữ liệu tiếp theo bằng cách gán con trỏ của nút tiếp theo cho phần tử dữ liệu hiện tại.
Thí dụ
class Node: def __init__[self, dataval=None]: self.dataval = dataval self.nextval = None class SLinkedList: def __init__[self]: self.headval = None def listprint[self]: printval = self.headval while printval is not None: print [printval.dataval] printval = printval.nextval list = SLinkedList[] list.headval = Node["Mon"] e2 = Node["Tue"] e3 = Node["Wed"] # Link first Node to second node list.headval.nextval = e2 # Link second Node to third node e2.nextval = e3 list.listprint[]
Đầu ra
Khi mã trên được thực thi, nó sẽ tạo ra kết quả sau -
Mon Tue Wed
Chèn vào một danh sách được liên kết
Phần tử chèn vào danh sách được liên kết liên quan đến việc chỉ định lại các con trỏ từ các nút hiện có đến nút mới được chèn. Tùy thuộc vào việc phần tử dữ liệu mới được chèn vào đầu hay ở giữa hay ở cuối danh sách được liên kết, chúng tôi có các kịch bản dưới đây.
Chèn vào đầu
Điều này liên quan đến việc trỏ con trỏ tiếp theo của nút dữ liệu mới vào đầu hiện tại của danh sách được liên kết. Vì vậy, đầu hiện tại của danh sách được liên kết trở thành phần tử dữ liệu thứ hai và nút mới trở thành người đứng đầu của danh sách được liên kết.
Thí dụ
class Node: def __init__[self, dataval=None]: self.dataval = dataval self.nextval = None class SLinkedList: def __init__[self]: self.headval = None # Print the linked list def listprint[self]: printval = self.headval while printval is not None: print [printval.dataval] printval = printval.nextval def AtBegining[self,newdata]: NewNode = Node[newdata] # Update the new nodes next val to existing node NewNode.nextval = self.headval self.headval = NewNode list = SLinkedList[] list.headval = Node["Mon"] e2 = Node["Tue"] e3 = Node["Wed"] list.headval.nextval = e2 e2.nextval = e3 list.AtBegining["Sun"] list.listprint[]
Đầu ra
Khi mã trên được thực thi, nó sẽ tạo ra kết quả sau -
Sun Mon Tue Wed
Chèn vào một danh sách được liên kết
Phần tử chèn vào danh sách được liên kết liên quan đến việc chỉ định lại các con trỏ từ các nút hiện có đến nút mới được chèn. Tùy thuộc vào việc phần tử dữ liệu mới được chèn vào đầu hay ở giữa hay ở cuối danh sách được liên kết, chúng tôi có các kịch bản dưới đây.
Thí dụ
class Node: def __init__[self, dataval=None]: self.dataval = dataval self.nextval = None class SLinkedList: def __init__[self]: self.headval = None # Function to add newnode def AtEnd[self, newdata]: NewNode = Node[newdata] if self.headval is None: self.headval = NewNode return laste = self.headval while[laste.nextval]: laste = laste.nextval laste.nextval=NewNode # Print the linked list def listprint[self]: printval = self.headval while printval is not None: print [printval.dataval] printval = printval.nextval list = SLinkedList[] list.headval = Node["Mon"] e2 = Node["Tue"] e3 = Node["Wed"] list.headval.nextval = e2 e2.nextval = e3 list.AtEnd["Thu"] list.listprint[]
Đầu ra
Khi mã trên được thực thi, nó sẽ tạo ra kết quả sau -
def print_linked_list[item]:
# base case
if item == None:
return
# lets print the current node
print[item.item]
# print the next nodes
print_linked_list[item.next]
0Chèn vào một danh sách được liên kết
Phần tử chèn vào danh sách được liên kết liên quan đến việc chỉ định lại các con trỏ từ các nút hiện có đến nút mới được chèn. Tùy thuộc vào việc phần tử dữ liệu mới được chèn vào đầu hay ở giữa hay ở cuối danh sách được liên kết, chúng tôi có các kịch bản dưới đây.
def print_linked_list[item]:
# base case
if item == None:
return
# lets print the current node
print[item.item]
# print the next nodes
print_linked_list[item.next]
1Đầu ra
Khi mã trên được thực thi, nó sẽ tạo ra kết quả sau -
def print_linked_list[item]:
# base case
if item == None:
return
# lets print the current node
print[item.item]
# print the next nodes
print_linked_list[item.next]
2Chèn vào một danh sách được liên kết
Phần tử chèn vào danh sách được liên kết liên quan đến việc chỉ định lại các con trỏ từ các nút hiện có đến nút mới được chèn. Tùy thuộc vào việc phần tử dữ liệu mới được chèn vào đầu hay ở giữa hay ở cuối danh sách được liên kết, chúng tôi có các kịch bản dưới đây.
Thí dụ
def print_linked_list[item]:
# base case
if item == None:
return
# lets print the current node
print[item.item]
# print the next nodes
print_linked_list[item.next]
3Đầu ra
Khi mã trên được thực thi, nó sẽ tạo ra kết quả sau -
def print_linked_list[item]:
# base case
if item == None:
return
# lets print the current node
print[item.item]
# print the next nodes
print_linked_list[item.next]
4