Mảng là kiểu dữ liệu cấu trúc

* Dữ liệu kiểu mảng là một tập hợp hữu hạn các phần tử có thứ tự, mỗi phần tử có một kiểu dữ liệu, gọi là kiểu của phần tử. Việc sắp xếp thứ tự được thực hiện bằng cách gán cho mối phần tử một chỉ số. 

-Dữ liệu kiểu mảng là một tập hộp hữu hạn các phần tử có thứ tự, mọi phần tử đều có chung một kiểu dữ liệu, gọi là kiểu của phần tử. Việc sắp xếp thứ tự được thực hiện bằng cách gán cho mỗi phần tử một chỉ số.

- cấu trúc khai báo biến mảng:

  Var: array[..] of;

- Trong đó chỉ số đầu và chỉ số cuối là hai số nguyên thỏa mãn chỉ số đầu nhỏ hơn chỉ số cuối và kiểu dữ liệu có thể là integer hoặc real.

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:

• Duyệt: In tất cả các phần tử mảng theo cách in từng phần tử một.

• Chèn: Thêm một phần tử vào mảng tại chỉ mục đã cho.

• Xóa: Xóa một phần tử từ mảng tại chỉ mục đã cho.

• Tìm kiếm: Tìm kiếm một phần tử bởi sử dụng chỉ mục hay bởi giá trị.

• Cập nhật: Cập nhật giá trị một phần tử tại chỉ mục nào đó.

Trong ngôn ngữ C, khi một mảng được khởi tạo với kích cỡ ban đầu, thì nó gán các giá trị mặc định cho các phần tử của mảng theo thứ tự sau:

Mảng (Array data structure hay đơn giản là array) - kiểu dữ liệu cơ bản nhất của mọi ngôn ngữ. Mặc dù nó rất là cơ bản nhưng bạn đã hiểu bao nhiêu về mảng? những xử lý như truy cập đến phần tử thứ i hay thêm một phần tử hoạt động như thế nào và có độ phức tạp bao nhiêu?

Hãy cùng mình tìm hiểu nhé.

Mảng là gì?

Rất đơn giản ai cũng có thể trả lời được như thế này

Mảng là tập hợp các phần tử, các phần tử được xác định bởi một chỉ mục (index)

Nhưng như vậy đã đủ chưa? Còn gì cần phải đề cập nào? Liệu bạn có biết hết những điều sau đây khi định nghĩa về mảng

• các phần tử có cùng một kiểu dữ liệu. Kiểu dữ liệu của các phần tử có thể là kiểu mảng nên chúng ta có thể có thêm các khái niệm về mảng một chiều và mảng đa chiều
• mảng có kích thước cố định
• các phần tử được lưu trong các ô nhớ liên tiếp nhau hoặc lưu theo cách có thể tính được vị trí của các phần tử bằng một biểu thức toán học

OK vậy cũng là đã đủ về khái niệm của mảng. Nếu còn thêm gì bạn có thể comment cho mình biết nhé.

Và khi nhắc tới mảng thì không thể nào không nói đến mảng động. Hầu hết chúng ta đều thích sử dụng mảng động trong code của mình hơn và mảng với số phần tử xác định. Vậy thế nào là mảng động (dynamic array)? Và nó có khác gì khái niệm ở trên?

Mảng động là mảng có kích thước thay đổi bằng cách cho phép thêm hoặc xóa phần tử

Một khái niệm ngắn gọn nhưng đầy đủ khi nói về mảng động. Nói thể hiện rõ sự khác biệt so với mảng chính là kích thước của nó có thể thay đổi được. Khi làm việc với mảng, ta không thể thêm hay xóa phần tử trong mảng (chỉ được phép thay đổi giá trị), còn với mảng động thì có thể. Nhắc tới làm việc với mảng, thì có 2 vấn đề chính ở mặt cấu trúc dữ liệu cần phải nắm đó chính là kích thước của mảng và chỉ mục của các phần tử. (bài viết này tập trung về cấu trúc dữ liệu chứ không phải thuật toán he)

Kích thước mảng

Kích thước của mảng cố định phần tử thì đơn giản rồi, thể hiện ngay trong định nghĩa, là một con số cụ thể. Thế nhưng kích thước của mảng động thì sao. Liệu bạn có trả lời được các vấn đề sau:

