✨Mảng (cấu trúc dữ liệu)

Trong khoa học máy tính, cấu trúc dữ liệu mảng hoặc mảng là một cấu trúc dữ liệu bao gồm một nhóm các phần tử giá trị hoặc biến, mỗi phần tử được xác định ít nhất bằng một chỉ số (index) hoặc khóa (key). Mảng được lưu theo cách có thể tính được vị trí của các phần tử từ giá trị của một tuple chỉ số bằng một biểu thức toán học.

Thí dụ, một mảng có 10 biến số nguyên, với các chỉ số từ 0 đến 9, có thể lưu trong 10 word tại địa chỉ bộ nhớ 2000, 2004, 2008,... 2036. Do đó, phần tử có chỉ số i sẽ nằm ở địa chỉ 2000 + 4 × i.

Do khái niệm ma trận trong toán học có thể được biểu diễn bằng một bảng hai chiều nên đôi khi mảng hai chiều cũng được gọi là ma trận. Một số trường hợp, khái niệm vector được dùng để chỉ mảng, mặc dù bộ (tuple) là khái niệm chính xác hơn về mặt toán học. Mảng thường được dùng để hiện thực các bảng, nhất là bảng tìm kiếm. Từ bảng đôi khi có cùng nghĩa với mảng.

Mảng là một trong những cấu trúc dữ liệu cũ và quan trọng nhất, và hầu hết các chương trình đều dùng nó. Các cấu trúc dữ liệu khác cũng được hiện thực bằng mảng, thí dụ như danh sách hoặc chuỗi. Nó rất hiệu quả trong việc tận dụng cách đánh địa chỉ trên máy tính. Trong hầu hết các máy tính hiện đại và các thiết bị lưu trữ ngoài, bộ nhớ là chuỗi một chiều các word, và chỉ số của nó chính là địa chỉ. Bộ xử lý, đặc biệt là bộ xử lý vector, thường tối ưu hóa các tác vụ trên mảng.

Sự hữu dụng của mảng nằm ở chỗ chỉ số của các phần tử có thể tính toán được vào lúc chương trình đang chạy. Tính năng này cho phép một lệnh lặp có thể xử lý một số lượng lớn các phần tử trong mảng. Do đó, các phần tử trong cấu trúc mảng cần phải có cùng kích thước và cùng kiểu dữ liệu. Tập hợp các bộ chỉ số và địa chỉ của các phần tử (cũng như công thức tính địa chỉ các phần tử) thường, nhưng không phải luôn luôn,^p. 159 Đánh chỉ số cho mảng ban đầu được dùng trong mã tự sửa đổi, và sau đó dùng trong thanh ghi chỉ số và truy xuất giáng tiếp. Một số máy tính lớn thiết kế vào thập niên 1960, như Burroughs B5000 và hậu duệ của nó, có những lệnh đặc biệt để đánh chỉ số cho mảng bao gồm kiểm tra biên của chỉ số.

Hợp ngữ nói chung không có hỗ trợ đặc biệt cho mảng ngoài việc dùng các hỗ trợ từ phần cứng. Ngôn ngữ lập trình cấp cao đầu tiên, bao gồm FORTRAN (1957), COBOL (1960), và ALGOL 60 (1960), có hỗ trợ mảng nhiều chiều, và sau đó là C (1972). Trong C++ (1983) có các class template cho mảng nhiều chiều, với số lượng chiều là cố định trong lúc chương trình đang chạy ; 1 (đánh chỉ số từ một) : Phần tử đầu tiên sẽ được đánh chỉ số là 1. ; n (đánh chỉ số từ n) : Chỉ số cơ sở của một mảng có thể được chọn tuỳ ý. Thông thường các ngôn ngữ lập trình cho phép đánh chỉ số từ n cũng sẽ cho phép các giá trị chỉ số âm.

Mảng nhiều chiều

Dope vector

Compact layout

Thay đổi kích thước mảng

Công thức tính địa chỉ phi tuyến tính

Hiệu quả

Sự hiệu quả so với các cấu trúc dữ liệu khác

So với danh sách liên kết, việc truy cập đến một phần tử trong mảng nhanh hơn với độ phức tạp là O(1).

Tuy nhiên, để xoá một phần tử không phải là phần tử cuối thì sử dụng cấu trúc mảng không hiệu quả. Bởi vì công việc này cần tốn thời gian cho việc dịch chuyển các phần tử còn lại lấp vào chỗ trống của mảng.

Ý nghĩa của số chiều

Số chiều của mảng tương ứng với số chỉ số (index) cần để xác định được phần tử đó.

Ví dụ:

Trong mảng một chiều a[N] với N là số phần tử, a[i] biểu diễn phần tử thứ i (i < N) của mảng.

Trong mảng hai chiều a[N][M] với N, M là giới hạn của mỗi chiều tương ứng, a[i][j] biểu diễn phần tử ở hàng i cột j của mảng.