문제 풀이에 많이 이용되는 행렬은 행과 열로 구성된 자료구조이다. 행 개수가 m개, 열 개수가 n개 이면 m x n 행렬이라 하고, 이 행렬을 구성하는 원소 개수는 (m x n) 개가 된다. 행렬 중에서 m과 n이 같은 행렬을 정방행렬 이라고 한다.

행렬의 행과 열은 서로 바꿔 구성한 행렬을 전치행렬이라 하는데, m x n 행렬의 모든 원소 (i, j)를 (j, i)로 순서를 교환하면 n x m 행렬인 전치 행렬이 된다. m x n 행렬 A와 전치행렬 A'는 [ 그림 3-18]의 (a)와 같다. 예를 들어, 3 x 4 행렬 A의 전치 행렬은 (b)와 같이 (4x3) 행렬 A' 가 된다.

행렬의 각 원소는 행과 열로 표현할 수 있으므로, m x n 행렬 A를 [ 그림 3-19 ]와 같이 2차원 배열 A[m][n]으로 표현할 수 있다.

m x n 행렬을 그대로 2차원 배열 [m][n]으로 구현하기는 쉽지만 [그림 3-20]과 같이 원소 대부분이 0인 희소행렬은 실제로 사용하지 않는 공간이 많아 기억 공간의 활용도가 떨엊니다.

기억 공간을 좀 더 효율적으로 사용하려면 0이 아닌 값이 있는 원소만 따로 배열을 구성하는 방법을 사용할 수 있다. 희소행렬 B에서 [ 그림 3-21 ] 과 같이 0이 아닌 원소들에 대한 <행 번호, 열 번호, 값>의 쌍을 구해 2차원 배열에 저장한다. 이때 원래의 희소행렬에 대한 정보를 저장하기 위해 <전체 행의 개수, 전체 열의 개수, 0이 아닌 원소의 개수>의 쌍, 즉 <8, 7, 10>을 첫 번째 행으로 저장한다.

[ 그림 3-20 ] 의 2차원 배열에서는 행렬을 저장하기 위해 8 x 7 = 56개의 배열 원소에 대한 공간이 필요하지만, [ 그림 3-21 ]의 2차원 배열에서는 11x3 = 33 개의 배열 원소에 대한 공간만 사용한다. 희소행렬의 2차워 배열에 대해 사용할 수 있는 자료와 연산은 추상 자료형으로 다음과 같이 정의할 수 있다.

[ 예제 3- 5 ]는 희소행렬의 전치 연산에 대한 알고리즘을 구체화하여 구현한 프로그램이다.

#include "stdio.h"
#define MAX_COL 50   // 희소행렬 구조체 정의 - ( 행, 열, 값 )

typedef struct{ 
	int row;
	int col;
	int value;
} term;

void smTranspose(term a[], term b[]);
void init(term a[]);

void main(int argc, char* argv[]) {
	term a[MAX_COL], b[MAX_COL];
	init(a);
	int i;
	for (i = 0; i < 9; i++) {
		printf("%d, %d, %d\\n", a[i].row, a[i].col, a[i].value);
	}
	smTranspose(a, b);
	printf("\\n");
	for (i = 0; i < 9; i++) {
		printf("%d, %d, %d\\n", b[i].row, b[i].col, b[i].value);
	}
}

void init(term a[]) {
	a[0].row = 6;
	a[0].col = 6;
	a[0].value = 8;
	a[1].row = 0; a[1].col = 0, a[1].value = 15;
	a[2].row = 0; a[2].col = 3, a[2].value = 22;
	a[3].row = 0; a[3].col = 5, a[3].value = 15;
	a[4].row = 1; a[4].col = 1, a[4].value = 11;
	a[5].row = 1; a[5].col = 2, a[5].value = 3;
	a[6].row = 2; a[6].col = 3, a[6].value = 6;
	a[7].row = 4; a[7].col = 0, a[7].value = 91;
	a[8].row = 5; a[8].col = 2, a[8].value = 28;
}

void smTranspose(term a[], term b[]) {
	int m, n, v, i, j, p;
	m = a[0].row;
	n = a[0].col;
	v = a[0].value;
	b[0].row = n;
	b[0].col = m;
	b[0].value = v;
	if (v > 0) {
		p = 1;
		for (i = 0; i < n; i++) {
			for (j = 1; j <= v; j++) {
				if (a[j].col == i) {
					b[p].row = a[j].col;
					b[p].col = a[j].row;
					b[p].value = a[j].value;
					p++;
				}
			}
		}
	}
}