Bài 9: Mảng & Cấu Trúc


1. Nhắc lại kiểu dữ liệu cơ bản

Kiểux86-6432-bit
char11
short22
int44
long84
float44
double88
long double10/16
pointer84

Lưu ý quan trọng: Sự khác biệt lớn nhất giữa 32-bit và 64-bit là kiểu longpointer — trên 64-bit chúng chiếm 8 bytes thay vì 4.


2. Mảng 1 chiều (1D Array)

2.1 Cấp phát mảng

Khai báo tổng quát:

T A[L];

Ý nghĩa:

  • T là kiểu dữ liệu phần tử
  • L là số lượng phần tử
  • Vùng nhớ được cấp phát liên tục với tổng kích thước = L * sizeof(T) bytes
  • Định danh A có thể dùng như con trỏ trỏ đến phần tử đầu tiên (A ≡ &A[0])

Ví dụ minh hoạ bộ nhớ:

char string[12];   →  chiếm [x, x+12)
int  val[5];       →  chiếm [x, x+20), mỗi phần tử cách nhau 4 bytes
double a[3];       →  chiếm [x, x+24), mỗi phần tử cách nhau 8 bytes
char* p[3];        →  chiếm [x, x+24) trên x86-64 (pointer = 8 bytes)

2.2 Byte Ordering và mảng

Byte ordering không ảnh hưởng đến thứ tự các phần tử trong mảng (phần tử index 0 vẫn luôn ở địa chỉ thấp hơn index 1), nhưng ảnh hưởng đến thứ tự các byte bên trong mỗi phần tử có kích thước > 1 byte.

Ví dụ với int array[4] = {1, 5, 3, 7} — giá trị 5 (0x00000005):

Little Endian:  05 00 00 00  (byte thấp trước)
Big Endian:     00 00 00 05  (byte cao trước)

2.3 Truy xuất mảng

int val[5];  // Giả sử địa chỉ bắt đầu là x
// val = {1, 5, 2, 1, 3}
Biểu thứcKiểuGiá trị
val[4]int3
valint *x
val + 1int *x + 4
&val[2]int *x + 8
val[5]intundefined (ngoài mảng!)
*(val+1)int5
val + iint *x + 4*i

2.4 Ví dụ bảng truy xuất (IA32)

Cho các khai báo sau trong hệ thống 32-bit:

char    A[12];
char   *B[8];
double  C[7];
double *D[5];
char  **E[5];
MảngĐịa chỉ phần tử iĐịa chỉ bắt đầuTổng kích thướcKích thước phần tử
AxA + ixA12 bytes1
BxB + 4ixB32 bytes4 (pointer 32-bit)
CxC + 8ixC56 bytes8
DxD + 4ixD20 bytes4
ExE + 4ixE20 bytes4

2.5 Ví dụ assembly: đọc phần tử mảng

typedef int zip_dig[5];

int get_digit(zip_dig z, int i) {
    return z[i];
}

Assembly sinh ra (IA32):

# %edx = z (địa chỉ đầu mảng)
# %eax = i (chỉ số)
movl (%edx, %eax, 4), %eax   # đọc ô nhớ tại địa chỉ z + 4*i

Giải thích: Cú pháp (%edx, %eax, 4) = Mem[%edx + %eax * 4]. Vì mỗi int = 4 bytes, phần tử thứ i nằm cách đầu mảng 4*i bytes.


2.6 Vòng lặp trên mảng

Dùng chỉ số (IA32)

void zincr(zip_dig z) {
    int i;
    for (i = 0; i < 5; i++)
        z[i]++;
}
# %edx = z
        movl  $0, %eax        # i = 0
        jmp   .L3             # goto kiểm tra điều kiện
.L4:                          # loop:
        addl  $1, (%edx,%eax,4)  # z[i]++  (dùng i tính địa chỉ)
        addl  $1, %eax        # i++
.L3:
        cmpl  $5, %eax        # so sánh i với 5
        jne   .L4             # nếu i != 5, quay lại loop

