#include <stdio.h>
#include <malloc.h>

struct Polynomial
{
    float Coefficient;
    int Exponent;
    Polynomial *Next;
};

Polynomial *CreatPoly (int m)
{
    int i;
    Polynomial *front,*back,*h,*p;
    p = (Polynomial *)malloc(sizeof(Polynomial));
    p -> Next = NULL;
    p -> Coefficient = 0;
    p -> Exponent = -1;
    front = p;
    for(i = 1;i <= m; ++i)
    {
        back = (Polynomial *)malloc(sizeof(struct Polynomial));
        printf("Please enter the Exponent\n");
        scanf("%d",&back->Exponent);
        printf("Please enter the Coefficient\n");
        scanf("%f",&back->Coefficient);
        back->Next = front->Next;
        front->Next = back;
        front = back;
    }
    return p;
}

Polynomial *AddPolynomial(Polynomial *Poly1,Polynomial *Poly2)
{
    float sum;
    Polynomial *qa,*qb,*la,*lb;
    la = Poly1;
    lb = Poly2;
    qa = la -> Next;
    qb = lb -> Next;
    while(qa != NULL && qb != NULL)
    {
        if(qa -> Exponent < qb -> Exponent)
        {
            la = qa;
            qa = qa -> Next;
        }
        
        else if(qa -> Exponent == qb -> Exponent)
        {
            sum = qa -> Coefficient + qb -> Coefficient;
            if(sum != 0.0)
            {
                qa -> Coefficient = sum;
                la = qa;
                qa = qa -> Next;
                lb = qb;
                qb = qb -> Next;
                free(qb);
                qb = lb -> Next;
            }
           else
           {
            la -> Next = qa -> Next;
            free(qa);
            qa = la -> Next;
            lb -> Next = qb -> Next;
            free(qb);
            qb = lb -> Next;
           }
        }
        else if(qa -> Exponent > qb -> Exponent)
        {
            lb -> Next = qb -> Next;
            la -> Next = qb;
            qb -> Next = qa;
            la = qb;
            qb = lb -> Next;
        }
    }
    if(qb != NULL)
    la -> Next = qb;
    free(lb);
    free(qa);
    return Poly1;
}


int main()
{
    int m,n;
    Polynomial *Poly1,*Poly2,*PolySum,*on;
    printf("Please enter the items of the first polynomial\n");
    scanf("%d",&m);
    printf("Please enter the items of the second polynomial\n");
    scanf("%d",&n);
    printf("Now input the items for the first polynomial\n");
    Poly1 = CreatPoly(m);
    printf("Now input the items for the second polynomial\n");
    Poly2 = CreatPoly(n);
    PolySum = AddPolynomial(Poly1,Poly2);
    printf("The sum is\n");
    on = PolySum;
    on = on -> Next;
    while(on -> Next != NULL)
    {        
        printf("%f %d ",on -> Coefficient,on -> Exponent);
        on = on -> Next;
    }
    system("pause");
    
    return 0;
}