Cấu trúc dữ liệu - Arrays

 

Mảng(Array) là một trong những cấu trúc dữ liệu cơ bản và được sử dụng rộng rãi trong phát triển phần mềm. Mảng cung cấp một cách để lưu trữ và tổ chức dữ liệu một cách hệ thống và hiệu quả về mặt bộ nhớ máy tính.

Về cơ bản, mảng là một tập hợp các phần tử, mỗi phần tử được xác định bằng một chỉ số mảng. Các phần tử của mảng được lưu trữ ở các vị trí bộ nhớ liên tiếp, có nghĩa là chúng được lưu trữ theo một chuỗi liên tục.

Mảng có kích thước tĩnh và động

Mảng có thể được phân loại thành hai loại dựa trên việc kích thước của chúng có thể thay đổi trong thời gian chạy hay không: mảng có kích thước tĩnh và mảng có kích thước động.

Mảng có kích thước tĩnh(Static-sized Arrays)

Định nghĩa: Mảng kích thước tĩnh có kích thước cố định, được xác định tại thời điểm biên dịch. Khi đã khai báo, kích thước của mảng tĩnh không thể thay đổi.

Đặc điểm:

• Kích Thước Cố Định: Số lượng phần tử mà mảng có thể chứa được định nghĩa khi mảng được tạo ra và không thể thay đổi.
• Cấp Phát Bộ Nhớ: Bộ nhớ cho mảng được cấp phát trên ngăn xếp (trong hầu hết các môi trường lập trình), điều này làm cho việc cấp phát và giải phóng bộ nhớ trở nên nhanh chóng.
• Hiệu Suất: Truy cập các phần tử trong mảng tĩnh rất nhanh vì các phần tử được lưu trữ liên tiếp trong bộ nhớ, cho phép việc lập chỉ mục hiệu quả.

Trường Hợp Sử Dụng: Lưu trữ một số lượng phần tử được xác định trước, chẳng hạn như các ngày trong tuần.

Dưới đây là cách khai báo mảng tĩnh trong javascript:

 let staticArray = new Array(5).fill(null); // Array with a fixed size of 5, filled with null  
 staticArray[0] = 1; // Assigning value to the first element  

Mảng có kích thước động(Dynamic-sized Arrays)

Định nghĩa: Mảng kích thước động có thể thay đổi kích thước trong thời gian chạy. Chúng có thể mở rộng hoặc thu nhỏ theo nhu cầu, cung cấp sự linh hoạt cao hơn.

Đặc điểm:

• Có Thể Thay Đổi Kích Thước: Mảng có thể điều chỉnh kích thước của nó trong thời gian chạy để chứa nhiều (hoặc ít) phần tử hơn so với khi được khai báo ban đầu.
• Cấp Phát Bộ Nhớ: Bộ nhớ cho mảng động thường được cấp phát trên đ heap, điều này cho phép chúng có kích thước linh hoạt nhưng cũng có nghĩa là việc quản lý bộ nhớ (cấp phát và giải phóng) phức tạp hơn và hơi chậm hơn.
• Xem Xét Hiệu Suất: Mặc dù mảng động cung cấp sự linh hoạt, nhưng các thao tác thay đổi kích thước (như mở rộng kích thước mảng) có thể yêu cầu cấp phát bộ nhớ mới và sao chép các phần tử hiện có đến vị trí mới, điều này có thể tốn kém về hiệu suất.

Trường Hợp Sử Dụng: Lưu trữ danh sách các đầu vào của người dùng khi số lượng đầu vào không được biết trước.

Dưới đây là cách khai báo mảng động trong javascript:

 let dynamicArray = []; // Dynamic array  
 dynamicArray.push(1); // Adding an element  

So Sánh:

• Tính Linh Hoạt: Mảng động cung cấp sự linh hoạt cao hơn so với mảng tĩnh vì chúng có thể mở rộng hoặc thu nhỏ trong thời gian chạy.
• Hiệu Suất: Mảng tĩnh thường cung cấp hiệu suất tốt hơn cho các tập hợp có kích thước cố định nhờ vào việc cấp phát bộ nhớ liên tiếp và không có chi phí thay đổi kích thước.
• Quản Lý Bộ Nhớ: Mảng tĩnh thường yêu cầu quản lý bộ nhớ thủ công ít hơn so với mảng động, vì mảng động có thể yêu cầu cấp phát và giải phóng bộ nhớ rõ ràng để quản lý bộ nhớ trên heap.
• Sử Dụng: Việc lựa chọn giữa mảng tĩnh và mảng động phụ thuộc vào yêu cầu cụ thể của ứng dụng, bao gồm việc kích thước của tập dữ liệu có được biết trước hay không và mức độ biến động của số lượng phần tử cần lưu trữ.

Khái Niệm cơ bản và các phép toán

1.Truy Cập Các Phần Tử

Mỗi phần tử trong mảng có thể được truy cập bằng cách sử dụng chỉ số của nó, chỉ số này biểu thị vị trí của phần tử trong mảng. Các chỉ số thường bắt đầu từ số không, có nghĩa là phần tử đầu tiên được truy cập bằng array[0], phần tử thứ hai bằng array[1], và cứ như vậy. Truy cập các phần tử trong mảng là một hoạt động có độ phức tạp thời gian O(1), vì nó trỏ đến vị trí bộ nhớ chính xác mà không cần phải lặp qua các phần tử khác.

2. Chèn Các Phần Tử

Việc chèn các phần tử có thể được thực hiện theo nhiều cách khác nhau, tùy thuộc vào yêu cầu của ứng dụng:

• Tại Cuối Mảng: Một phần tử có thể được chèn vào cuối mảng, thường là một hoạt động O(1).
• Tại Một Chỉ Số Cụ Thể: Nếu cần chèn tại một chỉ số cụ thể, các phần tử tiếp theo phải được di chuyển để tạo khoảng trống, làm tăng độ phức tạp thời gian lên O(n) trong trường hợp xấu nhất.

3. Xóa Các Phần Tử

Việc xóa các phần tử cũng đi kèm với các yếu tố cần cân nhắc:

• Từ Cuối Mảng: Xóa một phần tử từ cuối mảng thường là một hoạt động O(1), vì nó không yêu cầu di chuyển các phần tử khác.
• Từ Một Chỉ Số Cụ Thể: Xóa từ một chỉ số cụ thể yêu cầu phải di chuyển các phần tử tiếp theo để lấp đầy khoảng trống, làm cho đây trở thành một hoạt động có độ phức tạp thời gian O(n).

4. Tìm kiếm phần tử

Việc tìm kiếm liên quan đến việc xác định chỉ số của một phần tử cụ thể. Khi không có thông tin hoặc ràng buộc bổ sung, một tìm kiếm tuyến tính sẽ được thực hiện, quét từng phần tử cho đến khi tìm thấy phần tử cần tìm, với độ phức tạp là O(n). Tuy nhiên, nếu mảng đã được sắp xếp, tìm kiếm nhị phân có thể được sử dụng, giảm độ phức tạp xuống O(log n)

5. Cập nhật phần tử

Cập nhật một phần tử tại một chỉ số cụ thể có thể được thực hiện trực tiếp và thường là một thao tác O(1), vì nó chỉ liên quan đến việc thay đổi giá trị tại một vị trí bộ nhớ cụ thể mà không cần quét qua các phần tử khác.

Các thuộc tính của mảng(Arrays)

1. Phân bổ bộ nhớ

Mảng (arrays) được định nghĩa bằng cách cấp phát bộ nhớ liên tục, nghĩa là mỗi phần tử được lưu trữ ở các vị trí bộ nhớ liền kề nhau. Điều này cho phép mảng cung cấp khả năng truy cập vào bất kỳ phần tử nào trong thời gian hằng số thông qua chỉ mục, vì địa chỉ bộ nhớ của bất kỳ phần tử nào cũng có thể được tính toán bằng cách sử dụng địa chỉ cơ sở (base address), kích thước của một phần tử và chỉ mục của phần tử đó.

Về mặt toán học, nếu B đại diện cho địa chỉ cơ sở(Base Address), I  là chỉ mục(Index), và S  là kích thước(Size) của mỗi phần tử, thì địa chỉ  A của phần tử tại chỉ mục i  có thể được tính như sau:

A = B + (I × S)

Ví dụ:

Giả sử bạn có một mảng các số nguyên (int), với địa chỉ cơ sở $B = 1000$(được tính bằng byte), chỉ mục $i = 3$, và mỗi số nguyên có kích thước $S = 4$ byte. Để tìm địa chỉ của phần tử thứ 4 trong mảng (tại chỉ mục 3), bạn sẽ tính như sau:

$$A = 1000 + (3 \times 4) = 1000 + 12 = 1012$$

Vậy địa chỉ của phần tử tại chỉ mục 3 trong mảng sẽ là 1012 byte.

2. Lập chỉ mục

Mảng (arrays) sử dụng chỉ mục bắt đầu từ 0, trong đó phần tử đầu tiên được truy cập bằng chỉ mục 0, phần tử thứ hai bằng chỉ mục 1, và cứ tiếp tục như vậy. Việc đánh chỉ mục (indexing) cho phép truy cập trực tiếp vào bất kỳ phần tử nào trong mảng, nhờ đó có thể thực hiện các thao tác như tìm kiếm, cập nhật và truy cập trực tiếp với độ phức tạp thời gian ổn định (O(1)).

Lưu Ý Khi Làm Việc Với Mảng Trong Phỏng Vấn Lập Trình

Mảng có vẻ là một cấu trúc dữ liệu đơn giản, nhưng để xử lý chúng một cách thành thạo trong phỏng vấn đòi hỏi sự hiểu biết sâu rộng về các chi tiết tinh tế và những lỗi tiềm ẩn. Dưới đây là những điểm quan trọng mà ứng viên cần chú ý khi làm việc với mảng trong các buổi phỏng vấn lập trình:

1. Xác thực Giả Định:

   • Giá trị Trùng Lặp: Luôn làm rõ liệu mảng có cho phép giá trị trùng lặp hay không. Hãy hiểu rõ và trao đổi về cách các giá trị trùng lặp có thể ảnh hưởng đến phương pháp của bạn.
   • Sắp Xếp/Chưa Sắp Xếp: Kiểm tra xem mảng đã được sắp xếp chưa, vì một số thuật toán như tìm kiếm nhị phân yêu cầu mảng phải được sắp xếp trước.

2. Điều Kiện Biên:

   • Chỉ Mục Ngoài Phạm Vi: Đảm bảo rằng mã của bạn không truy cập vào chỉ mục nằm ngoài phạm vi của mảng. Sử dụng các điều kiện kiểm tra để tránh lỗi phổ biến này.
   • Chỉ Mục Âm: Trong một số ngôn ngữ như Python, chỉ mục âm cho phép truy cập phần tử từ cuối mảng. Hãy thận trọng khi sử dụng chúng.

3. Mối quan tâm về Hiệu Suất:

   • Cắt và Nối Mảng: Nhớ rằng việc cắt và nối mảng có thể tốn thời gian. Hãy cân nhắc kỹ lưỡng khi thực hiện các thao tác này, vì chúng có thể tăng đáng kể độ phức tạp thời gian của giải pháp.
   • Trong Chỗ và Sử Dụng Không Gian Bổ Sung: Cân nhắc xem có cần thiết phải tạo một mảng mới hay không, hay bạn có thể thao tác trực tiếp trên mảng hiện tại để tiết kiệm không gian bộ nhớ.

4. Đặt Tên Biến và Chỉ Mục Vòng Lặp:

   • Biến Mô Tả: Sử dụng tên biến mô tả rõ ràng để giữ cho mã của bạn dễ đọc và logic của bạn rõ ràng, đặc biệt là khi đang trong buổi phỏng vấn.
   • Chỉ Mục Vòng Lặp: Hãy chắc chắn rằng các vòng lặp kết thúc đúng điều kiện để tránh lỗi sai lệch một đơn vị.

5. Lựa Chọn Thuật Toán và Độ Phức Tạp:

   • Độ Phức Tạp Thời Gian và Không Gian: Luôn nhận thức về độ phức tạp thời gian và không gian của thuật toán bạn chọn, và sẵn sàng thảo luận về chúng.
   • Vòng Lặp Lồng Nhau: Cẩn thận với việc sử dụng vòng lặp lồng nhau, vì chúng có thể làm tăng độ phức tạp thời gian lên rất nhiều (ví dụ, lên O(n^2)).

6. Kiểm Thử:

   • Trường Hợp Biên: Kiểm thử giải pháp của bạn với các trường hợp biên như mảng rỗng, mảng chỉ có một phần tử, hoặc mảng với các phần tử giống nhau để đảm bảo tính ổn định.
   • Các Đầu Vào Khác Nhau: Kiểm thử với cả các trường hợp điển hình và trường hợp biên để đảm bảo giải pháp của bạn hoạt động tốt trong mọi tình huống.

7. Xử Lý Số 0 và Số Âm:

   • Luôn kiểm tra và làm rõ cách xử lý số 0 và số âm trong các bài toán liên quan đến mảng. Điều này đặc biệt quan trọng trong các bài toán liên quan đến tích hoặc tổng.

8. Thay Đổi Trong Quá Trình Lặp:

   • Hãy thận trọng khi thay đổi mảng trong khi bạn đang lặp qua nó, vì điều này có thể gây ra lỗi hoặc các hành vi không mong muốn. Đôi khi, việc lặp ngược lại hoặc sử dụng một mảng riêng biệt để lưu trữ các thay đổi có thể là một giải pháp hiệu quả.

9. Quen Thuộc Với Các Phương Thức Mảng:

   • Hãy quen thuộc với các phương thức mảng mà ngôn ngữ bạn đang sử dụng cung cấp và hiểu rõ độ phức tạp về thời gian và không gian của chúng.

10. Kết Quả Tạm Thời:

    • Biến Trung Gian: Xem xét việc lưu trữ các kết quả trung gian (ví dụ: tổng tích lũy hoặc tích lũy) có thể tối ưu hóa các phép tính lặp lại.
    • Nhiều Lượt Lặp: Cân nhắc ưu và nhược điểm của việc thực hiện nhiều lượt lặp qua mảng nếu điều đó đơn giản hóa và tối ưu hóa thuật toán tổng thể.

11. Lặp Song Song và Ngược Lại:

    • Đôi khi việc lặp qua mảng từ cuối đến đầu hoặc lặp song song qua hai mảng có thể là chìa khóa để tìm ra giải pháp tối ưu.

12. Hiểu Rõ Yêu Cầu Bài Toán:

    • Luôn đảm bảo rằng bạn đã hiểu đúng các yêu cầu và giới hạn của bài toán để tránh làm việc sai hướng.

Tiếp cận các bài toán liên quan đến mảng với những cân nhắc này sẽ giúp bạn xây dựng giải pháp chính xác và hiệu quả hơn trong các buổi phỏng vấn. Luôn trình bày rõ ràng quá trình suy nghĩ của mình và đừng ngại đặt câu hỏi để làm rõ vấn đề. Thực hành, phản hồi, và lặp lại nhiều bài toán sẽ giúp bạn hiểu sâu hơn và nâng cao kỹ năng giải quyết vấn đề với mảng.

Mảng trong Các Ngôn ngữ Lập trình Khác nhau

Mảng là một thành phần quan trọng trong lập trình, và hiểu cách chúng hoạt động trong các ngôn ngữ khác nhau là rất cần thiết. Hãy cùng tìm hiểu cách mảng được triển khai trong Java, Python, C++, JavaScript, C#, và Go.

