Bài giảng 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@huflit.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 tuần tự 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ữ C2Nhu 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ếp3Vấn đề tìm kiếmDựa vào một phần thông tin được gọi là khoá (key)  tìm một mẫu tin (record) chứa các thông tin khác liên quan với khoá nàyCó thể có nhiều mẫu tin hoặc không có mẫu tin nào chứa khoá cần tìm4Đánh giá giải thuật tìm kiếmTìm kiếm thường là tác vụ tốn nhiều thời gian trong một chương trìnhTổ chức cấu trúc dữ liệu và giải thuật cho việc tìm kiếm ảnh hưởng lớn đến hiệu suất hoạt động của chương trìnhThông số đo chủ yếu là số lần so sánh khoá cần tìm với các mẫu tin khác5Phân loạiTìm kiếm nội và tìm kiếm ngoạiDữ liệu lưu trên thiết bị lưu trữ ngoài như đĩa hay băng từ: tìm kiếm ngoạiDữ liệu được lưu trữ trên bộ nhớ chính: tìm kiếm nội6Các giải thuật tìm kiếmCó 2 giải thuật thường được áp dụng: tìm tuần tự và tìm nhị phânĐặc tả:Tập dữ liệu được lưu trữ là dãy số gồm N phần tử a0, a1, ... ,an-1 Khai báo: int a[n];Khóa cần tìm: int x;7a0a1a2a3a4an-2an-1Tìm tuần tự (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ảng8Tìm tuần tựMinh họa tìm x =10Minh họa tìm x =259Chưa hết mảng7512411032139153012345678975124110321391530123456789101025Chưa hết mảngĐã tìm thấy tại vị trí 4Đã hết mảngGiải thuật Bước 1:   i = 0;         // 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-1: Hết mảng, không tìm thấy. Dừng Ngược lại: Lặp lại Bước 2. 10Nguyê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ề -1Hãy viết hàm tìm kiếm theo phương pháp tuần tự 11Vấn đề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 = 0; right = n-1; //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);22int main(){ srand((usigned int) time (NULL)); int a[MAX], n = 20, x, vt; TaoMang(a, n); XuatMang(a, n); printf( “Nhap gia tri can tim: “); scanf(“%d”, &x); vt=LinearSearch(a, n, x); if(vt==-1) printf(“Khong co phan tu can tim”); else printf(“Phan tu can tim tai vi tri: %d”, vt); return 0;}23void TaoMang(int a[], int n){ for(int i=0; i<n; i++) a[i]=rand()%N;}void XuatMang(int a[], int n){ for(int i=0; i<n; i++) printf(“%d “, a[i]);}24int LinearSearch(int a[], int n, int x){ int i=0; while ((i<n) && (a[i]!=x )) i++; if(i==n) return -1; else return i;}25Bài tập áp dụngViết chương trình tự động phát sinh ra mảng có giá trị ngẫu nhiên có thứ tự tăng dần; nhập vào giá trị cần tìm x; in ra vị trí xuất hiện của x (nếu có) và số lần so sánh với mỗi phương pháp tìm kiếm: tuyến tính và nhị phân26Bài tập lý thuyếtLT1_1: Cho dãy số sau: Cho biết vị trí tìm thấy và số lần so sánh để tìm được phần tử có giá trị x = 6 khi áp dụng giải thuật tìm kiếm: tuyến tính và nhị phân. LT1_2: Xây dựng giải thuật tìm kiếm phần tử có giá trị nhỏ nhất trong dãy số: Dùng mã tự nhiên, mã giả và lưu đồ.2734661216213441800123456789Q & A28