Câu hỏi: Nếu đổi thành `short zip_dig[6]`, code thay đổi như thế nào?

Có 2 điểm thay đổi:

  • Dòng so sánh: cmpl $5, %eaxcmpl $6, %eax (vì giờ có 6 phần tử)
  • Dòng tăng giá trị: addl $1, (%edx,%eax,4)addw $1, (%edx,%eax,2) vì:
    • addw thay cho addl (thao tác trên word 2 bytes thay vì dword 4 bytes)
    • Scale factor 42 (mỗi short chỉ 2 bytes, nên bước nhảy là 2*i)

Dùng con trỏ (IA32)

void zincr_v(zip_dig z) {
    void *vz = z;
    int dt = 0;
    do {
        (*((int *)(vz + dt)))++;
        dt += 4;
    } while (dt != 4 * 5);
}
# %edx = z = vz
        movl  $0, %eax          # dt = 0
.L8:
        addl  $1, (%edx,%eax)   # tăng giá trị tại vz+dt
        addl  $4, %eax          # dt += 4
        cmpl  $20, %eax         # so sánh dt với 20 (= 4*5)
        jne   .L8

Khác biệt so với dùng chỉ số: thay vì dùng i để tính 4*i, ta trực tiếp cộng dồn khoảng cách (offset) dt, rồi dùng (%edx, %eax) = Mem[vz + dt].

Câu hỏi: Nếu đổi thành `short zip_dig[6]`?
  • Dòng so sánh: cmpl $20, %eaxcmpl $12, %eax (vì 2*6 = 12)
  • Dòng tăng offset: addl $4, %eaxaddl $2, %eax (bước nhảy = sizeof(short) = 2)
  • Dòng thao tác: addl $1, (%edx,%eax)addw $1, (%edx,%eax) (thao tác 2 bytes)

Phiên bản x86-64

void zincr(zip_dig z) {
    size_t i;
    for (i = 0; i < 5; i++)
        z[i]++;
}
# %rdi = z
        movl  $0, %eax
        jmp   .L3
.L4:
        addl  $1, (%rdi,%rax,4)  # z[i]++
        addq  $1, %rax           # i++ (dùng addq vì i là size_t = 64-bit)
.L3:
        cmpq  $4, %rax           # so sánh với 4 (điều kiện i <= 4 tức i < 5)
        jbe   .L4                # jump if below or equal
        rep; ret

Lệnh jbe (jump if below or equal) dùng cho so sánh unsigned — phù hợp với kiểu size_t không dấu. Đây là điểm khác biệt quan trọng so với jl (signed less than).


2.7 Câu hỏi ôn tập: Mảng 1 chiều

Bài tập: Tìm T và N trong hệ 32-bit, biết `T A[N]` có tổng kích thước 20 bytes

Giải:

Ta có: sizeof(T) * N = 20

Với sizeof(T) ∈ {1, 2, 4, 8}N là số nguyên dương:

sizeof(T)NKết luận
120char A[20]
210short A[10]
45int A[5], float A[5], char* A[5] (pointer 32-bit = 4)
82.5❌ N không nguyên

Đáp án: Ba trường hợp thỏa mãn.


3. Mảng 2 chiều (Nested Array)

3.1 Định nghĩa và bố cục bộ nhớ

T A[R][C];   // R hàng, C cột, mỗi phần tử T chiếm K bytes
  • Tổng kích thước: R * C * K bytes
  • Bố cục: Row-Major Order — các phần tử của cùng một hàng nằm liên tiếp nhau trong bộ nhớ
Trong bộ nhớ (int A[3][4]):
A[0][0] A[0][1] A[0][2] A[0][3] | A[1][0] A[1][1] ... | A[2][0] ...
^--- hàng 0 liên tục ---^         ^--- hàng 1 ---^

3.2 Công thức tính địa chỉ

Địa chỉ A[i][j] = &A + i*(C*K) + j*K
                = &A + (i*C + j)*K

