Chương trình Python tìm kiếm phần tử trong Danh sách liên kết vòng

Khi cần tìm kiếm một phần tử trong danh sách liên kết vòng, trước tiên cần tạo một lớp Node. Lớp này có hai thuộc tính: dữ liệu chứa trong nút và tham chiếu đến nút tiếp theo của danh sách liên kết.

Trong danh sách liên kết vòng, nút đầu (head) và nút cuối (tail) liền kề nhau. Chúng được kết nối thành một vòng tròn và nút cuối không có giá trị NULL. Cần tạo một lớp khác có hàm khởi tạo, trong đó nút head được khởi tạo là None.

Nhiều phương thức do người dùng định nghĩa để thêm nút vào danh sách, tìm kiếm một nút cụ thể và in các giá trị của các nút.

Dưới đây là ví dụ minh họa:

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 search_value(self, elem_to_search):
        curr = self.head
        i = 1
        flag_val = False
        if self.head is None:
            print("Danh sách rỗng")
        else:
            while True:
                if curr.data == elem_to_search:
                    flag_val = True
                    break
                curr = curr.next
                i += 1
                if curr == self.head:
                    break
            if flag_val:
                print("Phần tử có trong danh sách tại vị trí: " + str(i))
            else:
                print("Phần tử không có trong danh sách")

    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("Đang thêm các 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 là:")
    my_cl.print_it()
    print("Đang tìm kiếm giá trị 99")
    my_cl.search_value(99)
    print("Đang tìm kiếm giá trị 0")
    my_cl.search_value(0)

Kết quả

Đang thêm các nút vào danh sách
Danh sách là:
21
54
78
99
27
Đang tìm kiếm giá trị 99
Phần tử có trong danh sách tại vị trí: 4
Đang tìm kiếm giá trị 0
Phần tử không có trong danh sách

Giải thích

• Tạo lớp Node.
• Tạo lớp khác với các thuộc tính cần thiết.
• Định nghĩa phương thức search_value để tìm kiếm phần tử cụ thể trong danh sách liên kết.
• Định nghĩa phương thức print_it để hiển thị các nút của danh sách liên kết vòng.
• Tạo đối tượng của lớp list_creation và gọi các phương thức để thêm dữ liệu.
• Phương thức __init__ khởi tạo nút đầu và nút cuối của danh sách liên kết vòng là None.
• Gọi phương thức search_value.
• Duyệt qua danh sách, kiểm tra xem phần tử cần tìm có được tìm thấy hay không.
• Nếu tìm thấy, hiển thị chỉ số của nó.
• Kết quả được hiển thị trên bảng điều khiển bằng phương thức print_it.