#include
class linklist
{
private :
// structure containing a data part and link part
struct node
{
int data ;
node * link ;
} *p ;
public :
linklist( ) ;
void append ( int num ) ;
void addatbeg ( int num ) ;
void addafter ( int loc, int num ) ;
void display( ) ;
int count( ) ;
void del ( int num ) ;
~linklist( ) ;
} ;
// initializes data member
linklist :: linklist( )
{
p = NULL ;
}
// adds a node at the end of a linked list
void linklist :: append ( int num )
{
node *temp, *r ;
// if the list is empty, create first node
if ( p == NULL )
{
p = new node ;
p -> data = num ;
p -> link = NULL ;
}
else
{
// go to last node
temp = p ;
while ( temp -> link != NULL )
temp = temp -> link ;
// add node at the end
r = new node ;
r -> data = num ;
r -> link = NULL ;
temp -> link = r ;
}
}
// adds a new node at the beginning of the linked list
void linklist :: addatbeg ( int num )
{
node *temp ;
// add new node
temp = new node ;
temp -> data = num ;
temp -> link = p ;
p = temp ;
}
// adds a new node after the specified number of nodes
void linklist :: addafter ( int loc, int num )
{
node *temp, *r ;
temp = p ;
// skip to desired portion
for ( int i = 0 ; i < loc ; i++ )
{
temp = temp -> link ;
// if end of linked list is encountered
if ( temp == NULL )
{
cout << "\nThere are less than " << loc << " elements in list" << endl ;
return ;
}
}
// insert new node
r = new node ;
r -> data = num ;
r -> link = temp -> link ;
temp -> link = r ;
}
// displays the contents of the linked list
void linklist :: display( )
{
node *temp = p ;
cout << endl ;
// traverse the entire linked list
while ( temp != NULL )
{
cout << temp -> data << " " ;
temp = temp -> link ;
}
}
// counts the number of nodes present in the linked list
int linklist :: count( )
{
node *temp = p ;
int c = 0 ;
// traverse the entire linked list
while ( temp != NULL )
{
temp = temp -> link ;
c++ ;
}
return c ;
}
// deletes the specified node from the linked list
void linklist :: del ( int num )
{
node *old, *temp ;
temp = p ;
while ( temp != NULL )
{
if ( temp -> data == num )
{
// if node to be deleted is the
// first node in the linked list
if ( temp == p )
p = temp -> link ;
// deletes the intermediate nodes in the linked list
else
old -> link = temp -> link ;
// free the memory occupied by the node
delete temp ;
return ;
}
// traverse the linked list till the last node is reached
else
{
// old points to the previous node
old = temp ;
// go to the next node
temp = temp -> link ;
}
}
cout << "\n\nElement " << num << " not found" ;
}
// deallocates memory
linklist :: ~linklist( )
{
node *q ;
while ( p != NULL )
{
q = p -> link ;
delete p ;
p = q ;
}
}
void main( )
{
clrscr();
linklist l ;
l.append ( 14 ) ;
l.append ( 30 ) ;
l.append ( 25 ) ;
l.append ( 42 ) ;
l.append ( 17 ) ;
cout << "\nElements in the linked list: " ;
l.display( ) ;
l.addatbeg ( 999 ) ;
l.addatbeg ( 888 ) ;
l.addatbeg ( 777 ) ;
cout << "\n\nElements in the linked list after addition at the beginning: " ;
l.display( ) ;
l.addafter ( 7, 0 ) ;
l.addafter ( 2, 1 ) ;
l.addafter ( 5, 99 ) ;
cout << "\n\nElements in the linked list after addition at given position: " ;
l.display( ) ;
cout << "\nNo. of elements in the linked list " << l.count( ) ;
l.del ( 99 ) ;
l.del ( 1 ) ;
l.del ( 10 ) ;
cout << "\n\nElements in the linked list after deletion: " ;
l.display( ) ;
cout << "\nNo. of elements in the linked list: " << l.count( ) ;
getch();
}
===================================================================================
// Program to add a new node to the asscending order linked list.
#include
class linklist
{
private :
// structure containing a data part and link part
struct node
{
int data ;
node *link ;
} *p ;
public :
linklist( ) ;
void add ( int num ) ;
void display( ) ;
int count( ) ;
void del ( int num ) ;
~linklist( ) ;
} ;
// initializes data member
linklist :: linklist( )
{
p = NULL ;
}
// adds node to an ascending order linked list
void linklist :: add ( int num )
{
node *r, *temp = p ;
r = new node ;
r -> data = num ;
// if list is empty or if new node is to be
// inserted before the first node
if ( p == NULL || p -> data > num )
{
p = r ;
p -> link = temp ;
}
else
{
// traverse the entire linked list to search the position
// to insert the new node
while ( temp != NULL )
{
if ( temp -> data <= num && ( temp -> link -> data > num ||
temp -> link == NULL ))
{
r -> link = temp -> link ;
temp -> link = r ;
return ;
}
// go to the next node
temp = temp -> link ;
}
}
}
// displays the contents of the linked list
void linklist :: display( )
{
node *temp = p ;
cout << endl ;
// traverse the entire linked list
while ( temp != NULL )
{
cout << temp -> data << " " ;
temp = temp -> link ;
}
}
// counts the number of nodes present in the linked list
int linklist :: count( )
{
node *temp = p ;
int c = 0 ;
// traverse the entire linked list
while ( temp != NULL )
{
temp = temp -> link ;
c++ ;
}
return c ;
}
// deallocate memory
linklist :: ~linklist( )
{
node *q ;
while ( p != NULL )
{
q = p -> link ;
delete p ;
p = q ;
}
}
void main( )
{
linklist l ;
l.add ( 5 ) ;
l.add ( 1 ) ;
l.add ( 6 ) ;
l.add ( 4 ) ;
l.add ( 7 ) ;
cout << "\nElements in the linked list: " ;
l.display( ) ;
cout << "\nNo. of elements in linked list: " << l.count( ) ;
}
===================================================================================
// Program to reverse a linked list
#include
class linklist
{
private :
// structure containing a data part and link part */
struct node
{
int data ;
node *link ;
} *p;
public :
linklist( ) ;
void addatbeg ( int num ) ;
void reverse( ) ;
void display( ) ;
int count( ) ;
~linklist( ) ;
} ;
// initializes data member
linklist :: linklist( )
{
p = NULL ;
}
// adds a new node at the beginning of the linked list
void linklist :: addatbeg ( int num )
{
node *temp ;
// add new node
temp = new node ;
temp -> data = num ;
temp -> link = p ;
p = temp ;
}
// reverses the linked list
void linklist :: reverse( )
{
node *q, *r, *s ;
q = p ;
r = NULL ;
// traverse the entire linked list
while ( q != NULL )
{
s = r ;
r = q ;
q = q -> link ;
r -> link = s ;
}
p = r ;
}
// displays the contents of the linked list
void linklist :: display( )
{
node *temp = p ;
cout << endl ;
// traverse the entire linked list
while ( temp != NULL )
{
cout << temp -> data << " " ;
temp = temp -> link ;
}
}
// counts the number of nodes present in the linked list
int linklist :: count( )
{
node *temp = p ;
int c = 0 ;
// traverse the entire linked list
while ( temp != NULL )
{
temp = temp -> link ;
c++ ;
}
return c ;
}
// deallocates memory
linklist :: ~linklist( )
{
node *q ;
while ( p != NULL )
{
q = p -> link ;
delete p ;
p = q ;
}
}
void main( )
{
linklist l ;
l.addatbeg ( 7 ) ;
l.addatbeg ( 43 ) ;
l.addatbeg ( 17 ) ;
l.addatbeg ( 3 ) ;
l.addatbeg ( 23 ) ;
l.addatbeg ( 5 ) ;
cout << "\nElements in the linked list before reversing: " ;
l.display( ) ;
cout << "\nNo. of elements in the linked list: " << l.count( ) ;
l.reverse( ) ;
cout << "\n\nElements in the linked list after reversing: " ;
l.display( ) ;
cout << "\nNo. of elements in the linked list: " << l.count( ) ;
}
===================================================================================
// Program to merge two linked list, restricting commomn elements
// to occur only once
#include
class linklist
{
private :
// structure containing a data part and link part
struct node
{
int data ;
node *link ;
} *p ;
public :
linklist( ) ;
void add ( int num ) ;
void display( ) ;
int count( ) ;
void merge( linklist &l1, linklist &l2 ) ;
~linklist( ) ;
} ;
// initializes data member
linklist :: linklist( )
{
p = NULL ;
}
// adds node to an ascending order linked list
void linklist :: add ( int num )
{
node *r, *temp ;
temp = p ;
r = new node ;
r -> data = num ;
// if list is empty or if new node is to be
// inserted before the first node
if ( p == NULL || p -> data > num )
{
p = r ;
p -> link = temp ;
}
else
{
// traverse the entire linked list to search
// the position to insert the new node
while ( temp != NULL )
{
if ( temp -> data < num && ( temp -> link -> data > num ||
temp -> link == NULL ))
{
r -> link = temp -> link ;
temp -> link = r ;
return ;
}
//go to next node
temp = temp -> link ;
}
r -> link = NULL ;
temp -> link = r ;
}
}
// displays the contents of the linked list
void linklist :: display( )
{
node *temp = p ;
cout << endl ;
// traverse the entire linked list
while ( temp != NULL )
{
cout << temp -> data << " " ;
temp = temp -> link ;
}
}
// counts the number of nodes present in the linked list
int linklist :: count( )
{
node *temp = p ;
int c = 0 ;
// traverse the entire linked list
while ( temp != NULL )
{
temp = temp -> link ;
c++ ;
}
return c ;
}
// merges two linked lists, restricting the common
// elements to occur only once in the final list
void linklist :: merge ( linklist &l1, linklist&l2 )
{
node *z ;
z = NULL ;
// if both lists are empty
if ( l1.p == NULL && l2.p == NULL )
return ;
// traverse both linked lists till the end.
// If end of any one list is reached loop is terminated
while ( l1.p != NULL && l2.p != NULL )
{
// if node being added is the first node
if ( p == NULL )
{
p = new node ;
z = p ;
}
else
{
z -> link = new node ;
z = z -> link ;
}
if ( l1.p -> data < l2.p -> data )
{
z -> data = l1.p -> data ;
l1.p = l1.p -> link ;
}
else
{
if ( l2.p -> data < l1.p -> data )
{
z -> data = l2.p -> data ;
l2.p = l2.p -> link ;
}
else
{
if ( l1.p -> data == l2.p -> data )
{
z -> data = l2.p -> data ;
l1.p = l1.p -> link ;
l2.p = l2.p -> link ;
}
}
}
}
// if end of first list has not been reached
while ( l1.p != NULL )
{
z -> link = new node ;
z = z -> link ;
z -> data = l1.p -> data ;
l1.p = l1.p -> link ;
}
// if end of second list has been reached
while ( l2.p != NULL )
{
z -> link = new node ;
z = z -> link ;
z -> data = l2.p -> data ;
l2.p = l2.p -> link ;
}
z -> link = NULL ;
}
// deallocates memory
linklist :: ~linklist( )
{
node *q ;
while ( p != NULL )
{
q = p -> link ;
delete p ;
p = q ;
}
}
void main( )
{
linklist l1 ;
l1.add ( 9 ) ;
l1.add ( 12 ) ;
l1.add ( 14 ) ;
l1.add ( 17 ) ;
l1.add ( 35 ) ;
l1.add ( 61 ) ;
l1.add ( 79 ) ;
cout << "\nElements in first linked list: " ;
l1.display( ) ;
cout << "\nNo. of elements in linked list: " << l1.count( ) ;
linklist l2 ;
l2.add ( 12 ) ;
l2.add ( 17 ) ;
l2.add ( 24 ) ;
l2.add ( 36 ) ;
l2.add ( 59 ) ;
l2.add ( 64 ) ;
l2.add ( 87 ) ;
cout << "\n\nElements in second linked list: " ;
l2.display( ) ;
cout << "\nNo. of elements in linked list: " << l2.count( ) ;
linklist l3 ;
l3.merge ( l1, l2 ) ;
cout << "\n\nThe merged list: " ;
l3.display( ) ;
cout << "\nNo. of elements in the merged linked list: " << l3.count( ) ;
}
============================================================================
// Program to sort a linked list by swapping data.
#include
class linklist
{
private :
// structure containing a data part and link part
struct node
{
int data ;
node *link ;
} *p ;
public :
linklist( ) ;
void getdata( ) ;
void append ( int num ) ;
void display( ) ;
int count( ) ;
void selection_sort ( int num ) ;
void bubble_sort ( int num ) ;
~linklist( ) ;
} ;
// initializes data member
linklist :: linklist( )
{
p = NULL ;
}
// accepts data
void linklist :: getdata( )
{
int val ;
char ch ;
do
{
cout << "\nEnter a value: " ;
cin >> val ;
append ( val ) ;
cout << "\nAny More Nodes (Y/N): " ;
cin >> ch ;
} while ( ch == 'y' || ch == 'Y' ) ;
}
// adds a node at the end of a linked list
void linklist :: append ( int num )
{
node *temp ;
temp = p ;
// if the list is empty, create first node
if ( temp == NULL )
{
temp = new node ;
p = temp ;
}
else
{
// go to last node
while ( temp -> link != NULL )
temp = temp -> link ;
// add node at the end
temp -> link = new node ;
temp = temp -> link ;
}
// assign data to the last node
temp -> data = num ;
temp -> link = NULL ;
}
// displays the contents of the linked list
void linklist :: display( )
{
node *temp = p ;
cout << endl ;
// traverse the entire linked list
while ( temp != NULL )
{
cout << temp -> data << " ";
temp = temp -> link ;
}
}
// counts the number of nodes present in the linked list
int linklist :: count( )
{
node *temp = p ;
int c = 0 ;
// traverse the entire linked list
while ( temp != NULL )
{
temp = temp -> link ;
c++ ;
}
return c ;
}
// sorts list using selection sort
void linklist :: selection_sort ( int n )
{
int temp ;
node *q, *r ;
q = p ;
for ( int i = 0 ; i < n - 1 ; i++ )
{
r = q -> link ;
for ( int j = i + 1 ; j < n ; j++ )
{
if ( q -> data > r -> data )
{
temp = q -> data ;
q -> data = r -> data ;
r -> data = temp ;
}
r = r -> link ;
}
q = q -> link ;
}
}
// sort list using bubble sort
void linklist :: bubble_sort ( int n )
{
int k, temp ;
node *q, *r ;
k = n ;
for ( int i = 0 ; i < n - 1 ; i++, k-- )
{
q = p ;
r = q -> link ;
for ( int j = 1 ; j < k ; j++ )
{
if ( q -> data > r -> data )
{
temp = q -> data ;
q -> data = r -> data ;
r -> data = temp ;
}
q = q -> link ;
r = r -> link ;
}
}
}
// deallocates memory
linklist :: ~linklist( )
{
node *q ;
while ( p != NULL )
{
q = p -> link ;
delete p ;
p = q ;
}
}
void main( )
{
linklist l1 ;
l1.getdata( ) ;
cout << "\nElements in first linked list before sorting: " ;
l1.display( ) ;
int n = l1.count( ) ;
l1.selection_sort( n ) ;
cout << "\nElements in first linked list after selection sorting: " ;
l1.display( ) ;
linklist l2 ;
l2.getdata( ) ;
cout << "\n\nElements in second linked list before sorting: " ;
l2.display( ) ;
n = l2.count( ) ;
l2.bubble_sort( n ) ;
cout << "\nElements in second linked list after bubble sorting: " ;
l2.display( ) ;
}
No comments:
Post a Comment