연결리스트를 통한 희소행렬 표현

희소행렬(Sparse matrix)이 다음 그림과 같이 연결리스트를 이용하여 표현되어 있다.
각 노드는 row,col,val 필드를 가지는데 각각 행 번호, 열 번호, 원소의 값을 나타낸다. 또한 이 노드의 Rlink와 Dlink는 각각 같은 행과 열에서 0이 아닌 다음 원소를 나타내는 노드의 주소를 가지는 필드이다. rowHead[i]는 i번째 행의 해드 노드를 나타내고, colHead[j]는 j번째 열의 해드 노드를 나타낸다.

아래에 연결리스트를 통한 희소 행렬 및 전치 행렬(transpose)을 C언어로 구현해보았다.

Linked List & Sparse Matrix.c

#pragma warning(disable:4996)
#include <stdio.h>
#include <stdlib.h>

typedef struct element {
	int row;
	int col;
	int val;
	struct element* Dlink;
	struct element* Rlink;
}element;

typedef struct Head {
	element* ptr;
}Head;

// 헤드 만들기 
Head* make_head(int num) {
	int i;
	Head* head = (Head*)malloc(sizeof(Head)*num);

	for (i = 0; i < num; i++)
		head[i].ptr = 0;
	return head;
}

// 리스트 삽입 
void insert(Head* rowHead, Head* colHead, int row, int col, int val) {
	element* e = (element*)malloc(sizeof(element));
	e->row = row;
	e->col = col;
	e->val = val;
	e->Rlink = e->Dlink = 0;

	// insert_first
	if (rowHead[row].ptr == 0)
		rowHead[row].ptr = e;
	// insert_last
	else {
		element* ptr = rowHead[row].ptr;
		while (ptr->Rlink != NULL) {
			ptr=ptr->Rlink;
		}
		ptr->Rlink = e;
	}

	// insert_first
	if (colHead[col].ptr == 0)
		colHead[col].ptr = e;
	// insert_last
	else {
		element* ptr = colHead[col].ptr;
		while (ptr->Dlink != NULL) {
			ptr = ptr->Dlink;
		}
		ptr->Dlink = e;
	}
}

// 리스트 출력 
void print_list(Head* rowHead, Head* colHead,int rows, int cols) {
	int i;
	// print rowHead list 
	for (i = 0; i < rows; i++) {
		printf("\nrowHead[%d]에 해당하는 리스트 출력:",i);
		element* ptr = rowHead[i].ptr;
		if (ptr == NULL)
			printf(" x");
		while (ptr != NULL) {
			printf("[%d %d %d] ", ptr->row, ptr->col, ptr->val);
			ptr = ptr->Rlink;
		}
	}
	printf("\n");

	// print colHead list 
	for (i = 0; i < cols; i++) {
		printf("\ncolHead[%d]에 해당하는 리스트 출력:", i);
		element* ptr = colHead[i].ptr;
		if (ptr == NULL)
			printf(" x");
		while (ptr != NULL) {
			printf("[%d %d %d] ", ptr->row, ptr->col, ptr->val);
			ptr = ptr->Dlink;
		}
	}
	printf("\n");

}

// 전치행렬 만들기 
void transpose(Head** rowHead_ptr, Head** colHead_ptr,int* rows,int* cols) {
	// element 노드의 위치가 전치행렬된 상태가 되도록 
	Head* tmp = *rowHead_ptr;
	*rowHead_ptr = *colHead_ptr;
	*colHead_ptr = tmp;

	// 행의 개수와 열의 개수를 교환 
	int temp = *rows;
	*rows = *cols;
	*cols = temp;

	// 기존에 Rlink였던 것을 Dlink로 변경, Dlink였던 것을 Rlink로 변경 
	int i;
	element* ptr;
	tmp = *rowHead_ptr; // 바뀐 위치를 기준으로 판단함 
	for (i = 0; i < *rows; i++) {
		ptr = tmp[i].ptr;
		while (ptr != NULL) {
			if ((ptr->Rlink != NULL) || (ptr->Dlink != NULL)) {
				element* t = ptr->Rlink;
				ptr->Rlink = ptr->Dlink;
				ptr->Dlink = t;
			}
			ptr = ptr->Rlink;
		}
	}

	// element정보(행,열)도 교환 
	for (i = 0; i < *rows; i++) {
		ptr = tmp[i].ptr;
		while (ptr != NULL) {
			int t = ptr->row;
			ptr->row = ptr->col;
			ptr->col = t;
			ptr = ptr->Rlink;
		}
	}
}

int main() {
	int rows, cols;
	rows = cols = 0;

	printf("행과 열의 개수를 입력하세요:");
	scanf("%d %d",&rows,&cols);

	Head* rowHead = make_head(rows); // rowHead 동적 배열
	Head* colHead = make_head(cols); // colHead 동적 배열
	
	int terms = 0;
	printf("0이 아닌 항의 개수를 입력하세요:");
	scanf("%d", &terms);

	int i;
	for (i = 0; i < terms; i++) {
		printf("%d번째 항의 (행,열,값)을 입력하세요:",i); // 희소행렬 항 입력받기 
		int row, col, val;
		row = col = val = 0;
		scanf("%d %d %d", &row, &col, &val);
		insert(rowHead, colHead, row, col, val); // 입력된 값으로 리스트 삽입 
	}

	print_list(rowHead,colHead,rows,cols); // 리스트 출력 

	printf("\n전치행렬 결과:");
	transpose(&rowHead, &colHead,&rows,&cols); // 전치행렬 만들기 
	print_list(rowHead, colHead, rows, cols); // 리스트 출력 
}

Other Example