Giải thuật tìm kiếm tuyến tính

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!