C언어로 복습하는 자료구조 (2) 배열, 구조체

 

중요한건 알지만 맨날 까먹는 그거

이번에야말로 확실히 해두자... (ㅜ)

 

- 배열

여러 데이터를 저장하기 위한 자료형

c에서는 자료형과 배열이름, 크기를 줘서 선언한다

배열의 첫 번째 요소가 배열의 기본주소가 되고 이후 인덱스들은 해당 자료형이 가지는 크기만큼 기본주소에서 떨어진 위치의 메모리 주소를 갖는다

별루 할 말이 없네...

 

- 구조체

다양한 타입의 데이터를 묶는 방법. struct를 사용해 선언

typedef를 사용해 구조체를 새로운 타입으로 선언하는 것도 가능

 

대충그렇다

예제나 보자

 

1) 다항식 연산

다항식의 각 항은 계수, 변수, 차수로 이루어져 있다

다항식의 연산은 어떻게 프로그래밍할까..

 

일단 가장 간단한 방법은 모든 차수에 대한 계수를 배열에 저장해서 구현하는 것

다항식을 아래와 같은 구조체로 표현할 수 있을 것이다

typedef struct {
	int degree;
	float coef[MAX_DEGREE];
} polynomial;

 

다항식의 차수와 각 계수(최고차항부터 배열로 저장)를 구조체로 표현

이 표현 방식을 바탕으로 다항식 덧셈 프로그램을 만들어보자

int max(int a, int b) {
	if (a > b) return a;
	else return b;
}

typedef struct {
	int degree;
	float coef[MAX_DEGREE];
} polynomial;

polynomial poly_add(polynomial A, polynomial B) {
	polynomial C;
	int Apos = 0, Bpos = 0, Cpos = 0;
	int degree_a = A.degree;
	int degree_b = B.degree;
	C.degree = max(A.degree, B.degree);
	while (Apos <= A.degree && Bpos <= B.degree) {
		if (degree_a > degree_b) {
			C.coef[Cpos++] = A.coef[Apos++];
			degree_a--;
		}
		else if (degree_a < degree_b) {
			C.coef[Cpos++] = B.coef[Bpos++];
			degree_b--;
		}
		else {
			C.coef[Cpos++] = A.coef[Apos++] + B.coef[Bpos++];
			degree_a--; degree_b--;
		}
	}
	return C;
}

void print_poly(polynomial p) {
	for (int i = p.degree; i > 0; i--) {
		printf("%3.1fx^%d + ", p.coef[p.degree - i], i);
	}
	printf("%3.1f \n", p.coef[p.degree]);
}

 

덧셈이니까 결과다항식(C)의 차수는 둘중 더 큰 것을 따라야 할 것이고

차수를 비교해서 차수가 같으면 두 항의 계수를 더해주고 다르면 큰 쪽의 계수를 사용

 

그러나 이 방법은 희소다항식(대부분의 항의 계수가 0인 다항식)에서 비효율적이다

계수가 없어도 일일이 0을 써줘야하니...

그럼 계수가 0인 항은 저장하지 않는 방법을 생각해보자

struct {
	float coef;
	int expon;
} terms[MAX_TERMS];
int avail;

 

0이 아닌 항은 계수(coef), 차수(expon) 형식으로 구조체 배열에 저장한다

하나의 배열에 하나 이상의 다항식을 저장할 수 있게 된다.

avail은 terms 배열에서 현재 비어 있는 요소의 인덱스를 의미한다

 

이 방식을 바탕으로 다항식의 덧셈을 구현해보자

앞서 작성한 코드와 마찬가지로, 차수가 같으면 더하고 차수가 다르면 더 큰 쪽을 사용한다.

계산한 값을 terms 배열의 avail 인덱스가 가리키는 곳에 채워넣는 방식

 

// A: 8x^3 + 7x+ 1, B: 10x^3 + 3x^2 + 1
polynomial terms[MAX_TERMS] = { {8, 3}, {7, 1}, {1,0}, {10, 3}, {3,2}, {1,0} };
int avail = 6;

char compare(int a, int b) {
	if (a > b) return '>';
	else if (a == b) return '=';
	else return '<';
}

