Mảng (cấu trúc dữ liệu) – Wikipedia tiếng Việt

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 những thành phần hoàn toàn có thể giám sát được vào lúc chương trình đang chạy. Tính năng này được cho phép một lệnh lặp hoàn toàn có thể giải quyết và xử lý một số lượng lớn những thành phần trong mảng. Do đó, những thành phần trong cấu trúc mảng cần phải có cùng kích cỡ và cùng kiểu tài liệu. Tập hợp những bộ chỉ số và địa chỉ của những thành phần ( cũng như công thức tính địa chỉ những thành phần ) thường, [ 3 ] [ 5 ] nhưng không phải luôn luôn, [ 2 ] cố định và thắt chặt 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 diễn đạt những giải thuật, khái niệm này cũng được dùng để chỉ mảng link, một quy mô kim chỉ nan khoa học máy tính ( kiểu tài liệu trừu tượng hay ADT ) để sử dụng những đặc thù thiết yếu của mảng .

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ó tương hỗ đặc biệt quan trọng cho mảng ngoài việc dùng những tương hỗ từ phần cứng. Ngôn ngữ lập trình cấp cao tiên phong, gồm có FORTRAN ( 1957 ), COBOL ( 1960 ), và ALGOL 60 ( 1960 ), có tương hỗ mảng nhiều chiều, và sau đó là C ( 1972 ). Trong C + + ( 1983 ) có những class template cho mảng nhiều chiều, với số lượng chiều là cố định và thắt chặt trong lúc chương trình đang chạy [ 3 ] [ 5 ], cũng như những mảng có số chiều biến hóa được khi chương trình đang chạy. [ 2 ]
Mảng được dùng để hiện thực những vector và những ma trận cũng như những loại bảng chữ nhật. Nhiều cơ sở tài liệu từ nhỏ đến lớn chứa ( hoặc gồm có ) những mảng một chiều mà những thành phần là những bản ghi .Mảng cũng được dùng để hiện thực những cấu trúc tài 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 thành phần 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]

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 những thành phần 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[sửa|sửa mã nguồn]

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

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

Sự hiệu suất cao so với những cấu trúc tài liệu khác[sửa|sửa mã nguồn]

So với list link, việc truy vấn đến một thành phần trong mảng nhanh hơn với độ phức tạp là O ( 1 ) .Tuy nhiên, để xoá một thành phần không phải là thành phần cuối thì sử dụng cấu trúc mảng không hiệu suất cao. Bởi vì việc làm này cần tốn thời hạn cho việc di dời những thành phần còn lại lấp vào chỗ trống của mảng .

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

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

Ví dụ:

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

Rate this post