🔗 detailed Implementation in Github

1. Structure Representation

Sparse Matrix is a matrix in which most of the elements are zero. And if we represent this matrix as a 2D array, it makes a huge amount of wasted memory space. Therefore, it’s the right choice that we represent a sparse matrix as a structure representation like below Code 1, and Figure 1, 2. It’s because we can save a lot of memory space.

#define MAX_ELEMS 101
typedef struct term{
	int row;
	int col;
	int value;
} term;
term a[MAX_ELEMS]

Figure 1: Abstraction 2D array matrix.

Figure 2: Abstraction of structure representation matrix.

2. Algorithm for Fast Matrix Transpose

However, this structure representation makes transpose operation more difficult than 2D array representation. when matrix is represented to 2D array, we don't need to recreate the 2D array, but just need to change the direction of reading the elements, which is like green two arrow of matrix in Figure 1. On the other hand, when we use structure representation, it is necessary to recreate the entire structure to read the value of the matrix comfortably. For this recreation, the structure representation matrix, arranged by the number of row, must be re-ordered by the number of column like below Figure 3.

Figure 3: The structure representation matrix on the left is changed to the matrix on the right after the Transpose operation.

Naive Approach