[Data structures] Cấu trúc dữ liệu - Mảng (Array) C++ Example

Thế mảng nghĩa là gì?

Mảng là tập hợp các mục dữ liệu đồng nhất (cùng kiểu) được lưu trữ ở các vị trí bộ nhớ liền nhau. Ví dụ: nếu một mảng có kiểu int, nó chỉ có thể lưu trữ các phần tử nguyên và không cho phép các phần tử thuộc các kiểu khác như double, float, char, v.v.

Tại sao chúng ta cần một mảng?

Mảng đặc biệt hữu ích khi chúng ta xử lý nhiều biến cùng kiểu. Ví dụ, giả sử tôi cần lưu trữ điểm trong môn toán của 100 học sinh. Để giải quyết vấn đề cụ thể này, tôi phải tạo 100 biến kiểu int hoặc tạo một mảng kiểu int với kích thước 100.

Rõ ràng là lựa chọn thứ hai là tốt nhất, bởi vì khai báo 100 biến khác nhau là một công việc nhàm chán, ngoài ra nó còn vi phạm quy tắc về mặt Clean code, coding convention. Mặt khác, xử lý mảng rất đơn giản và dễ dàng, tất cả 100 giá trị có thể được lưu trữ trong cùng một mảng ở các chỉ mục khác nhau (0 đến 99).

Biểu diễn bộ nhớ mảng

Sơ đồ sau biểu diễn một mảng số nguyên có 12 phần tử. Chỉ số (index) của mảng bắt đầu bằng 0, vì vậy mảng có 12 phần tử có chỉ số từ 0 đến 11.

Truy cập các phần tử của mảng

Trong ví dụ này, chúng ta có một mảng tên arr kiểu int. Kích thước của mảng là 10 có nghĩa là nó có thể chứa 10 giá trị nguyên. arr[0] sẽ là phần tử đầu tiên, arr[1] thứ hai, v.v. Ở đây tôi chỉ gán giá trị cho một vài phần tử của mảng. Chạy đoạn code ví dụ sau và xem xét kết quả trả về của chương trình, nó cho thấy rằng giá trị mặc định của các phần tử của một mảng int là 0. Các phần tử không được gán bất kỳ giá trị nào sẽ hiển thị giá trị của chúng là 0 (default value).

Tuy nhiên không phải tất cả các ngôn ngữ đều như vậy. Java có các giá trị mặc định khi khai báo cấu trúc dữ liệu nhưng C ++ thì không. Giá trị mặc định trong C++ là Không xác định.

Output:

Đây là cách đặt giá trị mặc định trong C++ khi tạo mảng.

int array[100] = {};

Bây giờ mọi phần tử được đặt thành 0. Nếu không thực hiện điều này, mọi phần tử sẽ chứa giá trị rác.

Time complexity của Mảng

Chúng ta hãy xem xét time complexity của các thao tác khác nhau trên mảng.

Ưu điểm và nhược điểm của Mảng

Ưu điểm
1. Đọc một phần tử mảng rất đơn giản và hiệu quả. Như trong bảng trên, thời gian đọc của mảng là O(1) trong cả Average Case và Worst Case. Điều này là do bất kỳ phần tử nào có thể được đọc ngay lập tức bằng cách sử dụng các chỉ mục mà không cần duyệt qua toàn bộ mảng.

2. Mảng là một nền tảng của các cấu trúc dữ liệu khác. Ví dụ, các cấu trúc dữ liệu khác như LinkedList, Stack, Queue, v.v. được thực hiện bằng cách sử dụng mảng.

3. Tất cả các phần tử của một mảng có thể được truy cập bằng một tên duy nhất (tên mảng) cùng với chỉ mục, dễ đọc, thân thiện với người dùng và hiệu quả hơn là lưu trữ các phần tử đó trong 2 biến khác nhau.

Nhược điểm
1. Khi sử dụng mảng, chúng ta cần phải khai báo kích thước của mảng ngay từ đầu, vì vậy nếu chúng ta không biết chúng ta sẽ lưu trữ bao nhiêu phần tử trong mảng sẽ làm cho công việc trở nên khó khăn.

2. Kích thước của mảng là cố định nên nếu sau này, nếu chúng ta cần lưu trữ nhiều phần tử hơn trong đó thì không thể thực hiện được. Mặt khác, nếu chúng ta lưu trữ số lượng phần tử ít hơn kích thước đã khai báo, thì bộ nhớ được cấp phát còn lại sẽ bị lãng phí.

Một số bài toán hay gặp:

• Các bài toán liên quan đến sắp xếp và tìm kiếm: implement binary search, implement quick sort/merge sort,….
• Tìm tổng toàn bộ các phần tử trong array (các phần tử chẵn, lẻ v…v)
• Đếm số lần xuất hiện của các phần tử, tìm phần tử xuất hiện nhiều nhất

Source tham khảo:
https://vi.wikipedia.org/wiki/C%2B%2B
https://beginnersbook.com/2018/10/data-structure-array

Hashtags: