[자료구조] 배열을 이용한 다항식 표현2 : 행렬

배열을 이용하여 행렬(matrix)을 표현하는 2가지 방법이 있습니다.

위 행렬의 경우, 대부분의 항들이 0으로 되어있는데 이러한 행렬을 '희소 행렬' 이라 부릅니다.

(1) 2차원 배열을 이용하여 배열의 전체 요소를 저장하는 방법

(2) 0이 아닌 요소들만 저장하는 방법

 

 

(1) 2차원 배열을 이용하여 배열의 전체 요소를 저장하는 방법

이 방법의 장점은 행렬의 연산들을 간단하게 구현할 수 있다는 점이 있으며, 단점은 희소 행렬의 경우 너무 많은 메모리 공간을 낭비한다는 점이 있습니다. 

#include <stdio.h>
#define ROWS 3
#define COLS 3

// 행렬 전치
void matrix_transpose(int A[ROWS][COLS], int B[ROWS][COLS])    {
	for (int r = 0; r<ROWS; r++)
		for (int c = 0; c<COLS; c++)
			B[c][r] = A[r][c];
}
// 출력
void matrix_print(int A[ROWS][COLS])    {
	printf("====================\n");
	for (int r = 0; r<ROWS; r++) {
		for (int c = 0; c<COLS; c++)
			printf("%d ", A[r][c]);
		printf("\n");
	}
	printf("====================\n");
}

int main(void) {
	int array1[ROWS][COLS] = 	
    			{ { 2,3,0 },
		          { 8,9,1 },
	    		  { 7,0,5 } };
	int array2[ROWS][COLS];
	matrix_transpose(array1, array2);
	matrix_print(array1);
	matrix_print(array2);
	return 0;
}

matrix_transpose() 함수는 행렬을 전치합니다. (x, y)를 (y, x)으로 변경하는 것이죠. 

예를 들어, 메인 함수에서 선언된 array1 행렬에서 2는 [0][1]에, 9는 [1][1]에, 7은 [2][0]에 있습니다. 행렬을 전치하게 되면 각각 [1][0], [1][1], [0][2] 로 이동하게 되는 것입니다.

 

 

0이 아닌 요소들만 저장하는 방법

이 방법의 장점은 희소 행렬의 경우, 메모리 공간을 절약할 수 있는 점이 있으며, 단점으로는 각종 행렬 연산들의 구현이 복잡해진다는 점이 있습니다.

 

#include <stdio.h>
#define MAX_TERMS 100

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

typedef struct SparseMatrix {
  element data[MAX_TERMS];
  int rows; // 행의 개수
  int cols; // 열의 개수
  int terms; // 항의 개수
} SparseMatrix;

Sparse Matrix matrix_transpose2(SparseMatrix a)
{
  SparseMatrix b;
  int bindex; // 행렬 b에서 현재 저장 위치
  b.rows = a.rows;
  b.cols = a.cols;
  b.terms = a.terms;
  if (a.terms > 0) {
     bindex = 0;
     for (int c = 0; c < a.cols; c++) {
       for (int i = 0; i < a.terms; i++) {
           if (a.data[i].col == c) {
           b.data[bindex].row = a.data[i].col;
           b.data[bindex].col = a.data[i].row;
           b.data[bindex].value = a.data[i].value;
           bindex++;
           }
         }
       }
     }
  return b;
}

void matrix_print(SparseMatrix a)
{
  printf("====================\n");
  for (int i = 0; i<a.terms; i++) {
    printf("(%d, %d, %d) \n", a.data[i].row, a.data[i].col, a.data[i].value);
  }
    printf("====================\n");
  }
int main(void)
{
  SparseMatrix m = {
    { { 0, 3, 7 },{ 1, 0, 9 },{ 1, 5, 8 },{ 3, 0, 6 },{ 3, 1, 5 },{ 4, 5, 1 },{ 5, 2, 2 } },
    6,
    6,
    7
  };
  SparseMatrix result;
  result = matrix_transpose2(m);
  matrix_print(result);
  return 0;
}