Archive for the ‘LINKEDLIST’ Category

LINKED LIST

April 1, 2008

HOME

Linked list:

In order to store elements in the sequential
fashion we use Arrays. But they are fixed max
size,suppose if we want to use less memory than
that of fixed size then memory is wastaged, or
If we want to use more memory than that of fixed
size then deficiency of the memory will be the
problem.

In order to overcome all these type of problem
we use dynamically allocated memory ,which can
be allocated at run time called as node, so the
sequential arrangement of nodes are called linked
lists.

There are 2 types Single linkedlist and Double

linkedlist

HOME

Advertisements

POLYNOMIAL

March 27, 2008

HOME
/*PROGRAM
FOR ADDING,SUBTRACTION,

 
MULTIPLYCATION OF 2 POLINOMIALS*/

#include<iostream.h>
#include<stdlib.h>
int
d,i,y;

static
int z=0;//GLOBAL
VARIABLES

class
poly//CLASS
DECLARATION

{
private:
  
float  coeff;

  
int degree;

  
poly *next;

public:
  
void  getdata(float ,int );

  
void add();

  
void  show(poly *);

  
void list_add(float ,poly *);

  
void sub();

  
void list_sub(float ,poly *);

  
void mul();

  
void list_mul(float,int);

 

}
*head1,*head2,*head3,

 *head,*head4,*head5,*head6;

//FUNCTION
FOR READING DATA

void  
poly::getdata(float c,int d)

{
poly
*n,*temp;

n=new(poly);
n->degree=d;
n->coeff=c;
n->next=NULL;
if(head==NULL)
head=n;
else
{
temp=head;
while(temp->next!=NULL)
temp=temp->next;
temp->next=n;
}
if(i==0&&z==0)
{
head1=head;
head=NULL;
temp=NULL;
z++;
}
else
{
head2=head;
}
  
     

}
void
poly::add()

//FUNCTION
FOR FINDING THE ADDITION

{
poly
*t1,*t2;

float
x;

t1=head1;
t2=head2;
while(t1!=NULL||t2!=NULL)
{
  
 

if(t1->degree>t2->degree)
{
x=t1->coeff;
list_add(x,t1);
t1=t1->next;
}

else
if(t1->degree<t2->degree)
{
x=t2->coeff;
list_add(x,t2);
t2=t2->next;
}
else
{
x=t1->coeff+t2->coeff;
list_add(x,t1);
t1=t1->next;
t2=t2->next;
}
}
}
void
poly::list_add(float ele,poly *t)

/*FUNCTION
FOR CREATING

 
LINKEDLIST FOR ADDED COEFFICIENTS*/

{
poly
*t3,*n1;

n1=new(poly);
n1->coeff=ele;
n1->degree=t->degree;
n1->next=NULL;
if(head3==NULL)
head3=n1;
  
         

else
{
t3=head3;
while(t3->next!=NULL)
t3=t3->next;
t3->next=n1;
}

}
//FUNCTION
FOR SUBTRACTION

void
poly::sub()

{
poly
*t1,*t2;

float
x;

t1=head1;
t2=head2;
while(t1!=NULL||t2!=NULL)
{
  
 

if(t1->degree>t2->degree)
{
x=t1->coeff;
list_sub(x,t1);
t1=t1->next;
}

else
if(t1->degree<t2->degree)
{
x=t2->coeff;
list_sub(x,t2);
t2=t2->next;
}
else
{
x=t1->coeff-t2->coeff;
list_sub(x,t1);
t1=t1->next;
t2=t2->next;
}
}
}

/*FUNCTION
FOR CREATING LIST  

  
FOR SUBTRACTED COEFFICIENTS*/

void
poly::list_sub(float ele,poly *t)

{  
 

poly
*t3,*n1;

n1=new(poly);
n1->coeff=ele;
n1->degree=t->degree;
n1->next=NULL;
if(head4==NULL)
head4=n1;
  
         

else
{
t3=head4;
while(t3->next!=NULL)
t3=t3->next;
t3->next=n1;
}

}
void
poly::mul()

//FUNCTOIN
FOR MULTIPLICATION