Ví dụ với int pgh[6][5] (tức zip_dig pgh[6]):

#define PCOUNT 6
zip_dig pgh[PCOUNT] = {
    {1, 5, 2, 0, 6},
    {1, 5, 2, 1, 3},
    ...
};

Địa chỉ pgh[i][j] = pgh + 20*i + 4*j (vì C=5, K=4, nên C*K=20)

Lấy giá trị phần tử `1` ở hàng 2 cột 3 của `pgh`?
  • Cú pháp C: pgh[2][3]
  • Địa chỉ: pgh + 2*20 + 3*4 = pgh + 40 + 12 = pgh + 52
  • Nếu pgh bắt đầu tại địa chỉ 76: địa chỉ phần tử = 76 + 52 = 128

3.3 Truy xuất một hàng

A[i] là một mảng con gồm C phần tử kiểu T:

Địa chỉ bắt đầu A[i] = &A + i*(C*K)

Khi truyền A[i] vào hàm, ta truyền địa chỉ đầu hàng đó — đây là con trỏ tới phần tử A[i][0].


3.4 Assembly: truy xuất phần tử mảng 2 chiều (IA32)

int get_pgh_digit(int index, int dig) {
    return pgh[index][dig];
}
movl  8(%ebp), %eax           # eax = index
leal  (%eax,%eax,4), %eax     # eax = 5*index  (index + 4*index)
addl  12(%ebp), %eax          # eax = 5*index + dig
movl  pgh(,%eax,4), %eax      # đọc pgh + 4*(5*index + dig)

Giải thích từng bước:

  1. Load index vào %eax
  2. leal (%eax,%eax,4) = eax + 4*eax = 5*index (tính số phần tử tính từ đầu đến hàng index)
  3. Cộng thêm dig5*index + dig (chỉ số tuyến tính trong mảng 1D)
  4. Scale với 4 (sizeof int) và cộng địa chỉ pgh

4. Mảng Nhiều Cấp (Multi-Level Array)

4.1 Khái niệm

int *univ[3] = {mit, cmu, ucb};

Đây không phải mảng 2 chiều thực sự. Cấu trúc:

univ[0] → địa chỉ của mit → [0, 2, 1, 3, 9]
univ[1] → địa chỉ của cmu → [1, 5, 2, 1, 3]
univ[2] → địa chỉ của ucb → [9, 4, 7, 2, 0]
  • univ là mảng 3 phần tử, mỗi phần tử là con trỏ (4 hoặc 8 bytes)
  • Mỗi con trỏ trỏ đến một mảng int nằm ở vùng nhớ riêng biệt — không liên tục nhau

4.2 So sánh Nested Array vs Multi-Level Array

Cú pháp C A[i][j] giống nhau, nhưng cách tính địa chỉ hoàn toàn khác:

Nested Array:     Mem[pgh + 20*index + 4*digit]    → 1 lần đọc bộ nhớ
Multi-Level:      Mem[Mem[univ + 4*index] + 4*digit] → 2 lần đọc bộ nhớ

Assembly cho multi-level (IA32):

# int get_univ_digit(int index, int digit)
movl  8(%ebp), %eax           # eax = index
movl  univ(,%eax,4), %edx     # edx = univ[index]  ← lần đọc 1: lấy con trỏ
movl  12(%ebp), %eax          # eax = digit
movl  (%edx,%eax,4), %eax     # eax = *(univ[index] + 4*digit)   lần đọc 2

5. Ma Trận N×N

5.1 Ba cách hiện thực

Cách 1: Số chiều cố định (biết tại compile time)

#define N 16
typedef int fix_matrix[N][N];

int fix_ele(fix_matrix a, size_t i, size_t j) {
    return a[i][j];
}

Địa chỉ a[i][j] = &a + i*(N*4) + j*4 = &a + 64*i + 4*j

