Friday, September 23, 2011

Polynomial using Linked Lists: Insertion, printing, adding two polynomials


//Any issues will be discussed in comments. Program tested with gcc compiler.
//Polynomial using linked lists: insert new term, print polynomial, add two polynomials

#include<stdio.h>
typedef struct polyNode *polyPointer;
struct polyNode
{
    int coef;
    int expon;
    polyPointer link;
}polyNode;

void printPoly(polyPointer);
void insertTerm(int,int,polyPointer);
polyPointer addPoly(polyPointer,polyPointer);

main()
{
    polyPointer p1,p2,p3;
    p1=malloc(sizeof(polyNode));
    p1->link=NULL;

    p2=malloc(sizeof(polyNode));
    p2->link=NULL;

    insertTerm(2,2,p1);
    insertTerm(5,5,p1);
    insertTerm(7,4,p2);
    insertTerm(-3,0,p2);
    insertTerm(4,4,p2);
    p3=addPoly(p1,p2);
    printf("\n");
    printPoly(p3);
    printf("\n");
    printPoly(p2);
    printf("\n");
    printPoly(p1);
}

void insertTerm(int coef,int expon,polyPointer root)
{
    if(root->link)
    {
        while(root->link && root->link->expon>=expon)
        root=root->link;
    }

    if(root->expon==expon)
    {
        root->coef+=coef;
        return;
    }

    polyPointer temp;
    temp=malloc(sizeof(polyNode));
    temp->coef=coef;
    temp->expon=expon;

    temp->link=root->link;
    root->link=temp;
}

void printPoly(polyPointer root)
{
    printf("\n");
    while(root->link)
    {
        printf("(%dx^%d)+",root->link->coef,root->link->expon);
        root=root->link;
    }
}

polyPointer addPoly(polyPointer p1, polyPointer p2)
{
    polyPointer p3;
    p3=malloc(sizeof(struct polyNode));
    p3->link=NULL;

    while(p1->link && p2->link)
    {
        while(p2->link && (p1->link->expon >= p2->link->expon))
        {
            insertTerm(p2->link->coef,p2->link->expon,p3);
            p2=p2->link;
        }

        while(p2->link && p1->link && (p2->link->expon >= p1->link->expon))
        {
            insertTerm(p1->link->coef,p1->link->expon,p3);printf("1");
            p1=p1->link;
        }
    }

    while(p1->link)
    {
        insertTerm(p1->link->coef,p1->link->expon,p3);
        p1=p1->link;
    }

    while(p2->link)
    {
        insertTerm(p2->link->coef,p2->link->expon,p3);
        p2=p2->link;
    }

    return p3;
}

No comments:

Post a Comment