[자료구조] C언어 - 다항식(polynomial) 구현 - 객체지향

- C언어로 구현한 다항식(polynomial) 코드이다. 완벽하진 않지만 c에서 객체지향 개념을 넣을 수 있는 기본 베이스는 마련해둔 코드이다.

 

- 글 말고 github으로 보려면 여기를 누르면 된다.

 

- 영어를 잘 못하지만 주석을 영어로 작성했으므로 틀린 표현이 많을 수 있다. (댓글로 알려줘요 ㅠ)

 

- 이하 코드에서 사용된 node.h, list.h, list.c는 '[자료구조] C언어 - 이중 연결 리스트(doubly linked list) 구현 - 객체지향' 글에서 구현한 코드들이다. 위 github에서 보거나, 여기를 눌러 해당 글에서 확인하면 된다.

 

 

0. 사용예시

#include<stdio.h>
#include"polynomial.h"

int main(int argc, char* argv[])
{
	polynomial_t* p;
	polynomial_t* p1;
	polynomial_t* p2;

	p1 = create_polynomial();
	p1->op->insert_term(p1, 3.3, 2);
	p1->op->insert_term(p1, 7.4, 6);
	p1->op->insert_term(p1, 2.5, 1);
	p1->op->insert_term(p1, 9.2, 8);	
	p1->op->print(p1);
	
	p2 = create_polynomial();
	p2->op->insert_term(p2, 6.2, 2);
	p2->op->insert_term(p2, 4.3, 6);
	p2->op->insert_term(p2, 2.6, 1);
	p2->op->insert_term(p2, 10.3, 10);
	p2->op->insert_term(p2, 22.1, 12);	
	p2->op->insert_term(p2, 2.0, 8);		
	p2->op->print(p2);
	
	p = p->op->add_polynomials(p1, p2);
	p->op->print(p);

	p->op->destroy(p);
	p1->op->destroy(p1);
	p2->op->destroy(p2);
}

 

1. polynomial.h

/**
* Polynomial Header
* made by nahwasa
*/

#ifndef NODE_POLYNOMIAL_H_NAHWASA
#define NODE_POLYNOMIAL_H_NAHWASA

#define MAX(a,b) ((a>b)?a:b)
#define MAX_DEGREE 10

#include"node.h"
#include"list.h"

typedef struct polynomial_term {
	double coef;
	int exp;
} polynomial_term_t;

typedef struct {
	list_t* list;
	struct polynomial_operations* op;	
} polynomial_t;

struct polynomial_operations {
	void (*destroy)(polynomial_t* p);
	void (*insert_term)(polynomial_t* p, double coef, int exp);
	polynomial_t* (*add_polynomials)(polynomial_t* p1, polynomial_t* p2);
	void (*print)(polynomial_t* p);
};

extern polynomial_t* create_polynomial();

#endif

 

2. polynomial.c

/**
* Polynomial
* made by nahwasa
*/

#include <stdio.h>
#include <stdlib.h>
#include"polynomial.h"

static void destroy(polynomial_t* p);
static void insert_term(polynomial_t* p, double coef, int exp);
static polynomial_t* add_polynomials(polynomial_t* p1, polynomial_t* p2);
static void print(polynomial_t* p);

static struct polynomial_operations op =
	{
		.destroy = destroy,
		.insert_term = insert_term,
		.add_polynomials = add_polynomials,
		.print = print
	};

polynomial_t* create_polynomial()
{
	polynomial_t* p = (polynomial_t*)malloc(sizeof(polynomial_t));

	p->list = create_list();
	p->op = &op;

	return p;
}

static void destroy(polynomial_t* p)
{
	p->list->op->destroy(p->list);
	p->op = NULL;
	free(p);
	p = NULL;
}

/*
* polynomial_t list terms ascend. so find position
*/
static node_t* find_add_position_node(polynomial_t* p, int exp)
{
	int i;
	polynomial_term_t* t;
	node_t* pos = p->list->op->get_head_node(p->list);
		
	for (i = 0; i < p->list->op->get_size(p->list); i++) {
		t = (polynomial_term_t*)pos->data;		

		if (t->exp < exp)
			return pos;
		pos = pos->next;			
	}

	return NULL;
}

/*
* insert term(coef^exp) to p
*/
static void insert_term(polynomial_t* p, double coef, int exp)
{
	node_t* pos; 
	polynomial_term_t* t = (polynomial_term_t*)malloc(sizeof(polynomial_term_t));
	t->coef = coef;
	t->exp = exp;
	
	if (!p->list->op->get_size(p->list)) {
		p->list->op->insert_to_head(p->list, t);
		return;	
	}

	pos = find_add_position_node(p, exp);
	
	if (pos == NULL)
		p->list->op->insert_to_tail(p->list, t);
	else
		p->list->op->insert_to_before_node(p->list, pos, t);
}

/*
* add p1 and p2. finally new polynomial_t return
*/
static polynomial_t* add_polynomials(polynomial_t* p1, polynomial_t* p2)
{
	polynomial_t* p = create_polynomial();
	node_t* n1 = p1->list->op->get_head_node(p1->list);
	node_t* n2 = p2->list->op->get_head_node(p2->list);
	polynomial_term_t* t1 = (polynomial_term_t*)n1->data;
	polynomial_term_t* t2 = (polynomial_term_t*)n2->data;

	while (n1 != NULL && n2 != NULL) {
		printf("deb!\n");
		p->op->print(p);
		if (n1 == NULL) {
			p->op->insert_term(p, t2->coef, t2->exp);
			
			n2 = n2->next;
			if (n2 != NULL)
				t2 = (polynomial_term_t*)n2->data;
		} else if (n2 == NULL) {
			p->op->insert_term(p, t1->coef, t1->exp);
			
			n1 = n1->next;
			if (n1 != NULL)			
				t1 = (polynomial_term_t*)n1->data;
		} else if (t1->exp > t2->exp) {
			p->op->insert_term(p, t1->coef, t1->exp);
			
			n1 = n1->next;
			if (n1 != NULL)			
				t1 = (polynomial_term_t*)n1->data;
		} else if (t2->exp > t1->exp) {
			p->op->insert_term(p, t2->coef, t2->exp);
			
			n2 = n2->next;
			if (n2 != NULL)
				t2 = (polynomial_term_t*)n2->data;
		} else {
			if (t1->coef + t2->coef != 0)
				p->op->insert_term(p, t1->coef + t2->coef, t1->exp);

			n1 = n1->next;
			if (n1 != NULL)
				t1 = (polynomial_term_t*)n1->data;
			n2 = n2->next;

			if (n2 != NULL)
				t2 = (polynomial_term_t*)n2->data;
		}		
	}	
	return p;
}


static void print(polynomial_t* p)
{
	node_t* nd;
	polynomial_term_t* t;	

	if (!p->list->op->get_size(p->list)) {
		printf("No data!");
		return;
	}

	nd = p->list->op->get_head_node(p->list);

	while (nd != NULL) {
		t = (polynomial_term_t*)nd->data;

		if (!(nd == p->list->tail))
			printf("%.1fx^%d + ", t->coef, t->exp);
		else
			printf("%.1fx^%d", t->coef, t->exp);

		nd = nd->next;		
	}
	printf("\n");
}