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

Đừng nhầm lẫn với Mảng (tin học).

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.^[1][2][3]

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.^[4]

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,^[3][5] nhưng không phải luôn luôn,^[2] cố định khi mảng đang được sử dụng.

Khái niệm mảng thường dùng có nghĩa là kiểu dữ liệu mảng được cung cấp bởi hầu hết các ngôn ngữ lập trình cấp cao, nó bao gồm tập hợp các giá trị hoặc biến có thể lựa chọn bằng một hoặc nhiều chỉ số được tính toán trong lúc chạy. Kiểu dữ liệu mảng thường được hiện thực bằng cấu trúc mảng; tuy nhiên một số ngôn ngữ lập trình có thể hiện thực bằng bảng băm, cây tìm kiếm hoặc các cấu trúc dữ liệu khác.

Khi mô tả các giải thuật, khái niệm này cũng được dùng để chỉ mảng liên kết, một mô hình lý thuyết khoa học máy tính (kiểu dữ liệu trừu tượng hay ADT) để sử dụng các tính chất thiết yếu của mảng.

Lịch sử

Các máy tính kỹ thuật số đầu tiên dùng chương trình được viết bằng ngôn ngữ máy để tạo và truy xuất cấu trúc mảng cho các bảng dữ liệu, vector và tính toán ma trận, và các mục đích khác. Von Neumann viết chương trình sắp xếp mảng (sắp xếp trộn) vào năm 1945, khi đang xây dựng chương trình lưu trữ máy tính đầu tiên.^[6]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ố.^{[cần dẫn nguồn]}

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^[3][5], cũng như các mảng có số chiều thay đổi được khi chương trình đang chạy.^[2]

Ứng dụng

Mảng được dùng để hiện thực các vector và các ma trận cũng như các loại bảng chữ nhật. Nhiều cơ sở dữ liệu từ nhỏ đến lớn chứa (hoặc bao gồm) các mảng một chiều mà các phần tử là các bản ghi.

Mảng cũng được dùng để hiện thực các cấu trúc dữ liệu khác, như đống, bảng băm, hàng đợi hai đầu, hàng đợi, ngăn xếp, xâu và VList.

Một hoặc nhiều mảng lớn đôi khi được dùng để giả lập cấp phát bộ nhớ động trong chương trình, nhất là cấp phát memory pool.

Mảng có thể dùng để xác định một phần hoặc toàn bộ luồng thực thi của chương trình nhiều câu lệnh IF như là một cách thu gọn (nếu không sẽ lặp lại). Trong trường hợp này, nó được biết như là bảng điều khiển và được dùng kết hợp với mục tiêu xây dựng trình thông dịch, chương trình có luồng thực thi thay đổi tùy theo giá trị trong mảng. Mảng có thể chứ các con trỏ tới chương trình con (hoặc số chương trình con tương ứng có thể được xử lý bằng lệnh SWITCH) - để chỉnh hướng thực thi của chương trình.

Định danh cho phần tử và công thức tính địa chỉ

Mảng một chiều

Khi các đối tượng dữ liệu được lưu trữ trong một mảng, các đối tượng riêng lẻ được chon thông qua một chỉ số (index) thường là một biến số nguyên không âm. Các chỉ số này còn được gọi là chỉ số dưới (subscript). Một chỉ số ánh xạ giá trị của mảng đến một đối tượng được lưu trữ.

Có ba cách để đánh chỉ số cho các phần tử trong mảng:

0 (đánh chỉ số từ không)

Phần tử đầu tiên sẽ được đánh chỉ số là 0.^[7]

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

Bài chi tiết: Mảng độ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.

Chú thích

1. Black, Paul E. (ngày 13 tháng 11 năm 2008). “array”. Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology. Truy cập ngày 22 tháng 8 năm 2010.
2. ^ Bjoern Andres; Ullrich Koethe; Thorben Kroeger; Hamprecht (2010). "Runtime-Flexible Multi-dimensional Arrays and Views for C++98 and C++0x". arΧiv:1008.2909 [cs.DS]. 
3. ^ Garcia, Ronald; Lumsdaine, Andrew (2005). “MultiArray: a C++ library for generic programming with arrays”. Software: Practice and Experience. 35 (2): 159–188. doi:10.1002/spe.630. ISSN 0038-0644.
4. David R. Richardson (2002), The Book on Data Structures. iUniverse, 112 pages. ISBN 0-595-24039-9, ISBN 978-0-595-24039-5.
5. ^ T. Veldhuizen. Arrays in Blitz++. In Proc. of the 2nd Int. Conf. on Scientific Computing in Object-Oriented Parallel Environments (ISCOPE), LNCS 1505, pages 223-220. Springer, 1998.
6. Donald Knuth, The Art of Computer Programming, vol. 3. Addison-Wesley
7. “Array Code Examples - PHP Array Functions - PHP code”. Computer Programming Web programming Tips. Bản gốc lưu trữ ngày 13 tháng 4 năm 2011. Truy cập ngày 8 tháng 4 năm 2011. In most computer languages array index (counting) starts from 0, not from 1. Index of the first element of the array is 0, index of the second element of the array is 1, and so on. In array of names below you can see indexes and values.

Tham khảo

Tra array trong từ điển mở tiếng Việt Wiktionary

Wikimedia Commons có thêm hình ảnh và phương tiện truyền tải về Mảng (cấu trúc dữ liệu).