Đang chuẩn bị liên kết để tải về tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật (Data Structures and Algorithms): Chương 7 - GV. Ngô Công Thắng

Bài giảng Cấu trúc dữ liệu và giải thuật (Data Structures and Algorithms) - Chương 7: Giải thuật tìm kiếm. Nội dung chính của chương gồm có: Bài toán tìm kiếm, tìm kiếm tuần tự (sequential searching), tìm kiếm nhị phân trên mảng, tìm kiếm nhị phân trên cây. Mời các bạn cùng tham khảo! | 28 04 22 Chương 7 Giải thuật tìm kiếm 1. Bài toán tìm kiếm Bài toán tìm kiếm Cho dãy khóa k là các số nguyên có n phần tử. Tìm khóa có giá trị bằng x cho trước. Gọi x là khoá tìm kiếm hay giá trị tìm kiếm. Công việc tìm kiếm sẽ hoàn thành khi có một trong 2 tình huống sau xảy ra 1 1- Tìm được khóa có giá trị bằng x. 2- Không tìm được khóa nào có giá trị bằng x. Sau phép tìm kiếm không thấy nếu có yêu cầu bổ sung khoá x vào dãy khóa thì giải thuật này gọi là Tìm kiếm có bổ sung . 2 1 28 04 22 2. Tìm kiếm tuần tự Sequential searching 2.1. Phương pháp Đây là giải thuật đơn giản cổ điển. Ý tưởng giải thuật Bắt đầu từ khóa thứ nhất lần lượt so sánh khoá tìm kiếm x với các khóa trong dãy khóa cho đến khi tìm thấy hoặc đã hết dãy khóa mà chưa thấy. Giải thuật Cho dãy khoá k có n phần tử lưu trữ trên mảng một chiều k có n ô nhớ với chỉ số từ 1 đến n. Tìm khoá có giá trị bằng x nếu tìm thấy thì trả về thứ tự của khoá nếu không tìm thấy thì trả về 0. 3 Minh họa ý tưởng k 8 10 2 5 7 4 1 1 2 3 4 n 7 x 5 4 2 28 04 22 Function sequenceSearch k n x 1. Khởi tạo i 1 k n 1 x 2. Tìm kiếm trong dãy While k i x Do i i 1 3. Trả về kết quả tìm kiếm If i n 1 then Return 0 Esle Return i Return 5 6 3 28 04 22 3. Tìm kiếm nhị phân trên mảng 3.1 Phương pháp Phương pháp tìm kiếm thực hiện trên dãy khóa đã sắp xếp tăng dần - Điều kiện dãy khóa trên mảng sắp xếp tăng dần. - Tương tự như tra tìm từ trong từ điển hoặc danh bạ điện thoại. Chỉ khác là trong tra cứu ta chọn từ ngẫu nhiên còn trong tìm kiếm nhị phân luôn chọn khoá ở giữa dãy khoá. - Giả sử có dãy khoá kL . . . kR đã được sắp xếp tăng dần có khoá ở giữa là km với m L R div 2 7 Tìm kiếm sẽ kết thúc nếu x km Nếu xkm tìm kiếm sẽ được thực hiện tiếp với km 1 . . . kR với cách tương tự. Qúa trình tìm kiếm kết thúc khi tìm thấy một khoá mong muốn hoặc dãy khoá rỗng không tìm thấy . 8 4 28 04 22 Minh họa ý tưởng k 1 3 5 10 17 24 31 1 2 3 4 5 6 n 7 x 3 m 1 7 div 2 4 k m 10 9 Giải thuật Cho dãy k gồm n khoá sắp xếp theo thứ tự tăng dần. Tìm .