Cấu trúc dữ liệu mảng là gì?

Mảng (Array) là một trong các cấu trúc dữ liệu cũ và quan trọng nhất. Mảng có thể lưu giữ một số phần tử cố định và các phần tử này nền có cùng kiểu. Hầu hết các cấu trúc dữ liệu đều sử dụng mảng để triển khai giải thuật. Dưới đây là các khái niệm quan trọng liên quan tới Mảng.

Phần tử: Mỗi mục được lưu giữ trong một mảng được gọi là một phần tử.
Chỉ mục (Index): Mỗi vị trí của một phần tử trong một mảng có một chỉ mục số được sử dụng để nhận diện phần tử.

Mảng gồm các bản ghi có kiểu giống nhau, có kích thước cố định, mỗi phần tử được xác định bởi chỉ số

Mảng là cấu trúc dữ liệu được cấp phát lien tục cơ bản

Ưu điểm của mảng :

Truy câp phàn tử vơi thời gian hằng số O(1)

Sử dụng bộ nhớ hiệu quả

Tính cục bộ về bộ nhớ

Nhược điểm

Không thể thay đổi kích thước của mảng khi chương trình dang thực hiện

Mảng động

Mảng động (dynamic aray) : cấp phát bộ nhớ cho mảng một cách động trong quá trình chạy chương trình trong C là malloc và calloc, trong C++ là new

Sử dụng mảng động ta bắt đầu với mảng có 1 phàn tử, khi số lượng phàn tử vượt qua khả năng của ảng thì ta gấp đôi kích thước mảng cuc và copy phàn tử mảng cũ vào nửa đầu của mảng mới

Ưu điểm : tránh lãng phí bộ nhớ khi phải khai báo mảng có kích thước lớn ngay từ đầu

Nhược điểm: + phải thực hiện them thao tác copy phần tử mỗi khi thay đổi kích thước. + một số thời gian thực hiện thao tác không còn là hằng số nữa

Biểu diễn Cấu trúc dữ liệu mảng

Mảng có thể được khai báo theo nhiều cách đa dạng trong các ngôn ngữ lập trình. Để minh họa, chúng ta sử dụng phép khai báo mảng trong ngôn ngữ C:

Hình minh họa phần tử và chỉ mục:

Dưới đây là một số điểm cần ghi nhớ về cấu trúc dữ liệu mảng:

Chỉ mục bắt đầu với 0.
Độ dài mảng là 10, nghĩa là mảng có thể lưu giữ 10 phần tử.
Mỗi phần tử đều có thể được truy cập thông qua chỉ mục của phần tử đó. Ví dụ, chúng ta có thể lấy giá trị của phần tử tại chỉ mục 6 là 27.

Phép toán cơ bản được hỗ trợ bởi mảng

Dưới đây là các hoạt động cơ bản được hỗ trợ bởi một mảng: