[자료구조] 희소행렬 덧셈

희소행렬을 2차원 배열을 통해 전체를(0도 포함해서) 저장해버리는 방법

• 장점: 행렬의 연산이 간단해진다.
• 단점: 대부분의 항이 0인데 메모리 낭비이다.

0이 아닌 요소들만 구조체를 이용해서 저장하자

• 장점: 메모리 공간 절약
• 단점: 행렬의 연산들의 구현이 복잡

아래의 코드는 구조체를 이용해 0이 아닌 요소들만 있는 행렬의 덧셈을 하는 코드이다.

 

#include <iostream>
using namespace std;

#define ROWS 3
#define COLS 3
#define MAX_TERMS 10

typedef struct Element {
	int row;
	int col;
	int value;
}Element;

typedef struct sparse_matrix {
	Element data[MAX_TERMS];
	int num_of_rows; // 행의 개수
	int num_of_cols; // 열의 개수
	int num_of_terms; // 항의 개수
}sparse_matrix;

sparse_matrix sparse_matrix_add(sparse_matrix a, sparse_matrix b)
{
	sparse_matrix c;
	c.num_of_terms = 0;

	int ca = 0, cb = 0, cc = 0; // 각 배열의 항목을 가리키는 인덱스
	
	if (a.num_of_rows != b.num_of_rows || a.num_of_cols != b.num_of_cols)
	{
		cout << "희소행렬 크기 일치X\n";
		return c;
	}

	c.num_of_cols = a.num_of_cols;
	c.num_of_rows = a.num_of_rows;

	while (ca < a.num_of_terms && cb < b.num_of_terms)
	{
		int inda = a.data[ca].row * a.num_of_cols + a.data[ca].col;
		int indb = b.data[cb].row * b.num_of_cols + b.data[cb].col;

		if (inda < indb) {
			c.data[cc++] = a.data[ca++];
		}
		else if (inda == indb) {
			if (a.data[ca].value + b.data[cb].value != 0)
			{
				c.data[cc].row = a.data[ca].row;
				c.data[cc].col = a.data[ca].col;
				c.data[cc++].value = a.data[ca++].value + b.data[cb++].value;
			}
			else {
				ca++;
				cb++;
			}
		}
		else
			c.data[cc++] = b.data[cb++];
	}

	while (ca < a.num_of_terms)
		c.data[cc++] = a.data[ca++];
	while (cb < b.num_of_terms)
		c.data[cc++] = b.data[cb++];

	c.num_of_terms = cc;
	return c;
}

int main(void)
{
	sparse_matrix m1 = { {{1,1,5},{2,2,9}},3,3,2 };
	sparse_matrix m2 = { {{0,0,5},{2,2,9}},3,3,2 };
	sparse_matrix m3;
	m3 = sparse_matrix_add(m1, m2);
	for (int i = 0; i < m3.num_of_terms; i++)
		cout <<"["<< m3.data[i].col<<"," <<m3.data[i].row<<"]"<<"="<<m3.data[i].value<<"\n";
}

 

int ca = 0, cb = 0, cc = 0; // 각 배열의 항목을 가리키는 인덱스

ca : 현재 a의 가리키고 있는 인덱스

cb : b의 인덱스

cc : c의 현재 인덱스

 

 

if (a.num_of_rows != b.num_of_rows || a.num_of_cols != b.num_of_cols)
{
		cout << "희소행렬 크기 일치X\n";
		return c;
}

행렬 a와 행렬 b의 행과 열의 개수 중 일치하지 않는다면 크기 일치 x를 출력하고 함수 종료합니다.

 

while (ca < a.num_of_terms && cb < b.num_of_terms)

각 인덱스 값이 행렬 a 또는 b의 값의 개수 보다 클 경우 모든 인덱스를 방문한 것이므로 탈출하게 합니다.

 

 

int inda = a.data[ca].row * a.num_of_cols + a.data[ca].col;

 

3x3 크기 배열에서 (1,1)의 경우 번호 4를 갖습니다.

왜냐, 1행이므로 1(몇행?)X3(열의 개수)+1(1열이므로) = 4

 

		if (inda < indb) {
			c.data[cc++] = a.data[ca++];
		}

a의 번호가 b의 번호보다 작을경우 먼저 c의 data에 들어갑니다.

왜냐, 앞쪽의 번호들을 먼저 넣기위해서 입니다.

 

else if (inda == indb) {
			if (a.data[ca].value + b.data[cb].value != 0)
			{
				c.data[cc].row = a.data[ca].row;
				c.data[cc].col = a.data[ca].col;
				c.data[cc++].value = a.data[ca++].value + b.data[cb++].value;
			}
			else {
				ca++;
				cb++;
			}
		}

a와 b의 번호가 같을 경우 실행하는데

만약 a 값과 b 값을 더해서 0일 경우 c 배열에 넣어줄 의미가 없으므로

현재 ca, cb 인덱스 값을 넘어갑니다.

만약 0이 아닐 경우 의미 있는 값이므로 c의 행과 열을 초기화해주고 값 또한 넣어줍니다.

 

		else
			c.data[cc++] = b.data[cb++];

inda > intb 이므로 b를 먼저 데이터를 담아줍니다.

 

	while (ca < a.num_of_terms)
		c.data[cc++] = a.data[ca++];
	while (cb < b.num_of_terms)
		c.data[cc++] = b.data[cb++];

번호가 우선인 데이터부터 담다 보면 한쪽에 데이터가 남는 경우가 있는데

남은 데이터를 싹 c에 넣어줍니다

a데이터가 남는 경우 위의 while문만 실행되겠고

b에 데이터가 남아있는 경우 아래의 while문만 실행되겠죠

 

	c.num_of_terms = cc;

c의 값의 개수는 현재 cc와 같습니다.

 

실행결과

이 코드는 처음 m1, m2가 각각의 값이 순서대로 초기화되어 있지 않다면 문제가 발생합니다.

sparse_matrix m1 = { {{2,2,9},{1,1,5},{1,2,4}},3,3,3 };
sparse_matrix m2 = { {{0,0,5},{1,2,4},{2,2,9}},3,3,3 }; 을 실행 결과로

이렇게 덧셈이 실행되지 않고 데이터가 담겼습니다.

 

왜냐하면 아래의 inda, indb 비교해서 넣는 코드는

각각 m1, m2의 원소가 정렬이 되어있다고 가정하고 작성된 코드이기 때문입니다.

int inda = a.data[ca].row * a.num_of_cols + a.data[ca].col;
		int indb = b.data[cb].row * b.num_of_cols + b.data[cb].col;

		if (inda < indb)

 

이 코드의 한계점은 정렬되지 않고 초기화된 m1, m2를 덧셈하는 데 있습니다.