Bài giảng "Cấu trúc dữ liệu và thuật toán - Chương 6: Tìm kiếm" cung cấp cho người đọc các kiến thức: Tìm kiếm tuần tự và tìm kiếm nhị phân, cây nhị phân tìm kiếm, tìm kiếm xâu mẫu, bẳng băm,. nội dung chi tiết. | Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 6 - Trịnh Anh Phúc Chương 6 : Tìm kiếm Trịnh Anh Phúc 1 1 Bộ môn Khoa Học Máy Tính, Viện CNTT & TT, Trường Đại Học Bách Khoa Hà Nội. Ngày 28 tháng 4 năm 2014 Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc&dữTT, liệu Trường và giải thuật Đại Học Bách Khoa NgàyHà28Nội. tháng ) 4 năm 2014 1 / 82 Giới thiệu 1 Tìm kiếm tuần tự và tìm kiếm nhị phân Tìm kiếm tuần tự Tìm kiếm nhị phân 2 Cây nhị phân tìm kiếm Định nghĩa Biểu diễn cây nhị phân tìm kiếm Sắp xếp nhờ sử dụng BST Cây nhị phân tìm kiếm cân bằng 3 Tìm kiếm xâu mẫu Thuật toán trực tiếp Thuận toán Boyer-Moore Thuận toán Rabin-Karp Thuận toán Knuth-Morris-Pratt 4 Bảng băm (Mappping and Hashing) Đặt vấn đề Địa chỉ trực tiếp Hàm băm 5 Tổng kết Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc&dữTT, liệu Trường và giải thuật Đại Học Bách Khoa NgàyHà28Nội. tháng ) 4 năm 2014 2 / 82 Tìm kiếm tuần tự và tìm kiếm nhị phân Định nghĩa bài toán tìm kiếm Bài toán đặt ra Cho danh sách list[] và phần tử target, ta cần tìm vị trí i sao cho list[i] = target hoặc trả lại giá trị -1 nếu không có phần tử như vậy trong danh sách Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc&dữTT, liệu Trường và giải thuật Đại Học Bách Khoa NgàyHà28Nội. tháng ) 4 năm 2014 3 / 82 Tìm kiếm tuần tự và tìm kiếm nhị phân Tìm kiếm tuần tự (linear search or sequential search) Thuật toán tìm kiếm tuần tự được thực hiện theo ý tưởng sau đây : Bắt đầu từ phần tử đầu tiên, duyệt qua từng phần tử cho đến khi tìm được phần tử đích hoặc kết luận không tìm được. -7 9 -5 2 8 3 -4 Độ phức tạp : O(n) int linearSearch(dataArray list, int size, dataElem target){ int i; for(i = 0;i Tìm kiếm tuần tự và tìm kiếm nhị phân Tìm kiếm nhị phân (binary search) Điều kiện để thực hiện .
