다항식의 자료구조

Polynomial ADT의 연산을 사용하여 PolyAdd와 PolyMult 연산을 C 언어로 구현.

p1과 p2 다항식을 입력한 다음 다항식 덧셈과 다항식 곱셈 연산을 수행하여 화면에 실행 결과를 출력.

다항식의 자료 구조

typedef struct {

	int coef;

	int exp;

} poly;

 

• 마지막 항에는 coef와 exp의 값으로 -1을 넣어 줌.

 

• 공백 다항식

p	coef	exp
[0]	-1	-1

 

• 3x4 + 4x2 + 2

p	coef	exp
[0]	3	4
[1]	4	2
[2]	2	0
[3]	-1	-1

 

 

다음은 실제 프로그램을 실행시켜 본 결과이다.

소스 코드는 다음과 같다

#include <stdio.h>

#define N 20
#define TRUE 1
#define FALSE 0

typedef struct {
	int coef;
	int exp;
} poly;

void inputTerm(poly *p);
void printTerm(poly *p);
void zeroP(poly *p);
int isZeroP(poly *p);
int coef(poly *p, int e);
int maxExp(poly *p);
void addTerm(poly *p, int a, int e);
void delTerm(poly *p, int e);
void polyAdd(poly *p1, poly *p2, poly *p3);
void sMult(poly *p, int a, int e, poly *result);
void polyMult(poly *p1, poly *p2, poly *p3);
void copyPoly(poly *q, poly *p);

void main()
{
	poly p1[N], p2[N], p3[N];
	poly p1_temp[N], p2_temp[N];
	int c;
	int mxExp;
	
	
	p1[0].coef = 3; p1[0].exp = 4;
	p1[1].coef = 4; p1[1].exp = 2;
	p1[2].coef = 2; p1[2].exp = 0;
	p1[3].coef = -1; p1[3].exp = -1;
	p2[0].coef = 4; p2[0].exp = 4;
	p2[1].coef = 2; p2[1].exp = 3;
	p2[2].coef = -1; p2[2].exp = -1;
	
	
//	printf("p1 입력\n");
//	inputTerm(p1);
//	printf("p2 입력\n");
//	inputTerm(p2);

	
	printf("p1 = ");
	printTerm(p1);
	printf("p2 = ");
	printTerm(p2);
	
	
	c = coef(p2, 3);
	printf("coef(p2, 3) = %d\n", c);

	mxExp = maxExp(p2);
	printf("maxExp(p2) = %d\n", mxExp);

	addTerm(p1, 6, 3);
	printf("addTerm (p1, 6, 3) = ");
	printTerm(p1);

	delTerm(p1, 4);
	printf("delTerm (p1, 4) = ");
	printTerm(p1);

	printf("\n");
	printf("p1 = ");
	printTerm(p1);
	printf("p2 = ");
	printTerm(p2);
	
	zeroP(p1_temp);
	zeroP(p2_temp);
	copyPoly(p1, p1_temp);
	copyPoly(p2, p2_temp);

	printf("\n");
	polyAdd(p1_temp, p2_temp, p3);
	printf("polyAdd(p1, p2, p3) 결과\n");
	printf("p3 = ");
	printTerm(p3);

	zeroP(p1_temp);
	zeroP(p2_temp);
	copyPoly(p1, p1_temp);
	copyPoly(p2, p2_temp);

	printf("\n");
	sMult(p1_temp, 5, 2, p3);
	printf("sMult(p1, 5, 2, p3) 결과\n");
	printf("p3 = ");
	printTerm(p3);
	
	zeroP(p1_temp);
	zeroP(p2_temp);
	copyPoly(p1, p1_temp);
	copyPoly(p2, p2_temp);

	printf("\n");
	polyMult(p1_temp, p2_temp, p3);
	printf("polyMult(p1, p2, p3) 결과\n");
	printf("p3 = ");
	printTerm(p3);
}


