Polynomials with Linked List

​

M.Jeevana Sujitha

Asst Professor

​

Department of Computer science and Engineering

SRKR Engineering College, Bhimavaram, AP-534204

​

Advanced Data Structures

(Subject code:B19CS2104)

​

Objectives

• To differentiate polynomials representation with Arrays and linked lists.
• To learn polynomial implementation with Linked Lists

​

​

Definition of Polynomials

• A single variable Polynomial can be generalized

as

Example:

P(x)= 6x³-8x²+5x+4

Coefficient Variable Exponent

Implementation of Polynomials

There are different ways to implement the polynomials

• Arrays
• Linked Lists

​

​

Polynomials With Arrays

• p1(x)= 6x³-8x²+5x+4
• p2(x)=9x⁴+23x-6

p1(x) p2(x)

p1[0] p1[1] p1[2] p1[3] p2[0] p2[1] p2[2] p2[3] p2[4]

​

index represents exponents

4

5

-8

6

-6

23

0

0

9

Polynomials With Arrays

• P3(x)= 15x²⁵+6x³+8x-10

  p3(x)

​

p3[0] p3[1] p3[2] p3[3] p3[4] …………………………………… p3[24] p3[25]

Wastage of space

This iswhy Arrays are not good to represent polynomials

-10

8

0

6

0

…………………………………

15

0

0

Polynomials With Linked Lists

• For a single variable polynomial the information field of the node contains two parts:
• one for Coefficient and the other for Exponent

• P3(x)= 15x²⁵+6x³+8x-10

ROOT NULL

coefficient

Exponent

Next Node Address

15

25

6

3

8

1

-10

0

Polynomials With Linked Lists

Advantages

• Save Space
• Easy to Maintain

​

Disadvantage

• Sequential Access

​

​

​

​

​

� “C” routines for Polynomial Operations�

Node Declaration:

struct polynode

{

double coeff;

int expo;

struct polynode *link;

};

​

​

� “C” routines for Polynomial Operations�

polyptr readPoly()

{ //initialize root pointer

polyptr first=NULL; double c; int p;

printf("\n Enter the COEFFICIENT and EXPONENT in INCREASING ORDER of exponent(terminate with 0,0):\n");//give the input like this 3 4 2 3 5 1 6 0 0 0

scanf("%lf%d",&c,&p);

while(c!=0) Coefficient Exponent

{

first=insertend(first,c,p);

scanf("%lf%d",&c,&p);

}

return first;

}

​

3

4

2

3

5

1

6

0

� “C” routines for Polynomial Operations�

void writePoly(polyptr first)

{

polyptr t;

if(first==NULL) //if the given polynomial is empty then return

return;

t=first; //copy the given polynomial ptr to temporary ptr

while(t->link!=NULL)

{ //print all nodes up to last node

printf("(%3.1lf)*x^%ld+",t->coeff,t->expo);

t=t->link;//go to next node

}

printf("(%3.1lf)*x^%ld",t->coeff,t->expo);//Print last node

}

​

Output

Summary

• Wastage of Space
• Random Access

• Save Space
• Sequential Access

Arrays

Linked Lists

​

​

​

Thank you