tailieunhanh - bài giảng các chuyên đề phần 5

Cấu trúc dữ liệu và giải thuật TÌM KIẾM (SEARCHING) I. BÀI TOÁN TÌM KIẾM Cùng với sắp xếp, tìm kiếm là một đòi hỏi rất thường xuyên trong các ứng dụng tin học. Bài toán tìm kiếm có thể phát biểu như sau: Cho một dãy gồm n bản ghi r1, r2, ., rn. Mỗi bản ghi ri (1 ≤ i ≤ n) tương ứng với một khoá ki. Hãy tìm bản ghi có giá trị khoá bằng X cho trước. X được gọi là khoá tìm kiếm hay đối trị tìm . | Cấu trúc dữ liệu và giải thuật 70 8. TÌM KIẾM SEARCHING I. BÀI TOÁN TÌM KIẾM Cùng với sắp xếp tìm kiếm là một đòi hỏi rất thường xuyên trong các ứng dụng tin học. Bài toán tìm kiếm có thể phát biểu như sau Cho một dãy gồm n bản ghi r1 r2 . rn. Mỗi bản ghi ri 1 i n tương ứng với một khoá ki. Hãy tìm bản ghi có giá trị khoá bằng X cho trước. X được gọi là khoá tìm kiếm hay đối trị tìm kiếm argument . Công việc tìm kiếm sẽ hoàn thành nếu như có một trong hai tình huống sau xảy ra Tìm được bản ghi có khoá tương ứng bằng X lúc đó phép tìm kiếm thành công successful . Không tìm được bản ghi nào có khoá tìm kiếm bằng X cả phép tìm kiếm thất bại unsuccessful . Tương tự như sắp xếp ta coi khoá của một bản ghi là đại diện cho bản ghi đó. Và trong một số thuật toán sẽ trình bày dưới đây ta coi kiểu dữ liệu cho mỗi khoá cũng có tên gọi là TKey. const n . Số khoá trong dãy khoá có thể khai dưới dạng biến số nguyên để tuỳ biến hơn type TKey . Kiểu dữ liệu một khoá TArray array of TKey var k TArray Dãy khoá II. TÌM KIẾM TUẦN Tự SEQUENTIAL SEARCH Tìm kiếm tuần tự là một kỹ thuật tìm kiếm đơn giản. Nội dung của nó như sau Bắt đầu từ bản ghi đầu tiên lần lượt so sánh khoá tìm kiếm với khoá tương ứng của các bản ghi trong danh sách cho tới khi tìm thấy bản ghi mong muốn hoặc đã duyệt hết danh sách mà chưa thấy Tìm kiếm tuần tự trên dãy khoá ki k2 . kr hàm này thử tìm xem trong dãy có khoá nào X không nếu thấy nó trả về chỉ số của khoá ấy nếu không thấy nó trả về 0. Có sử dụng một khoá phụ kì 1 được gán giá trị X function SequentialSearch X TKey Integer var i Integer begin i 1 while i n and ki X do i i 1 if i n 1 then SequentialSearch 0 else SequentialSearch i end Dễ thấy rằng độ phức tạp của thuật toán tìm kiếm tuần tự trong trường hợp tốt nhất là O 1 trong trường hợp xấu nhất là O n và trong trường hợp trung bình cũng là O n . III. TÌM KIẾM NHỊ PHÂN BINARY SEARCH Phép tìm kiếm nhị phân có thể áp dụng trên dãy khoá đã có thứ tự k1 k2 . kn. Giả sử ta cần tìm trong đoạn kinf kinf 1