Mảng là một tập hợp có thứ tự gồm một số cố định các phần tử. Không có phép bổ sung phần tử hoặc loại bỏ phần tử được thực hiện.
Các phép toán thao tác trên mảng bao gồm : phép tạo lập [create] mảng, phép tìm kiếm [retrieve] một phần tử của mảng, phép lưu trữ [store] một phần tử của mảng.
Các phần tử của mảng được đặc trưng bởi chỉ số [index] thể hiện thứ tự của các phần tử đó trong mảng.
Mảng bao gồm các loại:
+ Mảng một chiều: Mảng mà mỗi phần tử ai của nó ứng với một chỉ số i.
Ví dụ : Véc tơ a[i] trong đó 0 = 1 . . n cho biết véc tơ là mảng một chiều gồm có n phần tử.
Khai báo : kiểu phần tử A[0...n]
A: Tên biến mảng; Kiểu phần tử: Chỉ kiểu của các phần tử mảng [integer, real, . . .]
+ Mảng hai chiều: Là mảng mà mỗi phần tử aij của nó ứng với hai chỉ số i và j
Ví dụ : Ma trận A[i],[j] là mảng 2 chiều có i là chỉ số hàng của ma trận và j là chỉ số cột của ma trận.
i = 0 . . n; j = 0 . . m
n: Số hàng của ma trận; m : số cột của ma trận.
Khai báo : kiểu phần tử A[n][m];
+ Mảng n chiều : Tương tự như mảng 2 chiều.
Cấu trúc dữ liệu đơn giản nhất dùng địa chỉ tính được để thực hiện lưu trữ và tìm kiếm phần tử, là mảng một chiều hay véc tơ.
Thông thường thì một số từ máy sẽ được dành ra để lưu trữ các phần tử của mảng. Cách lưu trữ này được gọi là cách lưu trữ kế tiếp [sequential storage allocation].
Trường hợp một mảng một chiều hay véc tơ có n phần tử của nó có thể lưu trữ được trong một từ máy thì cần phải dành cho nó n từ máy kế tiếp nhau. Do kích thước của véc tơ đã được xác định nên không gian nhớ dành ra cũng được ấn định trước.
Véc tơ A có n phần tử, nếu mỗi phần tử ai [0 ≤ i ≤ n] chiếm c từ máy thì nó sẽ được lưu trữ trong cn từ máy kế tiếp như hình vẽ:
L0 – Địa chỉ của phần tử a0
Địa chỉ của ai được tính bởi công thức:
Loc[ai] = L0 + c * i
trong đó :
L0 được gọi là địa chỉ gốc - đó là địa chỉ từ máy đầu tiên trong miền nhớ kế tiếp dành để lưu trữ véc tơ [gọi là véc tơ lưu trữ].
f[i] = c * i gọi là hàm địa chỉ [address function]
Đối với mảng nhiều chiều việc lưu trữ cũng tương tự như vậy nghĩa là vẫn sử dụng một véc tơ lưu trữ kế tiếp như trên.
| a01 | a11 | . . . | aij | . . . | anm |
Giả sử mỗi phần tử trong ma trận n hàng m cột [mảng nhiều chiều] chiếm một từ máy thì địa chỉ của aij sẽ được tính bởi công thức tổng quát như sau:
Loc[aij] = L0 + j * n + i { theo thứ tự ưu tiên cột [column major order }
Cũng với ma trận n hàng, m cột cách lưu trữ theo thứ tự ưu tiên hàng [row major order] thì công thức tính địa chỉ sẽ là:
Loc[aij] = L0 + i * m + j
+ Trường hợp cận dưới của chỉ số không phải là 1, nghĩa là ứng với aij thì b1 ≤ i ≤ u1, b2 ≤ j ≤ u2 thì ta sẽ có công thức tính địa chỉ như sau:
Loc[aij] = L0 + [i - b1] * [u2 - b2 + 1] + [j - b2]
vì mỗi hàng có [u2 - b2 + 1] phần tử.
Ví dụ : Xét mảng ba chiều B có các phần tử bijk với 1 ≤ i ≤ 2;
1 ≤ j ≤ 3; 1 ≤ k ≤ 4; được lưu trữ theo thứ tự ưu tiên hàng thì các phần tử của nó sẽ được sắp đặt kế tiếp như sau:
b111, b112, b113, b114, b121, b122, b123, b124, b131, b132, b133, b134, b211, b212, b213, b214, b221, b222, b223, b224, b231, b232, b233, b234.
Công thức tính địa chỉ sẽ là :
Loc[aijk] = L0 + [i - 1] *12 + [j - 1] * 4 + [k - 1]
VD Loc[b223] = L0 + 22.
Xét trường hợp tổng quát với mảng A n chiều mà các phần tử là :
A[s1, s2, . . ., sn] trong đó bi ≤ si ≤ ui [ i = 1, 2, . . ., n], ứng với thứ tự ưu tiên hàng ta có:
đặc biệt pn = 1.
Chú ý :
- Khi mảng được lưu trữ kế tiếp thì việc truy nhập vào phần tử của mảng được thực hiện trực tiếp dựa vào địa chỉ tính được nên tốc độ nhanh và đồng đều đối với mọi phần tử.
- Mặc dầu có rất nhiều ứng dụng ở đó mảng có thể được sử dụng để thể hiện mối quan hệ về cấu trúc giữa các phần tử dữ liệu, nhưng không phải không có những trường hợp mà mảng cũng lộ rõ những nhược điểm của nó.
Ví dụ : Xét bài toán tính đa thức của x,y chẳng hạn cộng hai đa thức sau:
[3x2 - xy + y2 + 2y - x]
+ [x2 + 4xy - y2 +2x]
= [4x2 + 3xy + 2y + x]
Ta biết khi thực hiện cộng 2 đa thức ta phải phân biệt được từng số hạng, phân biệt được các biến, hệ số và số mũ.
Để biểu diễn được một đa thức với 2 biến x,y ta có thể dùng ma trận: hệ số của số hạng xiyj sẽ được lưu trữ ở phần tử có hàng i cột j của ma trận. Nếu ta hạn chế kích thước của ma trận là n × n thì số mũ cao nhất của x,y chỉ xử lý được với đa thức bậc n-1 thôi.
Với cách biểu diễn kiểu này thì việc thực hiện phép cộng hai đa thức chỉ là cộng ma trận mà thôi. Nhưng nó có một số hạn chế : số mũ của đa thức bị hạn chế bởi kích thước của ma trận do đó lớp các đa thức được xử lý bị giới hạn trong một phạm vi hẹp. Mặt khác ma trận biểu diễn có nhiều phần tử bằng 0, dẫn đến sự lãng phí bộ nhớ.
Gọi là tế bào nhớ. Là khối lưu trữ dữ liệu nhỏ nhất được tạo ra. Một memory cell lưu trữ 1 bit.
Một tế bào nhớ bao gồm một transistor và một tụ điện. Transistor cho phép tụ điện tích trữ điện tích [electron]. Khi tụ điện tích điện đủ sẽ đại diện cho bit 1 [hiệu điện thế cao – high voltage level], khi tụ điện giải phóng điện tích sẽ đại diện cho bit 0 [hiệu điện thế thấp – low voltage level].
Các tế bào nhớ thường được sắp xếp theo dạng lưới. Mỗi hàng gồm có 8 tế bào nhớ, hình thành nên một byte. Người ta quy định đó là smallest addressable unit of memory.
Bộ nhớ có những tế bào nhớ có thể được truy xuất ngẫu nhiên, gọi là Random Access Memory [RAM].
Tạm dịch là đơn vị nhỏ nhất có thể đánh địa chỉ để quản lý bộ nhớ. Đơn vị này là gồm 8 bit liên tiếp [1 byte]. Tạm gọi là ô nhớ [các bạn đừng nhầm lẫn với memory cell, memory cell là tế bào nhớ chứ không phải ô nhớ].
Mỗi ô nhớ được đánh địa chỉ để CPU có thể truy xuất vào bộ nhớ. Địa chỉ thường được biểu diễn dưới dạng hệ cơ số 16 [hexadecimal]. Ví dụ như 0x008888ff, 0x001002fe,…[0x là quy ước trong C/C++, chữ số bắt đầu bằng 0x thì hiểu đó là số nguyên được biểu diễn dưới dạng hệ cơ số 16].
Các ô nhớ có địa chỉ duy nhất và được đánh số từ 0 trở đi. Số lượng địa chỉ có thể đánh cho ô nhớ phụ thuộc vào độ rộng thanh ghi trong CPU. Ví dụ, CPU 32 bit thì có 2^32 địa chỉ có thể đánh cho các ô nhớ trong RAM.
Khi gặp một lệnh khai báo biến:
int a; float f;Chương trình sẽ cấp phát cho biến số ô nhớ liền kề [tạm gọi là vùng nhớ] có kích thước tương ứng với kích thước kiểu dữ liệu của biến.
Ví dụ: Khi khai báo một biến a kiểu int 4 bytes, chương trình sẽ tự động cấp phát 1 vùng nhớ 4 bytes [gồm 4 ô nhớ liền kề đang trống và không bị sử dụng bởi chương trình khác]. Rồi lưu lại địa chỉ của ô nhớ đầu tiên mà biến nắm giữ và xem đó là địa chỉ của biến a, chẳng hạn là 0x0000fffe. Khi đó, mỗi lần gọi tới biến a thì hệ thống sẽ dùng địa chỉ 0x0000fffe để truy xuất dữ liệu lưu trong biến đó.
Hệ điều hành sẽ tạo ra một bảng để đối chiếu, ánh xạ giữa tên biến và địa chỉ. Ví dụ:
| Tên biến | Địa chỉ |
| name | 0x0000ffef |
| age | 0x0f001ffff |
| x | 0x01020304 |
| i | 0x040203ff |
Với ngôn ngữ C/C++, bạn có thể biết địa chỉ của một biến được cấp phát trong bộ nhớ thông qua toán tử &. Bên dưới là chương trình in ra địa chỉ của các biến.
#include using namespace std; int main[] { int a; float b; cout