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

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

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ù 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 nhwnxg 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ỉ associative array hay mảng trừu tượng, 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ử[sửa | sửa mã nguồn]

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 tinhd đầ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ố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[sửa | sửa mã nguồn]

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ư heap, bảng băm, hàng đợi hai đầu, hàng đợi, ngăn xếp, chuỗiVList.

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ỉ[sửa | sửa mã nguồn]

Mảng một chiều[sửa | sửa mã nguồn]

Mảng nhiều chiều[sửa | sửa mã nguồn]

Dope vector[sửa | sửa mã nguồn]

Compact layout[sửa | sửa mã nguồn]

Thay đổi kích thước mảng[sửa | sửa mã nguồn]

Bài chi tiết: Mảng động

Công thức tính địa chỉ phi tuyến tính[sửa | sửa mã nguồn]

Hiệu quả[sửa | sửa mã nguồn]

Sự hiệu quả so với các cấu trúc dữ liệu khác[sửa | sửa mã nguồn]

Ý nghĩa của số chiều[sửa | sửa mã nguồn]

Chú thích[sửa | sửa mã nguồn]

  1. ^ Black, Paul E. (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. ^ a ă â 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. ^ a ă â 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. ^ a ă 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

Tham khảo[sửa | sửa mã nguồn]