[자료구조] 배열의 응용 : 희소행렬

배열의 응용 : 희소행렬

---

• 행렬을 표현하는 첫 번째 방법 : 2차원 배열을 사용

  #define MAX_ROWS 100
  #define MAX_COLS 100
  int matrix[MAX_ROWS][MAX_COLS];

  • 단점 : 많은 항들이 0으로 되어 있는 희소행렬의 경우메모리의 낭비가 심하게 됨

  • 첫 번째 방법을 통해 전치행렬 구하기

  #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;
  }

• 행렬을 표현하는 두 번째 방법 : 0이 아닌 요소들만 나타낸다

  • 0이 아닌 노드만을 (행, 열, 값)으로 표시

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

  • 두 번째 방법을 통해 전치행렬 구하기

  #include <stdio.h>
  #include <stdlib.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;
  
  SparseMatrix 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;
  }

참조) C언어로 쉽게 풀어 쓴 자료구조(천인국, 2016, 생능출판사)