Bỏ qua

Mảng

Một mảng (array) là một cấu trúc dữ liệu tuyến tính (linear data structure) lưu trữ các phần tử cùng kiểu trong vùng nhớ liên tục (contiguous memory space). Vị trí của một phần tử trong mảng được gọi là chỉ số (index) của phần tử đó. Hình bên dưới minh họa các khái niệm chính và phương thức lưu trữ của mảng.

Định nghĩa và phương thức lưu trữ mảng

Các thao tác mảng thông thường

Khởi tạo mảng

Chúng ta có thể chọn giữa hai phương thức khởi tạo mảng dựa trên nhu cầu của mình: có hoặc không có giá trị khởi tạo. Khi không xác định giá trị khởi tạo, hầu hết các ngôn ngữ lập trình sẽ khởi tạo các phần tử mảng về giá trị \(0\):

array.py
# Khởi tạo mảng
arr: list[int] = [0] * 5  # [ 0, 0, 0, 0, 0 ]
nums: list[int] = [1, 3, 2, 5, 4]
array.cpp
/* Khởi tạo mảng */
// Lưu trữ trên ngăn xếp (stack)
int arr[5];
int nums[5] = { 1, 3, 2, 5, 4 };
// Lưu trữ trên đống (heap) (yêu cầu giải phóng bộ nhớ thủ công)
int* arr1 = new int[5];
int* nums1 = new int[5] { 1, 3, 2, 5, 4 };
array.java
/* Khởi tạo mảng */
int[] arr = new int[5]; // { 0, 0, 0, 0, 0 }
int[] nums = { 1, 3, 2, 5, 4 };
array.cs
/* Khởi tạo mảng */
int[] arr = new int[5]; // [ 0, 0, 0, 0, 0 ]
int[] nums = [1, 3, 2, 5, 4];
array.go
/* Khởi tạo mảng */
var arr [5]int
// Trong Go, xác định độ dài ([5]int) sẽ tạo một mảng; không xác định độ dài ([]int) sẽ tạo một slice
// Vì mảng trong Go được thiết kế để xác định độ dài tại thời điểm biên dịch, nên chỉ có thể dùng hằng số để chỉ định độ dài
// Để thuận tiện cho việc triển khai phương thức extend(), các slice dưới đây sẽ được coi như mảng
nums := []int{1, 3, 2, 5, 4}
array.swift
/* Khởi tạo mảng */
let arr = Array(repeating: 0, count: 5) // [0, 0, 0, 0, 0]
let nums = [1, 3, 2, 5, 4]
array.js
/* Khởi tạo mảng */
var arr = new Array(5).fill(0);
var nums = [1, 3, 2, 5, 4];
array.ts
/* Khởi tạo mảng */
let arr: number[] = new Array(5).fill(0);
let nums: number[] = [1, 3, 2, 5, 4];
array.dart
/* Khởi tạo mảng */
List<int> arr = List.filled(5, 0); // [0, 0, 0, 0, 0]
List<int> nums = [1, 3, 2, 5, 4];
array.rs
/* Khởi tạo mảng */
let arr: [i32; 5] = [0; 5]; // [0, 0, 0, 0, 0]
let slice: &[i32] = &[0; 5];
// Trong Rust, xác định độ dài ([i32; 5]) sẽ tạo một mảng; không xác định độ dài (&[i32]) sẽ tạo một slice
// Vì mảng trong Rust được thiết kế để xác định độ dài tại thời điểm biên dịch, nên chỉ có thể dùng hằng số để chỉ định độ dài
// Vector là kiểu dữ liệu thường được dùng làm mảng động trong Rust
// Để thuận tiện cho việc triển khai phương thức extend(), các vector dưới đây sẽ được coi như mảng
let nums: Vec<i32> = vec![1, 3, 2, 5, 4];
array.c
/* Khởi tạo mảng */
int arr[5] = { 0 }; // { 0, 0, 0, 0, 0 }
int nums[5] = { 1, 3, 2, 5, 4 };
array.kt
/* Khởi tạo mảng */
var arr = IntArray(5) // { 0, 0, 0, 0, 0 }
var nums = intArrayOf(1, 3, 2, 5, 4)
array.rb
# Khởi tạo mảng
arr = Array.new(5, 0)
nums = [1, 3, 2, 5, 4]
Trực quan hóa mã nguồn

