Ninja IT

Mảng

Mảng

Mảng là một danh sách các phần tử liên tiếp nhau cùng kiểu dữ liệu. Mảng tĩnh có số không thay đổi lúc biên dịch chương trình, còn mảng động có dữ liệu được khai báo trong Heap.

Vì các phần tử trong mảng được sắp xếp liên tiếp nhau nên thời gian truy cập một phần tử là như nhau O(1). Tương tự cập nhật cũng tốn thời gian là O(1).

Thêm và xóa một phần tử ở giữa mảng thì tốn thời gian là 0(n). Nên nếu thuật toán cần nhiều các thao tác thêm và xóa thì có thể dùng cấu trúc dữ liệu stack hoặc queue sử dụng danh sách liên kết. Cấu trúc stack hoặc queue sẽ có thời gian thêm và xóa là O(1).

Tìm kiếm trong mảng tốn thời gian trung bình là 0(n). Ví dụ sau tìm kiếm một phần tử trong mảng có độ dài là 10.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

const int LENGTH = 10;

// index     0  1  2  3  4  5  6  7  8  9
int arr[] = {5, 9, 0, 6, 4, 2, 7, 3, 1, 8};
int x = 3; // phần tử cần tìm
int foundIndex = -1; // -1 là không tìm thấy

for (int i = 0; i < LENGTH; i++) {
  if (arr[i] == x) {
    foundIndex = i;
    break; // dừng vòng lặp ngay khi tìm thấy
  }
}

printf("%d", foundIndex); // -> 7
return 0;

Tìm kiếm phần tử trong mảng được sắp xếp

Một mảng được sắp xếp thì tìm kiếm một phần tử sẽ tốn thời gian là O(log(n)). Thuật toán này tên là tìm kiếm nhị phân1. Cách làm ở đây là chúng ta sẽ tìm ở giữa mảng, sau đó chúng ta sẽ tìm nữa bên trái hoặc nữa bên phải khi số cần tìm nhỏ hơn hoặc lớn hơn vị trí ở giữa.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

int findOrderedArray(int *arr, int left, int right, int x) {
  if (left > right) { // điều kiện dừng
    return -1;
  }
  int mid = (left + right) / 2;
  if (x == arr[mid]) {
    return mid;
  } else if (x < arr[mid]) {
    return findOrderedArray(arr, left, mid - 1, x); // tìm nửa trái
  } else {
    return findOrderedArray(arr, mid + 1, right, x); // tìm nửa phải
  }
}
int main() {
  const int LENGTH = 10;
  // index     0  1   2   3   4   5   6   7   8   9
  int arr[] = {0, 12, 15, 18, 32, 40, 48, 57, 59, 81};
  int x = 59; // phần tử cần tìm
  int foundIndex = findOrderedArray(arr, 0, LENGTH, x);
  printf("%d", foundIndex); // -> 8
}

Hoặc có thể dùng giải thuật khử đệ quy như sau:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

int findOrderedArray(int *arr, int arrLength, int x) {
  int left = 0, right = arrLength;
  while (left <= right) {         // điều kiện dừng
    int mid = (left + right) / 2; // lấy phần tử ở giữa
    if (x == arr[mid]) {          // nếu tìm thấy
      return mid;                 // trả về kết quả
    } else if (x < arr[mid]) {    // nếu ở bên trái
      right = mid - 1;            // thu hẹp khoảng tìm về trái
    } else {
      left = mid + 1;             // thu hẹp khoảng tìm về bên phải
    }
  }
  return -1; // trường hợp không tìm thấy
}

  1. Tìm kiếm nhị phân wikipedia ↩︎