Chương 5: Mảng và chuỗi

Cấu trúc dữ liệu cơ bản cho phép lưu trữ một tập hợp các phần tử cùng kiểu dữ liệu. Chương này cung cấp các kiến thức cơ bản về mảng, mảng 1 chiều, mảng nhiều chiều và chuỗi (mảng kí tự).

---

1. Khái niệm

1.1. Khái niệm mảng

• Mảng trong lập trình là một cấu trúc dữ liệu cơ bản, giúp lưu trữ nhiều giá trị cùng kiểu trong một dãy có thứ tự.

  Bạn có thể hình dung nó như một chiếc kệ sách, mỗi ngăn đều chứa một cuốn sách cùng thể loại. Nhờ cách tổ chức này, việc truy cập và xử lý dữ liệu trở nên nhanh chóng và hiệu quả.

• Kích thước mảng được xác định ngay khi khai báo và không thay đổi.
• Mảng là một kiểu dữ liệu có cấu trúc do người lập trình định nghĩa.
• Ngôn ngữ lập trình $\texttt{C++}$ luôn chỉ định một khối nhớ liên tục cho một biến kiểu mảng.
• $\texttt{C++}$ hỗ trợ mảng một chiều và mảng đa nhiều (đơn giản nhất là mảng hai chiều).
• Mảng một chiều các ký tự được dùng để biểu diễn chuỗi C-string.

Ví dụ về cấu trúc lưu trữ:

• Mảng 1 chiều 6 giá trị số nguyên:
  • Giá trị: 6, 4, 7, 7, 9, 2
  • Địa chỉ (Giả định): 0x61fdf0, 0x61fdf4, 0x61fdf8, 0x61fdfc, 0x61fe00, 0x61fe04
• Mảng 1 chiều 5 ký tự:
  • Ký tự: 'h', 'e', 'l', 'l', 'o'
  • Địa chỉ (Giả định): 0x61fdeb, 0x61fdec, 0x61fded, 0x61fdee, 0x61fdef
• Mảng 2 chiều số thực 2 dòng 3 cột:
  • Ma trận:

    0.1   9.75   3.6 
    2.2   0.125   9.5 
  • Giá trị liên tục: 0.1, 9.75, 3.6, 2.2, 0.125, 9.5
  • Địa chỉ (Giả định): 0x61fdb0, 0x61fdb4, 0x61fdb8, 0x61fdbc, 0x61fdc0, 0x61fdc4

1.2. Lợi ích của mảng

Một số lợi ích quan trọng của mảng:

• Truy cập dữ liệu nhanh chóng: Truy cập phần tử dễ dàng thông qua chỉ số $\to$ truy cập và thay đổi giá trị.
• Quản lý dữ liệu đồng nhất: Mảng chỉ chứa các phần tử có cùng kiểu dữ liệu.
• Đơn giản và dễ sử dụng: Cú pháp của mảng tương đối đơn giản và dễ hiểu.
• Tích hợp với các hàm và thư viện: $\texttt{C++}$ cung cấp nhiều hàm và thư viện hỗ trợ thao tác với mảng.
• Tính linh hoạt trong sử dụng: Mảng có thể được sử dụng để triển khai nhiều cấu trúc dữ liệu khác nhau như hàng đợi (queue), ngăn xếp (stack).

---

1.3. Các yếu tố xác định mảng

Trong mảng, ta có 5 yếu tố xác định mảng, bao gồm:

• Tên mảng:
  • Tên gọi của mảng, được đặt theo quy tắc đặt tên biến.
  • Thông qua tên gọi kèm chỉ số có thể truy xuất đến từng phần tử của mảng.
• Kiểu mảng : Là kiểu dữ liệu của các phần tử trong mảng.
• Số chiều : Mảng 1 chiều, mảng 2 chiều hay mảng đa nhiều.
• Kích thước : Số lượng phần tử tối đa có thể lưu trữ theo mỗi chiều của mảng.

Ví dụ minh họa:

• Ví dụ: Mảng a là mảng 1 chiều lưu trữ 6 số nguyên:
  • Giá trị: {6, 4, 7, 7, 9, 2}
  • Tên mảng: a
  • Kiểu mảng: int
  • Số chiều: 1 chiều
  • Kích thước: 10 phần tử
• Ví dụ: Mảng str là mảng 1 chiều lưu trữ 5 ký tự: 'h', 'e', 'l', 'l', 'o'.
  • Tên mảng: str
  • Kiểu mảng: char
  • Số chiều: mảng 1 chiều
  • Kích thước: 5 phần tử
• Ví dụ: Mảng b là mảng 2 chiều lưu trữ 2 dòng 3 cột các giá trị số thực:
  • Ma trận:

    0.1, 9.75, 3.6 
    2.2, 0.125, 9.5 
  • Tên mảng: b
  • Kiểu mảng: float
  • Số chiều: mảng 2 chiều
  • Kích thước: 2 dòng x 3 cột = 6 phần tử

---

2. Mảng 1 chiều

Để bắt đầu hành trình với mảng trong $\texttt{C++}$, chúng ta sẽ làm quen trước với mảng một chiều, dạng đơn giản và dễ hình dung nhất.

