Printing the result linked list in correct order

Question

I am writing a program which add 2 given polynomials into a third one using linked lists but the result linked list is in reverse order and I cant get my head around it

Inputs: (10x7 + 5x4 + 3x2 + 5) + (3x8 + 3x4 + 3x -6)

result: -1x0 + 3x + 3x2 + 8x4 + 10x7 + 3x8

I want it: 3x8 + 10x7 + 8x4 + 3x2 +3x -1x0

those are the functions:

typedef struct term
{
    int coef;
    int exp;
    struct term *next;
} term;
        
void Push2(term **headRef, int coef, int exp)
{
    struct term *newNode = (term *)malloc(sizeof(term));
    if (coef == 0)
        return;
            
    newNode->coef = coef;
    newNode->exp = exp;
    newNode->next = *headRef;
    *headRef = newNode;
}

term *addPolynomials2(term *h1, term *h2)
{
    term *current1 = h1;
    term *current2 = h2;
        
    term *new = NULL;
    while (current1 && current2)
    {
        if (current1->exp == current2->exp)
        {
            Push2(&new, (current1->coef + current2->coef), current1->exp);
            current1 = current1->next;
            current2 = current2->next;
        }
        else if (current1->exp > current2->exp)
        
        {
            Push2(&new, current1->coef, current1->exp);
            current1 = current1->next;
        }
        
        else
        {
            Push2(&new, current2->coef, current2->exp);
            current2 = current2->next;
        }
    }

    while (current1)
    {
        Push2(&new, current1->coef, current1->exp);
        current1 = current1->next;
    }

    while (current2)
    {
        Push2(&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)
{
    if (head == 0)
        return;
            
    printTerm(*head);
    printPolynomial(head->next);
}

void addPolynomialsTest2()
{
    term *head1 = NULL;
    term *head2 = NULL;
    term *new;
    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]);
    }
    printf("F(x)= ");
    printPolynomial(head2);
    printf("\n");
    printf("Q(x)= ");
    printPolynomial(head1);
    printf("\n");
    printf("F(x) + Q(X)= ");
    new = addPolynomials2(head1, head2);
    printPolynomial(new);
    printf("\n");
    printf("\n");
}

Answer 1

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\n",
            current1->coef,current1->exp,
            current2->coef,current2->exp);

        if (current1->exp == current2->exp) {
            dbgprt("add: SAME\n");
            push(&new, (current1->coef + current2->coef), current1->exp);
            current1 = current1->next;
            current2 = current2->next;
            continue;
        }

        if (current1->exp > current2->exp) {
            dbgprt("add: CURR1\n");
            push(&new, current1->coef, current1->exp);
            current1 = current1->next;
            continue;
        }

        dbgprt("add: CURR2\n");
        push(&new, current2->coef, current2->exp);
        current2 = current2->next;
    }

    while (current1) {
        dbgprt("add: POST1 current1=%dX%d\n",
            current1->coef,current1->exp);
        push(&new, current1->coef, current1->exp);
        current1 = current1->next;
    }

    while (current2) {
        dbgprt("add: POST2 current2=%dX%d\n",
            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("\n");
    printf("Q(x)= ");
    printPolynomial(head1);
    printf("\n");
    printf("F(x) + Q(X)= ");
    new = addPolynomials2(head1, head2);
    printPolynomial(new);
    printf("\n");
    printf("\n");
}

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\n",
            current1->coef,current1->exp,
            current2->coef,current2->exp);

        if (current1->exp == current2->exp) {
            dbgprt("add: SAME\n");
            push(&new, (current1->coef + current2->coef), current1->exp);
            current1 = current1->next;
            current2 = current2->next;
            continue;
        }

        if (current1->exp > current2->exp) {
            dbgprt("add: CURR1\n");
            push(&new, current1->coef, current1->exp);
            current1 = current1->next;
            continue;
        }

        dbgprt("add: CURR2\n");
        push(&new, current2->coef, current2->exp);
        current2 = current2->next;
    }

    while (current1) {
        dbgprt("add: POST1 current1=%dX%d\n",
            current1->coef,current1->exp);
        push(&new, current1->coef, current1->exp);
        current1 = current1->next;
    }

    while (current2) {
        dbgprt("add: POST2 current2=%dX%d\n",
            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("\n");
    printf("Q(x)= ");
    printPolynomial(head1);
    printf("\n");
    printf("F(x) + Q(X)= ");
    new = addPolynomials2(head1, head2);
    printPolynomial(new);
    printf("\n");
    printf("\n");
}

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
}

This might fix the print of the result polynomial.

But, doing this would break the printing of the two input polynomials.

Answer 2

void Reverse(term *Node)
{
if(Node== NULL) return;

Reverse(Node->next);
printTerm(*Node);
}

And call Reverse(New) instead of PrintPolynomial(New)

Output: F(x) + Q(X)= 3x8 10x7 8x4 3x2 3x1 -1x0

Full solution:

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

typedef struct term
{
int coef;
int exp;
struct term *next;

} term;


void Push2(term **headRef, int coef, int exp)
{
struct term *NewNode = (term *)malloc(sizeof(term));
if (coef == 0)
    return;

NewNode->coef = coef;
NewNode->exp = exp;
NewNode->next = *headRef;
*headRef = NewNode;
}

term *addPolynomials2(term *h1, term *h2)
{
term *current1 = h1;
term *current2 = h2;

term *New = NULL;
while (current1 && current2)

{
    if (current1->exp == current2->exp)
    {
        Push2(&New, (current1->coef + current2->coef), current1->exp);
        current1 = current1->next;
        current2 = current2->next;
    }
    else if (current1->exp > current2->exp)

    {
        Push2(&New, current1->coef, current1->exp);
        current1 = current1->next;
    }

    else
    {
        Push2(&New, current2->coef, current2->exp);
        current2 = current2->next;
    }
}
while (current1)
{
    Push2(&New, current1->coef, current1->exp);
    current1 = current1->next;
}
while (current2)
{
    Push2(&New, current2->coef, current2->exp);
    current2 = current2->next;
}
return New;
}

void printTerm(term head)
{
 printf("%dx%d ", head.coef, head.exp);
}

void Reverse(term *Node)
{
if(Node== NULL)
    return;
Reverse(Node->next);
printTerm(*Node);
}

void printPolynomial(term *head)
{
if (head == 0)
    return;

printTerm(*head);
printPolynomial(head->next);
 }
void addPolynomialsTest2()
{
term *head1 = NULL;
term *head2 = NULL;
term *New;
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]);
}
printf("F(x)= ");
printPolynomial(head2);
printf("\n");
printf("Q(x)= ");
printPolynomial(head1);
printf("\n");
printf("F(x) + Q(X)= ");
New = addPolynomials2(head1, head2);

while(New!= NULL)
{
    printTerm(*New);
    New = New->next;
}
Reverse(New);
printf("\n");
printf("\n");
}
int main()
{
addPolynomialsTest2();
}