Cấu trúc dữ liệu và giải thuật - Chương 2: Giải thuật tìm kiếm

Chương 2.1. Giải thuật tìm kiếmTrần Minh TháiEmail: minhthai@itc.edu.vnWebsite: www.minhthai.edu.vn 1Mục tiêuXác định được vai trò của tìm kiếm và sắp xếp trong hệ thống thông tinNắ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ềuCài đặt được giải thuật tìm kiếm bằng ngôn ngữ C/C++2Suy nghĩ3 Tại sao hầu hết phần mềm phải có chức nă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??Nhu cầu tìm kiếm và sắp xếpTìm kiếm: Có trong hầu hết trong các hệ thống thông tinMuốn tìm kiếm nhanh và hiệu quả  dữ liệu có thứ tự  sắp xếp4Các giải thuật tìm kiếmCó 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ả:Tập dữ liệu được lưu trữ là dãy số a1, a2, ... ,aN. Khai báo: int a[N];Khóa cần tìm: int x;5a1a2a3a4a5an-1aNTì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ảng6Tìm kiếm tuyến tínhMinh họa tìm x =10Minh họa tìm x =257Chưa hết mảng751241103213915312345678910751241103213915312345678910101025Chưa hết mảngĐã tìm thấy tại vị trí 5Đã hết mảngGiải thuật Bước 1:   i = 1;         // bắt đầu từ phần tử đầu tiên của dãy Bướ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. 8Nguyên tắc cài đặt hàm tìm kiếmNếu có xuất hiện phần tử có giá trị x thì trả về vị trí tìm đượcNgược lại thì trả về -19Cài đặt int LinearSearch(int a[], int N, int x){ int i=0; while ((i r: Kết thúc: Không tìm thấyGiải thuậtBước 1: left = 1; right = N; //tìm kiếm tất cả các phần tử Bước 2: mid = (left+right)/2; // lấy mốc so sánh So sánh a[mid] với x, có 3 khả năng : a[mid] = x: Tìm thấy. Dừng a[mid] > x: //tìm tiếp x trong dãy con aleft .. amid -1 right =mid - 1;a[mid] #include #include#define MAX 1000void TaoMang(int a[], int N);void XuatMang(int a[], int N);int LinearSearch(int a[], int N, int x);20void main(){ srand((usigned int) time (NULL)); int a[MAX], N = 20, x, kq; TaoMang(a, N); XuatMang(a, N); cout>x; kq=LinearSearch(a, N, x); if(kq==-1) coutx  xét trái)l=1, r=4m=(l+r)/2=2(a[m]=4)  xCập nhật l=m+1=3(a[m]N thì trả về giá trị vt, kết thúc; Bước 3: Nếu a[i]<a[vt] thì vt=i; i=i+1; Lặp lại Bước 2;29Bài tập lý thuyết – Hướng dẫn LT1_2Input: Mảng số nguyên a, kích thước nOutput: vt: vị trí phần tử có giá trị nhỏ nhấtPseudocode: i=2, vt=1; WHILE i ≤ N DO IF a[i]<a[vt] THEN vt=i; i=i+1; END WHILE RETURN vt;30Bài tập lý thuyết – Hướng dẫn LT1_2Flow Chart: 31Q & A32