[Thuật toán] Thuật toán tìm kiếm tuần tự

Tìm kiếm

Tìm kiếm là công việc quan trọng đối với các hệ thống tin học và có liên quan mật thiết với quá trình sắp xếp dữ liệu. Bài toán tìm kiếm tổng quát có thể được phát biểu như sau:
Cho một bảng gồm n bản ghi R1,R2,..., Rn. Với mỗi bản ghi (phần tử) Ri được tương ứng với 1 khoá ki (trường thứ I trong record). Hãy tìm bản ghi có giá trị bằng khoá X cho trước.
Nếu quá trình chúng ta tìm được bản ghi có giá trị khoá là X thì phép tìm kiếm được thoả (successful). Nếu không có giá trị nào thoả thì quá trình tím kiếm không thành công, sau quá trình này có thể xuất hiện thêm yêu cầu bổ sung thêm bản ghi mới có giá trị khoá là X vào thì giải thuật được gọi là tìm kiếm bổ sung.
Các thuật toán tìm kiếm cơ bản là: tìm kiếm tuần tự, tìm kiếm nhị phân, tìm kiếm nhanh,...

Xem thêm trên amazon

Tìm kiếm tuần tự

Ý tưởng thuật toán: Xét dãy số cần tìm có n phần tử: a[0], a[1], a[2]... a[n-1]. Giá trị cần tìm là x.

- Bắt đầu từ khoá đầu tiên, lần lượt so sánh khoá x với khoá tương ứng trong dãy.

- Quá trình tìm kiếm kết thúc khi tìm được khoá thoả mãn hoặc đi đến hết dãy hoặc gặp điều kiện dừng vòng lặp.Đây là kĩ thuật tìm kiếm cổ điển nhất trên 1 danh sách chưa được sắp xếp. Nội dung cơ bản của phương pháp này là duyệt từ phần tử thứ nhất cho tới bản ghi cuối cùng, và so sánh lần lượt với khoá X cần tìm, trong quá trình duyệt nếu có bản ghi trùng với giá trị của X thì chúng ta đưa ra vị trí của bản ghi trong dãy, nếu duyệt tới cuối cùng mà không có bản ghi nào trùng giá trị thì quá trình tìm kiếm không thành công.

Phân loại : giải thuật tìm kiếm

Cấu trúc dữ liệu:    danh sách

Độ phức tạp thời gian: O(n) khi phần tử tìm kiếm nằm cuối danh sách hoặc không có trong danh sách

Thời gian chạy tốt nhất: O(1) khi phần tử cần tìm nằm ngay đầu danh sách

Độ phức tạp không gian: O(n)

Chương trình cài đặt thuật toán hoàn toàn đơn giản.

C Code:

Select All | Show/Hide

1. #include    <stdio.h>
2. #include    <conio.h>
3. #include    <stdlib.h>
4. #include    <alloc.h>
5. #include    <dos.h>
6. int Sequential(int *, int, int);
7. void Init(int *, int);
8. void Init(int *A, int n){
9.     int i;
10.     printf("\n Tao lap day so:");
11.     for (i=0; i<n;i++){
12.         A[i]=random(1000);
13.         printf("%5d",A[i]);
14.     }
15.     delay(1000);
16. }
17. int Sequential(int *A, int x, int n){
18.     register i,temp;
19.     for (i=0; i<n ; i ++){
20.         if (A[i] == X)
21.             return(i);
22.     }
23.     return(-1);
24. }
25. void main(void){
26.     int *A,n, x, k;clrscr();
27.     printf("\n Nhap n="); scanf("%d",&n);
28.     printf("Nhap so can tim"); scanf("%d", &x);
29.     A=(int *) malloc(n*sizeof(int));
30.     k= Sequential(A,x,n);
31.     if ( k>=0)
32.         printf("\n %d o vi tri %d", x,k);
33.     else
34.         printf("\n %d khong co trong mang",x);
35.     free(A); getch();
36. }

Tìm hiểu thêm thuật toán sắp xếp cơ bản
Tìm hiểu thêm thuật toán tìm kiếm cơ bản