Đang chuẩn bị liên kết để tải về tài liệu:
BÀI 6: TÌM KIẾM

Tìm kiếm là đòi hỏi rất thường xuyên trong xử lý tin học. Bài toán tìm kiếm: “ Cho 1 bảng chính gồm n bản ghi R1, R2, , Rn. Mỗi bản ghi Ri (1 ≤ i ≤ n) tương ứng với 1 khoá Ki. Hãy tìm bản ghi có giá trị khoá tương ứng bằng X cho trước.” – X được gọi là khoá tìm kiếm hay đối trị tìm kiếm. | BÀI 6: TÌM KIẾM 6.1. Tìm kiếm tuần tự 6.2. Tìm kiếm nhị phân 6.3. Câu hỏi ôn tập 6.1. Tìm kiếm tuần tự 6.1.1. Bài toán tìm kiếm 6.1.2. Nguyên tắc tìm kiếm 6.1.3. Giải thuật 6.1.4. Phân tích đánh giá 6.1.1. Bài toán tìm kiếm Tìm kiếm là đòi hỏi rất thường xuyên trong xử lý tin học. Bài toán tìm kiếm: “ Cho 1 bảng chính gồm n bản ghi R1, R2, , Rn. Mỗi bản ghi Ri (1 ≤ i ≤ n) tương ứng với 1 khoá Ki. Hãy tìm bản ghi có giá trị khoá tương ứng bằng X cho trước.” X được gọi là khoá tìm kiếm hay đối trị tìm kiếm. Công việc tìm kiếm sẽ hoàn thành khi xảy ra 1 trong 2 tình huống sau: Tìm được bản ghi có giá trị khoá = X (thành công) Không tìm được bản ghi có giá trị khoá = X (không thành công) Chú ý: Khoá được coi như đại diện của bản ghi, vì vậy trong các GT và ví dụ, ta chỉ nói tới khoá. Bài toán tìm kiếm bản ghi có giá trị khoá bằng X trong bảng chính chứa các bản ghi R1, R2, , Rn coi như được đặt ra 1 cách đơn giản với bảng khoá chứa các khoá K1, K2, , Kn và Ki ≠ Kj nếu i ≠ j. Tìm . | BÀI 6: TÌM KIẾM 6.1. Tìm kiếm tuần tự 6.2. Tìm kiếm nhị phân 6.3. Câu hỏi ôn tập 6.1. Tìm kiếm tuần tự 6.1.1. Bài toán tìm kiếm 6.1.2. Nguyên tắc tìm kiếm 6.1.3. Giải thuật 6.1.4. Phân tích đánh giá 6.1.1. Bài toán tìm kiếm Tìm kiếm là đòi hỏi rất thường xuyên trong xử lý tin học. Bài toán tìm kiếm: “ Cho 1 bảng chính gồm n bản ghi R1, R2, , Rn. Mỗi bản ghi Ri (1 ≤ i ≤ n) tương ứng với 1 khoá Ki. Hãy tìm bản ghi có giá trị khoá tương ứng bằng X cho trước.” X được gọi là khoá tìm kiếm hay đối trị tìm kiếm. Công việc tìm kiếm sẽ hoàn thành khi xảy ra 1 trong 2 tình huống sau: Tìm được bản ghi có giá trị khoá = X (thành công) Không tìm được bản ghi có giá trị khoá = X (không thành công) Chú ý: Khoá được coi như đại diện của bản ghi, vì vậy trong các GT và ví dụ, ta chỉ nói tới khoá. Bài toán tìm kiếm bản ghi có giá trị khoá bằng X trong bảng chính chứa các bản ghi R1, R2, , Rn coi như được đặt ra 1 cách đơn giản với bảng khoá chứa các khoá K1, K2, , Kn và Ki ≠ Kj nếu i ≠ j. Tìm kiếm khoá X trong 1 bảng các khoá K1, K2, , Kn (Ki ≠ Kj nếu i ≠ j) Sau 1 phép tìm kiếm không thành công, có thể xuất hiện yêu cầu bổ sung thêm bản ghi mới, GT như vậy được gọi là GT tìm kiếm có bổ sung. Giá trị của khoá có thể là số, ký tự, xâu ký tự, nhưng để cho tiện ta coi khoá là các số nguyên. Bài toán tìm kiếm 6.1.2. Nguyên tắc tìm kiếm Tìm kiếm tuần tự (sequential searching) là kỹ thuật tìm kiếm rất đơn giản và cổ điển. Nội dung có thể tóm tắt như sau: Nguyên tắc tìm kiếm: Lần lượt so sánh X (khoá tìm kiếm) với các khoá K1, K2, , Kn trong bảng cho tới khi tìm thấy X (X = Km) hoặc hết bảng khoá mà chưa tìm thấy X. Kết quả: Tìm được vị trí m của khoá (đầu tiên) có giá trị bằng X. Không tìm được khoá có giá trị bằng X. 6.1.3. Giải thuật Cho bảng khoá k gồm n phần tử (0 ≤ n ≤ 250), các khoá và X là các số nguyên Integer được nhập từ bàn phím hoặc sinh ngẫu nhiên (bằng random). Giải thuật tìm kiếm tuần tự sẽ thực hiện tìm kiếm trong bảng xem có khoá nào bằng X không. Nếu có