//새로운 항을 다항식에 추가
void attach(float coef, int expon) {
	if (avail > MAX_TERMS) {
		fprintf(stderr, "항의 개수가 너무 많음\n");
		exit(1);
	}
	terms[avail].coef = coef;
	terms[avail].expon = expon;
	avail++;
}

//As, Ae: A의 처음과 끝. Bs, Be: B의 처음과 끝
void poly_add(int As, int Ae, int Bs, int Be, int *Cs, int *Ce) {
	float tempcoef;
	*Cs = avail;
	while (As <= Ae && Bs <= Be) {
		switch (compare(terms[As].expon, terms[Bs].expon)) {
		case '>': //A의 차수가 더 클 때
			attach(terms[As].coef, terms[As].expon);
			As++;
			break;
		case '=':
			tempcoef = terms[As].coef + terms[Bs].coef;
			if(tempcoef)
				attach(tempcoef, terms[As].expon);
			As++; Bs++;
			break;
		case '<':
			attach(terms[Bs].coef, terms[Bs].expon);
			Bs++;
			break;
		}
	}
	for (; As <= Ae; As++)
		attach(terms[As].coef, terms[As].expon);
	for (; Bs <= Be; Bs++)
		attach(terms[Bs].coef, terms[Bs].expon);
	*Ce = avail - 1;
}

 

terms 배열의 인덱스를 일일이 변수로 만들어줘야한다는 점이 귀찮고 구현도 처음것보다 어렵지만 좀더 효율적이다

 

 

3) 행렬

행렬은 이차원 배열로 표현할 수 있다

row와 col로 나타내면 됨

그러나 이 방법 역시 희소행렬(0인 항이 많은 행렬)일 경우에도 전부 저장해줘야 하므로 낭비가 있다

그래서 다항식에서 했던 것과 마찬가지로 0이 아닌 항만 나타낸다 (행, 열, 해당 위치의 값)의 형태로

0	0	0	7	0	0
9	0	0	0	0	8
0	0	0	0	0	0
6	5	0	0	0	0
0	0	0	0	0	1
0	0	2	0	0	0

이 행렬은 6x6이지만 0이 아닌 값은 7개뿐이다

이걸 구조체로 표현해보면

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

typedef struct SparseMatrix {
	element data[MAX_TERMS];
	int rows;
	int cols;
	int terms;
} SparseMatrix;

SparseMatrix 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 };

이런식으로 할수있다

 

행렬 연산의 예시로 전치 행렬 계산을 구현해보자

전치행렬 transpose 즉 [i][j]의 값을 [j][i]의 값으로 바꿔주는것

단순한 첫 번째 표현방식으로 구현한다면 그냥 이중반복문을 사용해 바꿔주면 되지만 두 번째 희소행렬 표현으로는 어떻게 하면 될까..

row와 col 값을 바꿔주는것까진 어렵지 않은데 그럼 순서가 뒤죽박죽이 되어서 출력되니까, 원래 행렬에서 0열 요소부터 찾아서 바꿔주고 다음으로 1열 요소를 바꿔주고... 하는 식으로 순서를 맞춰주어야 할 듯하다

SparseMatrix transpose(SparseMatrix a) {
	SparseMatrix b;
	b.rows = a.cols;
	b.cols = a.rows;
	b.terms = a.terms;

	int bindex;
	if (a.terms > 0) {
		bindex = 0;
		for (int i = 0; i < a.cols; i++) {
			for (int j = 0; j < a.terms; j++) {
				if (a.data[j].col == i) {
					b.data[bindex].row = a.data[j].col;
					b.data[bindex].col = a.data[j].row;
					b.data[bindex].value = a.data[j].value;
					bindex++;
				}
			}
		}
	}
	return b;
}

void printMatrix(SparseMatrix 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");
}

 

마찬가지로 이중반복문을 도는데 첫 번째 for문에서 a의 column 수를 이용하여, 0번째 column부터 transpose하도록 해서 순서를 맞춰준다

 

다음은 포인터인데 이미 포스트 코드 길이가 생각보다 길어져갖고 나눠야지...