Mảng trong Java: Cứng cáp và mạnh mẽ

• Kích thước cố định: Trong Java, khi bạn tạo một mảng, bạn cần xác định kích thước của nó và kích thước này không thể thay đổi sau đó.
  Ví dụ: int[] numbers = new int[5];
• Cùng loại dữ liệu: Tất cả các phần tử trong một mảng Java phải có cùng kiểu dữ liệu.
• Mảng nguyên thủy và đối tượng: Java hỗ trợ mảng của các kiểu dữ liệu nguyên thủy (như int, char, v.v.) và mảng đối tượng.
  • Mảng nguyên thủy tiết kiệm bộ nhớ hơn.
• Phân bổ bộ nhớ trực tiếp: Mảng trong Java được cấp phát bộ nhớ trực tiếp, đảm bảo truy cập nhanh chóng nhưng cũng có nghĩa là bạn phải quản lý kích thước một cách cẩn thận.

Mảng trong Python: Linh hoạt và động

• Danh sách động: "Mảng" trong Python thực ra là các danh sách, và chúng có thể mở rộng hoặc thu nhỏ kích thước.
  Ví dụ: numbers = [1, 2, 3], và bạn có thể đơn giản thêm phần tử bằng numbers.append(4).
• Kiểu dữ liệu hỗn hợp: Bạn có thể lưu trữ các phần tử với các kiểu dữ liệu khác nhau trong một danh sách Python.
  Ví dụ: mixed = [1, "hai", 3.0]
• Đối tượng ẩn dưới: Ngay cả khi bạn lưu trữ một kiểu dữ liệu nguyên thủy như số nguyên, Python vẫn xử lý nó như một đối tượng.
• Chi phí bộ nhớ: Do tính linh hoạt và động, danh sách Python tiêu tốn bộ nhớ nhiều hơn so với mảng trong Java.

Mảng trong C++: Nhanh chóng

• Kích thước cố định: Giống như Java, mảng C++ có kích thước cố định. Bạn quyết định kích thước khi tạo chúng.
  Ví dụ: int numbers[5];
• Cùng loại dữ liệu: Tất cả các phần tử phải có cùng kiểu dữ liệu.
• Tiết kiệm bộ nhớ: Mảng C++ rất tiết kiệm bộ nhớ và cung cấp truy cập nhanh chóng vì chúng được lưu trữ trong các vị trí bộ nhớ liên tiếp.
• Con trỏ và mảng: C++ có mối quan hệ chặt chẽ với con trỏ, cho phép bạn duyệt qua các phần tử mảng.

Mảng trong JavaScript: Linh hoạt

• Mảng động: Mảng trong JavaScript có thể mở rộng hoặc thu nhỏ kích thước động. Bạn không bị ràng buộc bởi kích thước ban đầu.
  Ví dụ: let numbers = [1, 2, 3]; numbers.push(4);
• Kiểu dữ liệu hỗn hợp: Bạn có thể tự do kết hợp các kiểu dữ liệu trong một mảng JavaScript.
  Ví dụ: let mixed = [1, "hai", 3.0];
• Đối tượng ẩn dưới: Mặc dù là mảng, JavaScript xử lý chúng như một đối tượng với các khóa là số nguyên.
• Bộ nhớ và hiệu suất: Do tính chất động và hướng đối tượng, mảng trong JavaScript có thể không tiết kiệm bộ nhớ như mảng trong các ngôn ngữ như C++ hoặc Java.

Mảng trong C#: Đa năng

• Mảng cố định và động: C# cung cấp cả mảng kích thước cố định và mảng động (thông qua Lists).
  Ví dụ: int[] numbers = new int[5]; (mảng cố định) hoặc List<int> numbers = new List<int>(); (mảng động)