2.1. Khai báo và khởi tạo mảng 1 chiều

2.1.1. Khai báo mảng 1 chiều

Cú pháp:

<Kiểu_dữ_liệu> <Tên_biến_mảng>[<Số_phần_tử>]; 

Trong đó

• <Kiểu_dữ_liệu>: int, float, char, ...
• <Tên_biến_mảng>: Đặt tên theo quy tắc đặt tên/định danh
• <Số_phần_tử>: Là số lượng tối đa các phần tử mảng có thể lưu trữ. Cần xác định ngay khi khai báo. Là một hằng số nguyên (literal, hoặc dùng const hoặc define để định nghĩa).

Ví dụ

• Khai báo Tường minh:

  int a[100];
  $\to$ Kiểu: int, Tên: a, Kích thước: 100 phần tử.
• Sử dụng const:

  const int MAXN = 100;
  int c[MAXN];
  $\to$ Kiểu: int, Tên: c, Kích thước: 100 phần tử.
• LỖI khi dùng biến cho kích thước:

  int n1 = 10;
  int b[n1]; // => LỖI 
• Sử dụng #define:

  #define MAXN 100
  float d[MAXN];
  $\to$ Kiểu: float, Tên: d, Kích thước: 100 phần tử.

Cú pháp khai báo Không tường minh (sử dụng typedef):

typedef <kiểu_dữ_liệu_mảng> <Tên_kiểu_mảng>[<Số_phần_tử>]; 
<Tên_kiểu_mảng> <Tên_biến_Mảng>; 

• Ví dụ:

  typedef int Mang1Chieu[10]; 
  Mang1Chieu m1, m2, m3; 
  $\to$ Tương đương với: int m1[10], m2[10], m3[10];.

2.1.2. Khởi tạo mảng 1 chiều

• Khởi tạo giá trị cho mọi phần tử của mảng:
  • Giá trị: 10, 20, 30, 40
  • Chỉ số: 0, 1, 2, 3

  int A[4] = {10, 20, 30, 40}; 
• Khởi tạo giá trị cho một số phần tử đầu mảng:
  • Giá trị: 10, 20, 0, 0
  • Chỉ số: 0, 1, 2, 3

  int B[4] = {10, 20}; 
• Khởi tạo giá trị 0 cho mọi phần tử của mảng:
  • Giá trị: 0, 0, 0, 0
  • Chỉ số: 0, 1, 2, 3

  int C[4] = {}; 
• Tự động xác định số lượng phần tử:
  • Giá trị: 10, 20, 30, 40
  • Chỉ số: 0, 1, 2, 3

  int E[] = {10,  20, 30, 40}; 
  int F[] {10, 20, 30, 40}; 

---

2.2. Chỉ số mảng và truy xuất phần tử mảng

• Chỉ số mảng (vị trí trong mảng) là một giá trị số nguyên int.
• Chỉ số bắt đầu là 0 và không vượt quá số lượng phần tử tối đa trong mảng.
• Số lượng các chỉ số mảng = số lượng phần tử tối đa trong mảng.
• Các phần tử là 1 dãy liên tục có chỉ số từ 0 đến <Số_phần_tử_mảng>-1.

Ví dụ int A[5];:

• Tên mảng: A.
• Kiểu dữ liệu: int.
• Số phần tử tối đa: 5.
• Các chỉ số được đánh số: 0 → 4 (0, 1, 2, 3, 4).

Cú pháp truy xuất:

<Tên biến mảng>[<Chỉ số mảng>]; 

Ví dụ:

• Ví dụ Truy xuất:

  • Các truy xuất hợp lệ: A[0], A[1], A[2], A[3], A[4].
  • Các truy xuất không hợp lệ: A[-1], A[5], A[6].
  • Giá trị các phần tử (Giả định): A[0]=99, A[1]=17, A[2]=50, A[3]=43, A[4]=72.

• Ví dụ code xuất mảng:

  • Giá trị: 10, 20, 30, 40, 50
  • Địa chỉ (Giả định): 0x61fe00, 0x61fe04, 0x61fe08, 0x61fe0c, 0x61fe10

  #include<iostream> 
  using namespace std; 
  int main() { 
      int a[5]={10, 20, 30, 40, 50}; 
      for(int i=0; i<5; i++) 
          cout << a[i] << " "; 
      cout << endl; 
      return 0; 
  }

  $\to$ Kết quả thực thi: 10 20 30 40 50.

---

2.3. Lấy kích thước mảng (toán tử sizeof)

Cú pháp: Cho mảng 1 chiều A có n phần tử

• sizeof(A): kích thước toàn mảng.
• sizeof(A[i]): lấy kích thước phần tử thứ $i$ ($0 \leq i < n$) trong mảng.

Ví dụ code:

#include<iostream> 
using namespace std; 
int main() { 
    int A[] ={ 1, 2, 3, 4, 5, 6}; 
    cout << "Kich thuoc mang: " << sizeof(A) << " bytes." << endl; 
    cout << "Kich thuoc phan tu A[0]: " << sizeof(A[0]) << " byte." << endl; 
    cout << "Mang co: " << sizeof(A)/sizeof(int) << " phan tu."; 
    return 0; 
} 

