Trên thực tế, mỗi khi khai thác và sử dụng dữ liệu chúng ta luôn phải thực hiện thao tác là tìm kiếm. Nhưng để tìm kiếm có hiệu quả thì chúng ta phải có một giải thuật hợp lí. Hôm nay chúng ta sẽ tìm hiểu giải thuật đầu tiên đó là tìm kiếm tuyến tính.
Ý tưởng:
Giải thuật chính của tìm kiếm tuyến tính chính là: so sánh phần tử cần tìm với tất cả các phần tử có trong mảng hoặc danh sách cần tìm. Chạy từ phần tử đầu đến cuối và so sánh từng đôi một, nếu bằng thì thông báo có, ngược lại nếu đã đi hết dãy mà vẫn chưa có phần tử nào thõa mãn thì cho kết quả là không tìm thấy.
Giải thuật:
Bước 1: Khởi tạo biến i và gán biến i bằng 0;
Bước 2: so sánh a[i] với giá trị cầm tìm.
+ Nếu tìm được giá trị a[i] bằng giá trị cần tìm thì dừng lại và dừng. Ngược lại
+ Nếu a[i] khác giá trị cần tìm thì sang bước 3
Bước 3: Tăng i lên một đơn vị, nếu i bằng số phần tử trừ 1 của mảng thì dừng lại và cho kết quả là không tìm thấy. Ngược lại quay lại bước 2.
Ví dụ: Cho dãy A gồm các phần tử: 11 4 3 9 8 0 2 45. Dùng giải thuật tìm kiếm tuyến tính để tìm xem có phần tử 8 nằm ở trong mảng hay không.
Bước 1: gán i=0.
Bước 2: so sánh a[0]= 11 != 8. Tăng i lên một đơn vị.
Bước 3: i=1 < n-1 (n = 8). Quay lại bước 2.
So sánh a[1] = 4 !=8. Tăng i lên một đơn vị .
Lặp lại Bước 3: i=2 < n-1 (n = 8). Quay lại bước 2.
So sánh a[2] = 3 !=8. Tăng i lên một đơn vị .
Lặp lại Bước 3: i=3 < n-1 (n = 8). Quay lại bước 2.
So sánh a[3] = 9 !=8. Tăng i lên một đơn vị .
Lặp lại Bước 3: i=4 < n-1 (n = 8). Quay lại bước 2.
So sánh a[4] = 8 = 8. Nên kết thúc và tìm được x ở vị trí số a[4].
Ngoài việc tìm kiếm trong mảng số chúng ta còn có thể áp dụng giải thuật tìm kiếm cho mảng, danh sách với cấu trúc dưới dạng struct.
Ví dụ: Cho danh sách sinh viên với với cấu trúc: mã sinh viên, họ, tên, năm sinh.
Ma SV Ho Ten NamSinh
2001140442 Nguyen Tuan 1996
2001140443 Le Huyen 1996
2001140444 Nguyen Phat 1996
2001140445 Tran An 1996
2001140446 Phan Tran 1996
Hãy tìm sinh viên có tên Phat.
Tương tự như dãy của mảng số nguyên ở ví dụ 1. Ta đi qua lần lượt các phần tử, ở đây chúng ta tạm đặt cấu trúc SinhVien và gọi là SV và mảng a[], khi đó ta xét a[i].Ten==Phat.
Với i=0 thì a[0].Ten == Tuan != Phat nên ta tăng i lên một đơn vị và i<n-1 nên
i=1 thì a[1].Ten == Huyen !Phat nên tăng i lên một đơn vị và i<n-1 nên.
i=2 thì a[2].Ten == Phat == Phat nên dừng lại và cho kết quả là tìm thấy. Code về ví dụ này mình sẽ viết ở phần dưới.
Code C/C++
Code tổng quát giải thuật:
int TimKiemTuyenTinh(int a[], int n, int x) { for (int i = 0; i < n;i++) if (a[i] == x) return 1; return 0; }
Code ví dụ 1.
void NhapMang(int a[], int &n) { printf("Cho biet so phan tu cua mang: "); scanf("%d", &n); for (int i = 0; i<n; i++) { printf("Gia tri phan tu a[%d]=", i); scanf("%d", &a[i]); } } void XuatMang(int a[], int n) { for (int i = 0; i<n; i++) printf("%4d", a[i]); } int TimKiemTuyenTinh(int a[], int n, int x) { for (int i = 0; i < n;i++) if (a[i] == x) return 1; return 0; } #define Max 100 void main() { int A[Max]; int N; int X; NhapMang(A, N); printf("Nhap phan tu can tim"); scanf("%d", &X); int b=TimKiemTuyenTinh(A, N, X); if (b == 1) printf("%d co trong mang",X); else { printf("%d khong co trong mang", X); } getch(); }
Kết quả:
Cho biet so phan tu cua mang: 8
Gia tri phan tu a[0]=11
Gia tri phan tu a[1]=4
Gia tri phan tu a[2]=3
Gia tri phan tu a[3]=9
Gia tri phan tu a[4]=8
Gia tri phan tu a[5]=0
Gia tri phan tu a[6]=2
Gia tri phan tu a[7]=45
Nhap phan tu can tim 8
8 co trong mang
Code ví dụ về Struct
#include<stdio.h> #include<conio.h> #define Max 100 struct SinhVien { char Ma[10]; char Ho[10]; char Ten[10]; int NamSinh; }; void NhapMangSV(SinhVien a[], int &n); void XuatMangSV(SinhVien a[], int n); void NhapMangSV(SinhVien a[], int &n) { do{ printf("Cho biet so Sinh vien: "); scanf("%d", &n); } while (n <= 0); for (int i = 1; i <= n; i++) { printf("Thong tin Sinh vien thu %d la: \n", i); printf("Ma so: \n"); fflush(stdin); gets(a[i].Ma); printf("Ho :\n"); fflush(stdin); gets(a[i].Ho); printf("Ten :\n"); fflush(stdin); gets(a[i].Ten); printf("Nam sinh :\n"); scanf("%d", &a[i].NamSinh); } } int TimSV(SinhVien a[], int n, char ten[10]) { for (int i = 0; i < n; i++) if (a[i].Ten == ten) return 1; return 0; } void main() { SinhVien A[100]; int N; int X; char TEN[10]; NhapMangSV(A, N); printf("Nhap ten SV can tim"); fflush(stdin); gets(TEN); int y=TimSV(A, N, TEN); if (y == 1) printf("Co sinh vien ten %s trong danh sach", TEN); else { printf("Khong co sinh vien %s trong danh sach", TEN); } getch(); }
Trên đây là giải thuật cũng như các ví dụ đơn giản nhất để các bạn làm quen với bài toán tìm kiếm. Chúc các bạn thành công!
dạ cho em xin hỏi tại sao khi em dùng code nó chạy rất tốt nhưng khi em nhập tên sinh viên cần tìm thì luôn không tìm thấy ạ . em xin cảm ơn
co the do no so sanh ko khop, ban thu debug xem
Bài 2 lỗi ko chạy đc ạ
Lỗi gì vậy bạn ?
Cho em hỏi trong hàm Tìm kiếm tuyến tính trên bài ví dụ có lỗi lúc chạy thì nó chỉ xét cái giá trị đầu tiên và xuất ra màn hình mà nó không chạy tiếp đến hết mảng thì phải sửa sao ạ ?
ủa ví dụ chạy bình thường mà ta. em copy code lên đây xem!