30/09/2018, 17:56

Thắc mắc về giải thuật LinearSearch trong C

Theo em nghĩ nếu như không có dòng a[n] = x; thì khi nhập X không nằm trong mảng thì vòng lặp while sẽ lặp vô hạn nhưng sao em chạy thì vẫn ra kết quả đúng. Mong các cao nhân giúp đỡ đa tạ

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>

void NhapMang(int a[], int n);
void XuatMang(int a[], int n);
int LinearSearch(int a[], int n, int x);
//int LinearSearch1(int a[], int n, int x);
//int LinearSearch2(int a[], int n, int x);

int main()
{
    int n, x;
    printf("Nhap so phan tu cua mang: ");
    scanf("%d", &n);
    int a[n];
    NhapMang(a,n);
    XuatMang(a,n);
    printf("
Nhap vao so X can tim kiem trong mang: ");
    scanf("%d", &x);
    int result1 = LinearSearch(a,n,x);
    if(result1 == -1)
        printf("khong thay X");
    else
        printf("Thay X o vi tri a[%d] khi duyet tu dau den cuoi mang", result1);
    //LinearSearch1(a,n,x);
    //LinearSearch2(a,n,x);
    getch();
    return 0;
}

void NhapMang(int a[], int n)
{
    srand((int)time(NULL));
    for(int i=0; i<n; i++)
        a[i] = rand()%50;
}

void XuatMang(int a[], int n)
{
    for(int i=0; i<n; i++)
    {
        if(i%10==0 && i!=0)
            printf("
");
        printf("%d	", a[i]);
    }
}

int LinearSearch(int a[], int n, int x)
{
    int i=0;
    //a[n] = x; phương pháp lính canh
    while (a[i] != x)
        i++;
    if(i<n) return i;
    return -1;
}
Gió viết 20:12 ngày 30/09/2018

Đó là vì trong mảng có giá trị x, nếu không có thì vô hạn

duong viết 20:09 ngày 30/09/2018

bạn chạy thử đi nếu X không có trong mảng thì nó vẫn in ra "khong thay X " chứ đâu có lặp vô hạn đâu bạn

minh tran viết 20:07 ngày 30/09/2018

while (a[i] != x)
i++;

vòng lặp này ko bao giờ thoát được nếu x ko có trong mảng

Lễ Bùi viết 20:12 ngày 30/09/2018

Trong C, bạn có thể truy cập phần từ ngoài vùng cấp phát của mảng, ví dụ như a[n], a[n+1], những vị trí này chứa những giá trị “rác”. Vòng lặp không vô hạn vì có thể “đằng sau” mảng (tức là gia trị từ a[n] trở đi) có một giá trị rác nào đó trùng với số cần tìm nhưng lại không nằm trong kích thước mảng thì hàm LinearSearch trả về -1. Nếu không có giá trị nào trùng thì vòng lặp vẫn có thể lặp vô hạn. Bạn thử in ra giá trị của biến i khi chạy xong vòng lặp thì sẽ rõ.

duong viết 19:58 ngày 30/09/2018

bạn chạy thử đi sẽ biết kết quả

duong viết 20:06 ngày 30/09/2018

Nếu không có giá trị nào trùng thì vòng lặp vẫn có thể lặp vô hạn

có khi nào xảy ra trường hợp này không nhỉ .

Lễ Bùi viết 20:13 ngày 30/09/2018

Mình chạy thử chục lần thì không thấy bị lặp vô hạn, chỉ có 2 khả năng:

  • Một là tìm thấy giá trị rác.
  • Hai là i tăng đến một gia trị nào đó (mình chạy thì là i = 3188), thì “đụng” đến vùng nhớ đặc biệt nào đó gây xung đột (access violation reading…) kết quả dẫn đến chương trình dừng lại không chạy được nữa.
Bài liên quan
0