$\to$ Kết quả thực thi: Kich thuoc mang: 24 bytes., Kich thuoc phan tu A[0]: 4 byte., Mang co: 6 phan tu..

---

2.4. Lấy địa chỉ các phần tử mảng

Cú pháp:

& <Tên biến mảng>[<Chỉ số mảng>]; 

Ví dụ:

• int A[5];:
  • Giá trị: 10, 20, 30, 40, 50
  • Địa chỉ của mảng: &A.
  • Địa chỉ phần tử thứ 0: &A[0] (&A[0] = &A).
  • Địa chỉ phần tử thứ 1: &A[1].
  • Địa chỉ phần tử thứ 4: &A[4].

  Lưu ý: những giá trị 0x14, 0x18, 0x22, 0x26, 0x30 là các địa chỉ giả định.

• Ví dụ code xuất địa chỉ:
  • Giá trị: 10, 20, 30, 40, 50
  • Địa chỉ (Giả định): 0x61fe00, 0x61fe04, 0x61fe08, 0x61fe0c, 0x61fe10

  #include<iostream> 
  using namespace std; 
  int main() { 
      int a[5]={10, 20, 30, 40, 50}; 
      for(int i=0; i<5; i++) 
          cout << a[i] << " "; 
      cout << endl; 
      cout << a << endl; 
      for(int i=0; i<5; i++) 
          cout << &a[i] << " "; 
      return 0; 
  } 
  $\to$ Kết quả thực thi (Tóm tắt): 10 20 30 40 50, 0x61fe00, 0x61fe00 0x61fe04 0x61fe08 0x61fe0c 0x61fe10.

---

2.5. Gán dữ liệu kiểu mảng

• Không được sử dụng phép gán thông thường mà phải gán trực tiếp giữa các phần tử tương ứng:

  <Biến_mảng_đích> = <biến_mảng_nguồn>;  ➔  sai 
  <Tên_biến_mảng>[<Chỉ_số_thứ_i>] = <Giá_trị>;  ➔   đúng 
• Ví dụ code:

  #define MAX 3 
  typedef int MangSo[MAX]; 
  MangSo a = {1, 2, 3}, b; 
  b = a; // Sai 
  for (int i = 0; i < 3; i++) 
      b[i] = a[i]; 
• Ví dụ chi tiết:

  #include<iostream> 
  using namespace std; 
  #define MAX 3 
  int main() { 
      typedef int MangSo[MAX]; 
      MangSo a = {1, 2, 3}, b; // hay: int a[MAX], b[MAX]; 
      for (int i = 0; i < 3; i++) 
          b[i] = a[i]; 
      cout << "&a= " << &a << " " << endl; 
      for (int i = 0; i < 3; i++) 
          cout << "&a[" << i << "]= " << &a[i] << " " << endl; 
      cout << "&b= " << &b << " " << endl; 
      for (int i = 0; i < 3; i++) 
          cout << "&b[" << i << "]= " << &b[i] << " " << endl; 
  } 
  $\to$ Kết quả thực thi (Tóm tắt): &a= 0x61fe08, &a[0]= 0x61fe08..., &b= 0x61fdfc, &b[0]= 0x61fdfc....

---

2.6. Truyền mảng cho hàm và lời gọi hàm

Cú pháp khai báo tham biến mảng:

<Giá_Trị_Trả_Về> <Tên_Hàm> (<Kiểu_Dữ liệu> <Tên_Mảng>[<Số _phần_tử>], 
<Tham số khác>, ...) ; 

• Mảng có thể thay đổi nội dung sau khi thực hiện hàm.
• Có thể bỏ số lượng phần tử hoặc sử dụng con trỏ.

Ví dụ:

• Ví dụ các cách khai báo tham số mảng:

  1. void NhapMang(int A[MAXN], int n);
  2. void NhapMang(int A[], int n);
  3. void NhapMang(int *A, int n);

• Ví dụ chương trình chính:

  #include <iostream> 
  #define MAXN 100 
  void NhapMang(int*, int &); 
  void XuatMang(int[], const int &); 
  int TinhTong(int A[MAXN], int N); 
  int main() { 
      int a[MAXN], n, S; 
      NhapMang(a, n); 
      XuatMang(a, n); 
      S = TinhTong(a, n); 
      std::cout << std::endl; 
      std::cout << "Tong cac phan tu trong mang: " << S; 
      return 0; 
  } 

  $\to$ Kết quả thực thi (Tóm tắt): Nhap N (0 ≤ N ≤ 100): 3, Mang gom: 5, 4, 9., Tong cac phan tu trong mang: 18.

• Định nghĩa hàm NhapMang:

  void NhapMang(int *A, int &N) { 
      std::cout << "Nhap N (0 ≤ N ≤ 100): "; 
      std::cin >> N; 
      for (int i = 0; i < N; i++) { 
          std::cout << "a[" << i << "]= "; 
          std::cin >> A[i]; 
      } 
  } 

• Định nghĩa hàm XuatMang:

  void XuatMang(int A[], const int &N) 
  { 
      std::cout << "Mang gom: "; 
      for (int i = 0; i < N - 1; i++) 
          std::cout << A[i] << ", "; 
      std::cout << A[N - 1] << ". "; 
  } 

