Bài giảng môn Cấu trúc dữ liệu chương 2: Kỹ thuật tìm kiếm

Môn: CẤU TRÚC DỮ LIỆU Chương 2: KỸ THUẬT TÌM KIẾM (SEARCHING) NỘI DUNG CHƯƠNG 2 2.1 Khái quát về tìm kiếm 2.2 Các giải thuật tìm kiếm nội (Tìm kiếm trên mảng) Tìm tuyến tính (Linear Search) Tìm nhị phân (Binary Search) 2.3 Các giải thuật tìm kiếm ngoại (Tìm kiếm trên tập tin) Tìm tuyến tính (F Linear Search) Tìm nhị phân (Binary Search) BÀI TẬP 2.1 Khái quát về tìm kiếm Trong các hệ lưu trữ và quản lý dữ liệu, thao tác tìm kiếm được thực hiện nhiều nhất để khai thác thông tin một các dễ dàng. Số lượng thông tin trong một hệ thống thông tin là đáng kể nên việc xây dựng các giải thuật tìm kiếm nhanh sẽ có ý nghĩa quan trọng. Nếu tìm kiếm trong một hệ thống đã tổ chức thì việc tìm kiếm dễ dàng hơn. Các giải thuật tìm kiếm được xây dựng nhằm mục tiêu hỗ trợ ứng dụng có hiệu quả hơn. Các giải thuật phụ thuộc vào vào cấu trúc dữ liệu mà nó tác động đến. Dữ liệu được lưu trữ trên bộ nhớ chính và bộ nhớ phụ. 2.1 Khái quát về tìm kiếm (tt) Giả sử mỗi phần tử được xem xét có một thành phần khóa (Key) để nhận diện có kiểu dữ liệu T, các thành phần còn lại là thông tin (Info), như vậy mỗi phần tử có cấu trúc như sau: typedef struct DataElement { T Key; InfoData Info; } DataType; Để đơn giản, quan tâm thành phần dữ liệu chỉ là khóa nhận diện 2.2 Các giải thuật tìm kiếm nội Bài toán đặt ra: Giả sử có một mảng M gồm N phần tử. Cần xác định có hay không phần tử có giá trị bằng X trong mảng M?? Nếu có phần tử X thì phần tử bằng phần tử X là phần tử thứ mấy trong mảng X? Các giải thuật tìm kiếm nội đưa ra 2 cách tìm kiếm Tìm kiếm tuần tự hay (Sequential Search) còn gọi tìm kiếm tuyến tính (Linear Search) Tìm kiếm nhị phân (Binary Search) 2.2 Các giải thuật tìm kiếm nội (tt) Tìm tuyến tính (Linear Seach) Ý tưởng: So sánh lần lượt các phần tử của mảng M với giá trị X cần tìm bắt đầu từ phần tử đầu tiên cho đến khi tìm ra phần tử có giá trị X hoặc đã duyệt hết tất cả các phần tử của mảng M thì kết thúc. Thuật toán B1: k = 1 B2: Nếu M[k]  X và k M[Mid] rút ngắn phạm vi tìm kiếm và First = Mid +1 Lặp lại quá trình cho đến khi tìm thấy phần tử có giá trị = X 2.2 Các giải thuật tìm kiếm nội (tt) Tìm nhị phân (tt) Thuật toán đệ quy (Recursion Algorithm) B1: First = 1 B2: Last = N B3: Nếu (First > Last) // hết phạm vi tìm kiếm Không tìm thấy Ngược lại: Thực hiện B8 B4: Mid = (First + Last )/2 B5: Nếu (X = M[Mid]) Tìm thấy tại vị trí Mid Ngược lại: Thực hiện B6 B6: Nếu (XM[Mid]) Tìm đệ quy từ First = Mid +1 đến Last B8: Kết thúc 2.2 Các giải thuật tìm kiếm nội (tt) Tìm nhị phân (tt) Cài đặt Thuật toán đệ quy (Recursion Algorithm) int RecursiveBinarySearch (T M[], int First, int Last, T X) { if (First > Last) return (-1); int Mid = (First + Last)/2; if (X == M[Mid]) return Mid; if (X Last) // hết phạm vi tìm kiếm Không tìm thấy Ngược lại: Thực hiện B8 B4: Mid = (First + Last )/2 B5: Nếu (X = M[Mid]) Tìm thấy tại vị trí Mid Ngược lại: Thực hiện B6 B6: Nếu (XM[Mid]) First = Mid + 1 và lặp lại B3 B8: Kết thúc 2.2 Các giải thuật tìm kiếm nội (tt) Tìm nhị phân (tt) Cài đặt Thuật toán không đệ quy (Non-Recursion Algorithm) int NRBinarySearch (T M[], int N, T X) { int First = 0; int Last = N-1; while (First = giá trị X hay đọc đến cuối tập tin. Nếu trong quá trình trên tìm kiếm được phần tử có giá trị = X, truy xuất tập tin F tại vị trí này để đọc dữ liệu, tránh mất thời gian. 2.3 Các giải thuật tìm kiếm ngoại Tìm kiếm theo chỉ mục (tt) Thuật toán B1: Trở về đầu tập tin chỉ mục IDX(rewind(IDX)) B2: Đọc 1 phần tử trong tập tin (read(IDX, ai)) B3: Kiểm tra Nếu ai.IdxKey = X) break; } fclose (IDXFp); if (ai.IdxKey == X) return (ai.Pos); return (-1); } 2.3 Các giải thuật tìm kiếm ngoại Tìm kiếm theo chỉ mục (tt) Phân tích Thuật toán: Trường hợp tốt nhất (phần tử đầu tiên trong tập tin chỉ mục có giá trị = X) Số phép gán Gmin = 1 Số phép so sánh Smin = 2 + 1 Số lần đọc tập tin Dmin = 1 Trường hợp xấu nhất (không có phần tử nào trong tập tin chỉ mục có giá trị = X) Số phép gán Gmax = 1 Số phép so sánh Smax = 2N +1 Số lần đọc tập tin Dmax = N Trung bình Số phép gán Gavg = ½(N +5) Số phép so sánh Savg = (3 + 2N + 1)/2 Số lần đọc tập tin Davg = ½(N + 1) Bài tập Cài đặt các thuật toán trong lý thuyết Bài tập trong giáo trình chương 2 Bài tập thực hành tuần 2, 3