void inputTerm(poly *p)
{
	int i = 0;
	printf("  계수와 지수 입력 (종료시는 -1 -1 입력) : ");
	scanf("%d %d", &p[i].coef, &p[i].exp);
	while (p[i].coef != -1 && p[i].exp != -1) {
		printf("  계수와 지수 입력 (종료시는 -1 -1 입력) : ");
		i++;
		scanf("%d %d", &p[i].coef, &p[i].exp);
	}
}
void printTerm(poly *p)
{
	int i = 0;
	while (p[i].exp != -1) {
		printf("%dx^%d", p[i].coef, p[i].exp);
		i++;
		if (p[i].exp != -1 && p[i].coef > 0) printf("+");
	}
	printf("\n");
}
void zeroP(poly *p)
{
	p[0].coef = -1;
	p[0].exp = -1;
}
int isZeroP(poly *p)
{
	if (p[0].exp == -1) return TRUE;
	else return FALSE;
}
int coef(poly *p, int e)
{
	int i=0;
	while(p[i].exp != -1) {
		if (p[i].exp == e)
			return p[i].coef;
		i++;
	}
	return 0;
}
int maxExp(poly *p)
{
	if (p[0].exp != -1) return p[0].exp;
	else return 0;
}
void addTerm(poly *p, int a, int e)
{
	int i=0;

	while(p[i].exp != -1) {
		if (p[i].exp == e) {
			printf("지수 값 중복 에러\n");
			return;
		}
		i++;
	}
	while((i != -1) && (p[i].exp < e)) {
		p[i+1].coef = p[i].coef;
		p[i+1].exp = p[i].exp;
		i--;
	}
	p[i+1].coef = a;
	p[i+1].exp = e;
}
void delTerm(poly *p, int e)
{
	int i=0;

	while(p[i].exp != e) {
		if (p[i].exp == -1) {
			printf("존재하지 않는 항입니다.\n");
			return;
		}
		i++;
	}
	while(p[i].exp != -1) {
		p[i].coef = p[i+1].coef;
		p[i].exp = p[i+1].exp;
		i++;
	}
}

void polyAdd(poly *p1, poly *p2, poly *p3)
{
	int sum;

	zeroP(p3);
	while((isZeroP(p1)!=TRUE) && (isZeroP(p2)!=TRUE)) {
		if(maxExp(p1) < maxExp(p2)) {
			addTerm(p3, coef(p2, maxExp(p2)), maxExp(p2));
			delTerm(p2, maxExp(p2));
		}
		else if(maxExp(p1) == maxExp(p2)) {
			sum = coef(p1, maxExp(p1)) + coef(p2, maxExp(p2));
			if(sum!=0) addTerm(p3, sum, maxExp(p1));
			delTerm(p1, maxExp(p1));
			delTerm(p2, maxExp(p2));
		}
		if(maxExp(p1) > maxExp(p2)) {
			addTerm(p3, coef(p1, maxExp(p1)), maxExp(p1));
			delTerm(p1, maxExp(p1));
		}
	}
	if(isZeroP(p1)!=TRUE) copyPoly(p1, p3);
	else if(isZeroP(p2)!=TRUE) copyPoly(p2, p3);
}

void sMult(poly *p, int a, int e, poly *result)
{
	zeroP(result);
	while(isZeroP(p)!=TRUE) {
		addTerm(result, coef(p, maxExp(p))*a, maxExp(p)+e);
		delTerm(p, maxExp(p));
	}
}

void polyMult(poly *p1, poly *p2, poly *p3)
{
	poly temp_Result[N];
	poly temp_p2[N], temp_p3[N];
	zeroP(p3);
	while(isZeroP(p1)!=TRUE) {
		zeroP(temp_Result);
		zeroP(temp_p2);
		zeroP(temp_p3);
		copyPoly(p2, temp_p2);
		copyPoly(p3, temp_p3);
		sMult(temp_p2, coef(p1, maxExp(p1)), maxExp(p1), temp_Result);
		polyAdd(temp_Result, temp_p3, p3);
		delTerm(p1, maxExp(p1));
	}
}

void copyPoly(poly *q, poly *p)
{
	int i=0, j=0;
	while(p[i].exp != -1) {
		i++;
	}
	while(q[j].exp != -1) {
		p[i].coef = q[j].coef;
		p[i].exp = q[j].exp;
		i++;
		j++;
	}
	p[i].coef = -1;
	p[i].exp = -1;
}