tailieunhanh - Chương 2.1. Giải thuật tìm kiế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 *Cài đặt được giải thuật tìm kiếm | Chương . Giải thuật tìm kiế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++ Hãy liệt kê những phần mềm trên máy tính có dùng chức năng 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. Có 2 giải thuật thường được áp dụng: Tìm tuyến tính và tìm nhị phân. Để đơn giản cho việc minh họa, ta đặc tả như sau: Tập dữ liệu được lưu trữ là dãy số a1, a2, . ,aN. | Chương . Giải thuật tìm kiế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++ Hãy liệt kê những phần mềm trên máy tính có dùng chức năng 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. Có 2 giải thuật thường được áp dụng: Tìm tuyến tính và tìm nhị phân. Để đơn giản cho việc minh họa, ta đặc tả như sau: 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; a1 a2 a3 a4 a5 an-1 aN Ý tưởng Tiến hành so sánh x lần lượt 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ó khóa 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 Minh họa tìm x =25 Chưa hết mảng 7 5 12 41 10 32 13 9 15 3 1 2 3 4 5 6 7 8 9 10 7 5 12 41 10 32 13 9 15 3 1 2 3 4 5 6 7 8 9 10 10 10 25 Chưa hết mảng Đã tìm thấy tại vị trí 5 Đã hết mảng Giả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. Cài đặt int LinearSearch(int a[], int N, int x) { int i=0; while ((i