Program to maintain a linked list

#include
#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( ) ;
}

Related Links :

No comments:

Post a Comment


If you face any Problem in viewing code such as Incomplete "For Loops" or "Incorrect greater than or smaller" than equal to signs then please collect from My Web Site CLICK HERE


More Useful Topics...

 

History Of C..

In the beginning was Charles Babbage and his Analytical Engine, a machine
he built in 1822 that could be programmed to carry out different computations.
Move forward more than 100 years, where the U.S. government in
1942 used concepts from Babbage’s engine to create the ENIAC, the first
modern computer.
Meanwhile, over at the AT&T Bell Labs, in 1972 Dennis Ritchie was working
with two languages: B (for Bell) and BCPL (Basic Combined Programming
Language). Inspired by Pascal, Mr. Ritchie developed the C programming
language.

My 1st Program...


#include
#include
void main ()
{
clrscr ();
printf ("\n\n\n\n");
printf ("\t\t\t*******Pankaj *******\n");
printf ("\t\t\t********************************\n");
printf ("\t\t\t\"Life is Good...\"\n");
printf ("\t\t\t********************************");
getch ();
}

Next Step...


#include
#include

void main ()
{
clrscr ();
printf ("\n\n\n\n\n\n\n\n");
printf ("\t\t\t --------------------------- \n\n");

printf ("\t\t\t | IGCT, Info Computers, INDIA | \n\n");
printf ("\t\t\t --------------------------- ");

getch ();

}

Hits!!!