[C로 쓴 자료구조] 다항식 (Polynomials)

다항식 구현

 

struct poly {
	int coef; //차수
	int expon; //지수
	struct poly* link;
};
struct poly* a, * b, * d; // 다항식 d = a + b

 

 

다항식의 합

 

Time complexity : O(m+n)

 

다항식 d의 항 추가는 리스트의 끝에서 발생하므로 Queue 형식으로 구현

 

 

지수를 비교하여 지수가 같다면 차수끼리 덧셈 후 다항식 d에 추가, 어느 한쪽 지수가 크다면 다항식 d에 큰 지수를 가진 노드를 추가하는 방식으로 진행.

 

#include <stdio.h>
#include <stdlib.h>
#define COMPARE(x,y) ((x<y) ? -1 : (x==y) ? 0 : 1)
#define IS_FULL(ptr) (!(ptr))
#define FALSE 0
#define TRUE 1

struct poly {
	int coef; //차수
	int expon; //지수
	struct poly* link;
};
struct poly* a, * b, * d; // 다항식 d = a + b

struct poly* avail; // 안쓰는 노드들을 가지고있는 전역변수

struct poly* padd(struct poly* a, struct poly* b) { // d = a + b 인 다항식 d를 return
	struct poly* front, * rear, * temp;
	int sum;

	rear = (struct poly*)malloc(sizeof(struct poly)); //초기 노드

	if (rear == NULL) {
		fprintf(stderr, "The memory is full\n");
		exit(1);
	}

	front = rear;

	while (a && b) {
		switch (COMPARE(a->expon, b->expon)) {

		case -1: // a->expon < b->expon
			attach(b->coef, b->expon, &rear);
			b = b->link;
			break;
		case 0: // a->expon == b->expon
			sum = a->coef + b->coef;
			if (sum) 
				attach(sum, a->expon, &rear);
			a = a->link; 
			b = b->link; 
			break;
		case 1: // a->expon > b->expon
			attach(a->coef, a->expon, &rear);
			a = a->link;
		}
		
	}
	for (; a; a = a->link) attach(a->coef, a->expon, &rear); //a != NULL 까지 a=a->link
	for (; b; b = b->link) attach(b->coef, b->expon, &rear);
	rear->link = NULL;
	// 초기 노드를 삭제
	temp = front;
	front = front->link;
	free(temp);
	return front;
}

void attach(float coefficient, int exponent, struct poly** rear)
{
	/* coef = coefficient이고 expon = exponent인 새로운 노드를 생성한 후, ptr이 가리키
	는 노드 다음에 연결. ptr은 생성된 노드를 가리키도록 변경 */
	struct poly* temp;
	temp = (struct poly*)malloc(sizeof(struct poly));

	if (temp == NULL) {
		fprintf(stderr, "The memory is full \n");
		exit(1);
	}
	temp->coef = coefficient;
	temp->expon = exponent;
	(*rear)->link = temp;
	*rear = temp;
}