Khi cần sắp xếp các phần tử trong danh sách liên kết vòng (circular linked list), ta dùng thuật toán sắp xếp bong bóng (bubble sort) trên cấu trúc vòng.
Ví dụ
class Node:
def __init__(self, data):
self.data = data
self.next = None
class list_creation:
def __init__(self):
self.head = Node(None)
self.tail = Node(None)
self.head.next = self.tail
self.tail.next = self.head
def add_data(self, my_data):
new_node = Node(my_data)
if self.head.data is None:
self.head = new_node
self.tail = new_node
new_node.next = self.head
else:
self.tail.next = new_node
self.tail = new_node
self.tail.next = self.head
def sort_list(self):
curr = self.head
if self.head is None:
print("Danh sách rỗng")
else:
while True:
index_val = curr.next
while index_val != self.head:
if curr.data > index_val.data:
temp = curr.data
curr.data = index_val.data
index_val.data = temp
index_val = index_val.next
curr = curr.next
if curr.next == self.head:
break
def print_it(self):
curr = self.head
if self.head is None:
print("Danh sách rỗng")
return
else:
print(curr.data)
while curr.next != self.head:
curr = curr.next
print(curr.data)
print("\n")
class circular_linked_list:
my_cl = list_creation()
print("Thêm nút vào danh sách")
my_cl.add_data(21)
my_cl.add_data(54)
my_cl.add_data(78)
my_cl.add_data(99)
my_cl.add_data(27)
print("Danh sách ban đầu:")
my_cl.print_it()
print("Đang sắp xếp danh sách...")
my_cl.sort_list()
print("Danh sách đã sắp xếp:")
my_cl.print_it()
Kết quả
Thêm nút vào danh sách Danh sách ban đầu: 21 54 78 99 27 Đang sắp xếp danh sách... Danh sách đã sắp xếp: 21 27 54 78 99
Giải thích
- Lớp
Nodecho danh sách vòng (next). - Lớp
list_creationkhởi tạo head, tail trỏ lẫn nhau. add_datathêm vào cuối, duy trì vòng (tail.next = head).sort_list: bubble sort – duyệt curr, bên trong duyệt index_val từ curr.next đến head, hoán đổi data nếu curr.data > index_val.data.print_itin từ head cho đến khi quay lại head.- Demo thêm 5 số, in, sắp xếp, in lại.