Polynomial ADT

Polynomial ADT

• A polynomial has the main fields as coefficient, exponent.

• In linked list it will have one more field called 'link' field to point to next term in the polynomial.

• If there are n terms in the polynomial then n such nodes has to be created.

• The typical node will look like this.

• For example: To represent 3x²+5x+7 the link list will be

• In each node, the exponent field will store exponent corresponding to that term, the coefficient field will store coefficient corresponding to that term and the link field will point to next term in the polynomial. Again for simplifying the algorithms such as addition of two polynomials we will assume that the polynomial terms are stored in descending order of exponents.

• The node structure for a singly linked list for representing a term of polynomial can be defined as follows:

typedef struct Pnode

{

float coef;

int exp;

struct node *next;

} p;

Advantages of linked representation over arrays :

1. Only one pointer will be needed to point to first term of the polynomial.

2. No prior estimation on number of terms in the polynomial is required. This results in flexible and more space efficient representation.

3. The insertion and deletion operations can be carried out very easily without movement of data.

Disadvantage of linked representation over arrays :

We can not access any term randomly or directly we have to go from start node always.

Addition of Two Polynomials using Singly Linked List

Logic for polynomial addition by linked list :

Step 1: First of all we create two linked polynomials.

For e.g.:

P₁ = 3x³ +2x² + 1x

P₂ = 5x⁵ +3x² +7

Each node in the polynomial will look like this.

Step 2: For addition of two polynomials if exponents of both the polynomials are same then we add the coefficients. For storing the result we will create the third linked list say p3. The processing will be as follows:

Step 3:

Step 4:

Step 5:

Step 6:

Finally

P₃ list is the addition of two polynomials.

Ex. 1.11.1: Implementation of polynomial operation using SLL.

Program To Perform Addition Of Two Polynomials Using

Singly Linear Linked List

#include <stdio.h>

#include <conio.h>

#include <process.h>

#include <alloc.h>

#include <stdlib.h>

#define TRUE 1

#define FALSE O

typedef struct pnode

{

float coef;

int exp;

struct pnode *next;

}p;

void main()

{

p *p1, *p2, *p3;

p *get_poly(),*add(p *,p *);

void display(p *);

clrscr();

printf("\n Enter the first polynomial\n\n");

p1 = get_poly();

clrscr();

printf("\nEnter the Second polynomial\n\n");

p2 = get_poly();

clrscr();

printf("\nThe first polynomial is \n");

display(p1);

printf("\nThe second polynomial is\n");

display(p2);

p3 = add(p1, p2);

printf("\nThe addition of the polynomials is...\n");

display(p3);

exit(0);

}

p *get_poly()

{

p *temp, *New, *last;

int Exp,flag;

float Coef;

p *get_node();

char ans='y';

temp==NULL;

flag=TRUE; /* flag to indicate whether a new node

is created for the first time or not */

printf("\nEnter the polynomial in descending order of exponent\n");

do

{

printf("\nEnter the Coefficient and Exponent of a term :"); scanf("%f%d", &Coef, &Exp);

/* allocate new node */

New get_node();

if (New==NULL)

printf("\nMemory can not be allocated");

New coef = Coef;

/*putting coef, exp values in the node*/

New-> exp = Exp;

if (flag==1) /* Executed only for the first time */

{ /*for creating the first node */

temp = New;

last = temp;

flag = FALSE;

}

else

{

/* last keeps track of the most recently created node */

last ->next = New;

last = = New;

}

printf("\n Do you Want To Add more Terms?(y/n)");

ans=getch();

} while(ans=='y');

return (temp);

}

p *get_node()

{

p *temp;

temp = (p*) malloc(sizeof(p) );

temp->next=NULL;

return(temp);

}

void display(p *head)

{

p *temp;

temp=head;

if (temp == NULL)

{

printf("The polynomial is empty\n");

getch();

return;

}

printf("\n");

while (temp->next!= NULL)

{

printf("%0.1fx^%d + ", temp->coef, temp->exp);

temp =temp -> next;

}

printf("%0.1fx^%d ", temp->coef, temp->exp);

getch();

}