{
float
x;

poly
*t1,*t2;

t1=head1;
t2=head2;
int k;
k=t1->degree+t2->degree;
while(k>=0)
{
x=0;
 while(t1!=NULL)
{
while(t2!=NULL)
{
if((t1->degree+t2->degree)==k)
x=x+t1->coeff*t2->coeff;
t2=t2->next;
}
t1=t1->next;
t2=head2;
}
list_mul(x,k);  
 

 k–;
 t1=head1;
t2=head2;

}
  
     

}
void
poly::list_mul(float x,int k )

/*FUNCTION
FOR CREATION OF

 LIST
FOR MULTIPLIED COEFFICIENTS*/

{  
 

poly
*t,*n;

n=new(poly);
n->coeff=x;
n->next=NULL;
n->degree=k;
if(head5==NULL)
head5=n;
else
{
 t=head5;
 while(t->next!=NULL)
t=t->next;
 t->next=n;
}

}

  
       
     

void
poly::show(poly * head)

//FUNCTION
FOR DISPLAYING OUTPUT

{
poly
*temp=NULL;

if(head==NULL)
cout<<“LIST
EMPTY”;

else
{
temp=head;
while(temp!=NULL)
{
if(temp->coeff>0&&temp->degree>0)
cout<<temp->coeff
   
<<” x^
“<<temp->degree<<” + “;

else
if(temp->degree==0&&temp->coeff<0)
cout<<“(“<<temp->coeff<<“)”;
else
if(temp->degree==0)
cout<<temp->coeff;
else
if(temp->coeff==0);
else
cout<<“\b”<<“(“<<temp->coeff<<“)”
   
<<“x^”<<temp->degree<<“-“;

temp=temp->next;
}
}

}

void
main()//MAIN()
FUNCTION STARTS

{
head1=NULL;
head2=NULL;
head3=NULL;
head4=NULL;
head5=NULL;
head6=NULL;

float
c;

poly
p;//OBJECT CREATION

cout<<“PROGRAM
FOR THE

    
OPERATIONS ON THE POLYNOMIAL”;

cout<<“\n\nENTER
THE DEGREE

      
OF THE first POLYNOMIAL\n”;

cin>>d;
for(i=d;i>=0;i–)
{
  
     

if(i==0)
{
cout<<“\nENTER
THE CONSTANT\t”;

cin>>c;
}
else
{  
 

cout<<“\nENTER
THE

      
COEFFICIENT OF x^”<<i<<“\t”;

cin>>c;
}
p.getdata(c,i);
  
     

}
p.show(head1);
  
 

cout<<“\n\nENTER
THE DEGREE

      
OF THE second POLYNOMIL\n”;

cin>>d;
for(
i=d;i>=0;i–)

{
  
     

if(i==0)
{
cout<<“\nENTER
THE CONSTANT\t”;

cin>>c;
}
else
{
cout<<“\nENTER
THE

     
COEFFICIENT OF x^”<<i<<“\t”;

cin>>c;
}
p.getdata(c,i);
  
     

}
p.show(head2);
p.add();
cout<<“\nAFTER
ADDING \n\n”;

p.show(head3);
p.sub();
cout<<“\nAFTER
SUBTRACTNG \n\n”;

p.show(head4);
cout<<“\nAFTER
MULTIPLICATION \n\n”;

p.mul();
p.show(head5);
}

/*OUTPUT:
case
1:

ENTER
THE DEGREE OF THE first POLYNOMIAL

3

ENTER
THE COEFFICIENT OF x^3    1

ENTER
THE COEFFICIENT OF x^2    2

ENTER
THE COEFFICIENT OF x^1    -0.5

ENTER
THE CONSTANT      5.9

1
x^ 3 + 2 x^ 2 +(-0.5)x^1-5.9

ENTER
THE DEGREE OF THE second POLYNOMIL

2

ENTER
THE COEFFICIENT OF x^2    10.5

ENTER
THE COEFFICIENT OF x^1    7

ENTER
THE CONSTANT      0

10.5
x^ 2 + 7 x^ 1 + 0

AFTER
ADDING

1
x^ 3 + 12.5 x^ 2 + 6.5 x^ 1 + 5.9

AFTER
SUBTRACTNG

1
x^ 3 +(-8.5)x^2(-7.5)x^1-5.9

AFTER
MULTIPLICATION

10.5
x^ 5 + 28 x^ 4 + 8.75 x^ 3

 
+ 58.45 x^ 2 + 41.3 x^ 1 + 0

 

  
 Press any key to continue

*/