• Định nghĩa hàm TinhTong:

  int TinhTong(int A[MAXN], int N) { 
      int S = 0; 
      for (int i = 0; i < N; i++) 
          S += A[i]; 
      return S; 
  } 

---

2.7. Một số tác vụ trên mảng 1 chiều

2.7.1 Nhập mảng

Yêu cầu: Cho phép nhập mảng a, số lượng phần tử n.

void NhapMang(int A[], int N) { 
    for (int i = 0; i < N; i++) { 
        std::cout << "a[" << i << "]= "; 
        std::cin >> A[i]; 
    } 
}

2.7.2. Xuất mảng

Yêu cầu: Cho trước mảng a, số lượng phần tử n. Hãy xuất nội dung mảng a ra màn hình

void XuatMang(int A[MAXN], int N) { 
    for (int i = 0; i < N; i++) 
        std::cout << A[i]; 
}

2.7.3. Tìm kiếm 1 phần tử trong mảng

Yêu cầu: Tìm xem phần tử x có nằm trong mảng a kích thước n hay không? Nếu có thì xuất ra màn hình vị trí đầu tiên tìm thấy được

int TimKiem(int *a, int n, int x) { 
    for (int vt = 0; vt < n; vt++) 
        if (a[vt] == x) return vt; 
    return -1; 
}

2.7.4. Tìm giá trị nhỏ nhất/lớn nhất của mảng

int Max(int a[], int n) { 
    int Max = a[0]; 
    for (int i = 1; i < n; i++) 
        if (Max < a[i]) Max = a[i]; 
    return Max; 
}

int Min(int a[], int n) { 
    int Min = a[0]; 
    for (int i = 1; i < n; i++) 
        if (Min > a[i]) Min = a[i]; 
    return Min; 
}

2.7.5. Kiểm tra tính chất của mảng

Yêu cầu: Mảng a kích thước n có phải là mảng toàn các số nguyên tố hay không?

Ý tưởng:

1. Ý tưởng 1: Đếm số lượng số nguyên tố của mảng. Nếu số lượng này bằng đúng n thì mảng toàn nguyên tố.
2. Ý tưởng 2: Đếm số lượng số không phải nguyên tố. Nếu số lượng này bằng 0 thì mảng toàn nguyên tố.
3. Ý tưởng 3: Tìm xem có phần tử nào không phải số nguyên tố không. Nếu có thì mảng không toàn số nguyên tố.

Hàm kiểm tra SNT:

int LaSNT(int n) {
    int flag = 0;
    for (int i = 2; i < n; i++)
        if (n % i == 0) // áp dụng kỹ thuật cờ hiệu
            flag = 1;
    if (flag == 0) return 1; // SNT
    return 0; // Không phải SNT
}

Hàm kiểm tra toàn SNT (theo các ý tưởng)

• Ý tưởng 1

  int KiemTra_YT1(int a[], int n) {
      int dem = 0;
      for (int i = 0; i < n; i++)
          if (LaSNT(a[i]) == 1)
              dem++;
      if (dem == n)
          return 1;
      return 0;
  }

• Ý tưởng 2

  int KiemTra_YT2(int a[], int n){
      int dem = 0;
      for (int i = 0; i < n; i++)
          if (LaSNT(a[i]) == 0)
              dem++;
      if (dem == 0)
          return 1;
      return 0;
  }

• Ý tưởng 3

  int KiemTra_YT3(int a[], int n) {
      for (int i = 0; i < n; i++)
          if (LaSNT(a[i]) == 0)
              return 0;
      return 1;
  }

2.7.6. Đếm số lượng các phần tử chẵn trong mảng

#include <stdio.h>

void NhapMang(int A[], int &N);
void XuatMang(int A[], int N);
void DemSoChan(int A[], int N);

int main() {
    int a[100], n, count;
    NhapMang(a, n);
    XuatMang(a, n);
    count = DemSoChan(a, n);
    printf("So ptu chan là % d", count);
}

int DemSoChan(int A[], int N) {
    int c = 0;
    for (int i = 0; i < N; i++)
        if (A[i] % 2 == 0)
            c++;
    return c;
}

2.7.7. Tách mảng / Gộp mảng

Gộp mảng

Yêu cầu Gộp mảng a (na phần tử) và mảng b (nb phần tử) thành mảng c (nc phần tử).

Ý tưởng

• Chuyển các phần tử của mảng a sang mảng c $\to$ nc = na.
• Tiếp tục đưa các phần tử của mảng b sang mảng c $\to$ nc = nc + nb.

void GopMang(int a[], int na, int b[], int nb, int c[], int &nc) {
    nc = 0;
    for (int i = 0; i < na; i++) {
        c[nc] = a[i];
        nc++; // c[nc++] = a[i];
    }
    for (int i = 0; i < nb; i++) {
        c[nc] = b[i];
        nc++; // c[nc++] = b[i];
    }
}

Tách mảng

Yêu cầu Tách mảng a (na phần tử) thành 2 mảng:

• b: chứa số nguyên tố
• c: chứa các số còn lại