p *add(p* first, p* second)

{

p *p1, *p2, *temp, *dummy;0

char ch;

float Coef;

p *append(int,float,p *);

p1= first;

p2 = second;

temp = ( p *)malloc(sizeof( p ) );

if (temp == NULL)

printf("\nMemory can not be allocated");

dummy = temp;/*dummy is a start node */

while (p1 != NULL && p2 != NULL)

{

if(p1->exp==p2->exp)

{

Coef = p1->coef + p2->coef;

temp = append(p1->exp, Coef,temp);

p1 = p1->next;

p2 = p2->next;

}

else if(p1->exp<p2->exp)

{

Coef = p2 -> coef;

temp =append(p2->exp, Coef, temp);

p2 = p2 ->next;

}

else if(p1->exp>p2->exp)

{

Coef p1-> coef;

temp = append(p1->exp, Coef,temp);

p1 = p1 ->next;

}

}

/*copying the contents from first polynomial to the resultant polynomial */

while (p1 != NULL)

{

temp=append(p1->exp, p1->coef, temp);

p1 = p1 ->next;

}

/*copying the contents from second polynomial to the resultant polynomial */

while (p2 != NULL)

{

temp = append(p2->exp, p2->coef,temp);

p2 = p2 ->next;

}

temp->next = NULL;

temp=dummy->next;/*Now set temp as starting node*/

free (dummy);

return( temp);

}

p *append(int Exp, float Coef, p* temp)

{

p *New, *dummy;

New = (p*)malloc(sizeof(p) );

if (New == NULL)

printf("\n Memory can not be allocated \n");

New->exp = Exp;

New->coef= Coef;

New->next = NULL;

dummy = temp;

dummy->next = New;

dummy New;

return(dummy);

}

Output

Enter the first polynomial

Enter the polynomial in descending order of exponent

Enter the Coefficient and Exponent of a term :3 3

Do you Want To Add more Terms?(y/n)

Enter the Coefficient and Exponent of a term :2 2

Do you Want To Add more Terms?(y/n)

Enter the Coefficient and Exponent of a term :1 1

Do you Want To Add more Terms?(y/n)

Enter the Coefficient and Exponent of a term :1 0

Do you Want To Add more Terms?(y/n)

Enter the Second polynomial

Enter the polynomial in descending order of exponent

Enter the Coefficient and Exponent of a term :53

Do you Want To Add more Terms?(y/n)

Enter the Coefficient and Exponent of a term :7 1

Do you Want To Add more Terms?(y/n)

The first polynomial is

3.0x3+2.0x^2 + 1.0x1+ 1.0x^0

The second polynomial is

5.0x^3+ 7.0x^1

The addition of the polynomials is...

8.0x3+ 2.0x^2+8.0x1+ 1.0x^0

Ex. 1.11.2: Write a C program for performing addition, subtraction and multiplication operations on polynomial using linked list.

Sol. :

Addition : Refer example 1.11.1

Subtraction: Refer example 1.11.1. Replace + operator of add function by (minus)

operator

Multiplication :

#include <stdio.h>

#include <conio.h>

#include <process.h>

#include <stdlib.h>

#define TRUE 1

#define FALSE O

typedef struct pnode

{

float coef;

int exp;

struct pnode *next;

}p;

void main()

{

p *p1, *p2, *p3;

p *get_poly(),*mul(p *,p *);

void display(p *);

printf("\n Enter the first polynomial\n");

p1=get_poly();

printf("\nEnter the Second polynomial\n");

p2=get_poly();

printf("\nThe first polynomial is \n");

display(p1);

printf("\nThe second polynomial is\n");

display(p2);

p3=mul(p1,p2);

printf("\nThe multiplication of the polynomials is...\n");

display(p3);

exit(0);

}

p * get_poly()

