Trong khoa học máy tính, Array(mảng) là một cấu trúc dữ liệu bao gồm một tập các phần tử, mà mỗi phần tử được xác định bởi một chỉ mục hoặc khoá.
Mảng có rất nhiều biến thể, trong đó đơn giản nhất là mảng một chiều, ngoài ra còn1 có mảng 2 chiều,… Mảng cũng có thể dùng để implement table, vector.
Một mảng được lưu trữ sao cho vị trí của mỗi phần tử được tính tính dựa trên một biểu thức toán học. Cho ví dụ sau, một mảng số nguyên có 10 phần tử, có chỉ mục tử 0 đến 9. Lúc này 10 phần tử của mảng có thể được lưu tại các địa chỉ trong memory như sau: 1000, 1002, 1004, 1006, … 1018. từ các địa chỉ trên ta có thể suy ra được địa chỉ các phần tử trong mảng được tính theo công tính 1000 + 2*i (với i là chỉ mục của các phần tử trong mảng).
Như vậy địa chỉ của phần tử đầu tiên của mảng được gọi là foundation address, các địa chỉ của các phần tử còn lại trong mảng được tính dựa trên địa chỉ của phần tử đầu tiên.
Mảng là một trong những cấu trúc dữ liệu lâu đời, và được sử dụng trong hầu hết các chương trình. Mảng còn được sử dụng để implement các cấu trúc dữ liệu khác như List, Strings,..
Thực hành
Tìm kiếm(Searching)
- Tìm kiếm, thêm, xoá phần tử trong mảng chưa được sắp xếp
- Tìm kiếm, thêm, xoá phần tử trong mảng đã được sắp xếp
- Cho mảng arr và số nguyên X, kiểm tra trong mảng cặp số có tổng bằng X
- Tìm phần tử trong mảng có phần tử liền kề cách nhau không quá k
- Tìm phần tử xuất hiện ở cả 3 mảng
- Tìm phần tử X trong mảng tăng dần, không cho biết số lượng phần tử của mảng
- Tìm phần tử duy nhất trong mảng bị lặp lại trong khoảng 1 đến n – 1
- Tìm phần tử chỉ xuất hiện một lần trong mảng
- Tìm tổng lớn nhất của các mảng con trong mảng A mà không chứa các phần tử trong B
Sắp xếp(Sorting)
- Xuất mạng theo dạng số lớn nhất – số bé nhất – số lớn thứ nhì – số bé thứ nhì cứ như vậy cho đến hết mảng
- Sắp xếp mảng tăng dần theo giá trị tuyệt đối |x – arr[i]| với x là phần tử cho trước, arr[i] là các phần tử của mảng
- Sắp xếp mảng theo dạng sóng. Mảng có dạng sóng : arr[0] >= arr[1] <= arr[2] <= arr[3] >= …
- Hãy hợp nhất 2 mảng A và B để có mảng output có m + n phần tử của A và B tăng dần
- Sắp xếp mảng theo số lần xuất hiện của các phần tử
- Tìm 2 phần tử có tổng gần bằng 0 nhất