Cho biết: Một danh sách các bản ghi (record). Một khóa cần tìm. Tìm bản ghi có khóa trùng với khóa cần tìm (nếu có). Đo độ hiệu quả: Số lần so sánh khóa cần tìm và khóa của các bản ghi Phân loại: Tìm kiếm nội (internal searching) Tìm kiếm ngoại (external searching) | CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Chương 7: Tìm kiếm Khái niệm tìm kiếm Cho biết: Một danh sách các bản ghi (record). Một khóa cần tìm. Tìm bản ghi có khóa trùng với khóa cần tìm (nếu có). Đo độ hiệu quả: Số lần so sánh khóa cần tìm và khóa của các bản ghi Phân loại: Tìm kiếm nội (internal searching) Tìm kiếm ngoại (external searching) Chương 7: Tìm kiếm Bản ghi và khóa Bản ghi: Khóa Dữ liệu Khóa: So sánh được Thường là số Trích khóa từ bản ghi: So sánh các bản ghi Chương 7: Tìm kiếm Bản ghi và khóa trên C++ class Key { public: // Add any constructors and methods for key data. private: // Add declaration of key data members here. }; bool operator == (const Key &x, const Key &y); bool operator > (const Key &x, const Key &y); bool operator = (const Key &x, const Key &y); bool operator Chương 7: Tìm kiếm Hàm tìm kiếm Tham số vào: Danh sách cần tìm Khóa cần tìm Tham số ra: Vị trí phần tử tìm thấy (nếu có) Kết quả hàm: kiểu Error_code Tìm thấy: success Không tìm thấy: not_present Chương 7: Tìm kiếm Tìm tuần tự (sequential search) 5 Target key 7 13 5 21 6 2 8 15 0 1 2 3 4 5 6 7 position = 2 return success Số lần so sánh: 3 Chương 7: Tìm kiếm Tìm tuần tự - không tìm thấy 9 Target key 7 13 5 21 6 2 8 15 0 1 2 3 4 5 6 7 return not_present Số lần so sánh: 8 Chương 7: Tìm kiếm Tìm tuần tự - Mã C++ Error_code sequential_search(const List &the_list, const Key &target, int &position) /* Post: If an entry in the_list has key equal to target, then return success and the output parameter position locates such an entry within the list. Otherwise return not_present and position becomes invalid. */ { int s = ( ); for (position = 0; position Chương 7: Tìm kiếm Bản ghi và khóa Bản ghi: Khóa Dữ liệu Khóa: So sánh được Thường là số Trích khóa từ bản ghi: So sánh các bản ghi Chương 7: Tìm kiếm Bản ghi và khóa trên C++ class Key { public: // Add any constructors and methods for key data. private: // Add declaration of key data members here. }; bool operator == (const Key &x, const Key &y); bool operator > (const Key &x, const Key &y); bool operator = (const Key &x, const Key &y); bool operator <= (const Key &x, const Key &y); bool operator != (const Key &x, const Key &y); class Record{ public: operator Key( ); // implicit conversion from Record
