Home | | **Fundamentals of Data Structures in C** | | **Data Structures** | | **Programming and Data Structures I** | Applications of lists

1. Polynomial ADT
2. Radix Sort
3. Multilist
- POLYNOMIAL MANIPULATION:
Representation ,
Addition,
Multiplication.

**APPLICATIONS OF LINKED
LIST **

1. Polynomial
ADT

2. Radix
Sort

3. Multilist

**POLYNOMIAL MANIPULATION**

Representation

Addition

Multiplication

**Representation of a Polynomial: **A
polynomial is an expression that contains more than two** **terms. A term is
made up of coefficient and exponent. An example of polynomial is

P(x)
= 4x^{3}+6x^{2}+7x+9

A polynomial thus may
be represented using arrays or linked lists. 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. The array representation for the above polynomial expression is
given below:

A polynomial may also be represented using a linked list. A structure may
be defined such that it contains two parts- one is the coefficient and second
is the corresponding exponent. The structure definition may be given as shown
below:

struct polynomial

{

int coefficient; int exponent;

struct polynomial *next; };

Thus the above polynomial may be represented using linked list as shown
below:

**Addition of two
Polynomials:**

For adding two polynomials using arrays is straightforward method, since
both the arrays may be added up element wise beginning from 0 to n-1, resulting
in addition of two polynomials. Addition of two polynomials using linked list
requires comparing the exponents, and wherever the exponents are found to be
same, the coefficients are added up. For terms with different exponents, the
complete term is simply added to the result thereby making it a part of
addition result. The complete program to add two polynomials is given in
subsequent section.

**Multiplication of two
Polynomials:**

Multiplication of two polynomials however requires manipulation of each
node such that the exponents are added up and the coefficients are multiplied.
After each term of first polynomial is operated upon with each term of the
second polynomial, then the result has to be added up by comparing the
exponents and adding the coefficients for similar exponents and including terms
as such with dissimilar exponents in the result. The ‘C’ program for polynom
given below:

**Program for Polynomial
representation, addition and multiplication**

/*Polynomial- Representation, Addition, Multiplication*/

Representation using structure

#include <stdio.h> #include <conio.h> #include <math.h>

typedef struct node { int power;

int coeff;

struct
node *next;

}node;

node
* insert(node *head,int power1,float
coeff1);

node
* create();

node * padd(node *p1,node *p2); void print(node
*head);

node *insert(node *head,int power1,float coeff1)

{

node
*p,*q;

p=(node*) malloc(sizeof(node)); p->power=power1;
p->coeff=coeff1; p->next=NULL; if(head==NULL)

{

head=p; head->next=head; return(head);

}

if(power1>head->power)

{

p->next=head->next; head->next=p; head=p;
return(head);

}

if(power1==head->power)

{

head->coeff=head->coeff+coeff1; return(head);

}

q=head;

while(q->next!=head &&
power1>=q->next->power) q=q->next;

if(p->power==q->power)
q->coeff=q->coeff+coeff1;

else

{

p->next=q->next; q->next=p;

}

return(head);

}

node
*create()

{

int n,i,power1; float coeff1;

node *head=NULL; printf("\nEnter No. of
Terms:"); scanf("%d",&n);

printf("\nenter a term as a tuple of
(power,coefficient) : "); for(i=1;i<=n;i++)

{
scanf("%d%f",&power1,&coeff1);
head=insert(head,power1,coeff1);

}

return(head);

}

node * padd(node *p1,node *p2) { node *p;

node *head=NULL; int power;float coeff;
p=p1->next;

do

{

head=insert(head,p->power,p->coeff);
p=p->next;

} while(p!=p1->next); p=p2->next;

do

{

head=insert(head,p->power,p->coeff);
p=p->next;

} while(p!=p2->next);

return(head);

}

void print( node *head) { node *p;

p=head->next; printf("\n"); do

{

printf("%6.2fx^%d
",p->coeff,p->power); p=p->next;

}while(p!=head->next);

}

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

**Related Topics **

Copyright © 2018-2020 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.