HOME

DELETION_AT_ANYWHERE

March 27, 2008

DELETION_AT_ANY_POSITION

HOME
/*PROGRAM
FOR DELETION OF ELEMENTS AT ANYWHERE*/


#include”iostream.h”

class
List//NAME OF THE
CLASS

{
private: 
//DATA MEMBERS

  
 int data;

  
 List *next;

public:       
 

  
 void insert_end(int);

  
 int del_any();  //MEMBER FUNCTIONS

   
void display();

}
*head;  //OBJECT
ACTS AS NODE

//FUNCTION
DECLARATION

void
List::insert_end(int ele)

{

 
List *n,*temp;

   
n=new(List);//MEMORY
ALLOCATION

  
 n->data=ele;

  
 n->next=NULL;

/*IF
THE LIST IS EMPTY THEN ADD 1st NODE AS      
HEADER NODE*/

if(head==NULL)
  
 head=n;

else
{
  
temp=head;

while(temp->next!=NULL)
  
 temp=temp->next;

  
  temp->next=n;

}

}

/*FUNCTION
FOR DELETING NODE AT SPECIFIED   POSITION*/

int
List::del_any()

{
  
 int z,flag=1;

List
*temp,*old;

cout<<“ENTER
THE ELEMENT TO BE DELETED”;

cin>>z;
temp=old=head;
while(temp!=NULL)
{
  
     

if(temp->data==z)
  
     

{
flag=0;
if(temp==head)
 head=temp->next;
else
old->next=temp->next;
  
         

delete
temp;

return(0);
  
         

}
 else
{
old=temp;
temp=temp->next;
}
  
 

}
if(flag==1)
cout<<“ELEMENT
NOT FOUND\n”;

return(0);
}
void
List::display()
//DISPLAY THE RESULT

{
List 
*temp;

  
 

if(head==NULL)
  
     

cout<<“LIST
IS EMPTY\n”;

else
{
temp=head;
while(temp!=NULL)
{
  
         

cout<<temp->data<<endl;
temp=temp->next;
}
}
}

void
main() //main()
FUNCTION STARTS

{
head=NULL;//INITIALIZATION OF HEADER
NODE

List
l; //OBJECT OF THE
CLASS List

int
x,a[20];

cout<<“ENTER
THE NO OF ELEMENTS TO BE INSERTED\n”;

cin>>x;
 cout<<“ENTER
“<<x<<“ELEMENTS\n”;

for(int
i=0;i<x;i++)

{
cin>>a[i];
l.insert_end(a[i]);
 
/*PASING THE ELEMENTS
TO THE FUNCTION THROUGH OBJECT*/

}
cout<<“THE
ELEMENTS IN THE LIST ARE\n”;

l.display();
l.del_any();
cout<<“THE
LIST IS\n”;

l.display();

/*CALLING
FUNCTION TO DISPLAY RESULT THROUGH OBJECT*/

}
//PROGRAM
ENDS

/*
OUTPUT:
ENTER
THE NO OF ELEMENTS TO BE INSERTED

5
ENTER
5ELEMENTS

1
2
3
4
5
THE
ELEMENTS IN THE LIST ARE

1
2
3
4
5
ENTER
THE ELEMENT TO BE DELETED3

THE
LIST IS

1
2
4
5
Press
any key to continue

*/

HOME

INSERTION_AT_ANYWHERE

March 27, 2008

HOME

/*PROGRAM
FOR THE INSERTION OF

 
THE ELEMENTS INTO THE LINKEDLIST  

  AT
ANYWHERE  USING SELF  REFERENTIAL  
         CLASSES*/


#include<iostream.h>
#include<stdlib.h>

class
List //NAME OF THE
CLASS

{
private:  
//DATA MEMBERS

  
 int data;

  
 List *next;

public:       
 

 
void insert_front(int);

 
void insert_anywhere(int,int);

 
void insert_end(int);//MEMBER
FUNCTIONS

 
void display();

}
*head; //OBJECT ACTS
AS NODE

void
List::insert_front(int ele)  

{        /*FUNCTION  FOR THE
INSERTING AT THE   FRONTEND */

 
List *n,*temp;

   
n=new(List);  //MEMORY
ALLOCATION

  
 n->data=ele;

  
 n->next=NULL;

 /*IF THE LIST IS EMPTY THEN
ADD 1st NODE AS HEADER NODE*/

  
 if(head==NULL)

  
     head=n;

  
 else

  
 {

  
     temp=head;

  
     n->next=temp;

  
     head=n;

  
 }

}
/*FUNCTION
DECLARATION FOR THE INSERTING AT THE END*/