https://pythontutor.com/render.html#code=%23%20%E5%88%9D%E5%A7%8B%E5%8C%96%E6%95%B0%E7%BB%84%0Aarr%20%3D%20%5B0%5D%20*%205%20%20%23%20%5B%200,%200,%200,%200,%200%20%5D%0Anums%20%3D%20%5B1,%203,%202,%205,%204%5D&cumulative=false&curInstr=0&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=311&rawInputLstJSON=%5B%5D&textReferences=false

Truy cập phần tử

Các phần tử mảng được lưu trữ trong vùng nhớ liên tục, điều đó có nghĩa là việc tính toán địa chỉ bộ nhớ của các phần tử mảng rất dễ dàng. Biết địa chỉ bộ nhớ của mảng (địa chỉ bộ nhớ của phần tử đầu tiên) và chỉ số của một phần tử, chúng ta có thể sử dụng công thức hiển thị trong hình bên dưới để tính địa chỉ bộ nhớ của phần tử đó và truy cập trực tiếp phần tử đó.

Tính toán địa chỉ bộ nhớ cho các phần tử mảng

Quan sát hình trên, ta thấy phần tử đầu tiên của mảng có chỉ số là \(0\), điều này có vẻ trái với lẽ thường vì việc đếm từ \(1\) sẽ tự nhiên hơn. Tuy nhiên, dưới góc nhìn của công thức tính địa chỉ, chỉ số thực chất là một độ lệch (offset) so với địa chỉ bộ nhớ. Độ lệch địa chỉ của phần tử đầu tiên là \(0\), vì vậy việc chỉ số của nó bằng \(0\) là hợp lý.

Việc truy cập phần tử trong mảng rất hiệu quả; ta có thể truy cập ngẫu nhiên (random access) bất kỳ phần tử nào trong mảng với thời gian \(O(1)\).

[file]{array}-[class]{}-[func]{random_access}

Chèn phần tử

Các phần tử mảng nằm sát nhau trong bộ nhớ, không có khoảng trống nào ở giữa chúng cho dữ liệu bổ sung. Như hình bên dưới, nếu muốn chèn một phần tử vào giữa mảng, chúng ta cần dịch chuyển tất cả phần tử phía sau sang phải một vị trí và sau đó gán giá trị tại chỉ số đó.

Ví dụ về chèn phần tử vào mảng

Cần lưu ý rằng vì độ dài của mảng là cố định, việc chèn một phần tử sẽ khiến phần tử cuối cùng bị đẩy ra ngoài mảng. Chúng ta sẽ dành việc giải quyết vấn đề này để thảo luận trong chương "Danh sách".

[file]{array}-[class]{}-[func]{insert}

Xóa phần tử

Tương tự, như hình bên dưới, để xóa phần tử tại chỉ số \(i\), chúng ta cần dịch chuyển tất cả các phần tử sau chỉ số \(i\) lên phía trước một vị trí.

Ví dụ về xóa phần tử khỏi mảng

Lưu ý rằng sau khi hoàn thành thao tác xóa, phần tử cuối cùng ban đầu không còn ý nghĩa nữa, do đó chúng ta không cần chỉnh sửa nó một cách tường minh.

[file]{array}-[class]{}-[func]{remove}

Nhìn chung, thao tác chèn và xóa trong mảng có các nhược điểm sau:

  • Độ phức tạp thời gian cao: Độ phức tạp thời gian trung bình cho cả thao tác chèn và xóa trong mảng là \(O(n)\), với \(n\) là độ dài của mảng.
  • Mất mát phần tử: Vì độ dài của mảng là bất biến, sau khi chèn một phần tử, các phần tử vượt quá độ dài của mảng sẽ bị mất.
  • Lãng phí bộ nhớ: Chúng ta có thể khởi tạo một mảng tương đối dài và chỉ sử dụng phần đầu, khi đó bất kỳ phần tử thừa nào ở đuôi chỉ là các trình giữ chỗ không được sử dụng, gây lãng phí không gian bộ nhớ.

Duyệt mảng

Trong hầu hết các ngôn ngữ lập trình, chúng ta có thể duyệt qua một mảng bằng chỉ số hoặc duyệt trực tiếp qua từng phần tử trong mảng:

[file]{array}-[class]{}-[func]{traverse}

Tìm kiếm phần tử

Tìm kiếm một phần tử được chỉ định trong mảng yêu cầu duyệt qua mảng và kiểm tra xem giá trị phần tử có khớp trong mỗi lần lặp hay không; nếu khớp, xuất ra chỉ số tương ứng.

Vì mảng là một cấu trúc dữ liệu tuyến tính, thao tác tìm kiếm trên được gọi là tìm kiếm tuyến tính (linear search).

[file]{array}-[class]{}-[func]{find}

