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