{

p *temp, *New, *last;

int Exp,flag;

float Coef;

p *get_node();

char ans='y';

temp=NULL;

flag=TRUE; /* flag to indicate whether a new node

is created for the first time or not */

printf("\nEnter the polynomial in descending order of exponent\n");

do

{

printf("\nEnter the Coefficient and Exponent of a term :");

scanf("%f%d", &Coef, &Exp);

/* allocate new node */

New (p *)malloc(sizeof(p));

if(New== NULL)

printf("\nUnable to allocate memory ");

New->coef=Coef;

New->exp=Exp ;/*putting coef,exp values in the node*/

New->next=NULL;

if(flag==TRUE) /* Executed only for the first time */

{  /*for creating the first node*/

temp=New;

last=temp;

flag = FALSE;

}

else

{

/* last keeps track of the most recently created node */

last->next=New;

last=New;

}

printf("\n Do you Want To Add more Terms?(y/n)");

ans=getch();

}while(ans=='y');

return (temp);

}

void display(p *temp)

{

p *curr;

curr=temp;

if(curr== NULL)

{

printf("The polynomial is empty\n");

getch();

return;

}

while(curr->next!= NULL)

{

printf("%0.1fx^%d + ",curr->coef,curr->exp );

curr = curr->next;

}

printf("%0.1fx^%d ",curr->coef,curr->exp);

getch();

}

p* mul(p* First,p* Second)

{

p *p1,*p2,*p3, *dummy, *temp;

int Exp,flag;

float Coef;

p *Attach(int,float,p *);

p1 = First;

p3= (p*)malloc(sizeof(p));

p3->next=NULL;

dummy=p3;

while (p1 != NULL)

{

p2 = Second;

while (p2!= NULL)

{

Coef=p1->coef*p2->coef;

Exp-p1->exp+p2 ->exp;

temp = dummy->next;

flag = 0;

while(temp!= NULL && !flag)

{

if (temp->exp==Exp)

flag=1;

else

temp=temp->next;

}

if (flag==1)

temp->coef=temp->coef+Coef;

else

p3=Attach(Exp, Coef,p3);

p2= p2->next;

}

p1 = p1 ->next;

}

p3->next = NULL;

p3-dummy->next;

dummy->next=NULL;

free(dummy);

return(p3);

}

Р*Attach( int Exp, float Coef, p * third)

{

p *New,*tmp;

New = (p *)malloc(sizeof(p));

New->exp = Exp;

New->coef = Coef;

New->next = NULL;

tmp=third;

tmp->next=New;

tmp=New;

return(tmp);

}

Output

Enter the first polynomial

Enter the polynomial in descending order of exponent

Enter the Coefficient and Exponent of a term :3 3

Do you Want To Add more Terms?(y/n)

Enter the Coefficient and Exponent of a term :2 2

Do you Want To Add more Terms?(y/n)

Enter the Coefficient and Exponent of a term :1 1

Do you Want To Add more Terms?(y/n)

Enter the Second polynomial

Enter the polynomial in descending order of exponent

Enter the Coefficient and Exponent of a term :5 5

Do you Want To Add more Terms? (y/n)

Enter the Coefficient and Exponent of a term :3 2

Do you Want To Add more Terms?(y/n)

Enter the Coefficient and Exponent of a term :7 0

Do you Want To Add more Terms?(y/n)

The first polynomial is

3.0x3+ 2.0x^2+ 1.0x^1

The second polynomial is

5.0x53.0x^2 + 7.0x^0

The multiplication of the polynomials is...

15.0x89.0x^5 + 24.0x^3+ 10.0x^7+ 6.0x^4+ 14.0x^2 + 5.0x^6 + 7.0x^1

Ex. 1.11.3 State the polynomial representation for 6x3 +9x2+7x+1 using linked list. Write procedure to add and multiply two polynomial and explain with suitable example.

Sol. Representation :

Procedures for addition and multiplication - Refer : Addition of Two Polynomials using Singly Linked List

Review Questions

1. Write a function to add two Polynomials using linked list.

2. Write a C program to add two polynomials using linked list