Mảng động cũng là mảng. Mà mảng thì có kích thước cố định. Vậy mảng động có kích thước cố định?

• Nếu kích thước cố định vậy nó thay đổi kích thước như thế nào?
• Nếu kích thước không cố định thì xác định kích thước như thế nào?

Không dễ trả lời phải không. Mình cũng đã từng gục ngã trước câu hỏi này và nhận ra mình chẳng biết gì về nó cả. Cứ dùng và chẳng nghĩ suy thì cứ mãi là newbie. Thực ra thì đây là một cái bẫy trong cách logic của chúng ta. Các bạn nên hiểu đây là hai khái niệm khác biệt:

• Kích thước cố định tức là trong một thời điểm thì kích thước của mảng luôn là một con số có thể xác định được.
• Có thể thay đổi kích thước nghĩa là nó không có một kích thước nhất định ở mọi thời điểm. Đây mới là điều tạo nên sự khác biệt của mảng động.

Và để tìm hiểu sâu hơn về mảng động, chúng ta cần trả lời 2 câu hỏi

• Mảng động thay đổi kích thước như thế nào?
• Làm sao mảng động lại xác định được kích thước của nó?

Đây là 2 câu hỏi cơ bản để nắm được cấu trúc của một mảng động. Tuy có sự khác nhau giữa một số ngôn ngữ lập trình, nhưng nhìn chung cơ chế thay đổi kích thước của một mảng động như sau:

• Đầu tiên mảng động sẽ được cấp dựa trên một mảng có kích thước cố định. Điều này giải thích cho việc bạn gặp phải index error khi thao tác trên mảng động.
• Khi cần có thêm một phần tử mới. Thì lúc này hệ thống sẽ cấp phát một mảng cố định mới với kích thước lớn hơn, copy các phần tử hiện có vào mảng mới và sau đó thêm phần tử mới vào.

Đây là xử lý thông thường để tăng kích thước mảng. Tuy nhiên nhược điểm của nó chính là tốn kém tài nguyên cho việc cấp phát một mảng mới và sao chép các phần tử ban đầu. Một giải pháp chính là tạo ra mảng có kích thước lớn hơn số lượng phần tử hiện tại. Việc thêm hay xóa phần tử sẽ không ảnh hưởng đến kích thước của mảng hiện tại. Chỉ khi tất cả ô nhớ được cấp phát thì lúc này hệ thống mới tạo ra mảng mới và thực hiện copy các phần tử. Điều này giúp tăng hiệu suất của hệ thống và giảm bớt độ phức tạp khi thêm hoặc xóa phần tử. Tuy nhiên vì để xác định được kích thước của mảng cho trường hợp này thì có 2 khái niệm cần phải nắm:

• logical size hay array size: thể hiện số lượng phần tử thực tế có trong mảng
• physical size hay capacity: đây là kích thước vật lý của mảng được cấp pháp trong hệ thống.

Lê Vũ Quỳnh Trinh @TrinhLVTQ

Theo dõi

2.0K 111 30

Đã đăng vào thg 3 24, 2020 6:50 SA 12 phút đọc

2.7K

1

1

Tìm hiểu về cấu trúc dữ liệu của mảng

• Báo cáo
• Thêm vào series của tôi

Bài đăng này đã không được cập nhật trong 2 năm

Lời mở đầu

Mảng (Array data structure hay đơn giản là array) - kiểu dữ liệu cơ bản nhất của mọi ngôn ngữ. Mặc dù nó rất là cơ bản nhưng bạn đã hiểu bao nhiêu về mảng? những xử lý như truy cập đến phần tử thứ i hay thêm một phần tử hoạt động như thế nào và có độ phức tạp bao nhiêu?

Hãy cùng mình tìm hiểu nhé.

Mảng là gì?

Rất đơn giản ai cũng có thể trả lời được như thế này

Mảng là tập hợp các phần tử, các phần tử được xác định bởi một chỉ mục (index)

Nhưng như vậy đã đủ chưa? Còn gì cần phải đề cập nào? Liệu bạn có biết hết những điều sau đây khi định nghĩa về mảng

