2장- 희소행렬의 전치 C언어 구현

모든 원소를 반복해서 돌면서 col 오름차순으로 찾아 B에 넣는 방식

#include <stdio.h>
#define MAX_TERMS 101
typedef struct {
	//term[0]에는 행 수, 열 수, 원소 수가 들어가고 이후부터 행,열,값임
	int row;
	int col;
	int value;
}term;
term a[MAX_TERMS];
void transpose(term a[], term b[]) {
	//a행렬을 전치하여 b행렬에 저장
	int count = a[0].value; //원소의 개수
	int i, j, currentb;
	b[0].row = a[0].col;
	b[0].col = a[0].row;
	b[0].value = a[0].value;

	if (count > 0) { //원소가 존재하는 경우
		currentb = 1; //새로운 원소가 b에 저장될 위치
		for (i = 0; i < a[0].col; i++) {
			for (j = 0; j < count; j++) {
				if (a[j].col == i) {
					b[currentb].row = a[j].col;
					b[currentb].col = a[j].row;
					b[currentb].value = a[j].value;
					currentb++;
				}
			}
		}
	}
}
//row-col 오름차순 정렬이 되어있던 것을 col-row 오름차순으로 정리하여 b에 저장하는 과정이다.
//시간복잡도가 O(n^3)이다. 너무 구려서 못쓰겠어.

시간복잡도가 O(n^3)이기 때문에 아래의 Fast Transpose 사용 

---

Fast Transpose

A희소행렬 배열의 값을 읽고, 이를 전치하여 B희소행렬 배열에 저장해야한다.

전치를 한 후에도 row 오름차순으로 저장하고싶은데,

B배열의 몇번째 칸에 값을 넣어야할까?

 

우선 A배열을 돌면서 각 열의 원소 수를 센다

개수를 찾았으니 

column이 몇일 때 배열의 몇번째 칸부터 넣으면 되는지 계산할 수 있다

이걸 starting_pos 배열에 저장하여 이용함

#include <stdio.h>
#define MAX_COL 50
typedef struct {
	//term[0]에는 행 수, 열 수, 원소 수가 들어가고 이후부터 행,열,값임
	int row;
	int col;
	int value;
}term;
void fast_transpose(term a[], term[b]) {

	int row_terms[MAX_COL]; //a행렬에서 열의 원소 수를 저장
	int starting_pos[MAX_COL]; //각 열의 시작위치를 저장
	int i, j, num_col = a[0].col, num_terms = a[0].value;

	b[0].row = num_col;
	b[0].col = a[0].row;
	b[0].value = num_terms;

	if (num_terms > 0) {
		for (i = 0; i < num_col; i++) {
			row_terms[i] = 0; //배열 초기화
		}
		for (i = 0; i <= num_terms; i++) {
			row_terms[a[i].col]++; //a의 각 열의 원소 수를 row_terms에 넣음
		}
		starting_pos[0] = 1;
		for (i = 1; i < num_col; i++) {
			starting_pos[i] = starting_pos[i - 1] + row_terms[i - 1]; //시작위치를 계싼
		}

		for (i = 1; i <= num_terms; i++) {
			j = starting_pos[a[i].col]++;
			b[j].row = a[i].col;
			b[j].col = a[i].row;
			b[j].value = a[i].value;

		}
	}
}//시간복잡도는 O(columns+elements) 이며 대략 O(columns*rows)임

여기서 starting_pos 배열을 선언하지 않고

row_terms 배열에 starting_pos에 들어갈 값을 덮어씌운 개선 버전 코드도 있다.

#include <stdio.h>
#define MAX_COL 50
typedef struct {
	//term[0]에는 행 수, 열 수, 원소 수가 들어가고 이후부터 행,열,값임
	int row;
	int col;
	int value;
}term;
void fast_transpose(term a[], term[b]) {

	int row_terms[MAX_COL]; //a행렬에서 열의 원소 수를 저장
	int starting_pos[MAX_COL]; //각 열의 시작위치를 저장
	int i, j, num_col = a[0].col, num_terms = a[0].value;
	int temp1, temp2;

	b[0].row = num_col;
	b[0].col = a[0].row;
	b[0].value = num_terms;

	if (num_terms > 0) {
		for (i = 0; i < num_col; i++) {
			row_terms[i] = 0; //배열 초기화
		}
		for (i = 0; i <= num_terms; i++) {
			row_terms[a[i].col]++; //a의 각 열의 원소 수를 row_terms에 넣음
		}
		temp1 = 1;

		for (i = 1; i < num_col; i++) {
			temp2 = row_terms[i];
			row_terms[i] = temp1;
			temp1 += temp2;
		}

		for (i = 1; i <= num_terms; i++) {
			j = row_terms[a[i].col]++;
			b[j].row = a[i].col;
			b[j].col = a[i].row;
			b[j].value = a[i].value;

		}
	}
}//시간복잡도는 O(columns+elements) 이며 대략 O(columns*rows)임
// starting_POS 대신 row_terms에 덮어씌운 개선판임.