테이터 구조1 실습 4주차(다항식의 표현)

1. 우선, 두 다항식 p와 q와 두 다항식을 더한 r을 정의해 보았다.

 

p = 5x^3 + 2x^2 + 3x + 1

q = 10x^5 + 3x^3 + 5x^2

r = 10x^5 + 8x^3 + 7x^2 + 3x + 1

 

 

 

2. 다음 각 다항식의 정보를 호함하는 데이터 구조를 정의하고, 해당 구조의 타입 이름은 element로 선언하였다.

typedef struct {
    float coef;
    int expo;
} element;

 

coef은 항에서 차수, expo는 계수의 역할을 하는 변수이다.

 

 

 

3. 또한, 임의의 다항식을 표현할 수 있는 데이터 구조를 작성하고, 타입 이름을 polynomial로 정의하였다.

#define MAX_SIZE 100

typedef struct {
    int nums;
    element terms[MAX_SIZE];
} polynomial;

 

해당 구조체를 설명하기 전, 어떻게 다항식을 표현할 지 알아야 한다.

 

예를 들어  p를 표현해 보면 {4, {{5, 3}, {2, 2}, {3, 1}, {1, 0}로 표현할 수 있다.

이는 4개의 항을 가지고 있고 계수가 5 이며 차수가 3인 항, 계수가 2 이며 차수가 2인 항... 으로 나타낼 수 있다.

 

그렇게 해당 구조체에서 저장할 정보는 항의 수를 저장할 num, 계수와 차수의 정보를 element로 넘겨주는

element terms[MAX_SIZE] 가 있다.

 

여기서 terms는 MAX_SIZE 만큼 배열에 저장되게 된다. MAX_SIZE를 지정한 이유는 항의 갯수를 MAX_SIZE 만큼 제한하기 위함이다.

 

 

 

4. 이제 구조체의 정의가 끝났으면 매개변수로 전달된 다항식을 출력하는 함수를 작성해야 한다.

void poly_print(polynomial n){
    for (int i = 0; i < n.nums; i++){
        if (i < n.nums - 1){
            printf("%0.1fx^%d + ", n.terms[i].coef, n.terms[i].expo);
        }
        else{
            printf("%0.1fx^%d\n", n.terms[i].coef, n.terms[i].expo);
        }
    }
}

 

해당 함수는 구조체 n을 매개변수로 받아 해당 다항식을 출력하는 함수이다.

 

우선 해당 구조체를 매개변수로 받고 해당 배열의 항의 갯수보다 작으면 루프문을 실행한다.

만약 변수 i가 해당 다항식의 항의 갯수를 나타내는 nums에 -1 연산한 값보다 작다면, 해당 출력문을 출력한다.

또한 nums와 같다면 else문을 출력한다.

 

조건을 나눈 이유는 마지막 숫자를 표현할 때는 뒤에 올 항이 없기에 + 문자열을 사용할 이유가 없다.

그렇기에 해당 조건문을 통해 구분해 주었다.

 

 

 

5. 다음 필요한 함수는 매개변수로 전달된 2개의 다항식에 대한 덧셈을 수행하고, 그 결과를 반환하는 함수를 작성했다.

polynomial poly_add(polynomial a, polynomial b){
    polynomial r;
    r.nums = 0;
    int aPos = 0;
    int bPos = 0;
    int rPos = 0;

    while(aPos < a.nums && bPos < b.nums){
        if (a.terms[aPos].expo > b.terms[bPos].expo){
            r.terms[rPos++] = a.terms[aPos++];
        }
        else if (a.terms[aPos].expo < b.terms[bPos].expo){
            r.terms[rPos++] = b.terms[bPos++];
        }
        else{
            r.terms[rPos].expo = a.terms[aPos].expo;
            r.terms[rPos++].coef = a.terms[aPos++].coef + b.terms[bPos++].coef;
        }
    }
    while(aPos < a.nums) {
        r.terms[rPos++] = a.terms[aPos++];
    }
    while(bPos < b.nums) {
        r.terms[rPos++] = b.terms[bPos++];
    }
    r.nums = rPos;

    return r;
}

 

함수의polynomial poly_add(polynomial a, polynomial b) 부분은 구조체 a와 b를 매개변수로 갖는 poly_add()함수이다.

또한 앞의 polynomial은 반환하는 값의 자료형을 표기해야 하므로 polynomial로 작성했다.

 

연산의 결과값을 저장할 polynomial r을 선언 및 r의 항의 갯수를 0으로 초기화 한다.

 

그리고 처리중인 항을 표현하기 위한 각 Pos 변수를 생성하고 0으로 초기화 한다.

 

이제 반복문을 돌 차례이다.

 

a의 항의 갯수보다 현재 처리중인 항의 수가 작고, b의 항의 갯수보다 현재 처리중인 항의 수가 작다면 루프문을 수행한다.

 

그리고 현재 처리중인 항의 차수가 a가 더 크고, 작거나 같을 경우를 구분해서 코드를 작성해준다.

해당 조건에 맞게 실행하고 코드에 영향을 끼친 배열의 pos값만 증감을 시켜준다.

 

위의 반복문이 && 연산자로 구분되어 있어, 하나의 다항식의 값이 남아있을 수 있다.

 

그러하여 그 경우도 구분하여 반복문 2개를 생성하여 해결한다.

 

 

 

6. 이제 main 함수를 작성해보자.

int main(void){
    polynomial p = {4, {{5, 3}, {2, 2}, {3, 0}, {1, 0}}};
    polynomial q = {3, {{10, 5}, {3, 3}, {5, 2}}};

    printf("p = ");
    poly_print(p);
    printf("q = ");
    poly_print(q);

    printf("p + q = ");
    polynomial r = poly_add(p, q);
    poly_print(r);

}

 

위의 main 함수에서는 각 배열 p, q를 형식에 맞게 구조체로 만들고 각 함수를 사용하여 출력하면 된다.

 

 

 

모든 과정을 담은 코드는 아래와 같다.

#include <stdio.h>
#define MAX_SIZE 100

typedef struct {
    float coef;
    int expo;
} element;

typedef struct {
    int nums;
    element terms[MAX_SIZE];
} polynomial;

void poly_print(polynomial n){
    for (int i = 0; i < n.nums; i++){
        if (i < n.nums - 1){
            printf("%0.1fx^%d + ", n.terms[i].coef, n.terms[i].expo);
        }
        else{
            printf("%0.1fx^%d\n", n.terms[i].coef, n.terms[i].expo);
        }
    }
}

polynomial poly_add(polynomial a, polynomial b){
    polynomial r;
    r.nums = 0;
    int aPos = 0;
    int bPos = 0;
    int rPos = 0;

    while(aPos < a.nums && bPos < b.nums){
        if (a.terms[aPos].expo > b.terms[bPos].expo){
            r.terms[rPos++] = a.terms[aPos++];
        }
        else if (a.terms[aPos].expo < b.terms[bPos].expo){
            r.terms[rPos++] = b.terms[bPos++];
        }
        else{
            r.terms[rPos].expo = a.terms[aPos].expo;
            r.terms[rPos++].coef = a.terms[aPos++].coef + b.terms[bPos++].coef;
        }
    }
    while(aPos < a.nums) {
        r.terms[rPos++] = a.terms[aPos++];
    }
    while(bPos < b.nums) {
        r.terms[rPos++] = b.terms[bPos++];
    }
    r.nums = rPos;

    return r;
}

int main(void){
    polynomial p = {4, {{5, 3}, {2, 2}, {3, 0}, {1, 0}}};
    polynomial q = {3, {{10, 5}, {3, 3}, {5, 2}}};

    printf("p = ");
    poly_print(p);
    printf("q = ");
    poly_print(q);

    printf("p + q = ");
    polynomial r = poly_add(p, q);
    poly_print(r);

}

 

 

해당 코드의 실행결과이다.

p = 5.0x^3 + 2.0x^2 + 3.0x^0 + 1.0x^0
q = 10.0x^5 + 3.0x^3 + 5.0x^2
p + q = 10.0x^5 + 8.0x^3 + 7.0x^2 + 3.0x^0 + 1.0x^0