Giải Thuật Tìm Kiếm Tuyến Tính

Trang chủ » độ Phức Tạp Của Thuật Toán Tìm Kiếm Tuyến Tính » Giải Thuật Tìm Kiếm Tuyến Tính

Có thể bạn quan tâm

Sign in Sign in Welcome!Log into your account your username your password Forgot your password? Password recovery Recover your password your email Search Sunday, December 22, 2024
  • Sign in / Join
Sign in Welcome! Log into your account your username your password Forgot your password? Get help Password recovery Recover your password your email A password will be e-mailed to you. sinhvientot.net sinhvientot.net sinhvientot.net sinhvientot.net Home Lập trình C/C++ Giải thuật tìm kiếm tuyến tính Facebook Twitter Pinterest WhatsApp

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!

RELATED ARTICLESMORE FROM AUTHOR

C/C++

Sự khác nhau giữa Inline function và Macro trong C

C/C++

Trong ngôn ngữ C/C++ có bao nhiêu vùng nhớ (Memory layout)

C/C++

Cấu trúc dữ liệu danh sách nhân viên

C/C++

Tổng quan File trong C

C/C++

Cấu trúc kiểu dữ liệu sinh viên

C/C++

Cấu trúc mô tả một điểm trên tọa độ xOy

6 COMMENTS

  1. 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

    Log in to leave a comment

    • co the do no so sanh ko khop, ban thu debug xem

      Log in to leave a comment

  2. Bài 2 lỗi ko chạy đc ạ

    Log in to leave a comment

    • Lỗi gì vậy bạn ?

      Log in to leave a comment

  3. 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 ạ ?

    Log in to leave a comment

    • ủa ví dụ chạy bình thường mà ta. em copy code lên đây xem!

      Log in to leave a comment

LEAVE A REPLY Cancel reply

Log in to leave a comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Danh sách các bài học

Các kiểu dữ liệu cơ bản trong ngôn ngữ C/C++

Mr Good - April 16, 2016 0

Hướng dẫn Tạo Project Visual C++ trong Visual Studio 2012

April 16, 2016

Biến-Hằng-Câu lệnh và biểu thức trong C/C++

April 16, 2016

Cấu trúc IF-ELSE

April 16, 2016

Cấu trúc switch – case

April 16, 2016

Vòng lặp For

April 16, 2016

Cấu trúc While, Do-while

April 16, 2016

Cách sử dụng hàm trong lập trình

April 16, 2016

Mảng một chiều

April 16, 2016 Load more

Bài viết mới nhất

Download

Download Cisco Packet Tracer

Windows 10

Hướng dẫn cài đặt webserver trên localhost để chạy wordpress

HPE

Hướng dẫn cấu hình IP ILO máy chủ HP DL380 Gen10

CentOS

CentOS 8 – Giới thiệu về hệ điều hành Linux (P1)

Load more © Copyright 2016, All Rights Reserved. Donations are always appreciated! MEW: 0x296f1a39d5Ca3cb83C76724eA38af3B90B90109D MORE STORIES

Giới thiệu các phím tắt trên Window 10

Nguyễn Quí Đức - September 12, 2016 0

ASP.NET – Tìm hiểu ASP.NET 4.5 Web Forms

MUNI - August 23, 2016 6

Từ khóa » độ Phức Tạp Của Thuật Toán Tìm Kiếm Tuyến Tính