자료구조 공부#7 (희소 행렬)

2021.03.16 - [전체글] - 자료구조 공부#6 (배열, 구조체)

이전내용에 이어지는 내용이다

---

희소 행렬(Sparse Matrix)

• 배열을 이용하여 행렬을 표현하는 2가지 방법
  • 2차원 배열을 이용하여 전체 요소를 저장하는 방법
  • 0이 아닌 요소들만 저장하는 방법(위치, 요소)
• 희소행렬 : 대부분의 항들이 0인 배열

 

희소 행렬 예시

 

2차원 배열에 전체 요소를 저장 하는 경우

장점 : 연산 구현이 간단함

단점 : 대부분의 항이 0인 희소 행렬의  경우에는 메모리 공간낭비가 있음

 

 

 

0이 아닌 요소들만 저장하는 경우

장점 : 희소 행렬에 경우에는 메모리 공간 절약이 된다.

단점 : 각종 행렬 연산들의 구현이 복잡해진다

 

[(x,y),요소] 식으로 저장

 

#include <stdio.h>
#define MAX_TERMS 101

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

 

행렬 전치

행을 열로 열을 행으로 바꾸어놓는 것

 

#include <stdio.h>

#define ROWS 3
#define COLS 3

void matrix_transp(int A[ROWS][COLS], intB[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_transp(array1,array2);
    matrix_print(array1);
    matrix_print(array2);
    
    return 0;
}

 

 

---

느낀점 : 메모리 낭비를 절약하는 방식과 연산을 편하게 하는 방식 두가지를 나누어서 교수님이 설명해주셨는데 그것에 장단점과 도대체 어떤식으로 구현이 되는지 예를 들어진 코드들을 잘 참고하자