Data Structure/자료구조

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

lumana 2023. 12. 26. 23:50

배열의 응용 : 희소행렬


  • 행렬을 표현하는 첫 번째 방법 : 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, 생능출판사)