자료구조/C언어 ④ 자료구조 희소행렬 - 행렬의 곱셈,덧셈,90도회전

희소 행렬(sparse matrix)?

​

희소 행렬이란 행렬안의 많은 항들이 거의 0으로 되어있는 행렬입니다.

행렬의 크기가 작다면 문제가 발생하지 않습니다!

하지만 엄청난 크기의 희소 행렬인 경우라면?

메모리 낭비도 심할뿐더러 컴파일러에 따라 사용하지 못하는 경우도 있습니다.​

​

그렇다면 희소행렬을 어떻게 효율적으로 표현할 수 있을까요?

 

 

 

위처럼 배열에 행과 열 (위치) 와 값을 같이 저장하는 방법을 사용하겠습니다!

 

typedef struct ma{ int row, col, value; } M; typedef struct mb{ int rows, cols, terms; M data[9]; }Mb; /* 0 0 2 // 0,2,2 1 0 0 //1,0,1 0 3 0 */

 

 

데이터를 저장할 구조체를 만들었습니다.  (여기서 행렬의 size는 3 x 3 으로 하겠습니다!)

  위의 행렬 m s 를 앞에서 설명했던 방법으로 만들었습니다.

  Mb m 은 전체 3X3행렬에 데이터는 총 4개있는데 뒤의 중괄호 안에서 그 데이터의 위치와 값을 지정해줍니다.

 

 

#include <stdio.h> #include <stdlib.h> typedef struct ma{ int row, col, value; } M; typedef struct mb{ int rows, cols, terms; M data[9]; }Mb; /* 0 0 2 // 0,2,2 1 0 0 //1,0,1 0 3 0 */ int main(int argc, char *argv[]) { Mb m={3,3,4, {{0,2,2}, {1,0,1}, {2,1,3},{2,2,8}}}; Mb s={3,3,3, {{0,2,3}, {1,0,2}, {2,2,8}}}; int **ap, **bp, **cp; int i,j,c; ap=(int**)calloc(m.rows,sizeof(int*)); bp=(int**)calloc(s.rows,sizeof(int*)); cp=(int**)calloc(m.rows,sizeof(int*)); for(i=0;i<m.rows;i++){ ap[i]=(int*)calloc(m.cols,sizeof(int)); bp[i]=(int*)calloc(s.cols,sizeof(int)); cp[i]=(int*)calloc(m.cols,sizeof(int)); } for(i=0;i<m.terms;i++){ ap[m.data[i].row][m.data[i].col]=m.data[i].value; } for(i=0;i<s.terms;i++){ bp[s.data[i].row][s.data[i].col]=s.data[i].value; } for(i=0;i<m.rows;i++){ for(j=0;j<s.cols;j++){ for(c=0;c<m.rows;c++){ cp[i][j]=cp[i][j]+(ap[i][c]*bp[c][j]); } } } printf(">>행렬의 곱셈<<\n"); for(i=0;i<m.rows;i++){ for(j=0;j<m.cols;j++){ printf("%2d",ap[i][j]);} printf(" x "); for(j=0;j<s.cols;j++){ printf("%2d",bp[i][j]); } printf(" = "); for(j=0;j<m.cols;j++){ printf("%3d",cp[i][j]); } printf("\n"); } //곱셈 하기 printf("\n>>행렬의 90도 회전\n"); int cnt=0; int p,q; while(cnt!=4){ for(i=0;i<m.rows;i++){ for(j=0;j<m.cols;j++){ ap[j][2-i]=cp[i][j]; } } for(i=0;i<m.rows;i++){ for(j=0;j<m.cols;j++){ printf("%3d",cp[i][j]); } printf(" >> "); for(j=0;j<m.cols;j++){ printf("%3d",ap[i][j]); } printf("\n"); } for(p=0;p<3;p++){ for(q=0;q<3;q++){ cp[p][q]=ap[p][q]; } } cnt++; system("pause"); } return 0; }

 

행렬의 곱셈/행렬을 90도씩 회전

 

ap와 bp는 원래 행렬을 저장하기 위해 만든 이중배열이며 cp에서는 ap와 bp를 곱한 결과를 저장합니다.

ap와 bp는 calloc을 써서 모두 0으로 초기화 시켰기 때문에 값이 있는 데이터값만 저장해주면 되겠죠?

 

 

*희소행렬을 이용한 행렬의 덧셈*

inda , indb = 값이 있는 곳의 위치

위의 두개를 비교해서 더해서 넣을 것인지 그냥 넣을 것인지 정한다.

마지막에는 넣어지지않은 a 나 b의 값들을 다 넣어준다.