void
List::insert_end(int ele)   

{

 
List *n,*temp;

   
n=new(List);//MEMORY
ALLOCATION

  
 n->data=ele;

  
 n->next=NULL;

 /*IF THE LIST IS EMPTY THEN
ADD 1st NODE AS HEADER NODE*/

  
 if(head==NULL)

  
     head=n;

  
 else

  
 {

  
 temp=head;

  
 while(temp->next!=NULL)

  
 temp=temp->next;

       
temp->next=n;

  
 }

}

/*FUNCTION
FOR THE INSERTING ELEMENTS AT ANY POSITION*/

void
List::insert_anywhere(int pos,int ele)   

{
  
 List *n,*temp;

  
 int  q=1;

  
 n=new(List);

  
 n->data=ele;

  
 n->next=NULL;

  
 temp=head;

   //GOING TO THE GIVEN
POSITION
 

  
 while(q<pos-1&&temp->next!=NULL)   &

nbsp;    
 
  
 {

  
     temp=temp->next;

  
     q++;

  
 }

//INSERTIG
THE NODE AT THE GIVEN POSITION

  
 n->next=temp->next->next;     &

nbsp;          
 
  
 temp->next=n;

}

void
List::display() //DISPLAY
THE RESULT

{
  
 List  *temp;

  
 

  
 if(head==NULL)

  
     cout<<“LIST IS
EMPTY\n”;

  
 else

  
 {

  
 temp=head;

  
 while(temp!=NULL)

  
 {

  
         

  
 cout<<temp->data<<endl;

  
 temp=temp->next;

  
 }

  
 }

}

void
main() //main()
FUNCTION STARTS