Ý tưởng

• Cách 1: Viết 1 hàm tách các số nguyên tố sang mảng b và 1 hàm tách số không phải nguyên tố sang mảng c.
• Cách 2: Duyệt từng phần tử của mảng a:
  • Nếu là số nguyên tố → đưa vào b
  • Ngược lại → đưa vào c

void TachSNT2(int a[], int na, int b[], int &nb, int c[], int &nc) {
    nb = 0;
    nc = 0;
    for (int i = 0; i < na; i++)
        if (LaSNT(a[i]) == 1) {
            b[nb] = a[i];
            nb++;
        }
        else {
            c[nc] = a[i];
            nc++;
        }
}

2.7.8. Sắp xếp mảng giảm dần / tăng dần

Hàm Hoán vị

void HoanVi(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

Tăng dần

Yêu cầu: Sắp xếp mảng a kích thước n sao cho các phần tử có giá trị tăng dần.

Ý tưởng: Sử dụng 2 biến i và j để so sánh tất cả các cặp phần tử với nhau và hoán vị các cặp nghịch thế (sai thứ tự).

void SapXepTang_InterchangeSort(int a[], int n) {
    for (int i = 0; i < n-1; i++)
        for (int j = i + 1; j < n; j++)
            if (a[i] > a[j])
                HoanVi(a[i], a[j]);
}

Giảm dần

Yêu cầu: Sắp xếp mảng a kích thước n sao cho các phần tử có giá trị giảm dần.

Ý tưởng: Tương tự sắp xếp tăng dần, nhưng điều kiện so sánh đảo lại.

void SapXepTang_InterchangeSort(int a[], int n) { // LƯU Ý: Tên hàm có vẻ sai, nhưng nội dung là sắp xếp Giảm dần
    for (int i = 0; i < n-1; i++)
        for (int j = i + 1; j < n; j++)
            if (a[i] < a[j])
                HoanVi(a[i], a[j]);
}

2.7.9. Thêm / Xóa / Sửa một phần tử vào mảng

Thêm phần tử

Yêu cầu: Thêm phần tử x vào mảng a kích thước n tại vị trí k.

Ý tưởng:

1. “Đẩy” các phần tử bắt đầu tại vị trí k sang phải 1 vị trí.

2. Đưa x vào vị trí k.

3. Tăng n lên 1 đơn vị.

bool Them(int a[], int &n, int k, int x) {
    if (k >= 0 && k <= n) {
        for (int i = n; i > k; i--)
            a[i] = a[i - 1];
        a[k] = x;
        n++;
        return 1;
    }
    return 0;
}

Xóa phần tử

Yêu cầu: Xóa một phần tử trong mảng a kích thước n tại vị trí k.

Ý tưởng:

• “Kéo” các phần tử bên phải vị trí k sang trái 1 vị trí.
• Giảm n xuống 1 đơn vị.

bool Xoa(int a[], int &n, int k) {
    if (k >= 0 && k < n) {
        for (int i = k; i < n - 1; i++)
            a[i] = a[i + 1];
        n--;
        return 1;
    }
    return 0;
}

Sửa phần tử

Yêu cầu: Sửa 1 phần tử của mảng a kích thước n tại vị trí k.

Ý tưởng: Gán lại giá trị mới cần thay đổi cho phần tử tại vị trí a[k].

Mảng tĩnh

/* Mảng tĩnh */
int main(){
    int a[n]; // với n là số nguyên cho trước
    a[k] = giá trị sửa mới;
    cout << a[k];
    return 0;
}

Mảng động

/* Mảng động */
int main(){
    int n;
    cin >> n;
    int* a[n];
    // Nhập giá trị ban đầu cho từng phần tử của mảng a
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    a[k] = giá trị sửa mới;
    return 0;
}

---

Bài tập

1. Viết chương trình nhập vào một dãy tăng dần, không cần sắp xếp.
   Nếu nhập sai yêu cầu sẽ phải nhập lại và xuất các số nguyên tố có trong mảng.

2. Kiểm tra mảng có đối xứng hay không.

3. Liệt kê các giá trị xuất hiện trong mảng đúng 1 lần.

4. Tìm vị trí của phần tử có giá trị âm lớn nhất trong mảng số nguyên.

5. Viết hàm xóa phần tử có chỉ số k trong mảng số nguyên a có n phần tử.
   Nếu k < 0 hoặc k ≥ n thì không xóa và hàm trả về giá trị 0.
   Ngược lại xóa phần tử a[k] và hàm trả về giá trị 1.

---

3. Mảng hai chiều

Sau khi đã quen với mảng một chiều, bước tiếp theo là tiếp cận mảng hai chiều và mảng nhiều chiều – dạng mở rộng giúp biểu diễn dữ liệu theo hàng và cột giống như bảng.
Đây là nền tảng để xử lý các bài toán phức tạp hơn (ma trận, lưới…).

3.1. Khai báo và khởi tạo mảng 2 chiều

Cú pháp:

<Kiểu_dữ_liệu> <Tên_biến_mảng>[<Số_dòng>] [<Số_cột>];

Trong đó:

• <Kiểu_dữ_liệu>: int, float, char, ...
• <Tên_biến_mảng>: tên biến theo quy tắc định danh
• <Số_dòng>, <Số_cột>: kích thước mảng
• Phải xác định khi khai báo
• Phải là hằng số

Cú pháp khai báo không tường minh (typedef)

typedef <kiểu cơ sở> <tên kiểu>[<Số_dòng>][<Số_cột>];
<tên kiểu> <tên biến>;

Ví dụ:

typedef int MaTran10x20[10][20];
MaTran10x20 a, b;

Tương đương:

int a[10][20], b[10][20];

Khởi tạo giá trị cho mảng 2 chiều

Tạo ma trận: $\begin{bmatrix}1&2&3\\4&5&6\end{bmatrix}$

int A[2][3] = {1, 2, 3, 4, 5, 6};
int A[2][3] = { {1, 2, 3}, {4, 5, 6} };
int A[2][3] {1, 2, 3, 4, 5, 6};

Khởi tạo toàn $0$ $\begin{bmatrix}0&0&0\\0&0&0\end{bmatrix}$:

int C[2][3] = {};

Ví dụ xuất mảng

#include<iostream>
using namespace std;

int main() {
    int A[2][3] = { 1, 2, 3, 4, 5, 6};
    int B[2][3] = { {1, 2, 3}, {4, 5, 6}};
    int C[2][3] = { {1, 2}, {4} };

    for(int i=0; i<2; i++)
        for(int j=0; j<3; j++)
            cout << A[i][j];
    cout << endl;

    for(int i=0; i<2; i++)
        for(int j=0; j<3; j++)
            cout << B[i][j];
    cout << endl;

    for(int i=0; i<2; i++)
        for(int j=0; j<3; j++)
            cout << C[i][j];
    return 0;
}

$\to$ Kết quả:

123456
123456
120400

---

3.2. Chỉ số mảng & truy xuất phần tử

• Chỉ số dòng: 0 ≤ i ≤ số_dòng - 1
• Chỉ số cột: 0 ≤ j ≤ số_cột - 1

Cú pháp truy xuất:

<Tên_biến_mảng>[<dòng>][<cột>];

Ví dụ xuất giá trị từng phần tử

#include<iostream>
using namespace std;

int main() {
    int A[4][3] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
    int r = 4, c = 3;

    cout << "Gia tri mang:\n";
    for(int i=0; i<r; i++) {
        for(int j=0; j<c; j++)
            cout << A[i][j] << "\t";
        cout << endl;
    }
    return 0;
}

Kết quả:

1 2 3
4 5 6
7 8 9
10 11 12

---

3.3. Lấy kích thước mảng dùng toán tử sizeof

Cú pháp:

• sizeof(A): kích thước toàn mảng
• sizeof(A[i][j]): kích thước phần tử dòng i, cột j
• sizeof(A[i]): kích thước của cả dòng thứ i

Ví dụ

#include<iostream>
using namespace std;

int main() {
    int A[4][3] { {1, 2, 3}, {4, 5, 6},
                  {7, 8, 9}, {10, 11, 12}};
    int r = 4, c = 3;

    cout << "Kich thuoc mang: " << sizeof(A) << endl;
    cout << "Kich thuoc phan tu A[0][0]: " << sizeof(A[0][0]) << endl;

    for(int i = 0; i < r; i++)
        cout << "Kich thuoc dong " << i << ": " << sizeof(A[i]) << endl;

    return 0;
}

Kết quả (tóm tắt):

Kich thuoc mang: 48
Kich thuoc phan tu A[0][0]: 4
Kich thuoc dong 0: 12
Kich thuoc dong 1: 12
...

---

3.4. Lấy địa chỉ các phần tử mảng

Cú pháp:

&<Tên_biến_mảng>[<dòng>][<cột>];

Địa chỉ minh họa:

• Dòng 0: &A[0][0] = A[0], &A[0][1], &A[0][2]
• Dòng 1: &A[1][0] = A[1], &A[1][1], &A[1][2]

Ví dụ xuất địa chỉ

#include<iostream>
using namespace std;

int main() {
    int A[4][3] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
    int r = 4, c = 3;

    cout << "Dia chi cac phan tu mang:\n";
    for(int i = 0; i < r; i++) {
        for(int j = 0; j < c; j++)
            cout << &A[i][j] << " ";
        cout << endl;
    }

    cout << "\nDia chi moi dong:\n";
    for(int i = 0; i < r; i++)
        cout << A[i] << endl;

    cout << "\nDia chi mang:\n";
    cout << &A << endl;

    return 0;
}

Kết quả (tóm tắt):

0x61fdd0 0x61fdd4 0x61fdd8 ...
Dia chi moi dong:
0x61fdd0
0x61fddc
0x61fde8
0x61fdf4

Dia chi mang:
0x61fdd0

---

Ví dụ về A[i] + 1

#include<iostream>
using namespace std;

int main() {
    int A[4][3] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
    int r = 4, c = 3;

    cout << endl;
    cout << "A[0] + 1: " << A[0] + 1 << endl;
    cout << "A[1] + 1: " << A[1] + 1 << endl;
    cout << "A[2] + 1: " << A[2] + 1 << endl;
    cout << "A[3] + 1: " << A[3] + 1 << endl;

    return 0;
}

Kết quả (tóm tắt):

A[0] + 1: 0x61fde4
A[1] + 1: 0x61fdf0
A[2] + 1: 0x61fdfc
A[3] + 1: 0x61fe08

---

3.5. Phép gán dữ liệu kiểu mảng

Không được dùng phép gán trực tiếp:

b = a;   // Sai

Chỉ được gán từng phần tử:

b[i][j] = a[i][j];   // Đúng

Ví dụ

int a[3][3] = {
    {1, 2},      // row 1 = 1, 2, 0
    {6, 7, 8},   // row 2 = 6, 7, 8
    {11}         // row 3 = 11, 0, 0
};

int b[3][3];

b = a; // Sai

for (int i = 0; i < 3; i++)
    for (int j = 0; j < 3; j++)
        b[i][j] = a[i][j]; // Đúng

---

3.6. Một số khái niệm ma trận liên quan

Cho ma trận A gồm 3 dòng × 3 cột: $\begin{bmatrix}1&8&4\\2&9&6\\3&7&5\end{bmatrix}$

• Các phần tử nằm trên đường chéo chính là: {1, 9, 5}
• Các phần tử nằm trên đường chéo phụ là: {3, 9, 7}
• Các phần tử nằm nửa trên đường chéo chính là: {8, 7, 6}
• Các phần tử nằm nửa dưới đường chéo chính là: {2, 3, 4}

Quy tắc xác định vị trí phần tử trong ma trận

Vị trí	Điều kiện
Đường chéo chính	dòng = cột
Nửa dưới ĐCC	dòng > cột
Nửa trên ĐCC	dòng < cột
Đường chéo phụ	dòng + cột = n - 1
Nửa dưới ĐCP	dòng + cột > n - 1
Nửa trên ĐCP	dòng + cột < n - 1

---

3.7. Truyền mảng cho hàm và lời gọi hàm

Cú pháp khai báo tham biến mảng

<Giá_Trị_Trả_Về> <Tên_Hàm>(<Kiểu_Dữ_liệu> <Tên_Mảng>[<Số_dòng>][<Số_cột>],
                           <các tham số khác> ... );

• Mảng có thể thay đổi nội dung sau khi thực hiện hàm.
• Có thể bỏ số lượng phần tử dòng hoặc dùng con trỏ.

Ví dụ khai báo tham số mảng 2 chiều

void NhapMang(int A[3][2])

---

3.8. Các tác vụ trên mảng 2 chiều

1. Nhập mảng

Yêu cầu: Nhập mảng A gồm m dòng và n cột

void NhapMaTran(int A[][MAXC], int & n, int & m){  // 
  cin >> n >> m;                                   // 
  for (int i = 0; i < n; i++)                      // 
    for (int j = 0; j < m; j++)                    // 
      cin >> a[i][j];                              // 
}                                                   // 

2. Xuất mảng

Yêu cầu: Xuất mảng A gồm m dòng và n cột

void XuatMaTran(int A[][MAXC], int & n, int & m){   // 
   for (int i = 0; i < n; i++) {                     // 
      for (int j = 0; j < m; j++)                    // 
        cout << a[i][j] << " ";                      // 
      cout << endl;                                  // 
   }                                                 // 
}                                                    // 

3. Tìm kiếm 1 phần tử trong mảng

Yêu cầu: Tìm xem phần tử x có nằm trong ma trận a kích thước (m × n) hay không?

int TimKiem(int (*a)[MAXC], int n, int m, int x) {   // 
   for (int i = 0; i < n; i++)                       // 
      for (int j = 0; j < m; j++)                    // 
         if (a[i][j] == x)                           // 
            return 1;                                // 
   return 0;                                         // 
}                                                    // 

4. Kiểm tra tính chất của mảng (Số nguyên tố)

Yêu cầu: Ma trận a kích thước (n × m) có phải là ma trận toàn các số nguyên tố hay không?

Ý tưởng

• YT 1: Đếm số lượng số nguyên tố của ma trận. Nếu số lượng này bằng đúng (n × m) → ma trận toàn số nguyên tố

• YT 2: Đếm số lượng số không phải số nguyên tố. Nếu bằng 0 → ma trận toàn số nguyên tố

• YT 3: Nếu có phần tử nào không phải số nguyên tố → không toàn số nguyên tố

Hàm kiểm tra SNT

bool LaSNT(int n) {                   // 
    if (n < 2) return 0;              //   // Khong la SNT
    for (int i = 2; i <= sqrt(n); i++)// 
        if (n % i == 0) return 0;     //   // Khong la SNT
    return 1;                         //   // SNT
}                                     // 

Kiểm tra toàn SNT (Ý tưởng 3)

int KiemTra_YT3(int a[][MAXC], int n, int m) {   // 
    int i, j, dem = 0;                           // 
    for (i = 0; i < n; i++)                      // 
        for (j = 0; j < m; j++)                  // 
            if (LaSNT(a[i][j]) == 0)             // 
                return 0;                        // 
    return 1;                                    // 
}                                                // 

5. Tính tổng các phần tử có giá trị chẵn

int TongChan(int A[][MAXC], int n, int m) {
    int TC = 0;
    for (int i = 0; i < n; i++) 
        for (int j = 0; j < m; j++) 
            if (A[i][j] % 2 == 0) 
                TC = TC + A[i][j]; 
    return TC; 
} 

6. In các phần tử trên đường chéo chính (134)

void InDuongCheoChinh(int A[][MAXC], int n) { 
    int sum=0; 
    for (int i = 0; i < n; i++) 
        std::cout << A[i][i] << " "; 
} 
void InDuongCheoPhu(int A[][MAXC], int n) { 
    int sum=0; 
    for (int i = 0; i < n; i++) 
        std::cout << A[i][n-1-i] << " "; 
} 
int TongDCChinh(int a[][MAXC], int n, int m) { 
    int i, tong; 
    tong = 0; 
    for (i = 0; i < n; i++) 
        tong = tong + a[i][i]; 
    return tong; 
} 

---

4. Mảng nhiều chiều

4.1. Khai báo mảng nhiều chiều

Cú pháp:

<Kiểu_dữ_liệu> <Tên_biến_mảng>[<size_1>] ... [<size_n>];

Trong đó:

• <Kiểu_dữ_liệu>: int, float, char, ...
• <Tên_biến_mảng>: tên biến theo quy tắc định danh
• <size_1>, ... , <size_n>: số lượng tối đa mỗi chiều của mảng
• Các kích thước phải xác định ngay khi khai báo
• Các kích thước phải là hằng số nguyên

Ví dụ:

int A[2][3][2];
int B[20][3][5];

4.2. Khởi tạo giá trị mảng nhiều chiều

int A[2][3][2] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};

