Mảng

4.1 Định nghĩa mảng và các thuộc tính của nó

Mảng — là một cấu trúc dữ liệu, đại diện cho tập hợp có thứ tự của các phần tử cùng loại, nằm trong các ô bộ nhớ liền kề nhau. Mỗi phần tử của mảng có chỉ mục riêng biệt, được sử dụng để truy cập đến nó.

Đây là một mảng đơn giản kích thước 4, chứa các phần tử (1, 2, 3 và 4).

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

• Kích thước cố định: Kích thước của mảng được xác định khi tạo ra và không thể thay đổi trong quá trình chạy chương trình.
• Sự đồng nhất của các phần tử: Tất cả các phần tử của mảng phải có cùng loại (ví dụ: số nguyên, chuỗi).
• Bố trí tuần tự trong bộ nhớ: Các phần tử của mảng được lưu trữ trong các ô bộ nhớ liền kề, cho phép truy cập nhanh theo chỉ mục.
• Truy cập nhanh theo chỉ mục: Truy cập đến bất kỳ phần tử nào của mảng diễn ra trong thời gian cố định O(1).

4.2 Ví dụ về sử dụng mảng

Hãy xem xét các ví dụ về việc sử dụng mảng mà bạn có thể đã biết:

Lưu trữ dữ liệu có độ dài cố định

Các ngày trong tuần, các tháng trong năm:

# Tạo mảng với các ngày trong tuần
days_of_week = ["Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"]
print(days_of_week[2])  # Kết quả: Wednesday

Ma trận và mảng đa chiều

Ma trận 3x3:

# Tạo ma trận 3x3
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
print(matrix[1][1])  # Kết quả: 5

Sử dụng trong thuật toán sắp xếp

Sắp xếp mảng số:

# Sắp xếp mảng số
numbers = [5, 2, 9, 1, 5, 6]
numbers.sort()  # Sắp xếp mảng
print(numbers)  # Kết quả: [1, 2, 5, 5, 6, 9]

Bộ đệm để lưu trữ dữ liệu tạm thời

Bộ đệm để đọc dữ liệu từ file:

# Tạo bộ đệm kích thước 1024 byte
buffer = [0] * 1024
print(len(buffer))  # Kết quả: 1024

4.3 Các thao tác cơ bản với mảng

Quan trọng! Lớp list trong Python là mảng động, nó có thể thay đổi kích thước trong quá trình hoạt động. Bạn sẽ tìm hiểu chi tiết về mảng động trong vài bài giảng tới.

Các thao tác cơ bản: truy cập theo chỉ mục, chèn, xóa

Truy cập theo chỉ mục

Truy cập đến phần tử của mảng thực hiện bằng cách sử dụng chỉ mục, chỉ định vị trí của nó.

# Truy cập các phần tử của mảng theo chỉ mục
arr = [10, 20, 30, 40, 50]
print(arr[2])  # Kết quả: 30
print(arr[-1])  # Kết quả: 50 (phần tử cuối cùng)

Chèn

Chèn phần tử vào mảng có thể yêu cầu dịch chuyển tất cả các phần tử tiếp theo để tạo chỗ cho phần tử mới.

Ví dụ (chèn phần tử vào giữa mảng):

# Chèn phần tử vào mảng
arr = [10, 20, 30, 40, 50]
arr.insert(2, 25)  # Chèn 25 vào vị trí 2
print(arr)  # Kết quả: [10, 20, 25, 30, 40, 50]

Xóa

Xóa phần tử khỏi mảng có thể yêu cầu dịch chuyển tất cả các phần tử tiếp theo để lấp đầy khoảng trống.

Ví dụ (xóa phần tử):

# Xóa phần tử khỏi mảng
arr = [10, 20, 30, 40, 50]
arr.pop(2)  # Xóa phần tử ở vị trí 2
print(arr)  # Kết quả: [10, 20, 40, 50]

4.4 Ưu điểm và nhược điểm của việc sử dụng mảng

Xem xét các ưu điểm và nhược điểm của việc sử dụng mảng:

Ưu điểm:

• Truy cập nhanh theo chỉ mục: Truy cập đến bất kỳ phần tử nào của mảng diễn ra trong thời gian cố định O(1), làm cho mảng rất hiệu quả cho việc đọc dữ liệu.
• Đơn giản dễ thực hiện: Mảng dễ hiểu và sử dụng, dễ dàng thực hiện và áp dụng trong các bài toán khác nhau.
• Chi phí phụ thấp: Mảng chiếm ít bộ nhớ hơn so với các cấu trúc dữ liệu phức tạp hơn, như danh sách liên kết.

Nhược điểm:

• Kích thước cố định: Kích thước của mảng được xác định khi tạo ra và không thể thay đổi. Điều này có nghĩa là cần phải biết kích thước cần thiết của mảng trước hoặc sử dụng mảng động, có thể mở rộng khi cần thiết.
• Chi phí chèn và xóa: Chèn và xóa phần tử có thể tốn thời gian vì cần dịch chuyển các phần tử. Trong trường hợp xấu nhất, chèn hoặc xóa phần tử ở giữa mảng mất thời gian O(n).
• Sử dụng bộ nhớ không hiệu quả: Nếu mảng không được sử dụng hết, các ô bộ nhớ còn lại sẽ không được sử dụng, có thể dẫn đến sử dụng bộ nhớ không hiệu quả.