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

Share:

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,...
Tìm kiếm tuần tự - tinhoccoban.net

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.


Chương trình cài đặt thuật toán hoàn toàn đơn giản.
C Code:
  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<; 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. }