int B[2][3][2] = {
    { {1, 2},
      {3, 4},
      {5, 6} 
    },
    { {7, 8},
      {9, 10},
      {11, 12}
    }
};

int C[2][3][4] = {
    1, 1, 1, 1,
    2, 2, 2, 2,
    3, 3, 3, 3,
    5, 5, 5, 5,
    6, 6, 6, 6,
    7, 7, 7, 7
};

int D[2][3][4] = {
    { {1, 1, 1, 1},
      {2, 2, 2, 2},
      {3, 3, 3, 3} 
    },
    { {5, 5, 5, 5},
      {6, 6, 6, 6},
      {7, 7, 7, 7} 
    }
};

4.3. Kích thước mảng nhiều chiều

Tổng số phần tử có thể được lưu trữ trong một mảng nhiều chiều được tính bằng cách nhân tất cả các kích thước của mảng.

Ví dụ:
Mảng 3 chiều: int B[20][3][5];
Số phần tử tối đa: 20 × 3 × 5 = 300 phần tử
Mỗi phần tử có kích thước 4 byte $\to$ kích thước bộ nhớ của mảng: 300 × 4 = 1200 bytes

4.4. Chỉ số mảng và truy xuất mảng nhiều chiều

Truy xuất phần tử mảng nhiều chiều dùng cú pháp:

<Tên_biến_mảng>[<Chỉ_số_1>][<Chỉ_số_2>]...

Ví dụ

int A[2][3][2] = {
    { {1, 2}, {3, 4}, {5, 6} },
    { {7, 8}, {9, 10}, {11, 12} }
};

Các phần tử:
A[0][0][0] = 1        A[1][0][0] = 7
A[0][0][1] = 2        A[1][0][1] = 8

A[0][1][0] = 3        A[1][1][0] = 9
A[0][1][1] = 4        A[1][1][1] = 10

A[0][2][0] = 5        A[1][2][0] = 11
A[0][2][1] = 6        A[1][2][1] = 12

4.5. Lấy địa chỉ các phần tử mảng nhiều chiều

Cú pháp Lấy địa chỉ phần tử trong mảng nhiều chiều:

&<Tên_biến_mảng>[<Chỉ_số_1>][<Chỉ_số_2>]...

Ví dụ code (In các phần tử)

#include <iostream>
using namespace std;

int main() {
    // Mảng này có thể lưu trữ tối đa 12 phần tử (2 × 3 × 2)
    int A[2][3][2] = {
        { {1, 2},
          {3, 4},
          {5, 6} 
        },
        { {7, 8},
          {9, 10},
          {11, 12}
        }
    };

    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 3; ++j) {
            for (int k = 0; k < 2; ++k) {
                cout << "A[" << i << "][" << j << "][" << k << "] = "
                     << A[i][j][k] << endl;
            }
        }
    }

    return 0;
}
Kết quả thực thi:
A[0][0][0] = 1
A[0][0][1] = 2
A[0][1][0] = 3
A[0][1][1] = 4
A[0][2][0] = 5
A[0][2][1] = 6
A[1][0][0] = 7
A[1][0][1] = 8
A[1][1][0] = 9
A[1][1][1] = 10
A[1][2][0] = 11
A[1][2][1] = 12

5. Chuỗi

Đang cập nhật

---

Tài liệu tham khảo

1. UIT - Mảng một chiều
2. UIT - Mảng nhiều chiều
3. UIT - Chuỗi