movl  12(%ebp), %edx   # edx = i
sall  $6, %edx         # edx = i*64  (shift left 6 = nhân 2^6 = 64)
movl  16(%ebp), %eax   # eax = j
sall  $2, %eax         # eax = j*4
addl  8(%ebp), %eax    # eax = &a + j*4
movl  (%eax,%edx), %eax # đọc *(a + j*4 + i*64)

Cách 2: Số chiều biến đổi, đánh chỉ số tường minh (cách truyền thống)

#define IDX(n, i, j) ((i)*(n) + (j))

int vec_ele(size_t n, int *a, size_t i, size_t j) {
    return a[IDX(n, i, j)];
}

Mảng 2D được “giả lập” trên mảng 1D, lập trình viên tự tính chỉ số. Hữu ích khi n chỉ biết lúc runtime.


Cách 3: Số chiều biến đổi, đánh chỉ số ngầm (VLA — Variable Length Array, C99)

int var_ele(size_t n, int a[n][n], size_t i, size_t j) {
    return a[i][j];
}
movl  8(%ebp), %eax    # eax = n
sall  $2, %eax         # eax = n*4
movl  %eax, %edx
imull 16(%ebp), %edx   # edx = i*n*4
movl  20(%ebp), %eax   # eax = j
sall  $2, %eax         # eax = j*4
addl  12(%ebp), %eax   # eax = &a + j*4
movl  (%eax,%edx), %eax # đọc *(a + j*4 + i*n*4)

Khác biệt với fix_matrix: phải dùng lệnh imull (nhân nguyên) vì n không biết trước → không thể dùng shift cố định.


6. Bài Tập Tổng Hợp

Bài tập 1

Xác định M và N của `int array[M][N]`
# %ecx = i, %edx = j
movl  $array, %eax
sall  $2, %edx              # edx = 4*j
leal  (%edx, %eax), %eax   # eax = array + 4*j
movl  (%eax, %ecx, 16), %eax  # eax = *(array + 4*j + 16*i)

Từ công thức địa chỉ: array + i*(N*4) + j*4

So sánh với code: array + 16*i + 4*j

N*4 = 16N = 4

Đáp án: B — N = 4 (M không xác định được từ đoạn code này vì ta không thấy giới hạn vòng lặp)


Bài tập 2

Tìm M, N của `mat1[M][N]` và `mat2[N][M]`
int sum_element(int i, int j) {
    return mat1[i][j] + mat2[j][i];
}
movl  8(%ebp),  %ecx    # ecx = i
movl  12(%ebp), %edx    # edx = j
leal  0(,%ecx,8), %eax  # eax = 8*i
subl  %ecx, %eax        # eax = 8*i - i = 7*i
addl  %edx, %eax        # eax = 7*i + j   → chỉ số tuyến tính mat1[i][j]
movl  mat1(,%eax,4), %eax  # mat1 + 4*(7*i + j) → N = 7

leal  (%edx,%edx,4), %edx  # edx = 5*j
addl  %ecx, %edx           # edx = 5*j + i  → chỉ số tuyến tính mat2[j][i]
addl  mat2(,%edx,4), %eax  # mat2 + 4*(5*j + i)  M = 5

Phân tích:

  • mat1[i][j]: chỉ số = 7*i + jmat1[M][7]N = 7
  • mat2[j][i]: chỉ số = 5*j + imat2[7][5]M = 5

Đáp án: M = 5, N = 7


Bài tập 3

Tìm T và N của `T A[N][N]` trong hệ 32-bit

Cho: &A = 0x1000, &A[2][2] = 0x101C

Giải:

Công thức: &A[2][2] = &A + 2*sizeof(T)*N + 2*sizeof(T)

0x101C - 0x1000 = 0x1C = 28 bytes
28 = 2*sizeof(T)*(N + 1)
sizeof(T)*(N+1) = 14

Xét các trường hợp:

sizeof(T)N+1NKết luận
11413char A[13][13]
276short A[6][6]
43.5❌ không nguyên
81.75❌ không nguyên

Đáp án: char A[13][13] hoặc short A[6][6]