{
  
 head=NULL;//INITIALIZATION
OF HEADER NODE

  
 List l; //OBJECT
OF THE CLASS List

  
 int x,p,a[20],r;

s:
cout<<“ENTER
THE NO OF ELEMENTS TO BE INSERTED\n”;

  
 cin>>r;

  
 if(r==0)

  
 {

  
 cout<<“INVALID NUMBER TRY AGAIN”;

  
 goto s;

  
 }

  
 cout<<“ENTER
“<<r<<” ELEMENTS\n”;

  
 for(int i=0;i<r;i++)

  
 {

  
     cin>>a[i];

  
 l.insert_end(a[i]);

  
 }

cout<<“ENTER
THE POSITION OF  THE ELEMENT TO BE INSERTED”;

  
 cin>>p;

  
 if(p>r+2)

  
 {

  
 cout<<“LIST LENGTH IS ONLY “<<r;

  
 exit(0);

  
 cout<<“ENTER THE ELEMENT”;

  
 cin>>x;

  
 if(p==1)

  
 l.insert_front(x);  

else
if(p==r+1)

  
 l.insert_end(x);

else  //PASING THE ELEMENTS TO THE
FUNCTION
THROUGH OBJECT

    
l.insert_anywhere(p,x);

  
 cout<<“THE LIST IS\n”;

//CALLING FUNCTION TO DISPLAY
RESULT
THROUGH OBJECT

  
 l.display();        &nbsp

;         
 
}

//PROGRAM
ENDS

/*
OUTPUT:

ENTER
THE NO OF ELEMENTS TO BE INSERTED

4
ENTER
4 ELEMENTS

1
2
3
4
ENTER
THE POSITION OF  THE ELEMENT TO BE INSERTED

3
ENTER
THE ELEMENT

333
THE
LIST IS

1
2
333
4
Press
any key to continue

*/

HOME

INSERTION_AT_REARTEND

March 27, 2008

HOME
/*
PROGRAM FOR THE INSERTION OF THE ELEMENTS

    
INTO THE LINKEDLIST  AT THE END  USING SELF 

           

    
REFERENTIAL CLASSES   */

#include”iostream.h”

class
List //NAME OF THE
CLASS

{
private:   
//DATA MEMBERS

   
int data;

   
List *next;

public:       

   //MEMBER FUNCTIONS

  
void insert_end(int); 

   
void display();

}
*head;  //OBJECT
ACTS AS NODE

//FUNCTION
DECLARATION

void
List::insert_end(int ele)

{

 
List *n,*temp;

   
n=new(List); //MEMORY
ALLOCATION

   
n->data=ele;

   
n->next=NULL;

 /*IF THE LIST IS EMPTY THEN
ADD

           

    
1st NODE AS HEADER NODE*/
      
if(head==NULL)

   
    head=n;

   
else

   
{

   
   temp=head;

   
  while(temp->next!=NULL)

   
  temp=temp->next;

   
    temp->next=n;

   
}

}

//DISPLAY
THE RESULT

void
List::display()      
{

   
List  *temp;

   

   
if(head==NULL)

   
cout<<“LIST IS EMPTY\n”;

   
else

   
{

   
temp=head;

   
while(temp!=NULL)

   
{

   
       

   
cout<<temp->data<<endl;

   
temp=temp->next;

   
}

   
}

}

void
main() //main() FUNCTION STARTS

{
  //INITIALIZATION OF HEADER
NODE

   
head=NULL;

List
l; //OBJECT OF THE
CLASS List

   
int x,a[20];

cout<<“ENTER
THE NO OF ELEMENTS

     
TO BE INSERTED\n”;

   
cin>>x;

  
cout<<“ENTER
“<<x<<“ELEMENTS\n”;

   
for(int i=0;i<x;i++)

   
{

   
    cin>>a[i];

//PASING
THE ELEMENTS TO THE FUNCTION THROUGH OBJECT

   
l.insert_end(a[i]);

   
}

   
cout<<“THE LIST IS\n”;

//CALLING
FUNCTION TO DISPLAY RESULT THROUGH OBJECT

      
l.display();

}

//PROGRAM
ENDS

/*
OUTPUT:
ENTER
THE NO OF ELEMENTS TO

           

      
BE INSERTED
5
ENTER
5ELEMENTS

12
34
56
67
89
THE
LIST IS

12
34
56
67
89
Press
any key to continue 

*/

HOME

INSERTION_AT_FRONTEND

March 27, 2008

HOME

/*PROGRAM
FOR THE INSERTION OF THE ELEMENTS

     
INTO THE LINKEDLIST  AT THE FRONTEND 

          
USING SELF  REFERENTIAL
CLASSES     */

#include”iostream.h”


class List //NAME OF THE
CLASS

{
private:  
//DATA MEMBERS

   
int data;

   
List *next;

public:        

   
void insert_front(int); //MEMBER
FUNCTIONS

   
void display();

}
*head;  //OBJECT
ACTS AS NODE

void
List::insert_front(int ele) //FUNCTION
DECLARATION

{

 
List *n,*temp;

 n=new(List);  //MEMORY ALLOCATION

 n->data=ele;
 n->next=NULL;
/*IF
THE LIST IS EMPTY THEN ADD 1st NODE AS HEADER NODE*/

if(head==NULL)
head=n;
else
{
temp=head;
n->next=temp;
head=n;
}

}

void
List::display()
//DISPLAY THE RESULT

{
List 
*temp;

   

if(head==NULL)
cout<<“LIST
IS EMPTY\n”;

else
{
temp=head;
while(temp!=NULL)
{
   
       

cout<<temp->data<<endl;
temp=temp->next;
}
}
}

void
main() //main()
FUNCTION STARTS

{
head=NULL;
//INITIALIZATION OF
HEADER NODE

List
l;  
//OBJECT OF THE CLASS List

int
x,a[20];

cout<<“ENTER
THE NO OF ELEMENTS TO BE INSERTED\n”;

cin>>x;
cout<<“ENTER
“<<x<<” ELEMENTS\n”;

for(int
i=0;i<x;i++)

{
cin>>a[i];
//PASING
THE ELEMENTS TO THE FUNCTION THROUGH OBJECT

l.insert_front(a[i]);       

 

}
cout<<“THE
LIST IS\n”;

//CALLING
FUNCTION TO DISPLAY RESULT THROUGH OBJECT

}
l.display();      
}  

          

//PROGRAM
ENDS

/*
OUTPUT:
ENTER
THE NO OF ELEMENTS TO BE INSERTED

4
ENTER
4 ELEMENTS

1
2
3
4
THE
LIST IS

4
3
2
1
Press
any key to continue 

*/

HOME