tailieunhanh - Kiến trúc máy tính - Part 13

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 Bài 13. Tìm kiếm- Search Bài toán Input: Cho một dãy S các phần tử, mỗi phần tử là một bộ gồm khóa-giatrị (key-value). Một khóa k bất kỳ. Output: Trong S có phần tử có khóa k hay không? Search 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 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 Ví dụ 1 Cho dãy S: Tìm xem trong dãy có phần tử k=33 Quá trình tìm kiếm 45 3 34 13 7 43 9 11 0 45 3 34 13 7 43 9 11 0 Bước 1 Bước 8 Bước 7 Bước 2 Bước 3 Bước 4 Bước 5 Bước 6 Bước 9 Không tìm thấy Search Ví dụ 2 Cho dãy S: Tìm xem trong dãy có phần tử k=13 Quá trình tìm kiếm 45 3 34 13 7 43 9 11 0 | Search Bài 13. Tìm kiếm- Search Bài toán Input: Cho một dãy S các phần tử, mỗi phần tử là một bộ gồm khóa-giatrị (key-value). Một khóa k bất kỳ. Output: Trong S có phần tử có khóa k hay không? Search 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 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 Ví dụ 1 Cho dãy S: Tìm xem trong dãy có phần tử k=33 Quá trình tìm kiếm 45 3 34 13 7 43 9 11 0 45 3 34 13 7 43 9 11 0 Bước 1 Bước 8 Bước 7 Bước 2 Bước 3 Bước 4 Bước 5 Bước 6 Bước 9 Không tìm thấy Search Ví dụ 2 Cho dãy S: Tìm xem trong dãy có phần tử k=13 Quá trình tìm kiếm 45 3 34 13 7 43 9 11 0 45 3 34 13 7 43 9 11 0 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 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; } return found; Search 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 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 kiếm nhị phân trên mảng Các phần tử của S được lưu trữ trong mảng và được sắp xếp theo thứ tự tăng dần (giảm dần) của giá trị khóa (key). Thuật toán tìm kiếm nhị phân được thiết kế dựa trên chiến lược chia và trị Thuật toán: So sánh khóa k với khóa của phần tử ở giữa dãy. Nếu trùng thì thông báo tìm thấy và dừng Nếu k> thì gọi đệ qui tìm trên nửa cuối dãy Nếu k< thì gọi đệ .