Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 6

Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 6 Tìm kiếm gồm các nội dung chính được trình bày như sau: 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,...
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 6Chương 6 : Tìm kiếmTrịnh Anh Phúc1 Bộ1mô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 30 tháng 11 năm 2015Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, Viện CNTT & TT, Trường thuậtCấu trúc dữ liệu và giải Đại Học Bách Khoa Hà Nội. ) 11 năm 2015Ngày 30 tháng1 / 96Giới thiệu12345Tìm kiếm tuần tự và tìm kiếm nhị phânTìm kiếm tuần tựTìm kiếm nhị phânCây nhị phân tìm kiếmĐịnh nghĩaBiểu diễn cây nhị phân tìm kiếmSắp xếp nhờ sử dụng BSTCây nhị phân tìm kiếm cân bằng AVLBảng băm (Mappping and Hashing)Đặt vấn đềĐịa chỉ trực tiếpHàm bămTìm kiếm xâu mẫuThuật toán trực tiếpThuận toán Rabin-KarpThuận toán Knuth-Morris-PrattThuận toán Boyer-MooreTổng kếtTrịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, Viện CNTT & TT, Trường thuậtCấu trúc dữ liệu và giải Đại Học Bách Khoa Hà Nội. ) 11 năm 2015Ngày 30 tháng2 / 96Tìm kiếm tuần tự và tìm kiếm nhị phânĐịnh nghĩa bài toán tìm kiếmBài toán đặt ra Cho danh sách list[0...n-1] và phần tử target, ta cần tìmvị 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áchTrịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, Viện CNTT & TT, Trường thuậtCấu trúc dữ liệu và giải Đại Học Bách Khoa Hà Nội. ) 11 năm 2015Ngày 30 tháng3 / 96Tìm kiếm tuần tự và tìm kiếm nhị phânTì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 đượcphầ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