[C/자료구조] 희소행렬의 표현과 덧셈함수 구현하기

 

C언어를 이용한 자료구조 실습입니다.

 

---

 

I. 문제

희소 행렬은 다음과 같은 타입으로 표현된다. 배열  data와  int 변수 num으로 구성된 구조체이다. data는 희소 행렬에서 0이 아닌 요소를 포함하며, 이 요소의 타입은 (row, col, val)을 포함하는 구조체이다. 여기서 row, col, val은 해당 요소의 행렬에서 행 위치, 열 위치, 값을 각각 표현한다. num은 data에 포함된 요소의 개수를 표현한다. 

 

 

data의 요소 타입을 element_ty로 정의하라. 희소 행렬의 타입을 sparse_matrix로 정의하라.

p, q의 변수를 sparse_matrix의 타입으로 선언하면서, 다음 10*5 크기의 희소 행렬로 각각 초기화하라. 2개의 희소 행렬 p, q를 매개변수로 전달받고, 이 두 행렬에 대한 덧셈을 수행하고, 그  결과 희소 행렬 r을 반환하는 함수 add_sparseMatrix()의 알고리즘을 작성하라.

 

 

II. 구현

#include <stdio.h>
#include <stdlib.h>

// 요소타입 정의
typedef struct{ 
	int row; // 행
	int col; // 열
	int val; // 값

}element_ty;

// 희소 행렬 타입 정의
typedef struct{ 
	element_ty data[100];
	int num;	// 요소의 개수
}sparse_matrix;


// 덧셈 함수
sparse_matrix add(sparse_matrix p, sparse_matrix q){
	sparse_matrix r;
	int ip = 0, iq = 0, ir = 0;
	int pn = p.num, qn = q.num;
	r.num = 0;

	while (pn != 0 || qn != 0) {
		// 행이 같을 때
		if (p.data[ip].row == q.data[iq].row) {
			r.data[ir].row = p.data[ip].row;

			if (p.data[ip].col == q.data[iq].col) { // 열이 같다면
				r.data[ir].col = p.data[ip].col;
				r.data[ir++].val = p.data[ip++].val + q.data[iq++].val;
				pn--; qn--;
			}
			else if (p.data[ip].col < q.data[iq].col) { // p 열이 더 작다면 
				r.data[ir].col = p.data[ip].col;
				r.data[ir++].val = p.data[ip++].val;
				pn--;
			}
			else { // q 열이 더 작다면
				r.data[ir].col = q.data[iq].col;
				r.data[ir++].val = q.data[iq++].val;
				qn--;
			}
			r.num++;
		}
		// p의 행이 더 클 때
		else if (p.data[ip].row > q.data[iq].row) {
			r.data[ir].row = q.data[iq].row;
			r.data[ir].col = q.data[iq].col;
			r.data[ir++].val = q.data[iq++].val;
			r.num++;
			qn--;
		}
		// q의 행이 더 클 때
		else {
			r.data[ir].row = p.data[ip].row;
			r.data[ir].col = p.data[ip].col;
			r.data[ir++].val = p.data[ip++].val;
			r.num++;
			pn--;
		}
	}
	return r;
}

//출력함수
void print(sparse_matrix r){

	printf("=============\n");
	for (int i = 0; i < r.num; i++)
		printf("(%d, %d, %d) \n", r.data[i].row, r.data[i].col, r.data[i].val);
	printf("=============\n");
}


int main()
{
	sparse_matrix p = {
		{{0,2,1},{1,5,2},{3,1,3},{3,9,4},{4,0,5},{4,4,6},{4,9,7}
		},7 }; 
	sparse_matrix q = {
		{{0,0,5},{0,4,6},{0,9,7},{1,1,3},{1,5,1},{1,9,4},{2,2,1},{3,5,2},{4,4,1},{4,9,1}
		} ,10 }; 

	sparse_matrix r;
	r = add(p, q);
	print(r);

	return 0;
}

 

III. 결과

 

 

 

---

공부한 내용을 복습/기록하기 위해 작성한 글이므로 내용에 오류가 있을 수 있습니다.