[11] 다항식(polynomial) 표현과 계산

다항식을 표현하기 위해서는 구조체 선언이 필요하다.

구조체에서는 계수와 지수를 저장하는 필드가 필요하다.

또한 다항식의 특성상 지수의 내림차순으로 정렬하는 것이 좋기 때문에

중간에 원소를 잘 삽입할 수 있어야 하므로 linked list(연결 리스트)로 구현하는 것이 좋다.

 

따라서 다항식을 표현하기 위한 구조체 정의는 다음과 같다.

typedef struct _polyNode {
    int coef;
    int expon;
    struct _polyNode* link;
}polyNode;
typedef polyNode *polyPointer;

다항식의 덧셈과 뺄셈의 계산은 expon이 동일한 경우만 coef의 계산을 수행하도록 하면 된다.

 

그렇다면 두 개의 다항식을 입력으로 받아 두 다항식의 합을 출력하는 프로그램을 작성해보자

 

C언어 코드

입력 파일은 A.txt와 B.txt이며 내용은 다음과 같이 저장되어있다. 

여기서 다항식 A와 B는 다음과 같다.

 

출력은 두 다항식 A와 B의 합을 (계수, 지수)의 형태로 출력하도록 한다.

#include <stdio.h>
#include <stdlib.h>
#define COMPARE(x, y)(((x)>(y))?1:(((x)==(y))?0:-1)) //다항식 A, B의 지수의 크기를 비교하기 위함.
#define MAX 100
//다항식 D는 다항식 A와 B의 덧셈을 수행한 결과를 의미함.
typedef struct polynomial {
    int coef; //계수
    int exp; //지수
}poly;
 
int  avail = 0; //다음 넣을 곳의 index를 담는 변수
int finA = -1, finB = -1, finD = -1, stD = 0; //순서대로 다항식 A의 마지막, B의 마지막, D의 마지막, D의 첫항을 가리키기 위한 index
poly terms[MAX]; //다항식A, B,D를 모두 넣을 구조체 배열
 
void readPoly(FILE* fp); //입력을 받아 terms[]에 넣는 함수
void attach(int exp, int coef); //계산한 새로운 항을 terms[]에 더해주는 함수
void printPoly(); //계산 결과를 (지수, 계수)의 형태로 출력하는 함수
void padd(int stA, int stB); //두 다항식의 덧셈을 수행하여 새로운 다항식을 저장하는 함수
 
int main() {
    FILE *fp;
    int stA = 0, stB = 0;
 
    //다항식 A를 terms[0:finA]만큼 저장함.
    fp = fopen("A.txt", "r");
    readPoly(fp);
    fclose(fp);
    finA = avail - 1;//finA는 다항식 A의 마지막 항을 가리키는 index
    stB = avail;
 
    //다항식 B를 terms[stB:finB]만큼 저장함.
    fp = fopen("B.txt", "r");
    readPoly(fp);
    fclose(fp);
    finB = avail - 1; //finB는 다항식B의 마지막 항을 가리키는 index
    stD = avail; //stD는 다항식 D의 첫항을 가리키는 index
 
    padd(stA, stB);
    printPoly();
 
    system("pause");
    return 0;
}
 
void readPoly(FILE* fp) {
    //예외 처리
    if (!fp) {
        fprintf(stderr, "파일 오픈 에러\n");
        exit(1);
    }
    while (fscanf(fp, "%d%d", &terms[avail].coef, &terms[avail].exp) != -1)
        avail++;
 
}
void attach(int exp, int coef) {
    //예외 처리
    if (stD >= MAX) {
        fprintf(stderr, "다항식에 항이 너무 많습니다.\n");
        exit(1);
    }
    terms[avail].exp = exp;
    terms[avail++].coef = coef; //avail이 다음 넣을 곳을 가리킬 수 있도록 1을 더해준다.
}
void printPoly() {
    int i;
    for (i = stD;i <= finD;i++) {
        if (i == finD) //마지막 항의 출력은 ' , ' 출력 제외해야 하므로 해당 조건 필요
            printf("(%d, %d)\n", terms[i].coef, terms[i].exp);
        else
            printf("(%d, %d), ", terms[i].coef, terms[i].exp);
    }
}
void padd(int stA, int stB) {
    int coef;
    while (stA <= finA && stB <= finB) {
        switch (COMPARE(terms[stA].exp, terms[stB].exp)) { //다항식A와 B의 지수를 비교한후 해당하는 연산 수행
        case -1: //B의 지수가 더 큰 경우
            attach(terms[stB].exp, terms[stB].coef); //B의 항만 저장
            stB++;
            break;
        case 0: //A와 B가 같은 지수인 경우
            coef = terms[stA].coef + terms[stB].coef; //두 계수를 더함.
            if (coef) //계수의 합이 0이 아닐 때만 저장
                attach(terms[stA].exp, coef);
            stA++;
            stB++;
            break;
        case 1: //A의 지수가 더 큰 경우
            attach(terms[stA].exp, terms[stA].coef); //A의 항만 저장
            stA++;
            break;
        }
    }
 
    //다항식 A에 남은 항들을 terms[]에 넣어줌
    for (;stA <= finA;stA++)
        attach(terms[stA].exp, terms[stA].coef);
 
    //다항식 B에 남은 항들을 terms[]에 넣어줌
    for (;stB <= finB;stB++)
        attach(terms[stB].exp, terms[stB].coef);
 
    //다항식 D의 마지막 항의 index를 가리킴.
    //attach함수에서 avail++ 이 수행되었으므로, 1을 빼준다.
    finD = avail - 1;
}
 

출력 결과

시간 복잡도는 O(n+m)으로 여기서 n은 다항식 A의 항의 개수, m은 다항식 B의 항의 개수이다.