chapter 2-1(POLYNOMIAL) : 배열, 구조체, 포인터

2차원 배열 동적 할당

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main() {
	int** x; //이중 포인터
	int rows; //행
	int cols; //열
	scanf("%d", &rows);
	x = (int**)malloc(rows * sizeof(int*)); //행을 동적할당
	scanf("%d", &cols);
	for (int i = 0; i < rows; i++) {
		x[i] = (int*)malloc(cols * sizeof(int)); //행마다 열의 크기만큼 동적할당
	}

	for (int i = 0; i < rows; i++) {
		for (int j = 0; j < cols; j++) {
			scanf("%d", &x[i][j]);
		}
	}
	for (int i = 0; i < rows; i++) {
		for (int j = 0; j < cols; j++) {
			printf("%d ", x[i][j]);
		}
		printf("\n");
	}
	return 0;
}

 

POLYNOMIAL (다항식 배열)

다항식의 계산을 배열을 이용하여 계산하는 것 입니다. 

먼저 다항식을 배열에 저장하여야 합니다.

예를 들어 10x^5+6x^1+3은

10

0

0

0

6

3

이렇게 배열에 저장됩니다. 우리는 이러한 배열의 이름을 coef 라고 합시다.

이것을 코드로 구현하면

#define MAX_DEGREE 101 //다항식의 최대차수 +1
typedef struct {
	int degree; //최고차항의 차수
	float coef[MAX_DEGREE]; 
}polynominal;

polynominal a = { 5,{10,0,0,0,6,3} };

구조체를 이용하여 변수 degree에는 다항식의 최대차항의 차수가 들어갑니다. 

coef 배열을 이용하여 계수를 저장할 것입니다.

이를 polynominal이라는 구조체 변수에 저장합니다.

이제 다항식의 덧셈을 함수로 구현하였습니다.

polynominal poly_add1(polynominal A, polynominal B) {
	polynominal 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);

변수 Apos는 구조체 polynominal A의 coef배열의 인덱스 번호 를 가리키는 변수입니다. 따라서 배열의 첫번째인 0으로 초기화 해줍니다.

나머지 배열도 마찬가지로 초기화 해줍니다. 

polynominal C는 A와B를 계산한 값이 C로 들어가게 됩니다.

degree_a라는 변수는 A의 최대차항의 계수입니다. 

다항식의 계산은 먼저 최대차항의 차수를 비교하므로 비교가 끝나면 다음 차수로 넘어가야 하기 때문에

계산이 끝날때 마다 degree_a의 수를 1씩 빼줍니다.

C.degree는 A와B의 최대차항의 계수중 큰 수가 들어갑니다.

x^5와 x^4를 더하면 x^5+x^4가 되는데 당연히 최대차항은 5이므로 둘중 최대차항이 큰 수가 C에 들어갑니다.

while (Apos <= A.degree && Bpos <= B.degree) {
		if (degree_a > degree_b) { //A항의 차수 > B항의 차수
			C.coef[Cpos++] = A.coef[Apos++];
			degree_a--;
		}
		else if (degree_a == degree_b) {//A항의 차수 = B항의 차수
				C.coef[Cpos++] = A.coef[Apos++] + B.coef[Bpos++];
				degree_a--;
				degree_b--;
		}
		else { //A항의 차수 < B항의 차수
			C.coef[Cpos++] = B.coef[Bpos++];
			degree_b--;
		}
	}
	return C;
}

while절 안에서 A와 B의 최대차항을 비교해줍니다

while절을 모두 수행하면 구조체 C를 return해줍니다.

void print_poly(polynominal p) {
	for (int i = p.degree; i > 0; i--) {
		if (p.coef[p.degree - i] == 0) //계수가 0이면 출력안함
			continue;
		printf("%3.1fx^%d + ", p.coef[p.degree - i], i);
	}
	printf("%3.1f\n", p.coef[p.degree]);
}

구조체 출력부분입니다. 

계수가 0인 부분은 출력해주지 않았습니다.

---

전체코드입니다.

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX(a,b) (a>b ? a:b)
#define MAX_DEGREE 101 //다항식의 최대차수 +1
typedef struct {
	int degree; //최고차항의 차수
	float coef[MAX_DEGREE]; 
}polynominal;
polynominal poly_add1(polynominal A, polynominal B);
void print_poly(polynominal p);
int main() {
	polynominal a = { 5,{3,6,0,0,0,10} };
	polynominal b = { 4,{7,0,5,0,1} };
	polynominal c;

	print_poly(a);
	print_poly(b);
	c = poly_add1(a, b);
	printf("--------------------------------------------\n");
	print_poly(c);
	return 0;
}
// C는 A+B 여기서 A와 B는 다항식이다. 구조체가 반환된다.
polynominal poly_add1(polynominal A, polynominal B) {
	polynominal 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) { //A항의 차수 > B항의 차수
			C.coef[Cpos++] = A.coef[Apos++];
			degree_a--;
		}
		else if (degree_a == degree_b) {//A항의 차수 = B항의 차수
				C.coef[Cpos++] = A.coef[Apos++] + B.coef[Bpos++];
				degree_a--;
				degree_b--;
		}
		else { //A항의 차수 < B항의 차수
			C.coef[Cpos++] = B.coef[Bpos++];
			degree_b--;
		}
	}
	return C;
}
void print_poly(polynominal p) {
	for (int i = p.degree; i > 0; i--) {
		if (p.coef[p.degree - i] == 0) //계수가 0이면 출력안함
			continue;
		printf("%3.1fx^%d + ", p.coef[p.degree - i], i);
	}
	printf("%3.1f\n", p.coef[p.degree]);
}

