Order List : Single Variable Polynomial

Order list is the most common & frequently used data object.
Linear elements of an order list are related with each other in a particular order or sequence

Example:

1. Odd nos. Less than or equal to 15={1,3,5,7,11,13,15}

2. Months={January, February,....December}

Array are the most common data structure that can be used for representing an order list.
In order list, members of the list follow some specific sequence.
Polynomial is one of the example of order list.

Single Variable Polynomial

There is only a single variable in the polynomial expression, and we generally denote that single variable by x (or in some cases, y or z).

we will generally represent polynomial expressions by the following symbols:

p(x),q(y), r(t)....

p(x)=ax2+bx+c

When we think of a polynomial as an ADT, the basic operations are as follows:

1. Creation of a polynomial 

2. Addition 

3. Subtraction

4. Multiplication    

5. Polynomial Evaluation 

An essential characteristic of the polynomial is that each term in the polynomial expression consists of two parts:

1. one is the coefficient

2. other is the exponent

10x2 + 26x, here 10 and 26 are coefficients and 2, 1 is its exponential value.

3y5+2y3+y+4=0 is a polynomial with degree 5.

The important information about polynomial is contained in the coefficient & exponents of Y

Representation of Polynomial:

Polynomial can be represented in the various ways. These are:

1. By the use of arrays

2. By the use of Linked List

Representation of Polynomial using Array:

we store polynomials in the decreasing order of their exponents.

The degree of a polynomial is the highest exponent in the polynomial.

Array representation assumes that the exponents of the given expression are arranged from 0 to the highest value (degree),

which is represented by the subscript of the array beginning with 0. The coefficients of the respective exponent are placed at an appropriate index in the array.

For a polynomial of degree n , we would need an array of size n+1.

Example: p(x)= 3x3+x2-2x+5

Index	0	1	2	3
Coefficient	3	1	-2	5
Exponent	3	2	1	0

Pseudo Code:

struct polynomial

{

int coefficient;

int exponent;

Int arr[12][12];

};

Representation of Polynomial using Linked List:

Linked list is a data structure that stores each element as an object in a node of the list.

Node has two parts:

Data

Address

Node of a Polynomial:

Data	Address/ link

In the Polynomial linked list, the coefficients and exponents of the polynomial are defined as the data node of the list....

Pseudo Code:

struct polynomial

{

int coefficient;

int exponent;

polynomial *next;

};

Addition of two Polynomials:

Let us illustrate the way the two polynomials are added, let us consider P and Q be two polynomials having these two polynomials three terms each.

p= 30x2 + 20x + 100 —————(1)

Q= 60x3 + 50x2 + 60x——————(2)

we can represent these two polynomials as:-

........(1)

.........(2)

Algorithm:

Step 1: Compare the exponent of P and the corresponding exponent of q.

here expo(p) < expo(q) so, added the terms pointer to by q to the resultant list and now advanced the q pointer.

Step :2

first of all, here we compare the exponents of the current items between given P & Q.

expo(p) = expo(q)

therefore, add the coefficients of these two terms and link this to the resultant list and advance the pointers p and q to their next nodes.

Step :3

furthermore, we compare the exponents of the current terms again

expo(p)=expo(q)

therefore, we add the coefficients of these two terms and link this to the resultant linked list and advance the pointers to their next.

you will notice that nodes Q reaches the NULL and P points the last node.

Step :4

In the below figure, you will notice that there is no node in the second polynomial to compare with.

You can understand in a better way after seeing the figure, so the last node in the first polynomial is added to the end of the resultant linked list.