Đang chuẩn bị liên kết để tải về tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật trong C++ - Bài 13: Tìm kiếm - Search

Bài giảng "Cấu trúc dữ liệu và giải thuật trong C++ - Bài 13: Tìm kiếm - Search" cung cấp cho người học các kiến thức: Tìm kiếm tuần tự (Sequence search), tìm kiếm nhị phân (Binary search), bảng băm (Hash table). nội dung chi tiết. | Bài giảng Cấu trúc dữ liệu và giải thuật trong C++ - Bài 13: Tìm kiếm - Search Bài 13. Tìm kiếm- Search Bài toán Input: Cho một tập S các phần tử, mỗi phần tử là một bộ gồm khóa-giá trị (key-value) và một khóa k bất kỳ. Output: Trong S có phần tử có khóa k hay không? Search 1 Các phương pháp tìm kiếm Tìm kiếm tuần tự (Sequence search) Tìm kiếm nhị phân (Binary search) Bảng băm (Hash table) Search 2 1. Tìm kiếm tuần tự Tập S các phần tử được lưu bằng mảng hoặc danh sách liên kết. Thuật toán tìm kiếm: • Xuất phát từ phần tử đầu của dãy, thực hiện so sánh khóa của nó với k. Nếu trùng nhau thì dừng lại, nếu không trùng thì lặp lại với phần tử tiếp theo. • Quá trình dừng lại khi tìm thấy hoặc không còn phần tử nào nữa => Khi đó thông báo không tìm thấy. Search 3 1. Tìm kiếm tuần tự Ví dụ 1: Cho dãy S: 0 45 3 34 13 7 43 9 11 Tìm xem trong dãy có phần tử k=33 Quá trình tìm kiếm 0 45 3 34 13 7 43 9 11 Bước 1 Bước 2 Bước 3 Bước 4 Bước 5 Bước 6 Bước 7 Bước 8 Bước 9 • Không tìm thấy Search 4 1. Tìm kiếm tuần tự Ví dụ 2: Cho dãy S: 0 45 3 34 13 7 43 9 11 Tìm xem trong dãy có phần tử k=13 Quá trình tìm kiếm 0 45 3 34 13 7 43 9 11 Bước 1 Bước 2 Bước 3 Bước 4 Bước 5 • Tìm thấy, tại vị trí 5 Search 5 1. Tìm kiếm tuần tự Thuật toán Input: Cho một dãy S các phần tử, mỗi phần tử là một bộ key và value. Một khóa k bất kỳ. Output: Trong S có phần tử có khóa k hay không? found = 0; i =1; while ((chưa duyệt hết S ) && (found= =0) ){ if (S[i].key == k) found =1; i = i+1; //Chuyển sang phần tử kế tiếp } return found; Search 6 1. Tìm kiếm tuần tự Thời gian chạy: Trong trường hợp xấu nhất thuật toán phải duyệt qua tất cả các phần tử của S. Vậy thời gian chạy là O(n) Search 7 2. Tìm kiếm nhị phân Tập S được tổ chức lưu trữ dựa trên mảng Tập S được tổ chức lưu trữ dạng cây nhị phân Search 8 2.1 Tìm kiếm nhị phân trên mảng Các phần tử của S được lưu trữ