Showing posts with label list. Show all posts
Showing posts with label list. Show all posts

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;
}

Linked List Complete C program with insertion, deletion, print, reversing of List


//Any Problems can be discussed in comments.
//operations: insertNode, deleteNode, printList, reverseList

#include<stdio.h>

typedef struct node *nodePointer;
struct node
{
    int data;
    struct node *link;
}node;
int length=0;

void insertNode(int,nodePointer);
void print(nodePointer);
void deleteNode(int,nodePointer);
nodePointer reverseList(nodePointer);

main()
{
    nodePointer root;
    root=malloc(sizeof(node));
    root->link=NULL;
    insertNode(34,root);
    insertNode(56,root);
    insertNode(45,root);
    print(root);
    printf("Length is %d\n",length);

    root=reverseList(root);
    print(root);
    printf("Length is %d\n",length);
    deleteNode(56,root);
    deleteNode(34,root);
    insertNode(53,root);
    print(root);
    printf("Length is %d\n",length);

}

void insertNode(int data,nodePointer root)
{
    int i;
    if(length>0)
    {
        while(root->link)
        root=root->link;
    }

    nodePointer temp;
    temp=malloc(sizeof(node));
    temp->data=data;
    root->link=temp;
    temp->link=NULL;
    length++;
}

void print(nodePointer root)
{
    printf("Root");
    while(root->link)
    {
        printf("->%d",root->link->data);
        root=root->link;
    }
    printf("\n");
}

void deleteNode(int data,nodePointer root)
{
    nodePointer temp;
    temp=root;
    while(root->link)
    {
        if(root->link->data==data)
        {
            temp=root->link->link;
            free(root->link);
            root->link=temp;
            length--;
            return;
        }
        else
        {
            temp=root;
            root=root->link;
        }
    }
}

nodePointer reverseList(nodePointer root)
{
    nodePointer middle,trail,temp;
    temp=root;

    middle=NULL;
    root=root->link;

    while(root)
    {
        trail=middle;
        middle=root;
        root=root->link;
        middle->link=trail;
    }
    temp->link=middle;

    return temp;
}