자료구조
[11] 다항식(polynomial) 표현과 계산
지식보부상님
2021. 1. 15. 17:41
다항식을 표현하기 위해서는 구조체 선언이 필요하다.
구조체에서는 계수와 지수를 저장하는 필드가 필요하다.
또한 다항식의 특성상 지수의 내림차순으로 정렬하는 것이 좋기 때문에
중간에 원소를 잘 삽입할 수 있어야 하므로 linked list(연결 리스트)로 구현하는 것이 좋다.
따라서 다항식을 표현하기 위한 구조체 정의는 다음과 같다.
1
2
3
4
5
6
|
typedef struct _polyNode {
int coef;
int expon;
struct _polyNode* link;
}polyNode;
typedef polyNode *polyPointer;
|
cs |
다항식의 덧셈과 뺄셈의 계산은 expon이 동일한 경우만 coef의 계산을 수행하도록 하면 된다.
그렇다면 두 개의 다항식을 입력으로 받아 두 다항식의 합을 출력하는 프로그램을 작성해보자
C언어 코드
입력 파일은 A.txt와 B.txt이며 내용은 다음과 같이 저장되어있다.
여기서 다항식 A와 B는 다음과 같다.
출력은 두 다항식 A와 B의 합을 (계수, 지수)의 형태로 출력하도록 한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
|
#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;
}
|
cs |
출력 결과
시간 복잡도는 O(n+m)으로 여기서 n은 다항식 A의 항의 개수, m은 다항식 B의 항의 개수이다.