Bài giảng Cấu trúc dữ liệu: Chương 2 - ThS. Võ Quang Hoàng Khang

Chương 2 trang bị cho người học những kiến thức về giải thuật tìm kiếm. Mục tiêu của chương này gồm: Xác định được vai trò của tìm kiếm và sắp xếp trong hệ thống thông tin, nắm vững và minh họa được giải thuật tìm kiếm tuyến tính và tìm kiếm nhị phân trên mảng một chiều, cài đặt được giải thuật tìm kiếm bằng ngôn ngữ C/C++.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu: Chương 2 - ThS. Võ Quang Hoàng Khang Chương 2.1. Giải thuật tìm kiếmVõ Quang Hoàng KhangEmail: vqhkhang@gmail.com 1Mục tiêuXác định được vai trò của tìm kiếm và sắp xếp trong hệ thống thông tinNắm vững và minh họa được giải thuật tìm kiếm tuyến tính và tìm kiếm nhị phân trên mảng một chiềuCài đặt được giải thuật tìm kiếm bằng ngôn ngữ C/C++ 2Suy nghĩ ? Tại sao hầu hết phần mềm phải có chứcnăng tìm kiếm và sắp xếp, mối quan hệ giữa tìm kiếm và sắp xếp? 3Nhu cầu tìm kiếm và sắp xếpThao tác tìm kiếm được sử dụng nhiều nhất trong các hệ lưu trữ và quản lý dữ liệu.Do dữ liệu lớn nên tìm ra giải thuật tìm kiếm nhanh chóng là mối quan tâm hàng đầu. Để đạt được điều này dữ liệu phải được tổ chức theo một thứ tự nào đó thì việc tìm kiếm sẽ nhanh chóng và hiệu quả hơn, vì vậy nhu cầu sắp xếp dữ liệu cũng được lưu ý.Tóm lại, bên cạnh những giải thuật tìm kiếm thì các giải thuật sắp xếp dữ liệu không thể thiếu trong hệ quản lý thông tin trên máy tính. 4Các giải thuật tìm kiếmCó 2 giải thuật thường được áp dụng: Tìm tuyến tính và tìm nhị phân.Đặc tả như sau: a1 a2 a3 a4 a5 … an-1 aN Tập dữ liệu được lưu trữ là dãy số 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]; Khoá cần tìm là x, được khai báo như sau: int x; 5Tìm kiếm tuyến tínhÝ 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 đã tìm hết mảng mà không thấy xMinh họa tìm x =10 10 Đã tìm Chưa thấyhếttại 7 5 12 41 10 32 13 9 15 3 vịmảng trí 5 1 2 3 4 5 6 7 8 9 10Minh họa tìm x =25 Chưa hết Đã hết 25 mảng mảng 7 5 12 41 10 32 13 9 15 3 1 2 3 4 5 6 7 8 9 10 6Giải thuậtBước 1: i = 1; // bắt đầu từ phần tử đầu tiên của dãyBước 2: So sánh a[i] với x, có 2 khả năng :a[i] = x : Tìm thấy. Dừnga[i] != x : Sang Bước 3.Bước 3: i = i+1; // xét tiếp phần tử kế trong mảng Nếu i >N: Hết mảng, không tìm thấy. Dừng Ngược lại: Lặp lại Bước 2. 7Nguyên tắc cài đặt hàm tìm kiếmNếu có xuất hiện phần tử có giá trị x thì trả về vị trí tìm đượcNgược lại thì trả về -1 8Cài đặtint TimTuyenTinh(int a[], int N, int x){ int i=0; while ((iCải tiếnDùng lính canh giúp giảm bớt phép so sánhMinh họa tìm x =10 10 7 5 12 41 10 32 13 9 15 3 10 1 2 3 4 5 6 7 8 9 10 11Minh họa tìm x = 25 25 7 5 12 41 10 32 13 9 15 3 25 25 1 2 3 4 5 6 7 8 9 10 11 10Cài đặtint TimTuyenTinh2(int a[],int N,int x)//cải tiến{ int i=0; a[N] = x; // thêm phần tử x sau mảng while (a[i]!=x ) i++; if (i==N) return -1; // tìm hết mảng else return i; // tìm thấy x tại vị trí i}Độ phức tạp tính toán cấp n: T(n)=O(n) 11Tìm kiếm nhị phânÝ tưởngÁp dụng đối với những dãy số đã có thứ tự.Tại mỗi bước tiến hành so sánh x với phần tử nằm ở vị trí giữa của dãy tìm kiếm hiện hành, dựa vào kết quả so sánh này để quyết định phạm vi tìm kiếm ở bước kế tiếp. 12Minh họa tìm x = 41 x x x 3 14 16 19 22 41 46 51 63 71 1 2 3 4 5 6 7 8 9 10 Tìm thấy x tại vị trí 6 l m m r m 13Minh họa tìm x = 45 x x x x 3 14 16 19 22 41 46 51 63 71 1 2 3 4 5 6 7 8 9 10 l m m r ...