Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 2 Giải thuật tìm kiếm, cung cấp cho người học những kiến thức như: Giới thiệu bài toán tìm kiếm; Tìm kiếm tuyến tính; Tìm kiếm nhị phân. Mời các bạn cùng tham khảo! | KHOA CÔNG NGHỆ THÔNG TIN CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT BÀI 2 GIẢI THUẬT TÌM KIẾM GVGD 1. THS. TRẦN CÔNG THANH HỌC KỲ I NĂM HỌC 2020-2021 KHÓA 01. Giới thiệu bài toán tìm kiếm kiếm tuyến tính 03. Tìm kiếm nhị phân NỘI 04. Bài tập DUNG 05. 06. 1. Giới thiệu bài toán tìm kiếm Tìm kiếm là quá trình xác định một đối tượng nào đó trong một tập các đối tượng. Kết quả trả về Đối tượng tìm được nếu có Chỉ số nếu có xác định vị trí của đối tượng trong tập đó. 感谢您下载包图网平台上提供的PPT作品 为了您和包图网以及原创作者的利益 请勿复制 传播 销售 否则将承担法律责任 包图网将对作品进行维权 按照传播下载次数进行十倍的索取赔偿 Việc tìm kiếm dựa theo một trường nào đó của đối tượng trường này là khóa key của việc tìm kiếm. Ví dụ Tìm sinh viên có họ tên X trong DSSV. SV MaSV HoTen DiaChi Khoá Kết quả trả về 4 KHOA CÔNG NGHỆ THÔNG TIN 1. Giới thiệu bài toán tìm kiếm Bài toán được mô tả như sau Tập dữ liệu được lưu trữ là dãy a1 a2 . an. Giả sử chọn cấu trúc dữ liệu mảng để lưu trữ dãy số này trong bộ nhớ chính có khai báo int a n Khóa cần tìm là x int x 感谢您下载包图网平台上提供的PPT作品 为了您和包图网以及原创作者的利益 请勿复制 传播 销售 否则将承担法律责任 包图网将对作品进行维权 按照传播下载次数进行十倍的索取赔偿 Tìm kiếm Tìm kiếm tuyến tính Tìm kiếm nhị phân Tập dữ Tập dữ liệu liệu đã bất kỳ được sắp xếp 5 KHOA CÔNG NGHỆ THÔNG TIN 1. Giới thiệu bài toán tìm kiếm Ý tưởng duyệt tuần tự từ phần tử đầu tiên lần lượt so sánh khóa tìm kiếm với khoá tương ứng của các phần tử trong danh sách. Cho đến khi gặp phần tử cần tìm hoặc đến khi duyệt hết danh sách. i 0 Các bước tiến hành như sau 感谢您下载包图网平台上提供的PPT作品 为了您和包图网以及原创作者的利益 请勿复制 传播 销售 否则将承担法律责任 包图网将对作品进行维权 按照传播下载次数进行十倍的索取赔偿 S i lt Không tìm thấy n Đ Đ a i Tìm thấy x S i i 1 6 KHOA CÔNG NGHỆ THÔNG TIN 2. Tìm kiếm tuyến tính Linear Search Ý tưởng Lần lượt so sánh x với phần tử thứ nhất thứ hai . của mảng a cho đến khi gặp được phần tử cần tìm hoặc hết mảng 感谢您下载包图网平台上提供的PPT作品 为了您和包图网以及原创作者的利益 请勿复制 传播 销售 否则将承担法律责任 包图网将对作品进行维权 按照传播下载次数进行十倍的索取赔偿 7 KHOA CÔNG NGHỆ THÔNG TIN 2. Tìm kiếm tuyến tính Ví dụ Cho dãy số a giá trị tìm X 8 12 2 5 8 1 6
