[1 DAY] Array Data Structure

Mảng (Array) là một cấu trúc dữ liệu cơ bản trong lập trình, cho phép lưu trữ và truy cập các phần tử theo thứ tự. Mảng được sử dụng để lưu trữ một tập hợp các giá trị cùng kiểu dữ liệu, và các phần tử của mảng có thể được truy cập thông qua chỉ số.

Các thuộc tính của mảng bao gồm:

• Kích thước (size): số lượng phần tử của mảng
• Chỉ số (index): vị trí của từng phần tử trong mảng, bắt đầu từ 0 đến kích thước mảng - 1
• Kiểu dữ liệu (data type): loại dữ liệu được lưu trữ trong mảng, ví dụ như số nguyên, số thực, chuỗi ký tự, hoặc đối tượng

Các thao tác phổ biến với mảng bao gồm:

• Khởi tạo mảng (Initialize an array): tạo một mảng mới với kích thước cụ thể và các giá trị ban đầu
• Truy cập phần tử (Access an element): lấy giá trị của một phần tử trong mảng bằng cách sử dụng chỉ số của nó
• Thay đổi phần tử (Modify an element): thay đổi giá trị của một phần tử trong mảng bằng cách sử dụng chỉ số của nó
• Thêm phần tử (Add an element): thêm một phần tử mới vào cuối mảng hoặc ở vị trí bất kỳ trong mảng
• Xóa phần tử (Remove an element): xóa một phần tử trong mảng bằng cách di chuyển các phần tử phía sau lên trước

Cấu trúc dữ liệu Arrays là gì?

Một mảng là một cấu trúc dữ liệu tuyến tính được sử dụng để thu thập các phần tử cùng kiểu dữ liệu và lưu trữ chúng tại các vị trí nhớ liền kề và kề nhau. Mảng hoạt động trên hệ thống chỉ mục bắt đầu từ 0 đến (n-1), trong đó n là kích thước của mảng.

Mảng là một loại cấu trúc dữ liệu, nhưng có một lý do khiến mảng trở nên phổ biến.

Làm sao để khởi tạo mảng?

Theo mặc định, mảng chưa được khởi tạo và không có phần tử nào của mảng được đặt thành bất kỳ giá trị nào. Tuy nhiên, để mảng hoạt động bình thường, việc khởi tạo mảng trở nên quan trọng. Khởi tạo mảng có thể được thực hiện bằng các phương pháp sau:

• Không truyền giá trị trong bộ khởi tạo (Passing no value within the initializer): Người ta có thể khởi tạo mảng bằng cách xác định kích thước của mảng và không truyền giá trị nào trong bộ khởi tạo.

int arr[ 5 ] = {  };

• Bằng cách chuyển các giá trị cụ thể trong bộ khởi tạo (By passing specific values within the initializer): Người ta có thể khởi tạo mảng bằng cách xác định kích thước của mảng và chuyển các giá trị cụ thể trong bộ khởi tạo.

int arr[ 5 ] = { 1, 2, 3, 4, 5 };

• Lưu ý: Số phần tử trong “{ }” phải nhỏ hơn hoặc bằng kích thước của mảng. Nếu số phần tử trong “{ }” nhỏ hơn kích thước của mảng thì các vị trí còn lại được tính là '0'.

int arr[ 5 ] = { 1, 2, 3 };

• Bằng cách chuyển các giá trị cụ thể trong bộ khởi tạo nhưng không khai báo kích thước (By passing specific values within the initializer but not declaring the size): Người ta có thể khởi tạo mảng bằng cách chuyển các giá trị cụ thể trong bộ khởi tạo và không đề cập cụ thể đến kích thước, kích thước được trình biên dịch diễn giải.

int arr[  ] = { 1, 2, 3, 4, 5 };

Mảng được hoạt động thế nào?

Mảng cho phép truy cập ngẫu nhiên vào các phần tử. Điều này làm cho việc truy cập các phần tử theo vị trí nhanh hơn. Do đó hoạt động như tìm kiếm, chèn và truy cập trở nên thực sự hiệu quả. Các phần tử của mảng có thể được truy cập bằng cách sử dụng các vòng lặp.

Thêm các phần tử trong Array

Chúng tôi cố gắng chèn một giá trị vào một vị trí chỉ mục mảng cụ thể, vì mảng cung cấp quyền truy cập ngẫu nhiên nên có thể thực hiện dễ dàng bằng cách sử dụng toán tử gán.

// Để chèn một giá trị = 10 tại vị trí chỉ số 2;
arr[ 2 ] = 10;

Độ phức tạp

• O(1) để chèn một phần tử
• O(N) để chèn tất cả các phần tử mảng [trong đó N là kích thước của mảng]

arr = [0, 0, 0]
 
arr[0] = 1
arr[1] = 2
arr[2] = 3
 
print(arr) // Output:

Truy cập các phần tử trong Array

Việc truy cập các phần tử của mảng trở nên vô cùng quan trọng, để thực hiện các thao tác trên mảng.

// Truy cập phần tử mảng ở vị trí chỉ số 2
return arr[ 2 ]

Độ phức tạp: O(1)

arr = [1, 2, 3, 4]

# Truy cập phần tử tại chỉ số 2
print(arr[2]) // Output: 3

Tìm kiếm các phần tử trong Array

Chúng tôi cố gắng tìm một giá trị cụ thể trong mảng, để làm được điều đó, chúng tôi cần truy cập tất cả các phần tử của mảng và tìm kiếm giá trị cụ thể.

// Tìm kiếm giá trị 2 trong mảng;
Loop from i = 0 to 5:
    check if arr[i] = 2:
        return true;

Độ phức tạp về thời gian: O(N), trong đó N là kích thước của mảng.

import array
 
gfg = array.array('i', [1, 2, 3, 4])
 
for gfg2 in gfg:
    print(gfg2) // Output: 1 2 3 4

Ở đây, giá trị 5 được in vì phần tử đầu tiên có chỉ số 0 và tại chỉ số 0, chúng tôi đã gán giá trị 5.