Bài 10. Thực hành tổng hợp với cây tìm kiếm nhị phân
Sau bài học này em sẽ:
Trong Bài 9, chúng ta đã học thao tác duyệt cây. Với bài toán thực tế quản lí danh bạ điện thoại, làm thế nào để sử dụng các thao tác đó vào cây tìm kiếm nhị phân để thêm, tìm kiếm, hiển thị toàn bộ các liên hệ theo thứ tự sắp xếp của tên liên hệ trong danh bạ?
Nhiệm vụ: Viết chương trình quản lí danh bạ điện thoại
Các thiết bị máy tính, điện thoại hiện nay đều tích hợp ứng dụng quản lí danh bạ. Em hãy sử dụng cấu trúc dữ liệu cây tìm kiếm nhị phân để viết ứng dụng quản lí danh bạ đơn giản. Mỗi liên hệ trong danh bạ gồm các thông tin: tên liên hệ (duy nhất), tên đầy đủ, số điện thoại. Khi chạy chương trình, dữ liệu được đọc từ tệp contacts.inp với mỗi dòng ứng với một liên hệ có dạng như hình trên.
contacts.inp
Anh An, Nguyễn Văn Anh, 0901.000.159
Bố, Văn Hoàng, 0983 000 131
Mẹ, Hoàng Thị, 0962 000 481
ICTLab Station, Số cố định tại ICTLab, 024 124 000 313
Các chức năng chính của chương trình:
Hướng dẫn
Xây dựng chương trình hai bước: (1) Cài đặt cây tìm kiếm nhị phân bằng mảng để lưu thông tin của các liên hệ, mỗi liên hệ gồm ba thông tin là tên liên hệ, tên đầy đủ, số điện thoại; (2) Xây dựng chương trình hoàn chỉnh đọc dữ liệu từ tệp contacts.inp, lưu dữ liệu vào cây tìm kiếm nhị phân, cho phép người dùng tra cứu, bổ sung, cập nhật.
Bước 1. Cài đặt cây tìm kiếm nhị phân bằng mảng
Phân tích: Các cấu trúc dữ liệu của cây tìm kiếm nhị phân lưu trữ danh bạ tương tự như mã mẫu từ Bài 7 với hàm định nghĩa cấu trúc Tree, hàm left, right, parent được giữ nguyên; chỉ có hàm Tree_Insert và Tree_Insert_Update cần được sửa đổi để tích hợp thêm các trường dữ liệu key (khoá tìm kiếm), fullName (tên đầy đủ của liên hệ) và phoneNumber (số điện thoại) vào mỗi nút của cây. Để duyệt các nút từ nhỏ đến lớn với khoá tìm kiếm được sắp xếp theo thứ tự từ điển, em hãy dùng hàm inorder được giới thiệu ở Bài 9 nhưng cần chỉnh sửa để in các thông tin trong khi duyệt.
Các hàm Tree_Insert, Tree_Insert_Update, và inorder được sửa như sau:
def Tree_Insert(T, key, fullName, phoneNumber):
k = 0
while k < len(T) and T[k] != None:
if key < T[k][0]:
k = left(k)
elif key > T[k][0]:
k = right(k)
else:
return
if k >= len(T):
T.extend([None] * (k - len(T) + 1))
T[k] = [key, fullName, phoneNumber]
def Tree_Insert_Update(T, key, fullName, phoneNumber):
k = search(T, 0, key)
if k == -1:
Tree_Insert(T, key, fullName, phoneNumber)
return False #Thể hiện đã thêm mới liên hệ
else:
T[k][1] = fullName #Cập nhật tên
T[k][2] = phoneNumber #Cập nhật điện thoại
return True #Thể hiện đã cập nhật liên hệ
def inorder(T, k):
if k < len(T) and T[k] != None:
inorder(T, left(k))
print(T[k][0], "|", T[k][1], "|", T[k][2], end=" ")
inorder(T, right(k))Bước 2. Xây dựng chương trình hoàn chỉnh
Để xây dựng chương trình hoàn chỉnh, trước tiên cần đọc dữ liệu từ tệp contacts.inp rồi chèn vào cây tìm kiếm nhị phân. Tương tự Bài 8, chương trình có bảng chọn cho phép người dùng nhập số ứng với các lựa chọn như sau:
0: "Thoát chương trình"
1: "Hiển thị các liên hệ theo thứ tự từ điển"
2: "Tra cứu liên hệ hoặc thêm một liên hệ"
3: "Cập nhật liên hệ"
Mã nguồn
from BST_phonebook import * #Khai báo thư viện cây tìm kiếm nhị phân
#Khởi tạo cây tìm kiếm và đọc dữ liệu từ tệp
T = Tree()
f = open("contacts.inp", "r", encoding="utf8")
lines = f.readlines()
for line in lines:
line = line.strip()
parts = line.split(",", maxsplit=3)
Tree_Insert(T, parts[0], parts[1], parts[2])
f.close()
#Hiển thị các chức năng chương trình theo lựa chọn
options = ["Thoát chương trình", "Hiển thị các liên hệ theo thứ tự từ điển", "Tra cứu liên hệ hoặc thêm một liên hệ", "Cập nhật liên hệ"]
selected = -1 #Chức năng người dùng chọn lựa từ menu, khởi tạo bằng -1
while selected != 0:
for choice in range(len(options)):
print(choice, options[choice])
selected = int(input("Chọn chức năng: "))
if selected < 0 or selected > 4:
print("Chức năng không hợp lệ, hãy nhập số 0 đến 4")
continue
if selected == 1: #In danh bạ
print("Danh bạ theo thứ tự từ điển: ")
inorder(T, 0)
elif selected == 2: #Tìm liên hệ
item = input("Nhập tên liên hệ: ")
k = search(T, 0, item)
if k >= 0:
print("Tên đầy đủ: ", T[k][1], "Số điện thoại: ", T[k][2])
else:
print("Tên liên hệ ", item, "không có trong danh bạ")
elif selected == 3: #Thêm hoặc cập nhật liên hệ
key = input("Nhập tên liên hệ: ")
fullName = input("Nhập tên đầy đủ: ")
phoneNumber = input("Nhập số điện thoại: ")
if Tree_Insert_Update(T, key, fullName, phoneNumber):
print("Đã cập nhật liên hệ ", key)
else:
print("Đã thêm liên hệ vào danh bạ")