---

그러나 이러한 방법에는 메모리의 제한이 생긴다는 단점이 있습니다.

예를 들어 x^1000+1의 경우 배열의 칸을 1000개 이상의 메모리를 설정해야합니다.

따라서 계수가 0인 항들은 아예 배열에 저장하지 않아야 메모리를 절약할 수 있습니다.

예를 들어 10x^5+6x+3 의 경우 ((10, 5), (6, 1),(3, 0))이렇게 배열에 저장 가능합니다.

#define MAX_TERMS 101
struct{
    float coef; //계수
    int expn; //차수
}terms[MAX_TERMS];
int avail;

A = 8x^3 + 7x + 1

B =10x^3 + 3x^2 + 1

avail 변수는 현재 비어있는 요소의 인덱스를 가리킵니다. 여기서 avail은 6이 됩니다.

      A                                    B                                     avail

      0           1            2          3             4          5             6

8	7	1	10	3	1
3	1	0	3	2	0

하지만 이러한 방법에도 단점이 존재합니다.

예외의 다항식에 대해서는 1번쨰 방법보다 더 많은 메모리를 사용할 수 도 있습니다.

다항식의 차수도 배열로 저장해야하기 떄문입니다.

계산이 다된 계수와 차수는 avail자리에 들어가고 다시 avail+1해주면 됩니다. 

마지막으로 어느한쪽의 다항식이 계산이 끝날때 까지 poly_add2 함수를 반복해주면 됩니다.

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, "항의 개수가 너무 많음");
		exit(1);
	}
	terms[avail].coef = coef;
	terms[avail].expon = expon;
	avail++; //삽입이 끝난후 avail을 1을 늘려준다(다음 데이터가 들어올수 있게)
}

계산된 수를 배열에 삽입해주는 함수 입니다.

void poly_add2(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의 차수 > B의 차수
			attatch(terms[AS].coef, terms[AS].expon);
			AS++;
			break;
		case '=': //A의 차수 = B의 차수
			tempcoef = terms[AS].coef + terms[BS].coef;
			if (tempcoef) //두 계수의 합이 0이 아닐때
				attatch(tempcoef, terms[AS].expon);
			AS++; BS++;
			break;
		case '<': //A의 차수 < B의 차수
			attatch(terms[BS].coef, terms[BS].expon);
			BS++;
			break;
		}
	for (; AS <= AE; AS++)  //A의 나머지 항들을 이동
		attatch(terms[AS].coef, terms[AS].expon);
	for (; BS <= BE; BS++) //B의 나머지 항들을 이동
		attatch(terms[BS].coef, terms[BS].expon);
	*CE = avail - 1;
}

계산 부분입니다.

변수 AS와 AE는 다항식 A의 처음과 마지막을 카리키고 BS와 BE는 다항식 B의 처음과 끝을 가리킵니다.

CS와 CE는 덧셈의 결과로 생성되는 다항식의 처음과 끝을 가리킵니다.

void print_poly(int s, int e) {
	for (int i = s; i < e; i++) 
		printf("%3.1fx^%d + ", terms[i].coef, terms[i].expon);
	printf("%3.1fx^%d\n", terms[e].coef, terms[e].expon);
}

출력 부분입니다.

---

전체코드입니다.

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX_TERMS 101 //다항식의 최대차수 +1
typedef struct {
	float coef; //계수
	int expon;  //차수
}polynomial;
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);
void attach(float coef, int expon);
void poly_add2(int AS, int AE, int BS, int BE, int* CS, int* CE);
void print_poly(int s, int e);
int main() {
	int AS = 0, AE = 2, BS = 3, BE = 5, CS, CE;
	poly_add2(AS, AE, BS, BE, &CS, &CE);
	print_poly(AS, AE);
	print_poly(BS, BE);
	printf("---------------------------------------------\n");
	print_poly(CS, CE);
	return 0;
}
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, "항의 개수가 너무 많음");
		exit(1);
	}
	terms[avail].coef = coef;
	terms[avail].expon = expon;
	avail++; //삽입이 끝난후 avail을 1을 늘려준다(다음 데이터가 들어올수 있게)
}
void poly_add2(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의 차수 > B의 차수
			attach(terms[AS].coef, terms[AS].expon);
			AS++;
			break;
		case '=': //A의 차수 = B의 차수
			tempcoef = terms[AS].coef + terms[BS].coef;
			if (tempcoef) //두 계수의 합이 0이 아닐때
				attach(tempcoef, terms[AS].expon);
			AS++; BS++;
			break;
		case '<': //A의 차수 < B의 차수
			attach(terms[BS].coef, terms[BS].expon);
			BS++;
			break;
		}
	for (; AS <= AE; AS++)  //A의 나머지 항들을 이동
		attach(terms[AS].coef, terms[AS].expon);
	for (; BS <= BE; BS++) //B의 나머지 항들을 이동
		attach(terms[BS].coef, terms[BS].expon);
	*CE = avail - 1;
}
void print_poly(int s, int e) {
	for (int i = s; i < e; i++) 
		printf("%3.1fx^%d + ", terms[i].coef, terms[i].expon);
	printf("%3.1fx^%d\n", terms[e].coef, terms[e].expon);
}