Your Push2 always pushes to the front (i.e. head) of the list.
When combining/adding, you need a push that appends to the tail of the list.
Also, I think you want the sum to have 8x4 and not 3x4 as you say (i.e. your program is correct, except the order is reversed) because each input polynomial has an x4 term.
Also, your print polynomial function doesn't need to be recursive.
And, don't cast the result of malloc
Here's a refactored version with some debug prints. I created a second push function for appending. Ignore the TERM [macro]--it was an incomplete attempt at clarity before I found the real issue.
#include <stdio.h>
#include <stdlib.h>
typedef struct term {
int coef;
int exp;
struct term *next;
} term;
#ifdef DEBUG
#define dbgprt(_fmt...)
printf(_fmt)
#else
#define dbgprt(_fmt...)
do { } while (0)
#endif
typedef void (*pushfnc_p)(term **headRef, int coef, int exp);
void
Push2(term **headRef, int coef, int exp)
{
term *newNode = malloc(sizeof(*newNode));
if (coef == 0)
return;
newNode->coef = coef;
newNode->exp = exp;
newNode->next = *headRef;
*headRef = newNode;
}
void
Push2_tail(term **headRef, int coef, int exp)
{
term *newNode = malloc(sizeof(*newNode));
term *head = *headRef;
if (coef == 0)
return;
term *prev = NULL;
for (struct term *cur = head; cur != NULL; cur = cur->next)
prev = cur;
newNode->coef = coef;
newNode->exp = exp;
newNode->next = NULL;
if (prev != NULL)
prev->next = newNode;
else
head = newNode;
*headRef = head;
}
term *
addPolynomials2(term *h1, term *h2)
{
term *current1 = h1;
term *current2 = h2;
#if 0
pushfnc_p push = Push2;
#else
pushfnc_p push = Push2_tail;
#endif
term *new = NULL;
while (current1 && current2) {
dbgprt("add: DUAL current1=%dX%d current2=%dX%d
",
current1->coef,current1->exp,
current2->coef,current2->exp);
if (current1->exp == current2->exp) {
dbgprt("add: SAME
");
push(&new, (current1->coef + current2->coef), current1->exp);
current1 = current1->next;
current2 = current2->next;
continue;
}
if (current1->exp > current2->exp) {
dbgprt("add: CURR1
");
push(&new, current1->coef, current1->exp);
current1 = current1->next;
continue;
}
dbgprt("add: CURR2
");
push(&new, current2->coef, current2->exp);
current2 = current2->next;
}
while (current1) {
dbgprt("add: POST1 current1=%dX%d
",
current1->coef,current1->exp);
push(&new, current1->coef, current1->exp);
current1 = current1->next;
}
while (current2) {
dbgprt("add: POST2 current2=%dX%d
",
current2->coef,current2->exp);
push(&new, current2->coef, current2->exp);
current2 = current2->next;
}
return new;
}
void
printTerm(term *head)
{
printf("%dx%d ", head->coef, head->exp);
}
void
printPolynomial(term *head)
{
for (; head != NULL; head = head->next)
printTerm(head);
}
#define TERM(_coef,_exp)
{ .coef = _coef, .exp = _exp },
void
addPolynomialsTest2(void)
{
term *head1 = NULL;
term *head2 = NULL;
term *new;
#if 1
int a[] = { 10, 0, 0, 5, 0, 3, 0, 5 };
int b[] = { 7, 6, 5, 4, 3, 2, 1, 0 };
for (int i = sizeof(a) / sizeof(int) - 1; i >= 0; i--) {
Push2(&head1, a[i], b[i]);
}
int c[] = { 8, 7, 6, 5, 4, 3, 2, 1, 0 };
int d[] = { 3, 0, 0, 0, 3, 0, 0, 3, -6 };
for (int i = sizeof(d) / sizeof(int) - 1; i >= 0; i--) {
Push2(&head2, d[i], c[i]);
}
#else
term a[] = {
TERM(10,7)
TERM(0,6)
TERM(0,5)
TERM(5,4)
TERM(0,3)
TERM(3,2)
TERM(0,5)
};
for (int i = sizeof(a) / sizeof(term) - 1; i >= 0; i--) {
term *t = &a[i];
Push2(&head1,t->coef,t->exp);
}
#endif
printf("F(x)= ");
printPolynomial(head2);
printf("
");
printf("Q(x)= ");
printPolynomial(head1);
printf("
");
printf("F(x) + Q(X)= ");
new = addPolynomials2(head1, head2);
printPolynomial(new);
printf("
");
printf("
");
}
int
main(void)
{
addPolynomialsTest2();
return 0;
}
Here's the program output:
F(x)= 3x8 3x4 3x1 -6x0
Q(x)= 10x7 5x4 3x2 5x0
F(x) + Q(X)= 3x8 10x7 8x4 3x2 3x1 -1x0
UPDATE:
I tried doing it without inserting at the end by printing the result in reverse but the output was even weirder any idea why?
Not completely sure. Sounds like two wrongs making a right ... See below.
When creating the polynomials, your code using push-to-front does work, but, IMO, it's a bit more complex because you have to loop through the arrays in reverse order.
However, the add function does need push-to-tail. With push-to-front, the add will fail. So, trying to print in reverse order to "compensate" for the incorrect add function may not be a valid fix.
So, with the original code, you had the two input polynomials in high-to-low order [as we'd want], but the output polynomial had its order reversed.
So, if you tried to add the output to something else (e.g. one of the inputs again), it would break.
So, compensating by reverse printing does not fix the problem. It masks it for printing only.
The push-to-front isn't really needed. I got the TERM macro working. It uses push-to-tail and traverses the array from 0 to N [simpler to understand].
So, this is, IMO, a bit cleaner:
#include <stdio.h>
#include <stdlib.h>
typedef struct term {
int coef;
int exp;
struct term *next;
} term;
#ifdef DEBUG
#define dbgprt(_fmt...)
printf(_fmt)
#else
#define dbgprt(_fmt...)
do { } while (0)
#endif
typedef void (*pushfnc_p)(term **headRef, int coef, int exp);
void
Push2(term **headRef, int coef, int exp)
{
term *newNode = malloc(sizeof(*newNode));
if (coef == 0)
return;
newNode->coef = coef;
newNode->exp = exp;
newNode->next = *headRef;
*headRef = newNode;
}
void
Push2_tail(term **headRef, int coef, int exp)
{
term *newNode = malloc(sizeof(*newNode));
term *head = *headRef;
if (coef == 0)
return;
term *prev = NULL;
for (struct term *cur = head; cur != NULL; cur = cur->next)
prev = cur;
newNode->coef = coef;
newNode->exp = exp;
newNode->next = NULL;
if (prev != NULL)
prev->next = newNode;
else
head = newNode;
*headRef = head;
}
term *
addPolynomials2(term *h1, term *h2)
{
term *current1 = h1;
term *current2 = h2;
#if 0
pushfnc_p push = Push2;
#else
pushfnc_p push = Push2_tail;
#endif
term *new = NULL;
while (current1 && current2) {
dbgprt("add: DUAL current1=%dX%d current2=%dX%d
",
current1->coef,current1->exp,
current2->coef,current2->exp);
if (current1->exp == current2->exp) {
dbgprt("add: SAME
");
push(&new, (current1->coef + current2->coef), current1->exp);
current1 = current1->next;
current2 = current2->next;
continue;
}
if (current1->exp > current2->exp) {
dbgprt("add: CURR1
");
push(&new, current1->coef, current1->exp);
current1 = current1->next;
continue;
}
dbgprt("add: CURR2
");
push(&new, current2->coef, current2->exp);
current2 = current2->next;
}
while (current1) {
dbgprt("add: POST1 current1=%dX%d
",
current1->coef,current1->exp);
push(&new, current1->coef, current1->exp);
current1 = current1->next;
}
while (current2) {
dbgprt("add: POST2 current2=%dX%d
",
current2->coef,current2->exp);
push(&new, current2->coef, current2->exp);
current2 = current2->next;
}
return new;
}
void
printTerm(term *head)
{
printf("%dx%d ", head->coef, head->exp);
}
void
printPolynomial(term *head)
{
for (; head != NULL; head = head->next)
printTerm(head);
}
#define TERM(_coef,_exp)
{ .coef = _coef, .exp = _exp },
void
addPolynomialsTest2(void)
{
term *head1 = NULL;
term *head2 = NULL;
term *new;
#if 0
int a[] = { 10, 0, 0, 5, 0, 3, 0, 5 };
int b[] = { 7, 6, 5, 4, 3, 2, 1, 0 };
for (int i = sizeof(a) / sizeof(int) - 1; i >= 0; i--) {
Push2(&head1, a[i], b[i]);
}
int c[] = { 8, 7, 6, 5, 4, 3, 2, 1, 0 };
int d[] = { 3, 0, 0, 0, 3, 0, 0, 3, -6 };
for (int i = sizeof(d) / sizeof(int) - 1; i >= 0; i--) {
Push2(&head2, d[i], c[i]);
}
#else
term ab[] = {
TERM(10,7)
TERM(0,6)
TERM(0,5)
TERM(5,4)
TERM(0,3)
TERM(3,2)
TERM(0,5)
};
for (int i = 0; i < sizeof(ab) / sizeof(term); ++i) {
term *t = &ab[i];
Push2_tail(&head1,t->coef,t->exp);
}
term cd[] = {
TERM(3,8)
TERM(0,7)
TERM(0,6)
TERM(0,5)
TERM(3,4)
TERM(0,3)
TERM(0,2)
TERM(3,1)
TERM(-6,0)
};
for (int i = 0; i < sizeof(cd) / sizeof(term); ++i) {
term *t = &cd[i];
Push2_tail(&head2,t->coef,t->exp);
}
#endif
printf("F(x)= ");
printPolynomial(head2);
printf("
");
printf("Q(x)= ");
printPolynomial(head1);
printf("
");
printf("F(x) + Q(X)= ");
new = addPolynomials2(head1, head2);
printPolynomial(new);
printf("
");
printf("
");
}
int
main(void)
{
addPolynomialsTest2();
return 0;
}
It's a moot point because constructing the output in reverse order is incorrect (i.e. do not do this).
But, now, I understand why you wanted a recursive function to print the polynomial.
To print in reverse order, I think the function would have to print the current term after recursively calling itself. I've not thought this out [or tested it]:
void
printTerm(term *head)
{
printf("%dx%d ", head->coef, head->exp);
}
void
printPolynomial(term *head)
{
if (head == 0)
return;
#if 0
printTerm(head);
printPolynomial(head->next);
#else
printPolynomial(head->next);
printTerm(head);
#endif
}
</pre
