Giáo án điện tử chuyên đề Khoa học máy tính 12 kết nối Bài 10: Thực hành tổng hợp với cây tìm kiếm nhị phân

CHÀO MỪNG CẢ LỚP ĐẾN VỚI BÀI HỌC MỚI!

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ạ?

KHỞI ĐỘNG

BÀI 10. THỰC HÀNH TỔNG HỢP VỚI CÂY TÌM KIẾM NHỊ PHÂN

Viết chương trình quản lí danh bạ điện thoại

Nhiệm vụ:

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 li 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.

Nhiệm vụ

Viết chương trình quản lí danh bạ điện thoại

Nhiệm vụ:

Các chức năng chính của chương trình

a) Hiển thị danh sách liên hệ theo thứ tự sắp xếp tên theo thứ tự từ điển.

b) Tìm kiếm liên hệ theo tên.

c) Thêm, sửa các liên hệ.

Cài đặt cây tìm kiếm nhị phân bằng mảng

Bước 1

Các hàm Tree_Insert, Tree_Insert_Update, và inorder được sửa như sau:

Xây dựng chương trình hoàn chỉnh

Bước 2

Để 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.

Bảng chọn

0: Thoát chương trình

1: Hiển thị các liên hệ theo thứ tự từ điển

3: Tra cứu liên hệ

4: Tra cứu liên hệ

Mã nguồn chương trình

LUYỆN TẬP

Câu 1. Hãy vẽ cây tìm kiếm nhị phân ứng với:

a) Dữ liệu tệp contacts.inp ở trong phần thực hành.

b) Từ cây nhận được ở ý a, thêm liên hệ "Anh, Nguyễn Văn Tùng, 0982 000 134".

Câu 2. Tiếp tục với ứng dụng quản lí danh bạ, chức năng hiển thị danh sách liên hệ theo thứ tự từ điển. Do hạn chế của màn hình, mỗi trang chỉ hiển thị được 20 liên hệ. Hãy thêm tính năng in các liên hệ ở trang n bất kì do người dùng nhập vào, điều kiện n nguyên, lớn hơn 0 và nhỏ hơn hoặc bằng tổng số trang có thể hiển thị.

CÂU HỎI

Trả lời Câu 1

a) Để vẽ lại cây tìm kiếm nhị phân ứng với tệp contacts.inp hãy thực hiện dẫn các bước của thuật toán chèn cho từng liên hệ trong tệp contacts.inp

Do dữ liệu chỉ gồm 4 liên hệ trong đó 3 liên hệ đầu tiên được chèn vào lại đúng với thứ tự khoá của chúng, nút “Bố” và “Mẹ” đều nằm ở nhánh phải của cây.

Vì “ICTLab Station" < "Mẹ" nên “ICTLab Station" là nút con trái của “Mẹ”.

Cây tìm kiếm nhị phân thu được, không may thay, có dạng “cây suy biến” như Hình.

b) Khi thêm liên hệ mới có khoá “Anh” vào cây, do nút này có khoá nhỏ hơn khoá ở nút gốc “Anh An” nên liên hệ này được thay vào nút con trái None của nút gốc và ta thu được cây như Hình.

Trả lời Câu 2

Để in được các danh bạ ở một trang, cần phải đếm thứ tự các liên hệ khi duyệt cây.

Sử dụng biến toàn cục count để đếm khi duyệt bằng hàm inorder và các biến starting, ending để đánh dấu vị trí đầu tiên và cuối cùng của trang cần tìm. Mã nguồn tham khảo như sau:

VẬN DỤNG

Câu 1

Sử dụng cây tìm kiếm nhị phân để viết chương trình quản lí danh sách học sinh của một lớp. Thông tin mỗi học sinh gồm mã (duy nhất), tên đầy đủ, ngày sinh. Chương trình cho phép thêm mới thông tin các học sinh, in danh sách sắp xếp theo mã từ nhỏ đến lớn và từ lớn đến nhỏ, tìm kiếm học sinh theo mã.

Câu 2

Sử dụng cây tìm kiếm nhị phân để hiển thị các món trong tập menu.inp ở Bài 8 theo thứ tự giá tiền tăng dần. Mỗi dòng in ra gồm tên món và giá tiền. Nếu có hai hoặc nhiều món cùng giả tiền thì các món đó được hiển thị theo thứ tự xuất hiện trong tập menu.inp.

Trả lời câu 1

--------------- Còn tiếp ---------------