• các phần tử có cùng một kiểu dữ liệu. Kiểu dữ liệu của các phần tử có thể là kiểu mảng nên chúng ta có thể có thêm các khái niệm về mảng một chiều và mảng đa chiều
• mảng có kích thước cố định
• các phần tử được lưu trong các ô nhớ liên tiếp nhau hoặc lưu theo cách có thể tính được vị trí của các phần tử bằng một biểu thức toán học

OK vậy cũng là đã đủ về khái niệm của mảng. Nếu còn thêm gì bạn có thể comment cho mình biết nhé.

Và khi nhắc tới mảng thì không thể nào không nói đến mảng động. Hầu hết chúng ta đều thích sử dụng mảng động trong code của mình hơn và mảng với số phần tử xác định. Vậy thế nào là mảng động (dynamic array)? Và nó có khác gì khái niệm ở trên?

Mảng động là mảng có kích thước thay đổi bằng cách cho phép thêm hoặc xóa phần tử

Một khái niệm ngắn gọn nhưng đầy đủ khi nói về mảng động. Nói thể hiện rõ sự khác biệt so với mảng chính là kích thước của nó có thể thay đổi được. Khi làm việc với mảng, ta không thể thêm hay xóa phần tử trong mảng (chỉ được phép thay đổi giá trị), còn với mảng động thì có thể. Nhắc tới làm việc với mảng, thì có 2 vấn đề chính ở mặt cấu trúc dữ liệu cần phải nắm đó chính là kích thước của mảng và chỉ mục của các phần tử. (bài viết này tập trung về cấu trúc dữ liệu chứ không phải thuật toán he)

Kích thước mảng

Kích thước của mảng cố định phần tử thì đơn giản rồi, thể hiện ngay trong định nghĩa, là một con số cụ thể. Thế nhưng kích thước của mảng động thì sao. Liệu bạn có trả lời được các vấn đề sau:

Mảng động cũng là mảng. Mà mảng thì có kích thước cố định. Vậy mảng động có kích thước cố định?

• Nếu kích thước cố định vậy nó thay đổi kích thước như thế nào?
• Nếu kích thước không cố định thì xác định kích thước như thế nào?

Không dễ trả lời phải không. Mình cũng đã từng gục ngã trước câu hỏi này và nhận ra mình chẳng biết gì về nó cả. Cứ dùng và chẳng nghĩ suy thì cứ mãi là newbie. Thực ra thì đây là một cái bẫy trong cách logic của chúng ta. Các bạn nên hiểu đây là hai khái niệm khác biệt:

• Kích thước cố định tức là trong một thời điểm thì kích thước của mảng luôn là một con số có thể xác định được.
• Có thể thay đổi kích thước nghĩa là nó không có một kích thước nhất định ở mọi thời điểm. Đây mới là điều tạo nên sự khác biệt của mảng động.

Và để tìm hiểu sâu hơn về mảng động, chúng ta cần trả lời 2 câu hỏi

• Mảng động thay đổi kích thước như thế nào?
• Làm sao mảng động lại xác định được kích thước của nó?

Đây là 2 câu hỏi cơ bản để nắm được cấu trúc của một mảng động. Tuy có sự khác nhau giữa một số ngôn ngữ lập trình, nhưng nhìn chung cơ chế thay đổi kích thước của một mảng động như sau:

• Đầu tiên mảng động sẽ được cấp dựa trên một mảng có kích thước cố định. Điều này giải thích cho việc bạn gặp phải index error khi thao tác trên mảng động.
• Khi cần có thêm một phần tử mới. Thì lúc này hệ thống sẽ cấp phát một mảng cố định mới với kích thước lớn hơn, copy các phần tử hiện có vào mảng mới và sau đó thêm phần tử mới vào.

Đây là xử lý thông thường để tăng kích thước mảng. Tuy nhiên nhược điểm của nó chính là tốn kém tài nguyên cho việc cấp phát một mảng mới và sao chép các phần tử ban đầu. Một giải pháp chính là tạo ra mảng có kích thước lớn hơn số lượng phần tử hiện tại. Việc thêm hay xóa phần tử sẽ không ảnh hưởng đến kích thước của mảng hiện tại. Chỉ khi tất cả ô nhớ được cấp phát thì lúc này hệ thống mới tạo ra mảng mới và thực hiện copy các phần tử. Điều này giúp tăng hiệu suất của hệ thống và giảm bớt độ phức tạp khi thêm hoặc xóa phần tử. Tuy nhiên vì để xác định được kích thước của mảng cho trường hợp này thì có 2 khái niệm cần phải nắm:

• logical size hay array size: thể hiện số lượng phần tử thực tế có trong mảng
• physical size hay capacity: đây là kích thước vật lý của mảng được cấp pháp trong hệ thống.

Một hình ảnh giải thích rõ hơn về cấu trúc của mảng động. Các ô trống nét đứt thể hiện cho vùng nhớ được sử dụng để thêm phần tử. Nếu như chỉ cần sử dụng các ô nhớ này, việc thêm phần tử sẽ diễn ra rất nhanh và độ phức tạp chỉ là O(1). Tuy nhiên nếu cần phải cấp phát lại bộ nhớ (trường hợp được đánh dấu rùa xanh) thì độ phức tạp lúc này lại là O(n) vì cần phải thao tác sao chép lại n phần tử. Nếu phải đưa ra con số chính xác về độ phức tạp khi thêm hay xóa phần tử trong mảng động ở trường hợp này thì O(1) vẫn là lựa chọn hợp lý.

Bên cạnh đó, chính nhớ logical size, chúng ta mới có thể xác định được kích thước của mảng tại mọi thời điểm. Và tất nhiên độ phức tạp khi xác định kích thước của nó là O(1), chỉ cần lấy giá trị của logic size.

Lưu ý:

• Một số cấc trúc mảng động khác lại không theo cơ chế này. Chẳng hạn như danh sách liên kết. Danh sách liên kết là một cấu trúc mảng động đặc biệt, các phần tử được liên kết tuyết tính, thứ tự không được xác định bởi vị trí vật lý của chúng trong bộ nhớ. Đối với danh sách liên kết, việc thêm phần từ hoặc xóa phần tử khá là đơn giản nếu phần tử cuối cùng được xác định (độ phức tạp O(1)). Tuy nhiên nếu không xác định được phần tử cuối cùng thì nó là O(n). Mặc khác, danh sách liên kết vẫn là mảng cố định phần tử, số phần tử trong một thời điểm là một con số cụ thể. Tuy nhiên để xác định được số lượng phần tử chúng ta bắt buộc phải duyệt qua tất cả phần tử và độ phức tạp của nó chắc chắn là O(n).
• Độ phức tạp khi thêm vào giữa mảng động khác với độ phức tạp khi thêm vào cuối mảng

Indexing - chỉ mục trong mảng

Như các bạn đã biết thì khi làm việc với mảng, chúng ta có thể truy cập trực tiếp tới phần tử nào đó thông qua chỉ mục của nó (ví dụ: arr[5] dùng để truy cập đến phần tử thứ 6). Trở lại khái niệm của mảng thì các phần tử được lưu trong các ô nhớ liên tiếp nhau hoặc lưu theo cách có thể tính được vị trí của các phần tử bằng một biểu thức toán học. Và chỉ mục chính là tham số chính để xác định được vị trí của phần tử trong bộ nhớ.

Ví dụ: một mảng int gồm 10 phần tử được lưu trữ trong bộ nhớ, với mỗi phần tử int thì cần 4 byte dể lưu trữ thì lúc này hệ thống sẽ dành một vùng nhớ 40 byte để tạo mảng. Giả sử vùng nhớ này là từ ô nhớ 1000 ~ 1039, phần tử đầu tiên sẽ lưu ở 1000, phần tử thứ 2 sẽ là 1004.. Nếu là zero-base indexing thì index của các phần tử sẽ là từ 0 - 9 và biểu thức xác định vị trí của phần tử thứ i sẽ là 1000 + (i x 4)

Thông qua biểu thức này, thì việc truy cập phần tử theo chỉ mục chỉ có độ phức tạp là O(1), tức là rất nhanh.

Lời kết

Rất mong qua bài viết này các bạn có cái nhìn sâu hơn về cấu trúc dữ liệu mảng: cách tổ chức lưu trữ trong bộ nhớ cũng như cách nó hoạt động khi thêm/ xóa phần từ hay truy cập phần tử bằng chỉ mục. Ngoài cũng câu lệnh thực thi thì chúng ta cũng đã nắm được những xử lý đằng sau của nó. Thật tuyệt vời đúng không.