Chương trình C++ triển khai mảng thưa (Sparse Array)

Ma trận thưa là ma trận mà phần lớn các phần tử là 0. Ví dụ minh họa như sau.

Ma trận dưới đây chứa 5 số 0. Vì số lượng số 0 lớn hơn một nửa số phần tử của ma trận, nên đây là ma trận thưa.

0 0 9
5 0 8
7 0 0

Thuật toán

Bắt đầu
  Khai báo mảng 2D a[10][10] kiểu nguyên.
    Khởi tạo một số giá trị của mảng.
  Khai báo i, j, count kiểu nguyên.
    Khởi tạo count = 0.
  Khai báo row, col kiểu nguyên.
    Khởi tạo row = 3, col = 3.
  for (i = 0; i < row; ++i) {
    for (j = 0; j < col; ++j)
      if (a[i][j] == 0)
        count++.
  In "The matrix is:".
  for (i = 0; i < row; ++i)
    for (j = 0; j < col; ++j)
      In giá trị mảng.
  In "The number of zeros in the matrix are".
  if (count > ((row * col) / 2)) thì
    In "This is a sparse matrix".
  ngược lại
    In "This is not a sparse matrix".
Kết thúc.

Ví dụ

#include<iostream>
using namespace std;

int main () {
  int a[10][10] = { {0, 0, 9} , {5, 0, 8} , {7, 0, 0} };
  int i, j, count = 0;
  int row = 3, col = 3;
  for (i = 0; i < row; ++i) {
    for (j = 0; j < col; ++j) {
      if (a[i][j] == 0)
        count++;
    }
  }
  cout << "The matrix is:" << endl;
  for (i = 0; i < row; ++i) {
    for (j = 0; j < col; ++j) {
      cout << a[i][j] << " ";
    }
    cout << endl;
  }
  cout << "The number of zeros in the matrix are " << count << endl;
  if (count > ((row * col) / 2))
    cout << "This is a sparse matrix" << endl;
  else
    cout << "This is not a sparse matrix" << endl;
  return 0;
}

Kết quả

The matrix is:
0 0 9
5 0 8
7 0 0
The number of zeros in the matrix are 5
This is a sparse matrix