Skip to content

Instantly share code, notes, and snippets.

@rahcola rahcola/gist:3806989
Created Sep 30, 2012

Embed
What would you like to do?
addition and multiplication for polynomials
typedef struct termNode {
int coef;
int deg;
struct termNode* greater;
struct termNode* lesser;
} termNode;
termNode* make_term(int coef, int deg) {
termNode* p = malloc(sizeof(termNode));
p->coef = coef;
p->deg = deg;
p->greater = NULL;
p->lesser = NULL;
return p;
}
void free_polynomial(termNode* p) {
while (p != NULL) {
termNode* del = p;
p = p->lesser;
free(del);
}
}
termNode* link_polynomials(termNode* head,
termNode* last,
termNode* p) {
if (p != NULL) {
p->greater = last;
}
if (last != NULL) {
last->lesser = p;
}
if (head == NULL) {
head = p;
}
return head;
}
termNode* copy_polynomial(termNode* head,
termNode* last,
termNode* p) {
if (p == NULL) {
return head;
}
termNode* n = make_term(p->coef, p->deg);
head = link_polynomials(head, last, n);
return copy_polynomial(head, n, p->lesser);
}
termNode* add_polynomials_(termNode* head,
termNode* last,
termNode* p1,
termNode* p2) {
if (p1 == NULL) {
head = copy_polynomial(head, last, p2);
return head;
}
if (p2 == NULL) {
head = copy_polynomial(head, last, p1);
return head;
}
termNode* p = NULL;
if (p1->deg < p2->deg) {
p = make_term(p2->coef, p2->deg);
p2 = p2->lesser;
} else if (p1->deg > p2->deg) {
p = make_term(p1->coef, p1->deg);
p1 = p1->lesser;
} else {
p = make_term(p1->coef + p2->coef, p1->deg);
p1 = p1->lesser;
p2 = p2->lesser;
}
head = link_polynomials(head, last, p);
return add_polynomials_(head, p, p1, p2);
}
termNode* add_polynomials(termNode* p1, termNode* p2) {
return add_polynomials_(NULL, NULL, p1, p2);
}
termNode* mul_polynomials(termNode* p1, termNode* p2) {
if (p1 == NULL || p2 == NULL) {
return NULL;
}
termNode* mul = NULL;
while (p1 != NULL) {
termNode* p = p2;
while (p != NULL) {
termNode* n = make_term(p1->coef * p->coef,
p1->deg + p->deg);
termNode* new_mul = add_polynomials(mul, n);
free_polynomial(mul);
free_polynomial(n);
mul = new_mul;
p = p->lesser;
}
p1 = p1->lesser;
}
return mul;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.