Data Structure - 희소행렬, 전치행렬

Data Structure(자료 구조)를 주제로 한 두번째 포스팅은 희소행렬, 전치행렬의 구조를 이해하여, 구조체로 표현해보고 이와 관련된 예제를 해결해보겠습니다.

 

 

 

intro. 희소 행렬이란, 행렬의 원소에 비교적 0이 많은 행렬을 말한다

많은 항들이 0으로 되어있는 희소행렬인 경우에는 메모리의 낭비가 심하게 된다. 더구나 엄청난 크기의 희소행렬인 경우에는 컴파일러에 따라 사용하지 못하는 경우도 있다.

 

이러한 희소행렬을 표현함에 있어, 저장공간을 아끼기 위해 희소행렬을 전치행렬로 변환하는 프로그램을 두가지 방법으로 표현해보겠습니다.

 

 

 

 

 

방법1, 정통적인 2차원배열로 표현하여 전치 연산을 하는 것

 

(풀이)

#define rows 3

#define cols 3 3by3으로 행과 열의 공간을 지정했습니다

 

<전치행렬함수>

void mat_tran(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]; //원래 배열의 앞뒤 행과 열의 요소 들을 전치 시켜줌

}

 

반복문을 이용하여 행과열에 해당하는 요소들을 전치시켜주는 함수입니다.

 

 

 

방법2, 0이 아닌 요소들만으로 구성하는 것.

 

(풀이)

행렬의 요소는 행,열,값으로 표현 가능하며 이것을 구조체 element로 정의했습니다.

하나의 행렬에는 0이 아닌 요서가 여러개 있을수 있음으로 elemnt의 배열도 필요하고 희소행렬에 필요한 sparsemat도 정의했습니다

 

 

 

typedef struct {

int row;

int col;

int value;

}element;

 

typedef struct sparsemat {

element data[MAX_TERMS];

int rows;

int cols;

int terms;

}sparsemat;

 

전치행렬구성을 위해 행과열을 변경코드를 코딩합니다.

 

b.data[bindex].row = a.data[i].col;

b.data[bindex].col = a.data[i].row;

b.data[bindex].value = a.data[i].value;

 

이러한 과정을 반복시

(0,3,7) -> (3,0,7)

(1,0,9) -> (0,1,9)

(1,5,8) -> (5,1,8)

과 같은 결과를 얻을수 있습니다.

 

이제 낮은행부터 높은행까지 순서대로 저장하기 위해 아래와 같은 조건문,반복문을 중첩시킵니다.

 

if (a.terms>0){ a의 요소가 0보다 클 경우 즉,양수 중 0이 아닐경우

bindex = 0; 행렬 b의 저장위치 index를 0으로 초기화

for (int c = 0; c < a.cols; c++) a의 col을 하나하나 돌면서 실행 (0~6)

for (int i = 0; i < a.terms; i++) a.term의 개수만큼, 0이아닌 개수만큼 (0~7)

if (a.data[i].col == c) c와 같을 경우 반복

그리고 마지막에 return b;로 저장된 결과물을 return 시킵니다.

 

 

 

 

 

전체 코드)

 

방법1

 

#include <stdio.h>

 

#define rows 3

#define cols 3

 

void mat_tran(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 mat_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");

}

}

 

int main(void)

{

int array1[rows][cols] = { {2,3,0},{8,9,1 },{7,0,5} };

int array2[rows][cols];

mat_tran(array1, array2);

mat_print(array1);

mat_print(array2);

 

return 0;

}

 

 

 

 

 

방법2

 

#include <stdio.h>

#include <stdlib.h>

 

#define MAX_TERMS 100

 

typedef struct {

int row;

int col;

int value;

}element;

 

typedef struct sparsemat {

element data[MAX_TERMS];

int rows;

int cols;

int terms;

}sparsemat;

 

sparsemat mat_tran2(sparsemat a)

{

sparsemat b;

int bindex;

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 mat_print(sparsemat 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)

{

sparsemat 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

};

 

 

mat_print(m);

 

 

printf("\n <결과물> \n");

 

sparsemat result;

 

result = mat_tran2(m);

mat_print(result);

return 0;

}

 

 

 

결과 콘솔)