Mở rộng mảng

Trong môi trường hệ thống phức tạp, chương trình không thể đảm bảo rằng vùng nhớ phía sau một mảng là khả dụng, khiến việc mở rộng dung lượng của mảng trở nên không an toàn. Do đó, trong hầu hết các ngôn ngữ lập trình, độ dài của mảng là bất biến.

Nếu muốn mở rộng một mảng, chúng ta cần tạo một mảng mới lớn hơn, sau đó sao chép từng phần tử của mảng ban đầu sang mảng mới. Đây là một thao tác \(O(n)\), rất tốn thời gian khi mảng có kích thước lớn. Mã nguồn được hiển thị bên dưới:

[file]{array}-[class]{}-[func]{extend}

Ưu điểm và hạn chế của mảng

Mảng được lưu trữ trong vùng nhớ liên tục với các phần tử có cùng kiểu dữ liệu. Cách tiếp cận này chứa nhiều thông tin tiên nghiệm phong phú mà hệ thống có thể sử dụng để tối ưu hóa hiệu quả của các thao tác trên cấu trúc dữ liệu.

  • Hiệu quả không gian cao: Mảng phân bổ các khối bộ nhớ liên tục cho dữ liệu mà không có thêm chi phí cấu trúc bổ sung.
  • Hỗ trợ truy cập ngẫu nhiên: Mảng cho phép truy cập bất kỳ phần tử nào trong thời gian \(O(1)\).
  • Tính cục bộ của bộ đệm (cache locality): Khi truy cập các phần tử mảng, máy tính không chỉ tải phần tử đó mà còn lưu trữ tạm thời dữ liệu xung quanh nó vào bộ đệm, nhờ đó tận dụng cache để nâng cao tốc độ thực thi của các thao tác tiếp theo.

Lưu trữ vùng nhớ liên tục là con dao hai lưỡi với các hạn chế sau:

  • Hiệu quả chèn và xóa thấp: Khi mảng có nhiều phần tử, thao tác chèn và xóa yêu cầu dịch chuyển số lượng lớn phần tử.
  • Độ dài bất biến: Sau khi mảng được khởi tạo, độ dài của nó là cố định. Việc mở rộng mảng yêu cầu sao chép tất cả dữ liệu sang mảng mới, điều này rất tốn kém.
  • Lãng phí không gian: Nếu kích thước phân bổ của mảng vượt quá nhu cầu thực tế, không gian thừa sẽ bị lãng phí.

Ứng dụng điển hình của mảng

Mảng là cấu trúc dữ liệu cơ bản và phổ biến, thường được sử dụng trong nhiều thuật toán khác nhau và để triển khai các cấu trúc dữ liệu phức tạp khác nhau.

  • Truy cập ngẫu nhiên: Nếu muốn lấy mẫu ngẫu nhiên một số phần tử, ta có thể dùng mảng để lưu trữ chúng và tạo một chuỗi ngẫu nhiên để thực hiện lấy mẫu ngẫu nhiên dựa trên các chỉ số.
  • Sắp xếp và tìm kiếm: Mảng là cấu trúc dữ liệu được sử dụng phổ biến nhất cho các thuật toán sắp xếp và tìm kiếm. Sắp xếp nhanh (quick sort), sắp xếp trộn (merge sort), tìm kiếm nhị phân (binary search) và các thuật toán khác chủ yếu được thực hiện trên mảng.
  • Bảng tra cứu (lookup table): Khi cần tìm nhanh một phần tử hoặc mối quan hệ tương ứng của nó, chúng ta có thể sử dụng mảng làm bảng tra cứu. Ví dụ, nếu muốn triển khai ánh xạ từ ký tự sang mã ASCII, chúng ta có thể sử dụng giá trị mã ASCII của ký tự làm chỉ số, với phần tử tương ứng được lưu trữ tại vị trí đó trong mảng.
  • Học máy (machine learning): Mạng nơ-ron sử dụng rộng rãi các phép toán đại số tuyến tính giữa các vectơ, ma trận và tensor, tất cả chúng đều được xây dựng dưới dạng mảng. Mảng là cấu trúc dữ liệu được sử dụng phổ biến nhất trong lập trình mạng nơ-ron.
  • Triển khai cấu trúc dữ liệu: Mảng có thể được sử dụng để triển khai ngăn xếp, hàng đợi, bảng băm, hàng đợi ưu tiên (heap), đồ thị và các cấu trúc dữ liệu khác. Ví dụ, biểu diễn ma trận kề (adjacency matrix) của một đồ thị thực chất là một mảng hai chiều.