• Cùng loại dữ liệu: Giống như Java và C++, các phần tử trong mảng C# cần có cùng kiểu dữ liệu.
• Quản lý bộ nhớ: Mảng trong C# tiết kiệm bộ nhớ và cung cấp truy cập nhanh chóng nhờ vào quản lý bộ nhớ hiệu quả của .NET.
• Tính năng phong phú: C# cung cấp rất nhiều phương thức và thuộc tính để thao tác với mảng, giúp công việc của lập trình viên dễ dàng hơn.

Mảng trong Go: Nhanh và hiệu quả

• Kích thước cố định: Tương tự như Java và C++, mảng trong Go có kích thước cố định. Một khi bạn đã xác định kích thước của mảng, nó không thể thay đổi. Điều này đảm bảo hiệu quả bộ nhớ và truy cập nhanh hơn nhờ vào việc cấp phát bộ nhớ tĩnh.
  Ví dụ: var numbers [5]int định nghĩa một mảng gồm năm số nguyên.
• Cùng loại dữ liệu: Tất cả các phần tử trong một mảng Go phải có cùng kiểu dữ liệu. Điều này phù hợp với sự chú trọng của ngôn ngữ về an toàn kiểu dữ liệu và hiệu quả.
• Kiểm soát ở mức thấp: Go cung cấp mức độ kiểm soát ở mức thấp tốt. Mặc dù quản lý bộ nhớ an toàn hơn so với C++, Go vẫn cho phép sử dụng bộ nhớ hiệu quả, gần như những gì bạn mong đợi ở C hoặc C++.
• Phân bổ bộ nhớ trực tiếp: Mảng trong Go được cấp phát bộ nhớ trực tiếp trong một khối liền kề. Sự cấp phát trực tiếp này góp phần vào hiệu suất và hiệu quả của các thao tác mảng, giống như trong Java và C++.
• Mảng là giá trị: Trong Go, mảng là giá trị. Khi bạn gán hoặc truyền mảng, bạn đang làm việc với một bản sao của mảng gốc. Điều này khác với các ngôn ngữ như C++, nơi mà mảng thực chất là con trỏ.
• Slices cho hành vi động: Để có hành vi động tương tự mảng, Go cung cấp slices. Slices là một giao diện linh hoạt và mạnh mẽ cho các dãy dữ liệu. Chúng được xây dựng trên mảng nhưng cung cấp nhiều chức năng hơn, chẳng hạn như khả năng thay đổi kích thước.
  Ví dụ: numbers := []int{1, 2, 3} tạo một slice của các số nguyên.
• Cân nhắc về hiệu suất: Do kích thước cố định và việc cấp phát bộ nhớ trực tiếp, mảng Go có thể hiệu quả hơn về mặt hiệu suất và sử dụng bộ nhớ, tương tự như mảng trong Java và C++. Đối với các trường hợp yêu cầu sự linh hoạt và động, slices được ưa chuộng nhưng sẽ có một chút chi phí so với mảng.

Tóm lại

• Java: Tiết kiệm bộ nhớ hơn với việc cấp phát bộ nhớ trực tiếp và hỗ trợ các kiểu nguyên thủy. Thường nhanh hơn do gần với phần cứng và có kích thước cố định.
• Python: Linh hoạt hơn nhưng có chi phí bộ nhớ cao hơn và có thể chậm hơn do tính chất động và hướng đối tượng.
• C++: Nếu bạn cần tốc độ thuần và sẵn sàng tự quản lý bộ nhớ, mảng C++ là sự lựa chọn tốt nhất.
• JavaScript: Để có sự linh hoạt tối đa và dễ sử dụng, mảng JavaScript là lựa chọn đáng tin cậy.
• C#: Một sự kết hợp tuyệt vời giữa hiệu suất và chức năng, mảng (và Lists) trong C# mang đến trải nghiệm phong phú.
• Go: Mảng Go phù hợp cho các tình huống yêu cầu sử dụng bộ nhớ và hiệu suất có thể dự đoán được và hiệu quả, trong khi slices mang lại nhiều linh hoạt hơn và dễ sử dụng hơn cho các cấu trúc dữ liệu động.