Q. 1 Write a
program to find multiplication of a sparse matrix?
Ans.
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
#define MAX1 3
#define MAX2 3
#define MAXSIZE 20
#define TRUE 1
#define FALSE 2
struct sparse
{
int *sp ;
int row ;
int *result ;
} ;
void initsparse ( struct sparse * ) ;
void create_array ( struct sparse * ) ;
int count ( struct sparse ) ;
void display ( struct sparse ) ;
void create_tuple ( struct sparse*, struct sparse )
;
void display_tuple ( struct sparse ) ;
void prodmat ( struct sparse *, struct sparse,
struct sparse ) ;
void searchina ( int *sp, int ii, int*p, int*flag )
;
void searchinb ( int *sp, int jj, int colofa, int*p,
int*flag ) ;
void display_result ( struct sparse ) ;
void delsparse ( struct sparse * ) ;
void main( )
{
struct sparse s[5] ;
int i ;
clrscr( ) ;
for ( i = 0 ; i<= 3 ; i++ )
initsparse ( &s[i] ) ;
create_array ( &s[0] ) ;
create_tuple ( &s[1], s[0] ) ;
display_tuple ( s[1] ) ;
create_array ( &s[2] ) ;
create_tuple ( &s[3], s[2] ) ;
display_tuple ( s[3] ) ;
prodmat ( &s[4], s[1], s[3] ) ;
printf ( "\nResult of multiplication of two
matrices: " ) ;
display_result ( s[4] ) ;
for ( i = 0 ; i<= 3 ; i++ )
delsparse ( &s[i] ) ;
getch( ) ;
}
/* initialises elements of structure */
void initsparse ( struct sparse *p )
{
p -> sp = NULL ;
p -> result = NULL ;
}
/* dynamically creates the matrix */
void create_array ( struct sparse *p )
{
int n, i ;
/* allocate memory */
p -> sp = ( int * ) malloc ( MAX1 * MAX2 * sizeof
( int ) ) ;
/* add elements to the array */
for ( i = 0 ; i< MAX1 * MAX2 ; i++ )
{
printf ( "Enter element no. %d: ", i ) ;
scanf ( "%d", &n ) ;
* ( p -> sp + i ) = n ;
}
}
/* displays the contents of the matrix */
void display ( struct sparse s )
{
int i ;
/* traverses the entire matrix */
for ( i = 0 ; i< MAX1 * MAX2 ; i++ )
{
/* positions the cursor to the new line for every
new row */
if ( i % 3 == 0 )
printf ( "\n" ) ;
printf ( "%d\t", * ( s.sp + i ) ) ;
}
}
/* counts the number of non-zero elements */
int count ( struct sparse s )
{
int cnt = 0, i ;
for ( i = 0 ; i< MAX1 * MAX2 ; i++ )
{
if ( * ( s.sp + i ) != 0 )
cnt++ ;
}
return cnt ;
}
/* creates an array that stores information about
non-zero elements */
void create_tuple ( struct sparse *p, struct sparse
s )
{
int r = 0 , c = -1, l = -1, i ;
/* get the total number of non-zero elements */
p -> row = count ( s ) + 1 ;
/* allocate memory */
p -> sp = ( int * ) malloc ( p -> row * 3 *
sizeof ( int ) ) ;
/* store information about total no. of rows, cols,
and non-zero values */
* ( p -> sp + 0 ) = MAX1 ;
* ( p -> sp + 1 ) = MAX2 ;
* ( p -> sp + 2 ) = p -> row - 1 ;
l = 2 ;
/* scan the array and store info. about non-zero
values in the 3-tuple */
for ( i = 0 ; i< MAX1 * MAX2 ; i++ )
{
c++ ;
/* sets the row and column values */
if ( ( ( i % 3 ) == 0 ) && ( i != 0 ) )
{
r++ ;
c = 0 ;
}
/* checks for non-zero element, row, column and
non-zero value is assigned to the matrix */
if ( * ( s.sp + i ) != 0 )
{
l++ ;
* ( p -> sp + l ) = r ;
l++ ;
* ( p -> sp + l ) = c ;
l++ ;
* ( p -> sp + l ) = * ( s.sp + i ) ;
}
}
}
/* displays the contents of the matrix */
void display_tuple ( struct sparse s )
{
int i, j ;
/* traverses the entire matrix */
printf ( "\nElements in a 3-tuple: " ) ;
j = ( * ( s.sp + 2 ) * 3 ) + 3 ;
for ( i = 0 ; i< j ; i++ )
{
/* positions the cursor to the new line for every
new row */
if ( i % 3 == 0 )
printf ( "\n" ) ;
printf ( "%d\t", * ( s.sp + i ) ) ;
}
printf ( "\n" ) ;
}
/* performs multiplication of sparse matrices */
void prodmat ( struct sparse *p, struct sparse a,
struct sparse b )
{
int sum, k, position, posi, flaga, flagb, i , j ;
k = 1 ;
p -> result = ( int * ) malloc ( MAXSIZE * 3 *
sizeof ( int ) ) ;
for ( i = 0 ; i< * ( a.sp + 0 * 3 + 0 ) ; i++ )
{
for ( j = 0 ; j< * ( b.sp + 0 * 3 + 1 ) ; j++ )
{
/* search if an element present at ith row */
searchina ( a.sp, i, &position, &flaga ) ;
if ( flaga == TRUE )
{
sum = 0 ;
/* run loop till there are element at ith row in
first 3-tuple */
while ( * ( a.sp + position * 3 + 0 ) == i )
{
/* search if an element present at ith col. in
second 3-tuple */
searchinb ( b.sp, j, * ( a.sp + position * 3 + 1 ),
&posi, &flagb ) ;
/* if found then multiply */
if ( flagb == TRUE )
sum = sum + * ( a.sp + position * 3 + 2 ) * * ( b.sp
+ posi * 3 + 2 ) ;
position = position + 1 ;
}
/* add result */
if ( sum != 0 )
{
* ( p -> result + k * 3 + 0 ) = i ;
* ( p -> result + k * 3 + 1 ) = j ;
* ( p -> result + k * 3 + 2 ) = sum ;
k = k + 1 ;
}
}
}
}
/* add total no. of rows, cols and non-zero values
*/
* ( p -> result + 0 * 3 + 0 ) = * ( a.sp + 0 * 3
+ 0 ) ;
* ( p -> result + 0 * 3 + 1 ) = * ( b.sp + 0 * 3
+ 1 ) ;
* ( p -> result + 0 * 3 + 2 ) = k - 1 ;
}
/* searches if an element present at iith row */
void searchina ( int *sp, int ii, int *p, int *flag
)
{
int j ;
*flag = FALSE ;
for ( j = 1 ; j<= * ( sp + 0 * 3 + 2 ) ; j++ )
{
if ( * ( sp + j * 3 + 0 ) == ii )
{
*p = j ;
*flag = TRUE ;
return ;
}
}
}
/* searches if an element where col. of first
3-tuple is equal to row of second 3-tuple */
void searchinb ( int *sp, int jj, int colofa, int
*p, int *flag )
{
int j ;
*flag = FALSE ;
for ( j = 1 ; j<= * ( sp + 0 * 3 + 2 ) ; j++ )
{
if ( * ( sp + j * 3 + 1 ) == jj && * ( sp +
j * 3 + 0 ) == colofa )
{
*p = j ;
*flag = TRUE ;
return ;
}
}
}
/* displays the contents of the matrix */
void display_result ( struct sparse s )
{
int i ;
/* traverses the entire matrix */
for ( i = 0 ; i< ( * ( s.result + 0 + 2 ) + 1 ) *
3 ; i++ )
/* positions the cursor to the new line for every
new row */
if ( i % 3 == 0 )
printf ( "\n" ) ;
printf ( "%d\t", * ( s.result + i ) ) ;
}
}
/* deallocates memory */
void delsparse ( struct sparse *s )
{
if ( s -> sp != NULL )
free ( s -> sp ) ;
if ( s -> result != NULL )
free ( s -> result ) ;
}
OUTPUT
Q.2 Write a
program to transpose of Sparse Matrix?
Ans.
#include <stdio.h>
#include <conio.h>
#include <alloc.h>
#define MAX1 3
#define MAX2 3
struct sparse
{
int *sp ;
int row ;
} ;
void initsparse ( struct sparse * ) ;
void create_array ( struct sparse * ) ;
void display ( struct sparse ) ;
int count ( struct sparse ) ;
void create_tuple ( struct sparse *, struct sparse )
;
void display_tuple ( struct sparse ) ;
void transpose ( struct sparse *, struct sparse ) ;
void display_transpose ( struct sparse ) ;
void delsparse ( struct sparse * ) ;
void main( )
{
struct sparse s[3] ;
int c, i ;
for ( i = 0 ; i <= 2 ; i++ )
initsparse ( &s[i] ) ;
clrscr( ) ;
create_array ( &s[0] ) ;
printf ( "\nElements in Sparse Matrix: " )
;
display ( s[0] ) ;
c = count ( s[0] ) ;
printf ( "\n\nNumber of non-zero elements:
%d", c ) ;
create_tuple ( &s[1], s[0] ) ;
printf ( "\n\nArray of non-zero elements:
" ) ;
display_tuple ( s[1] ) ;
transpose ( &s[2], s[1] ) ;
printf ( "\n\nTranspose of array: " ) ;
display_transpose ( s[2] ) ;
for ( i = 0 ; i <= 2 ; i++ )
delsparse ( &s[i] ) ;
getch( ) ;
}
/* initialises data members */
void initsparse ( struct sparse *p )
{
p -> sp = NULL ;
}
/* dynamically creates the matrix of size MAX1 x
MAX2 */
void create_array ( struct sparse *p )
{
int n, i ;
p -> sp = ( int * ) malloc ( MAX1 * MAX2 * sizeof
( int ) ) ;
for ( i = 0 ; i
< MAX1 * MAX2 ; i++ )
{
printf ( "Enter element no. %d:", i ) ;
scanf ( "%d", &n ) ;
* ( p -> sp + i ) = n ;
}
}
/* displays the contents of the matrix */
void display ( struct sparse s )
{
int i ;
/* traverses the entire matrix */
for ( i = 0 ; i < MAX1 * MAX2 ; i++ )
{
/* positions the cursor to the new line for every
new row */
if ( i % MAX2 == 0 )
printf ( "\n" ) ;
printf ( "%d\t", * ( s.sp + i ) ) ;
}
}
/* counts the number of non-zero elements */
int count ( struct sparse s )
{
int cnt = 0, i ;
for ( i = 0 ; i < MAX1 * MAX2 ; i++ )
{
if ( * ( s.sp + i ) != 0 )
cnt++ ;
}
return cnt ;
}
/* creates an array that stores information about
non-zero elements */
void create_tuple ( struct sparse *p, struct sparse
s )
{
int r = 0 , c = -1, l = -1, i ;
p -> row = count ( s ) + 1 ;
p -> sp = ( int * ) malloc ( p -> row * 3 *
sizeof ( int ) ) ;
* ( p -> sp + 0 ) = MAX1 ;
* ( p -> sp + 1 ) = MAX2 ;
* ( p -> sp + 2 ) = p -> row - 1 ;
l = 2 ;
for ( i = 0 ; i < MAX1 * MAX2 ; i++ )
{
c++ ;
/* sets the row and column values */
if ( ( ( i % MAX2 ) == 0 ) && ( i != 0 ) )
{
r++ ;
c = 0 ;
}
/* checks for non-zero element row, column and
non-zero element value is assigned to the matrix */
if ( * ( s.sp + i ) != 0 )
{
l++ ;
* ( p -> sp + l ) = r ;
l++ ;
* ( p -> sp + l ) = c ;
l++ ;
* ( p -> sp + l ) = * ( s.sp + i ) ;
}
}
}
/* displays the contents of 3-tuple */
void display_tuple ( struct sparse p )
{
int i ;
for ( i = 0 ; i < p.row * 3 ; i++ )
{
if ( i % 3 == 0 )
printf ( "\n" ) ;
printf ( "%d\t", * ( p.sp + i ) ) ;
}
}
/* obtains transpose of an array */
void transpose ( struct sparse *p, struct sparse s )
{
int x, q, pos_1, pos_2, col, elem, c, y ;
/* allocate memory */
p -> sp = ( int * ) malloc ( s.row * 3 * sizeof (
int ) ) ;
p -> row = s.row ;
/* store total number of rows, cols and non-zero
elements */
* ( p -> sp + 0 ) = * ( s.sp + 1 ) ;
* ( p -> sp + 1 ) = * ( s.sp + 0 ) ;
* ( p -> sp + 2 ) = * ( s.sp + 2 ) ;
col = * ( p -> sp + 1 ) ;
elem = * ( p -> sp + 2 ) ;
if ( elem <= 0 )
return ;
x = 1 ;
for ( c = 0 ; c < col ; c++ )
{
for ( y = 1 ; y <= elem ; y++ )
{
q = y * 3 + 1 ;
if ( * ( s.sp + q ) == c )
{
pos_2 = x * 3 + 0 ;
pos_1 = y * 3 + 1 ;
* ( p -> sp + pos_2 ) = * ( s.sp + pos_1 ) ;
pos_2 = x * 3 + 1 ;
pos_1 = y * 3 + 0 ;
* ( p -> sp + pos_2 ) = * ( s.sp + pos_1 ) ;
pos_2 = x * 3 + 2 ;
pos_1 = y * 3 + 2 ;
* ( p -> sp + pos_2 ) = * ( s.sp + pos_1 ) ;
x++ ;
}
}
}
}
/* displays
3-tuple after transpose operation */
void display_transpose ( struct sparse p )
{
int i ;
for ( i = 0 ; i < p.row * 3 ; i++ )
{
if ( i % 3 == 0 )
printf ( "\n" ) ;
printf ( "%d\t", * ( p.sp + i ) ) ;
}
}
/* deallocates memory */
void delsparse ( struct sparse *p )
{
free ( p -> sp ) ;
}
OUTPUT
Q.3 Write a
program to implement a Binary Search Tree?
Ans.
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
struct btreenode
{
struct btreenode *leftchild;
int data;
struct btreenode *rightchild;
};
void insert(struct btreenode **, int);
void inorder(struct btreenode *);
void preorder(struct btreenode *);
void postorder(struct btreenode *);
void main()
{
struct btreenode *bt;
int req,i=1, num;
bt=NULL;
clrscr();
printf("Specify The Number Of Items To Be
Inserted: ");
scanf("%d", &req);
while(i++<=req)
{
printf("\nEnter The Data : ");
scanf("%d", &num);
insert(&bt, num);
}
printf("\n\nIn-order Traversal : ");
inorder(bt);
printf("\n\nPre-order Traversal : ");
preorder(bt);
printf("\n\nPost-order Traversal : ");
postorder(bt);
getch();
}
void insert(struct btreenode **sr, int num)
{
if(*sr==NULL)
{
*sr=malloc(sizeof(struct btreenode));
(*sr)->leftchild=NULL;
(*sr)->data=num;
sr)->rightchild=NULL;
return;
}
else
{
if(num<(*sr)->data)
insert(&((*sr)->leftchild), num);
else
insert(&((*sr)->rightchild), num);
}
return;
}
void inorder(struct btreenode *sr)
{
if(sr!=NULL)
{
inorder(sr->leftchild);
printf("%d\t", sr->data);
inorder(sr->rightchild);
}
else
return;
}
void preorder(struct btreenode *sr)
{
if(sr!=NULL)
{
printf("%d\t", sr->data);
preorder(sr->leftchild);
preorder(sr->rightchild);
}
else
return;
}
void postorder(struct btreenode *sr)
{
if(sr!=NULL)
{
postorder(sr->leftchild);
postorder(sr->rightchild);
printf("%d\t", sr->data);
}
else
return;
}
OUTPUT
Q.4
Write a program to to Delete a Node a from Binary Tree?
Ans.
#include <stdio.h>
#include <conio.h>
#include <alloc.h>
#define TRUE 1
#define FALSE 0
struct btreenode
{
struct btreenode *leftchild ;
int data ;
struct btreenode *rightchild ;
} ;
void insert ( struct btreenode **, int ) ;
void delete ( struct btreenode **, int ) ;
void search ( struct btreenode **, int, struct btreenode **, struct btreenode **, int * ) ;
void inorder ( struct btreenode * ) ;
void main( )
{
struct btreenode *bt ;
int req, i = 0, num, a[ ] = { 11, 9, 13, 8, 10, 12, 14, 15, 7 } ;
bt = NULL ; /* empty tree */
clrscr( ) ;
while ( i <= 8 )
{
insert ( &bt, a[i] ) ;
i++ ;
}
clrscr( ) ;
printf ( "Binary tree before deletion:\n" ) ;
inorder ( bt ) ;
delete ( &bt, 10 ) ;
printf ( "\nBinary tree after deletion:\n" ) ;
inorder ( bt ) ;
delete ( &bt, 14 ) ;
printf ( "\nBinary tree after deletion:\n" ) ;
inorder ( bt ) ;
delete ( &bt, 8 ) ;
printf ( "\nBinary tree after deletion:\n" ) ;
inorder ( bt ) ;
delete ( &bt, 13 ) ;
printf ( "\nBinary tree after deletion:\n" ) ;
inorder ( bt ) ;
}
/* inserts a new node in a binary search tree */
void insert ( struct btreenode **sr, int num )
{
if ( *sr == NULL )
{
*sr = malloc ( sizeof ( struct btreenode ) ) ;
( *sr ) -> leftchild = NULL ;
( *sr ) -> data = num ;
( *sr ) -> rightchild = NULL ;
}
else
#include <conio.h>
#include <alloc.h>
#define TRUE 1
#define FALSE 0
struct btreenode
{
struct btreenode *leftchild ;
int data ;
struct btreenode *rightchild ;
} ;
void insert ( struct btreenode **, int ) ;
void delete ( struct btreenode **, int ) ;
void search ( struct btreenode **, int, struct btreenode **, struct btreenode **, int * ) ;
void inorder ( struct btreenode * ) ;
void main( )
{
struct btreenode *bt ;
int req, i = 0, num, a[ ] = { 11, 9, 13, 8, 10, 12, 14, 15, 7 } ;
bt = NULL ; /* empty tree */
clrscr( ) ;
while ( i <= 8 )
{
insert ( &bt, a[i] ) ;
i++ ;
}
clrscr( ) ;
printf ( "Binary tree before deletion:\n" ) ;
inorder ( bt ) ;
delete ( &bt, 10 ) ;
printf ( "\nBinary tree after deletion:\n" ) ;
inorder ( bt ) ;
delete ( &bt, 14 ) ;
printf ( "\nBinary tree after deletion:\n" ) ;
inorder ( bt ) ;
delete ( &bt, 8 ) ;
printf ( "\nBinary tree after deletion:\n" ) ;
inorder ( bt ) ;
delete ( &bt, 13 ) ;
printf ( "\nBinary tree after deletion:\n" ) ;
inorder ( bt ) ;
}
/* inserts a new node in a binary search tree */
void insert ( struct btreenode **sr, int num )
{
if ( *sr == NULL )
{
*sr = malloc ( sizeof ( struct btreenode ) ) ;
( *sr ) -> leftchild = NULL ;
( *sr ) -> data = num ;
( *sr ) -> rightchild = NULL ;
}
else
{
if ( num < ( *sr ) -> data )
insert ( &( ( *sr ) -> leftchild ), num ) ;
else
insert ( &( ( *sr ) -> rightchild ), num ) ;
}
}
void delete ( struct btreenode **root, int num )
{
int found ;
struct btreenode *parent, *x, *xsucc ;
/* if tree is empty */
if ( *root == NULL )
{
printf ( "\nTree is empty" ) ;
return ;
}
parent = x = NULL ;
search ( root, num, &parent, &x, &found ) ;
if ( found == FALSE )
{
printf ( "\nData to be deleted, not found" ) ;
return ;
}
if ( x -> leftchild != NULL && x -> rightchild != NULL )
{
parent = x ;
xsucc = x -> rightchild ;
while ( xsucc -> leftchild != NULL )
{
parent = xsucc ;
xsucc = xsucc -> leftchild ;
}
x -> data = xsucc -> data ;
x = xsucc ;
}
if ( x -> leftchild == NULL && x -> rightchild == NULL )
{
if ( parent -> rightchild == x )
parent -> rightchild = NULL ;
else
parent -> leftchild = NULL ;
free ( x ) ;
return ;
}
if ( x -> leftchild == NULL && x -> rightchild != NULL )
{
if ( parent -> leftchild == x )
if ( num < ( *sr ) -> data )
insert ( &( ( *sr ) -> leftchild ), num ) ;
else
insert ( &( ( *sr ) -> rightchild ), num ) ;
}
}
void delete ( struct btreenode **root, int num )
{
int found ;
struct btreenode *parent, *x, *xsucc ;
/* if tree is empty */
if ( *root == NULL )
{
printf ( "\nTree is empty" ) ;
return ;
}
parent = x = NULL ;
search ( root, num, &parent, &x, &found ) ;
if ( found == FALSE )
{
printf ( "\nData to be deleted, not found" ) ;
return ;
}
if ( x -> leftchild != NULL && x -> rightchild != NULL )
{
parent = x ;
xsucc = x -> rightchild ;
while ( xsucc -> leftchild != NULL )
{
parent = xsucc ;
xsucc = xsucc -> leftchild ;
}
x -> data = xsucc -> data ;
x = xsucc ;
}
if ( x -> leftchild == NULL && x -> rightchild == NULL )
{
if ( parent -> rightchild == x )
parent -> rightchild = NULL ;
else
parent -> leftchild = NULL ;
free ( x ) ;
return ;
}
if ( x -> leftchild == NULL && x -> rightchild != NULL )
{
if ( parent -> leftchild == x )
parent -> leftchild = x -> rightchild ;
else
parent -> rightchild = x -> rightchild ;
free ( x ) ;
return ;
}
else
parent -> rightchild = x -> rightchild ;
free ( x ) ;
return ;
}
if ( x -> leftchild != NULL && x ->
rightchild == NULL )
{
if ( parent -> leftchild == x )
parent -> leftchild = x -> leftchild ;
else
parent -> rightchild = x -> leftchild ;
free ( x ) ;
return ;
}
}
void search ( struct btreenode **root, int num, struct btreenode **par, struct btreenode **x, int *found )
{
struct btreenode *q ;
q = *root ;
*found = FALSE ;
*par = NULL ;
while ( q != NULL )
{
if ( q -> data == num )
{
*found = TRUE ;
*x = q ;
return ;
}
*par = q ;
if ( q -> data > num )
q = q -> leftchild ;
else
q = q -> rightchild ;
}
}
void inorder ( struct btreenode *sr )
{
if ( sr != NULL )
{
inorder ( sr -> leftchild ) ;
printf ( "%d\t", sr -> data ) ;
inorder ( sr -> rightchild ) ;
}
}
if ( parent -> leftchild == x )
parent -> leftchild = x -> leftchild ;
else
parent -> rightchild = x -> leftchild ;
free ( x ) ;
return ;
}
}
void search ( struct btreenode **root, int num, struct btreenode **par, struct btreenode **x, int *found )
{
struct btreenode *q ;
q = *root ;
*found = FALSE ;
*par = NULL ;
while ( q != NULL )
{
if ( q -> data == num )
{
*found = TRUE ;
*x = q ;
return ;
}
*par = q ;
if ( q -> data > num )
q = q -> leftchild ;
else
q = q -> rightchild ;
}
}
void inorder ( struct btreenode *sr )
{
if ( sr != NULL )
{
inorder ( sr -> leftchild ) ;
printf ( "%d\t", sr -> data ) ;
inorder ( sr -> rightchild ) ;
}
}
OUTPUT
Q.5
Write a program to Sort a Linked List?
Ans.
#include <stdio.h>
#include <conio.h>
#include <alloc.h>
struct node
{
int data ;
struct node *link ;
} *newnode, *start, *visit ;
void getdata( ) ;
void append ( struct node **, int ) ;
void displaylist( ) ;
int count ( struct node * ) ;
void selection_sort ( int ) ;
void bubble_sort ( int ) ;
void main( )
{
int n ;
getdata( ) ;
clrscr( ) ;
printf ( "Linked List Before Sorting: " ) ;
displaylist( ) ;
n = count ( start ) ;
selection_sort ( n ) ;
printf ( "\nLinked List After Selection Sorting: " ) ;
displaylist( ) ;
getch( ) ;
getdata( ) ;
clrscr( ) ;
printf ( "Linked List Before Sorting: " ) ;
displaylist( ) ;
n = count ( start ) ;
bubble_sort ( n ) ;
printf ( "\nLinked List After Bubble Sorting: " ) ;
displaylist( ) ;
getch( ) ;
}
void getdata( )
{
int val, n ;
char ch ;
struct node *new ;
clrscr( ) ;
new = NULL ;
do
{
printf ( "\nEnter a value: " ) ;
scanf ( "%d", &val ) ;
append ( &new, val ) ;
printf ( "\nAny More Nodes (Y/N): " ) ;
ch = getche( ) ;
} while ( ch == 'y' || ch == 'Y' ) ;
start = new ;
#include <conio.h>
#include <alloc.h>
struct node
{
int data ;
struct node *link ;
} *newnode, *start, *visit ;
void getdata( ) ;
void append ( struct node **, int ) ;
void displaylist( ) ;
int count ( struct node * ) ;
void selection_sort ( int ) ;
void bubble_sort ( int ) ;
void main( )
{
int n ;
getdata( ) ;
clrscr( ) ;
printf ( "Linked List Before Sorting: " ) ;
displaylist( ) ;
n = count ( start ) ;
selection_sort ( n ) ;
printf ( "\nLinked List After Selection Sorting: " ) ;
displaylist( ) ;
getch( ) ;
getdata( ) ;
clrscr( ) ;
printf ( "Linked List Before Sorting: " ) ;
displaylist( ) ;
n = count ( start ) ;
bubble_sort ( n ) ;
printf ( "\nLinked List After Bubble Sorting: " ) ;
displaylist( ) ;
getch( ) ;
}
void getdata( )
{
int val, n ;
char ch ;
struct node *new ;
clrscr( ) ;
new = NULL ;
do
{
printf ( "\nEnter a value: " ) ;
scanf ( "%d", &val ) ;
append ( &new, val ) ;
printf ( "\nAny More Nodes (Y/N): " ) ;
ch = getche( ) ;
} while ( ch == 'y' || ch == 'Y' ) ;
start = new ;
}
void append ( struct node **q, int
num )
{
struct node *temp ;
temp = *q ;
if ( *q == NULL ) /* if the list is empty, create first node */
{
*q = malloc ( sizeof ( struct node ) ) ;
temp = *q ;
}
else
{
while ( temp -> link != NULL )
temp = temp -> link ;
temp -> link = malloc ( sizeof ( struct node ) ) ;
temp = temp -> link ;
}
temp -> data = num ;
temp -> link = NULL ;
}
void displaylist( )
{
visit = start ;
while ( visit != NULL )
{
printf ( "%d ", visit -> data ) ;
visit = visit -> link ;
}
}
int count ( struct node * q )
{
int c = 0 ;
while ( q != NULL )
{
q = q -> link ;
c++ ;
}
return c ;
}
void selection_sort ( int n )
{
int i, j, k, temp ;
struct node *p, *q ;
p = start ;
for ( i = 0 ; i < n - 1 ; i++ )
{
q = p -> link ;
for ( j = i + 1 ; j < n ; j++ )
{
if ( p -> data > q -> data )
{
temp = p -> data ;
p -> data = q -> data ;
q -> data = temp ;
}
q = q -> link ;
{
struct node *temp ;
temp = *q ;
if ( *q == NULL ) /* if the list is empty, create first node */
{
*q = malloc ( sizeof ( struct node ) ) ;
temp = *q ;
}
else
{
while ( temp -> link != NULL )
temp = temp -> link ;
temp -> link = malloc ( sizeof ( struct node ) ) ;
temp = temp -> link ;
}
temp -> data = num ;
temp -> link = NULL ;
}
void displaylist( )
{
visit = start ;
while ( visit != NULL )
{
printf ( "%d ", visit -> data ) ;
visit = visit -> link ;
}
}
int count ( struct node * q )
{
int c = 0 ;
while ( q != NULL )
{
q = q -> link ;
c++ ;
}
return c ;
}
void selection_sort ( int n )
{
int i, j, k, temp ;
struct node *p, *q ;
p = start ;
for ( i = 0 ; i < n - 1 ; i++ )
{
q = p -> link ;
for ( j = i + 1 ; j < n ; j++ )
{
if ( p -> data > q -> data )
{
temp = p -> data ;
p -> data = q -> data ;
q -> data = temp ;
}
q = q -> link ;
}
p = p -> link ;
}
}
void bubble_sort ( int n )
{
int i, j, k, temp ;
struct node *p, *q ;
k = n ;
for ( i = 0 ; i < n - 1 ; i++, k-- )
{
p = start ;
q = p -> link ;
for ( j = 1 ; j < k ; j++ )
{
if ( p -> data > q -> data )
{
temp = p -> data ;
p -> data = q -> data ;
q -> data = temp ;
}
p = p -> link ;
q = q -> link ;
}
}
}
p = p -> link ;
}
}
void bubble_sort ( int n )
{
int i, j, k, temp ;
struct node *p, *q ;
k = n ;
for ( i = 0 ; i < n - 1 ; i++, k-- )
{
p = start ;
q = p -> link ;
for ( j = 1 ; j < k ; j++ )
{
if ( p -> data > q -> data )
{
temp = p -> data ;
p -> data = q -> data ;
q -> data = temp ;
}
p = p -> link ;
q = q -> link ;
}
}
}
OUTPUT
Q.6 Write a
program to represent a Queue as an Array?
Ans.
#include<stdio.h>
#include<conio.h>
#define MAX 10
void addq(int*,int,int*,int*);
int delq(int*,int*,int*);
void main()
{
int arr[MAX];
int front=-1,rear=-1,i;
clrscr();
addq(arr,23,&front,&rear);
addq(arr,9,&front,&rear);
addq(arr,11,&front,&rear);
addq(arr,-10,&front,&rear);
addq(arr,25,&front,&rear);
addq(arr,16,&front,&rear);
addq(arr,17,&front,&rear);
addq(arr,22,&front,&rear);
addq(arr,19,&front,&rear);
addq(arr,30,&front,&rear);
addq(arr,32,&front,&rear);
i=delq(arr,&front,&rear);
printf("\nItem deleted:%d",i);
i=delq(arr,&front,&rear);
printf("\nItem deleted:%d",i);
i=delq(arr,&front,&rear);
printf("\nItem deleted:%d",i);
getch();
}
void addq(int*arr,int item,int*pfront,int*prear)
{
if(*prear==MAX-1)
{
printf("\nQueue is full.");
return;
}
(*prear)++;
arr[*prear]=item;
if(*pfront==-1)
*pfront=0;
}
int delq(int*arr,int*pfront,int*prear)
{
int data;
if(*pfront==-1)
{
printf("\nQueue is empty.");
return NULL;
}
data=arr[*pfront];
arr[*pfront]=0;
if(*pfront==*prear)
*pfront=*prear=-1;
else
(*pfront)++;
return data;
}
OUTPUT
Q.7 Write a
program to represent a Queue as a Linked List?
Ans.
#include <stdio.h>
#include <conio.h>
struct node
{
int data ;
struct node *link ;
} ;
struct queue
{
struct node *front ;
struct node *rear ;
} ;
void initqueue ( struct queue * ) ;
void addq ( struct queue *, int ) ;
int delq ( struct queue * ) ;
void delqueue ( struct queue * ) ;
void main( )
{
struct queue a ;
int i ;
clrscr( ) ;
initqueue ( &a ) ;
addq ( &a, 11 ) ;
addq ( &a, -8 ) ;
addq ( &a, 23 ) ;
addq ( &a, 19 ) ;
addq ( &a, 15 ) ;
addq ( &a, 16 ) ;
addq ( &a, 28 ) ;
i = delq ( &a ) ;
printf ( "\nItem extracted: %d", i ) ;
i = delq ( &a ) ;
printf ( "\nItem extracted: %d", i ) ;
i = delq ( &a ) ;
printf ( "\nItem extracted: %d", i ) ;
delqueue ( &a ) ;
getch( ) ;
}
/* initialises data member */
void initqueue ( struct queue *q )
{
q -> front = q -> rear = NULL ;
}
/* adds an element to the queue */
void addq ( struct queue *q, int item )
{
struct node *temp ;
temp = ( struct node * ) malloc ( sizeof ( struct
node ) ) ;
if ( temp == NULL )
printf ( "\nQueue is full." ) ;
temp -> data = item ;
temp -> link = NULL ;
if ( q -> front == NULL )
{ q -> rear = q -> front = temp ;
return ;
}
q -> rear -> link = temp ;
q -> rear = q -> rear -> link ;
}
/* removes an element from the queue */
int delq ( struct queue * q )
{
struct node *temp ;
int item ;
if ( q -> front == NULL )
{
printf ( "\nQueue is empty." ) ;
return NULL ;
}
item = q -> front -> data ;
temp = q -> front ;
q -> front = q -> front -> link ;
free ( temp ) ;
return item ;
}
/* deallocates memory */
void delqueue ( struct queue *q )
{
struct node *temp ;
if ( q -> front == NULL )
return ;
while ( q -> front != NULL )
{
temp = q -> front ;
q -> front = q -> front -> link ;
free ( temp ) ;
}
}
OUTPUT
Q.8
Write a program to Merge Linked List?
Ans.
#include <stdio.h>
#include <conio.h>
#include <alloc.h>
struct node
{
int data ;
struct node *link ;
} ;
void add ( struct node **, int ) ;
void display ( struct node * ) ;
int count ( struct node * ) ;
void merge ( struct node *, struct node *, struct node ** ) ;
void main( )
{
struct node *first, *second, *third ;
first = second = third = NULL ; /* empty linked lists */
add ( &first, 9 ) ;
add ( &first, 12 ) ;
add ( &first, 14 ) ;
add ( &first, 17 ) ;
add ( &first, 35 ) ;
add ( &first, 61 ) ;
add ( &first, 79 ) ;
clrscr( ) ;
printf ( "First linked list : " ) ;
display ( first ) ;
printf ( "\nNo. of elements in Linked List : %d" , count ( first ) ) ;
add ( &second, 12 ) ;
add ( &second, 17 ) ;
add ( &second, 24 ) ;
add ( &second, 36 ) ;
add ( &second, 59 ) ;
add ( &second, 64 ) ;
add ( &second, 87 ) ;
printf ( "\n\nSecond linked list : " ) ;
display ( second ) ;
printf ( "\nNo. of elements in Linked List : %d" , count ( second ) ) ;
merge ( first, second, &third ) ;
printf ( "\n\nThe merged list : " ) ;
display ( third ) ;
printf ( "\nNo. of elements in Linked List : %d", count ( third ) ) ;
}
void add ( struct node **q, int num )
{
struct node *r, *temp = *q ;
r = malloc ( sizeof ( struct node ) ) ;
r -> data = num ;
if ( *q == NULL || ( *q ) -> data > num )
{
*q = r ;
( *q ) -> link = temp ;
}
else
#include <conio.h>
#include <alloc.h>
struct node
{
int data ;
struct node *link ;
} ;
void add ( struct node **, int ) ;
void display ( struct node * ) ;
int count ( struct node * ) ;
void merge ( struct node *, struct node *, struct node ** ) ;
void main( )
{
struct node *first, *second, *third ;
first = second = third = NULL ; /* empty linked lists */
add ( &first, 9 ) ;
add ( &first, 12 ) ;
add ( &first, 14 ) ;
add ( &first, 17 ) ;
add ( &first, 35 ) ;
add ( &first, 61 ) ;
add ( &first, 79 ) ;
clrscr( ) ;
printf ( "First linked list : " ) ;
display ( first ) ;
printf ( "\nNo. of elements in Linked List : %d" , count ( first ) ) ;
add ( &second, 12 ) ;
add ( &second, 17 ) ;
add ( &second, 24 ) ;
add ( &second, 36 ) ;
add ( &second, 59 ) ;
add ( &second, 64 ) ;
add ( &second, 87 ) ;
printf ( "\n\nSecond linked list : " ) ;
display ( second ) ;
printf ( "\nNo. of elements in Linked List : %d" , count ( second ) ) ;
merge ( first, second, &third ) ;
printf ( "\n\nThe merged list : " ) ;
display ( third ) ;
printf ( "\nNo. of elements in Linked List : %d", count ( third ) ) ;
}
void add ( struct node **q, int num )
{
struct node *r, *temp = *q ;
r = malloc ( sizeof ( struct node ) ) ;
r -> data = num ;
if ( *q == NULL || ( *q ) -> data > num )
{
*q = r ;
( *q ) -> link = temp ;
}
else
{
while ( temp != NULL )
{
if ( temp -> data < num && ( temp -> link -> data > num || temp -> link == NULL ))
{
r -> link = temp -> link ;
temp -> link = r ;
return ;
}
temp = temp -> link ; }
r -> link = NULL ;
temp -> link = r ;
}
}
void display ( struct node *q )
{
printf ( "\n" ) ;
while ( q != NULL )
{
printf ( "%d ", q -> data ) ;
q = q -> link ;
}
}
int count ( struct node * q )
{
int c = 0 ;
while ( q != NULL )
{
q = q -> link ;
c++ ;
}
return c ;
}
void merge ( struct node *p, struct node *q, struct node **s )
{
struct node *z ;
z = NULL ;
if ( p == NULL && q == NULL )
return ;
while ( p != NULL && q != NULL )
{
if ( *s == NULL )
{ *s = malloc ( sizeof ( struct node ) ) ;
z = *s ;
}
else
{
z -> link = malloc ( sizeof ( struct node ) ) ;
z = z -> link ;
}
if ( p -> data < q -> data )
{
z -> data = p -> data ;
p = p -> link ;
}
while ( temp != NULL )
{
if ( temp -> data < num && ( temp -> link -> data > num || temp -> link == NULL ))
{
r -> link = temp -> link ;
temp -> link = r ;
return ;
}
temp = temp -> link ; }
r -> link = NULL ;
temp -> link = r ;
}
}
void display ( struct node *q )
{
printf ( "\n" ) ;
while ( q != NULL )
{
printf ( "%d ", q -> data ) ;
q = q -> link ;
}
}
int count ( struct node * q )
{
int c = 0 ;
while ( q != NULL )
{
q = q -> link ;
c++ ;
}
return c ;
}
void merge ( struct node *p, struct node *q, struct node **s )
{
struct node *z ;
z = NULL ;
if ( p == NULL && q == NULL )
return ;
while ( p != NULL && q != NULL )
{
if ( *s == NULL )
{ *s = malloc ( sizeof ( struct node ) ) ;
z = *s ;
}
else
{
z -> link = malloc ( sizeof ( struct node ) ) ;
z = z -> link ;
}
if ( p -> data < q -> data )
{
z -> data = p -> data ;
p = p -> link ;
}
else
{
if ( q -> data < p -> data )
{
z -> data = q -> data ;
q = q -> link ;
}
else
{
if ( p -> data == q -> data )
{
z -> data = q -> data ;
p = p -> link ;
q = q -> link ;
}
}
}
}
while ( p != NULL )
{
z -> link = malloc ( sizeof ( struct node ) ) ;
z = z -> link ;
z -> data = p -> data ;
p = p -> link ;
}
while ( q != NULL )
{
z -> link = malloc ( sizeof ( struct node ) ) ;
z = z -> link ;
z -> data = q -> data ;
q = q -> link ;
}
z -> link = NULL ;
}
{
if ( q -> data < p -> data )
{
z -> data = q -> data ;
q = q -> link ;
}
else
{
if ( p -> data == q -> data )
{
z -> data = q -> data ;
p = p -> link ;
q = q -> link ;
}
}
}
}
while ( p != NULL )
{
z -> link = malloc ( sizeof ( struct node ) ) ;
z = z -> link ;
z -> data = p -> data ;
p = p -> link ;
}
while ( q != NULL )
{
z -> link = malloc ( sizeof ( struct node ) ) ;
z = z -> link ;
z -> data = q -> data ;
q = q -> link ;
}
z -> link = NULL ;
}
OUTPUT
Q.9
Write a program to implement Circular
Linked List?
Ans.
#include <stdio.h>
#include <conio.h>
#include <alloc.h>
struct node
{
int data ;
struct node * link ;
} ;
void addcirq ( struct node **, struct node **, int ) ;
int delcirq ( struct node **, struct node ** ) ;
void cirq_display ( struct node * ) ;
void main( )
{
struct node *front, *rear ;
front = rear = NULL ;
addcirq ( &front, &rear, 10 ) ;
addcirq ( &front, &rear, 17 ) ;
addcirq ( &front, &rear, 18 ) ;
addcirq ( &front, &rear, 5 ) ;
addcirq ( &front, &rear, 30 ) ;
addcirq ( &front, &rear, 15 ) ;
clrscr( ) ;
printf ( "Before deletion:\n" ) ;
cirq_display ( front ) ;
delcirq ( &front, &rear ) ;
delcirq ( &front, &rear ) ;
delcirq ( &front, &rear ) ;
printf ( "\n\nAfter deletion:\n" ) ;
cirq_display ( front ) ;
}
void addcirq ( struct node **f, struct node **r, int item )
{
struct node *q ;
q = malloc ( sizeof ( struct node ) ) ;
q -> data = item ;
if ( *f == NULL )
*f = q ;
else
( *r ) -> link = q ;
*r = q ;
( *r ) -> link = *f ;
}
/* removes an element from front of queue */
int delcirq ( struct node **f, struct node **r )
{
struct node *q ;
int item ;
if ( *f == NULL )
#include <conio.h>
#include <alloc.h>
struct node
{
int data ;
struct node * link ;
} ;
void addcirq ( struct node **, struct node **, int ) ;
int delcirq ( struct node **, struct node ** ) ;
void cirq_display ( struct node * ) ;
void main( )
{
struct node *front, *rear ;
front = rear = NULL ;
addcirq ( &front, &rear, 10 ) ;
addcirq ( &front, &rear, 17 ) ;
addcirq ( &front, &rear, 18 ) ;
addcirq ( &front, &rear, 5 ) ;
addcirq ( &front, &rear, 30 ) ;
addcirq ( &front, &rear, 15 ) ;
clrscr( ) ;
printf ( "Before deletion:\n" ) ;
cirq_display ( front ) ;
delcirq ( &front, &rear ) ;
delcirq ( &front, &rear ) ;
delcirq ( &front, &rear ) ;
printf ( "\n\nAfter deletion:\n" ) ;
cirq_display ( front ) ;
}
void addcirq ( struct node **f, struct node **r, int item )
{
struct node *q ;
q = malloc ( sizeof ( struct node ) ) ;
q -> data = item ;
if ( *f == NULL )
*f = q ;
else
( *r ) -> link = q ;
*r = q ;
( *r ) -> link = *f ;
}
/* removes an element from front of queue */
int delcirq ( struct node **f, struct node **r )
{
struct node *q ;
int item ;
if ( *f == NULL )
printf ( "queue is empty"
) ;
else
{
if ( *f == *r )
{
else
{
if ( *f == *r )
{
item = ( *f ) -> data ;
free ( *f ) ;
*f = NULL ;
*r = NULL ;
}
else
{
q = *f ;
item = q -> data ;
*f = ( *f ) -> link ;
( *r ) -> link = *f ;
free ( q ) ;
}
return ( item ) ;
}
return NULL ;
}
void cirq_display ( struct node *f )
{
struct node *q = f, *p = NULL ;
while ( q != p )
{
printf ( "%d\t", q -> data ) ;
q = q -> link ;
p = f ;
}
}
free ( *f ) ;
*f = NULL ;
*r = NULL ;
}
else
{
q = *f ;
item = q -> data ;
*f = ( *f ) -> link ;
( *r ) -> link = *f ;
free ( q ) ;
}
return ( item ) ;
}
return NULL ;
}
void cirq_display ( struct node *f )
{
struct node *q = f, *p = NULL ;
while ( q != p )
{
printf ( "%d\t", q -> data ) ;
q = q -> link ;
p = f ;
}
}
OUTPUT
Q.10 Write a program to implement Ascending order Linked
List?
Ans.
#include <stdio.h>
#include <conio.h>
#include <alloc.h>
struct node
{
int data ;
struct node *link ;
} ;
void add ( struct node **, int ) ;
void display ( struct node * ) ;
int count ( struct node * ) ;
void delete ( struct node **, int ) ;
void main( )
{
struct node *p ;
p = NULL ;
add ( &p, 5 ) ;
add ( &p, 1 ) ;
add ( &p, 6 ) ;
add ( &p, 4 ) ;
add ( &p, 7 ) ;
clrscr( ) ;
display ( p ) ;
printf ( "\nNo. of elements in Linked List = %d", count ( p ) ) ;
}
void add ( struct node **q, int num )
{
struct node *r, *temp = *q ;
r = malloc ( sizeof ( struct node ) ) ;
r -> data = num ;
if ( *q == NULL || ( *q ) -> data > num )
{
*q = r ;
( *q ) -> link = temp ;
}
else
{
while ( temp != NULL )
{
if ( temp -> data <= num && ( temp -> link -> data > num || temp -> link == NULL ))
{
r -> link = temp -> link ;
temp -> link = r ;
return ;
}
temp = temp -> link ;
}
#include <conio.h>
#include <alloc.h>
struct node
{
int data ;
struct node *link ;
} ;
void add ( struct node **, int ) ;
void display ( struct node * ) ;
int count ( struct node * ) ;
void delete ( struct node **, int ) ;
void main( )
{
struct node *p ;
p = NULL ;
add ( &p, 5 ) ;
add ( &p, 1 ) ;
add ( &p, 6 ) ;
add ( &p, 4 ) ;
add ( &p, 7 ) ;
clrscr( ) ;
display ( p ) ;
printf ( "\nNo. of elements in Linked List = %d", count ( p ) ) ;
}
void add ( struct node **q, int num )
{
struct node *r, *temp = *q ;
r = malloc ( sizeof ( struct node ) ) ;
r -> data = num ;
if ( *q == NULL || ( *q ) -> data > num )
{
*q = r ;
( *q ) -> link = temp ;
}
else
{
while ( temp != NULL )
{
if ( temp -> data <= num && ( temp -> link -> data > num || temp -> link == NULL ))
{
r -> link = temp -> link ;
temp -> link = r ;
return ;
}
temp = temp -> link ;
}
}
}
void display ( struct node *q )
void display ( struct node *q )
{
printf ( "\n" ) ;
while ( q != NULL )
{
printf ( "%d ", q -> data ) ;
q = q -> link ;
}
}
int count ( struct node *q )
{
int c = 0 ;
while ( q != NULL )
{
q = q -> link ;
c++ ;
}
return c ;
}
printf ( "\n" ) ;
while ( q != NULL )
{
printf ( "%d ", q -> data ) ;
q = q -> link ;
}
}
int count ( struct node *q )
{
int c = 0 ;
while ( q != NULL )
{
q = q -> link ;
c++ ;
}
return c ;
}
OUTPUT
Q.11 Write a program to implement a Double Linked
List?
Ans.
#include <stdio.h>
#include <conio.h>
#include <alloc.h>
struct dnode
{
struct dnode *prev ;
int data ;
struct dnode * next ;
} ;
void d_append ( struct dnode **, int ) ;
void d_addatbeg ( struct dnode **, int ) ;
void d_addafter ( struct dnode *, int , int ) ;
void d_display ( struct dnode * ) ;
int d_count ( struct dnode * ) ;
void d_delete ( struct dnode **, int ) ;
void main( )
{
struct dnode *p ;
p = NULL ; /* empty doubly linked list */
d_append ( &p , 11 ) ;
d_append ( &p , 2 ) ;
d_append ( &p , 14 ) ;
d_append ( &p , 17 ) ;
d_append ( &p , 99 ) ;
clrscr( ) ;
d_display ( p ) ;
printf ( "\nNo. of elements in the DLL = %d\n", d_count ( p ) ) ;
d_addatbeg ( &p, 33 ) ;
d_addatbeg ( &p, 55 ) ;
d_display ( p ) ;
printf ( "\nNo. of elements in the DLL = %d\n", d_count ( p ) ) ;
d_addafter ( p, 4, 66 ) ;
d_addafter ( p, 2, 96 ) ;
d_display ( p ) ;
printf ( "\nNo. of elements in the DLL = %d\n", d_count ( p ) ) ;
d_delete ( &p, 55 ) ;
d_delete ( &p, 2 ) ;
d_delete ( &p, 99 ) ;
d_display ( p ) ;
printf ( "\nNo. of elements in the DLL = %d\n", d_count ( p ) ) ;
}
void d_append ( struct dnode **s, int num )
{
struct dnode *r, *q = *s ;
if ( *s == NULL )
{
*s = malloc ( sizeof ( struct dnode ) ) ;
( *s ) -> prev = NULL ;
( *s ) -> data = num ;
( *s ) -> next = NULL ;
}
else
{
#include <conio.h>
#include <alloc.h>
struct dnode
{
struct dnode *prev ;
int data ;
struct dnode * next ;
} ;
void d_append ( struct dnode **, int ) ;
void d_addatbeg ( struct dnode **, int ) ;
void d_addafter ( struct dnode *, int , int ) ;
void d_display ( struct dnode * ) ;
int d_count ( struct dnode * ) ;
void d_delete ( struct dnode **, int ) ;
void main( )
{
struct dnode *p ;
p = NULL ; /* empty doubly linked list */
d_append ( &p , 11 ) ;
d_append ( &p , 2 ) ;
d_append ( &p , 14 ) ;
d_append ( &p , 17 ) ;
d_append ( &p , 99 ) ;
clrscr( ) ;
d_display ( p ) ;
printf ( "\nNo. of elements in the DLL = %d\n", d_count ( p ) ) ;
d_addatbeg ( &p, 33 ) ;
d_addatbeg ( &p, 55 ) ;
d_display ( p ) ;
printf ( "\nNo. of elements in the DLL = %d\n", d_count ( p ) ) ;
d_addafter ( p, 4, 66 ) ;
d_addafter ( p, 2, 96 ) ;
d_display ( p ) ;
printf ( "\nNo. of elements in the DLL = %d\n", d_count ( p ) ) ;
d_delete ( &p, 55 ) ;
d_delete ( &p, 2 ) ;
d_delete ( &p, 99 ) ;
d_display ( p ) ;
printf ( "\nNo. of elements in the DLL = %d\n", d_count ( p ) ) ;
}
void d_append ( struct dnode **s, int num )
{
struct dnode *r, *q = *s ;
if ( *s == NULL )
{
*s = malloc ( sizeof ( struct dnode ) ) ;
( *s ) -> prev = NULL ;
( *s ) -> data = num ;
( *s ) -> next = NULL ;
}
else
{
while ( q -> next !=
NULL )
q = q -> next ;
r = malloc ( sizeof ( struct dnode ) ) ;
r -> data = num ;
r -> next = NULL ;
r -> prev = q ;
q -> next = r ;
}
}
void d_addatbeg ( struct dnode **s, int num )
{
struct dnode *q ;
q = malloc ( sizeof ( struct dnode ) ) ;
q -> prev = NULL ;
q -> data = num ;
q -> next = *s ;
( *s ) -> prev = q ;
*s = q ;
}
void d_addafter ( struct dnode *q, int loc, int num )
{
struct dnode *temp ;
int i ;
for ( i = 0 ; i < loc ; i++ )
{
q = q -> next ;
if ( q == NULL )
{ printf ( "\nThere are less than %d elements", loc );
return ;
}
}
q = q -> prev ;
temp = malloc ( sizeof ( struct dnode ) ) ;
temp -> data = num ;
temp -> prev = q ;
temp -> next = q -> next ;
temp -> next -> prev = temp ;
q -> next = temp ;
}
void d_display ( struct dnode *q )
{
printf ( "\n" ) ;
while ( q != NULL )
{
printf ( "%2d\t", q -> data ) ;
q = q -> next ;
}
}
int d_count ( struct dnode * q )
{
int c = 0 ;
while ( q != NULL )
{
q = q -> next ;
q = q -> next ;
r = malloc ( sizeof ( struct dnode ) ) ;
r -> data = num ;
r -> next = NULL ;
r -> prev = q ;
q -> next = r ;
}
}
void d_addatbeg ( struct dnode **s, int num )
{
struct dnode *q ;
q = malloc ( sizeof ( struct dnode ) ) ;
q -> prev = NULL ;
q -> data = num ;
q -> next = *s ;
( *s ) -> prev = q ;
*s = q ;
}
void d_addafter ( struct dnode *q, int loc, int num )
{
struct dnode *temp ;
int i ;
for ( i = 0 ; i < loc ; i++ )
{
q = q -> next ;
if ( q == NULL )
{ printf ( "\nThere are less than %d elements", loc );
return ;
}
}
q = q -> prev ;
temp = malloc ( sizeof ( struct dnode ) ) ;
temp -> data = num ;
temp -> prev = q ;
temp -> next = q -> next ;
temp -> next -> prev = temp ;
q -> next = temp ;
}
void d_display ( struct dnode *q )
{
printf ( "\n" ) ;
while ( q != NULL )
{
printf ( "%2d\t", q -> data ) ;
q = q -> next ;
}
}
int d_count ( struct dnode * q )
{
int c = 0 ;
while ( q != NULL )
{
q = q -> next ;
c++ ;
}
return c ;
}
void d_delete ( struct dnode **s, int num )
{
struct dnode *q = *s ;
while ( q != NULL )
{
if ( q -> data == num )
{
if ( q == *s )
{
*s = ( *s ) -> next ;
( *s ) -> prev = NULL ;
}
else
{
if ( q -> next == NULL )
q -> prev -> next = NULL ;
else
{
q -> prev -> next = q -> next ;
q -> next -> prev = q -> prev ;
}
free ( q ) ;
}
return ;
}
q = q -> next ;
}
printf ( "\n%d not found.", num ) ;
}
return c ;
}
void d_delete ( struct dnode **s, int num )
{
struct dnode *q = *s ;
while ( q != NULL )
{
if ( q -> data == num )
{
if ( q == *s )
{
*s = ( *s ) -> next ;
( *s ) -> prev = NULL ;
}
else
{
if ( q -> next == NULL )
q -> prev -> next = NULL ;
else
{
q -> prev -> next = q -> next ;
q -> next -> prev = q -> prev ;
}
free ( q ) ;
}
return ;
}
q = q -> next ;
}
printf ( "\n%d not found.", num ) ;
}
OUTPUT
Q.12
Write a program to Delete a Value from a B-Tree?
Ans.
#include
<stdio.h>
#include
<conio.h>
#include
<stdlib.h>
#include
<alloc.h>
#define MAX 4
#define MIN 2
struct btnode
{
int count ;
int value[MAX +
1] ;
struct btnode
*child[MAX + 1] ;
} ;
struct btnode *
insert ( int, struct btnode * ) ;
int setval (
int, struct btnode *, int *, struct btnode ** ) ;
struct btnode *
search ( int, struct btnode *, int * ) ;
int searchnode (
int, struct btnode *, int * ) ;
void fillnode (
int, struct btnode *, struct btnode *, int ) ;
void split (
int, struct btnode *, struct btnode *,int, int *, struct btnode ** ) ;
struct btnode *
delete ( int, struct btnode * ) ;
int delhelp (
int, struct btnode * ) ;
void clear (
struct btnode *, int ) ;
void copysucc (
struct btnode *, int ) ;
void restore (
struct btnode *, int ) ;
void rightshift
( struct btnode *, int ) ;
void leftshift (
struct btnode *, int ) ;
void merge (
struct btnode *, int ) ;
void display (
struct btnode * ) ;
void main( )
{
struct node
*root ;
root = NULL ;
clrscr( ) ;
root = insert (
27, root ) ;
root = insert (
42, root ) ;
root = insert (
22, root ) ;
root = insert (
47, root ) ;
root = insert (
32, root ) ;
root = insert (
2, root ) ;
root = insert (
51, root ) ;
root = insert (
40, root ) ;
root = insert (
13, root ) ;
printf (
"B-tree of order 5:\n" ) ;
display ( root )
;
root = delete (
22, root ) ;
root = delete (
11, root ) ;
printf (
"\n\nAfter deletion of values:\n" ) ;
display ( root )
;
getch( ) ;
}
struct btnode *
insert ( int val, struct btnode *root )
{
int i ;
struct btnode
*c, *n ;
int flag ;
flag = setval (
val, root, &i, &c ) ;
if ( flag )
{
n = ( struct
btnode * ) malloc ( sizeof ( struct btnode ) ) ;
n -> count =
1 ;
n -> value
[1] = i ;
n -> child
[0] = root ;
n -> child
[1] = c ;
return n ;
}
return root ;
}
int setval ( int
val, struct btnode *n, int *p, struct btnode **c )
{
int k ;
if ( n == NULL )
{
*p = val ;
*c = NULL ;
return 1 ;
}
else
{
if ( searchnode
( val, n, &k ) )
printf (
"\nKey value already exists.\n" ) ;
if ( setval (
val, n -> child [k], p, c ) )
{
if ( n ->
count < MAX )
{
fillnode ( *p,
*c, n, k ) ;
return 0 ;
}
else
{
split ( *p, *c,
n, k, p, c ) ;
return 1 ;
}
}
return 0 ;
}
}
struct btnode *
search ( int val, struct btnode *root, int *pos )
{
if ( root ==
NULL )
return NULL ;
else
{
if ( searchnode
( val, root, pos ) )
return root ;
else
return search (
val, root -> child [*pos], pos ) ;
}
}
int searchnode (
int val, struct btnode *n, int *pos )
{
if ( val < n
-> value [1] )
{
*pos = 0 ;
return 0 ;
}
else
{
*pos = n ->
count ;
while ( ( val
< n -> value [*pos] ) && *pos > 1 )
( *pos )-- ;
if ( val == n
-> value [*pos] )
return 1 ;
else
return 0 ;
}
}
void fillnode (
int val, struct btnode *c, struct btnode *n, int k )
{
int i ;
for ( i = n
-> count ; i > k ; i-- )
{
n -> value [i
+ 1] = n -> value [i] ;
n -> child [i
+ 1] = n -> child [i] ;
}
n -> value [k
+ 1] = val ;
n -> child [k
+ 1] = c ;
n -> count++
;
}
void split ( int
val, struct btnode *c, struct btnode *n,int k, int *y, struct btnode **newnode
)
{
int i, mid ;
if ( k <= MIN
)
mid = MIN ;
else
mid = MIN + 1 ;
*newnode = (
struct btnode * ) malloc ( sizeof ( struct btnode ) ) ;
for ( i = mid +
1 ; i <= MAX ; i++ )
{
( *newnode )
-> value [i - mid] = n -> value [i] ;
( *newnode ) ->
child [i - mid] = n -> child [i] ;
}
( *newnode )
-> count = MAX - mid ;
n -> count =
mid ;
if ( k <= MIN
)
fillnode ( val,
c, n, k ) ;
else
fillnode ( val,
c, *newnode, k - mid ) ;
*y = n ->
value [n -> count] ;
( *newnode )
-> child [0] = n -> child [n -> count] ;
n -> count--
;
}
struct btnode *
delete ( int val, struct btnode *root )
{
struct btnode *
temp ;
if ( ! delhelp (
val, root ) )
printf (
"\nValue %d not found.", val ) ;
else
{
if ( root ->
count == 0 )
{
temp = root ;
root = root
-> child [0] ;
free ( temp ) ;
}
}
return root ;
}
int delhelp (
int val, struct btnode *root )
{
int i ;
int flag ;
if ( root ==
NULL )
return 0 ;
else
{
flag =
searchnode ( val, root, &i ) ;
if ( flag )
{
if ( root ->
child [i - 1] )
{
copysucc ( root,
i ) ;
flag = delhelp (
root -> value [i], root -> child [i] ) ;
if ( !flag )
printf (
"\nValue %d not found.", val ) ;
}
else
clear ( root, i
) ;
}
else
flag = delhelp (
val, root -> child [i] ) ;
if ( root ->
child [i] != NULL )
{
if ( root ->
child [i] -> count < MIN )
restore ( root,
i ) ;
}
return flag ;
}
}
void clear (
struct btnode *node, int k )
{
int i ;
for ( i = k + 1
; i <= node -> count ; i++ )
{
node -> value
[i - 1] = node -> value [i] ;
node -> child
[i - 1] = node -> child [i] ;
}
node ->
count-- ;
}
void copysucc (
struct btnode *node, int i )
{
struct btnode
*temp ;
temp = node
-> child [i] ;
while ( temp
-> child[0] )
temp = temp
-> child [0] ;
node -> value
[i] = temp -> value [1] ;
}
void restore (
struct btnode *node, int i )
{
if ( i == 0 )
{
if ( node ->
child [1] -> count > MIN )
leftshift (
node, 1 ) ;
else
merge ( node, 1
) ;
}
else
{
if ( i == node
-> count )
{
if ( node ->
child [i - 1] -> count > MIN )
rightshift (
node, i ) ;
else
merge ( node, i
) ;
}
else
{
if ( node ->
child [i - 1] -> count > MIN )
rightshift (
node, i ) ;
else
{
if ( node ->
child [i + 1] -> count > MIN )
leftshift (
node, i + 1 ) ;
else
merge ( node, i
) ;
}
}
}
}
void rightshift
( struct btnode *node, int k )
{
int i ;
struct btnode
*temp ;
temp = node
-> child [k] ;
for ( i = temp
-> count ; i > 0 ; i-- )
{
temp -> value
[i + 1] = temp -> value [i] ;
temp -> child
[i + 1] = temp -> child [i] ;
}
temp -> child
[1] = temp -> child [0] ;
temp ->
count++ ;
temp -> value
[1] = node -> value [k] ;
temp = node
-> child [k - 1] ;
node -> value
[k] = temp -> value [temp -> count] ;
node -> child
[k] -> child [0] = temp -> child [temp -> count] ;
temp ->
count-- ;
}
void leftshift (
struct btnode *node, int k )
{
int i ;
struct btnode
*temp ;
temp = node
-> child [k - 1] ;
temp ->
count++ ;
temp -> value
[temp -> count] = node -> value [k] ;
temp -> child
[temp -> count] = node -> child [k] -> child [0] ;
temp = node
-> child [k] ;
node -> value
[k] = temp -> value [1] ;
temp -> child
[0] = temp -> child [1] ;
temp ->
count-- ;
for ( i = 1 ; i
<= temp -> count ; i++ )
{
temp -> value
[i] = temp -> value [i + 1] ;
temp -> child
[i] = temp -> child [i + 1] ;
}
}
void merge (
struct btnode *node, int k )
{
int i ;
struct btnode
*temp1, *temp2 ;
temp1 = node
-> child [k] ;
temp2 = node
-> child [k - 1] ;
temp2 ->
count++ ;
temp2 ->
value [temp2 -> count] = node -> value [k] ;
temp2 ->
child [temp2 -> count] = node -> child [0] ;
for ( i = 1 ; i
<= temp1 -> count ; i++ )
{
temp2 ->
count++ ;
temp2 -> value
[temp2 -> count] = temp1 -> value [i] ;
temp2 ->
child [temp2 -> count] = temp1 -> child [i] ;
}
for ( i = k ; i
< node -> count ; i++ )
{
node -> value
[i] = node -> value [i + 1] ;
node -> child
[i] = node -> child [i + 1] ;
}
node ->
count-- ;
free ( temp1 ) ;
}
void display (
struct btnode *root )
{
int i ;
if ( root !=
NULL )
{
for ( i = 0 ; i
< root -> count ; i++ )
{
display ( root
-> child [i] ) ;
printf (
"%d\t", root -> value [i + 1] ) ;
}
display ( root
-> child [i] ) ;
}
}
OUTPUT
Q.13
Write a program to Delete a Node from AVL tree?
Ans.
#include
<stdio.h>
#include
<conio.h>
#include
<alloc.h>
#define FALSE 0
#define TRUE 1
struct AVLNode
{
int data ;
int balfact ;
struct AVLNode
*left ;
struct AVLNode
*right ;
} ;
struct AVLNode *
buildtree ( struct AVLNode *, int, int * ) ;
struct AVLNode *
deldata ( struct AVLNode *, int, int * ) ;
struct AVLNode *
del ( struct AVLNode *, struct AVLNode *, int * ) ;
struct AVLNode *
balright ( struct AVLNode *, int * ) ;
struct AVLNode *
balleft ( struct AVLNode *, int * ) ;
void display (
struct AVLNode * ) ;
void deltree (
struct AVLNode * ) ;
void main( )
{
struct AVLNode
*avl = NULL ;
int h ;
clrscr( ) ;
avl = buildtree
( avl, 20, &h ) ;
avl = buildtree
( avl, 6, &h ) ;
avl = buildtree
( avl, 29, &h ) ;
avl = buildtree
( avl, 5, &h ) ;
avl = buildtree
( avl, 12, &h ) ;
avl = buildtree
( avl, 25, &h ) ;
avl = buildtree
( avl, 32, &h ) ;
avl = buildtree
( avl, 10, &h ) ;
avl = buildtree
( avl, 15, &h ) ;
avl = buildtree
( avl, 27, &h ) ;
avl = buildtree
( avl, 13, &h ) ;
printf (
"\nAVL tree:\n" ) ;
display ( avl )
;
avl = deldata (
avl, 20, &h ) ;
avl = deldata (
avl, 12, &h ) ;
printf (
"\nAVL tree after deletion of a node:\n" ) ;
display ( avl )
;
deltree ( avl )
;
getch( ) ;
}
struct AVLNode *
buildtree ( struct AVLNode *root, int data, int *h )
{
struct AVLNode
*node1, *node2 ;
if ( !root )
{
root = ( struct
AVLNode * ) malloc ( sizeof ( struct AVLNode ) ) ;
root -> data
= data ;
root -> left
= NULL ;
root -> right
= NULL ;
root ->
balfact = 0 ;
*h = TRUE ;
return ( root )
;
}
if ( data <
root -> data )
{
root -> left
= buildtree ( root -> left, data, h ) ;
if ( *h )
{
switch ( root
-> balfact )
{
case 1:
node1 = root
-> left ;
if ( node1 ->
balfact == 1 )
{
printf (
"\nRight rotation along %d.", root -> data ) ;
root -> left
= node1 -> right ;
node1 ->
right = root ;
root ->
balfact = 0 ;
root = node1 ;
}
else
{
printf (
"\nDouble rotation, left along %d", node1 -> data ) ;
node2 = node1
-> right ;
node1 ->
right = node2 -> left ;
printf ( " then
right along %d.\n", root -> data ) ;
node2 -> left
= node1 ;
root -> left
= node2 -> right ;
node2 ->
right = root ;
if ( node2 ->
balfact == 1 )
root ->
balfact = -1 ;
else
root ->
balfact = 0 ;
if ( node2 ->
balfact == -1 )
node1 ->
balfact = 1 ;
else
node1 ->
balfact = 0 ;
root = node2 ;
}
root ->
balfact = 0 ;
*h = FALSE ;
break ;
case 0:
root ->
balfact = 1 ;
break ;
case -1:
root ->
balfact = 0 ;
*h = FALSE ;
}
}
}
if ( data >
root -> data )
{
root -> right
= buildtree ( root -> right, data, h ) ;
if ( *h )
{
switch ( root
-> balfact )
{
case 1:
root ->
balfact = 0 ;
*h = FALSE ;
break ;
case 0:
root ->
balfact = -1 ;
break;
case -1:
node1 = root
-> right ;
if ( node1 ->
balfact == -1 )
{
printf (
"\nLeft rotation along %d.", root -> data ) ;
root -> right
= node1 -> left ;
node1 -> left
= root ;
root ->
balfact = 0 ;
root = node1 ;
}
else
{
printf (
"\nDouble rotation, right along %d", node1 -> data ) ;
node2 = node1
-> left ;
node1 -> left
= node2 -> right ;
node2 ->
right = node1 ;
printf ( "
then left along %d.\n", root -> data ) ;
root -> right
= node2 -> left ;
node2 -> left
= root ;
if ( node2 ->
balfact == -1 )
root ->
balfact = 1 ;
else
root ->
balfact = 0 ;
if ( node2 ->
balfact == 1 )
node1 ->
balfact = -1 ;
else
node1 ->
balfact = 0 ;
root = node2 ;
}
root ->
balfact = 0 ;
*h = FALSE ;
}
}
}
return ( root )
;
}
struct AVLNode *
deldata ( struct AVLNode *root, int data, int *h )
{
struct AVLNode
*node ;
if ( !root )
{
printf (
"\nNo such data." ) ;
return ( root )
;
}
else
{
if ( data <
root -> data )
{
root -> left
= deldata ( root -> left, data, h ) ;
if ( *h )
root = balright
( root, h ) ;
}
else
{
if ( data >
root -> data )
{
root -> right
= deldata ( root -> right, data, h ) ;
if ( *h )
root = balleft (
root, h ) ;
}
else
{
node = root ;
if ( node ->
right == NULL )
{
root = node
-> left ;
*h = TRUE ;
free ( node ) ;
}
else
{
if ( node ->
left == NULL )
{
root = node
-> right ;
*h = TRUE ;
free ( node ) ;
}
else
{
node -> right
= del ( node -> right, node, h ) ;
if ( *h )
root = balleft (
root, h ) ;
}
}
}
}
}
return ( root )
;
}
struct AVLNode *
del ( struct AVLNode *succ, struct AVLNode *node, int *h )
{
struct AVLNode
*temp = succ ;
if ( succ ->
left != NULL )
{
succ -> left
= del ( succ -> left, node, h ) ;
if ( *h )
succ = balright
( succ, h ) ;
}
else
{
temp = succ ;
node -> data
= succ -> data ;
succ = succ
-> right ;
free ( temp ) ;
*h = TRUE ;
}
return ( succ )
;
}
struct AVLNode *
balright ( struct AVLNode *root, int *h )
{
struct AVLNode
*node1, *node2 ;
switch ( root
-> balfact )
{
case 1:
root ->
balfact = 0 ;
break;
case 0:
root ->
balfact = -1 ;
*h = FALSE ;
break;
case -1:
node1 = root
-> right ;
if ( node1 ->
balfact <= 0 )
{
printf (
"\nLeft rotation along %d.", root -> data ) ;
root -> right
= node1 -> left ;
node1 -> left
= root ;
if ( node1 ->
balfact == 0 )
{
root ->
balfact = -1 ;
node1 ->
balfact = 1 ;
*h = FALSE ;
}
else
{
root ->
balfact = node1 -> balfact = 0 ;
}
root = node1 ;
}
else
{
printf (
"\nDouble rotation, right along %d", node1 -> data );
node2 = node1
-> left ;
node1 -> left
= node2 -> right ;
node2 ->
right = node1 ;
printf ( "
then left along %d.\n", root -> data );
root -> right
= node2 -> left ;
node2 -> left
= root ;
if ( node2 ->
balfact == -1 )
root ->
balfact = 1 ;
else
root -> balfact
= 0 ;
if ( node2 ->
balfact == 1 )
node1 ->
balfact = -1 ;
else
node1 ->
balfact = 0 ;
root = node2 ;
node2 ->
balfact = 0 ;
}
}
return ( root )
;
}
struct AVLNode *
balleft ( struct AVLNode *root, int *h )
{
struct AVLNode
*node1, *node2 ;
switch ( root
-> balfact )
{
case -1:
root ->
balfact = 0 ;
break ;
case 0:
root ->
balfact = 1 ;
*h = FALSE ;
break ;
case 1:
node1 = root
-> left ;
if ( node1 ->
balfact >= 0 )
{ printf (
"\nRight rotation along %d.", root -> data ) ;
root -> left
= node1 -> right ;
node1 ->
right = root ;
if ( node1 ->
balfact == 0 )
{
root ->
balfact = 1 ;
node1 ->
balfact = -1 ;
*h = FALSE ;
}
else
{
root ->
balfact = node1 -> balfact = 0 ;
}
root = node1 ;
}
else
{
printf (
"\nDouble rotation, left along %d", node1 -> data ) ;
node2 = node1
-> right ;
node1 ->
right = node2 -> left ;
node2 -> left
= node1 ;
printf ( "
then right along %d.\n", root -> data ) ;
root -> left
= node2 -> right ;
node2 ->
right = root ;
if ( node2 ->
balfact == 1 )
root ->
balfact = -1 ;
else
root ->
balfact = 0 ;
if ( node2->
balfact == -1 )
node1 ->
balfact = 1 ;
else
node1 ->
balfact = 0 ;
root = node2 ;
node2 ->
balfact = 0 ;
}
}
return ( root )
;
}
void display (
struct AVLNode *root )
{
if ( root !=
NULL )
{
display ( root
-> left ) ;
printf (
"%d\t", root -> data ) ;
display ( root
-> right ) ;
}
}
void deltree (
struct AVLNode *root )
{
if ( root !=
NULL )
{
deltree ( root
-> left ) ;
deltree ( root
-> right ) ;
}
free ( root ) ;
}
OUTPUT
Q.14
Write a program to build a Binary Search Tree from arrays?
Ans.
#include
<stdio.h>
#include
<conio.h>
#include
<alloc.h>
struct node
{
struct node
*left ;
char data ;
struct node
*right ;
} ;
struct node *
buildtree ( int ) ;
void inorder (
struct node * ) ;
char arr[ ] = {
'A', 'B', 'C', 'D', 'E', 'F', 'G', '\0', '\0', 'H' } ;
int lc[ ] = { 1,
3, 5, -1, 9, -1, -1, -1, -1, -1 } ;
int rc[ ] = { 2,
4, 6, -1, -1, -1, -1, -1, -1, -1 } ;
void main( )
{
struct node
*root ;
clrscr( ) ;
root = buildtree
( 0 ) ;
printf (
"\nIn-order Traversal:\n" ) ;
inorder ( root )
;
getch( ) ;
}
struct node *
buildtree ( int index )
{
struct node
*temp = NULL ;
if ( index != -1
)
{
temp = ( struct
node * ) malloc ( sizeof ( struct node ) ) ;
temp -> left
= buildtree ( lc[index] ) ;
temp -> data
= arr[index] ;
temp -> right
= buildtree ( rc[index] ) ;
}
return temp ;
}
void inorder (
struct node *root )
{
if ( root !=
NULL )
{
inorder ( root
-> left ) ;
printf (
"%c\t", root -> data ) ;
inorder ( root
-> right ) ;
}
}
OUTPUT
Q.15 Write a
program that implements a Priority Queue using an array?
Ans.
#include <stdio.h>
#include <conio.h>
#define MAX 5
struct data
{
char job[MAX] ;
int prno ;
int ord ;
} ;
struct pque
{
struct data d[MAX] ;
int front ;
int rear ;
} ;
void initpque ( struct pque * ) ;
void add ( struct pque *, struct data ) ;
struct data delete ( struct pque * ) ;
void main( )
{
struct pque q ;
struct data dt, temp ;
int i, j = 0 ;
clrscr( ) ;
initpque ( &q ) ;
printf ( "Enter Job description (max 4 chars) and its priority\n" ) ;
printf ( "Lower the priority number, higher the priority\n" ) ;
printf ( "Job Priority\n" ) ;
for ( i = 0 ; i < MAX ; i++ )
{
scanf ( "%s %d", &dt.job, &dt.prno ) ;
dt.ord = j++ ;
add ( &q, dt ) ;
}
printf ( "\n" ) ;
printf ( "Process jobs prioritywise\n" ) ;
printf ( "Job\tPriority\n" ) ;
for ( i = 0 ; i < MAX ; i++ )
{
temp = delete ( &q ) ;
printf ( "%s\t%d\n", temp.job, temp.prno ) ;
}
printf ( "\n" ) ;
getch( ) ;
}
/* initialises data members */
void initpque ( struct pque *pq )
{
int i ;
pq -> front = pq -> rear = -1 ;
for ( i = 0 ; i < MAX ; i++ )
{
strcpy ( pq -> d[i].job, '\0' ) ;
#include <conio.h>
#define MAX 5
struct data
{
char job[MAX] ;
int prno ;
int ord ;
} ;
struct pque
{
struct data d[MAX] ;
int front ;
int rear ;
} ;
void initpque ( struct pque * ) ;
void add ( struct pque *, struct data ) ;
struct data delete ( struct pque * ) ;
void main( )
{
struct pque q ;
struct data dt, temp ;
int i, j = 0 ;
clrscr( ) ;
initpque ( &q ) ;
printf ( "Enter Job description (max 4 chars) and its priority\n" ) ;
printf ( "Lower the priority number, higher the priority\n" ) ;
printf ( "Job Priority\n" ) ;
for ( i = 0 ; i < MAX ; i++ )
{
scanf ( "%s %d", &dt.job, &dt.prno ) ;
dt.ord = j++ ;
add ( &q, dt ) ;
}
printf ( "\n" ) ;
printf ( "Process jobs prioritywise\n" ) ;
printf ( "Job\tPriority\n" ) ;
for ( i = 0 ; i < MAX ; i++ )
{
temp = delete ( &q ) ;
printf ( "%s\t%d\n", temp.job, temp.prno ) ;
}
printf ( "\n" ) ;
getch( ) ;
}
/* initialises data members */
void initpque ( struct pque *pq )
{
int i ;
pq -> front = pq -> rear = -1 ;
for ( i = 0 ; i < MAX ; i++ )
{
strcpy ( pq -> d[i].job, '\0' ) ;
pq -> d[i].prno = pq -> d[i].ord = 0 ;
}
}
/* adds item to the priority queue */
void add ( struct pque *pq, struct data dt )
{
struct data temp ;
int i, j ;
if ( pq -> rear == MAX - 1 )
{
printf ( "\nQueue is full." ) ;
return ;
}
pq -> rear++ ;
pq -> d[pq -> rear] = dt ;
if ( pq -> front == -1 )
pq -> front = 0 ;
for ( i = pq -> front ; i <= pq -> rear ; i++ )
{
for ( j = i + 1 ; j <= pq -> rear ; j++ )
{
if ( pq -> d[i].prno > pq -> d[j].prno )
{
temp = pq -> d[i] ;
pq -> d[i] = pq -> d[j] ;
pq -> d[j] = temp ;
}
else
{
if ( pq -> d[i].prno == pq -> d[j].prno )
{
if ( pq -> d[i].ord > pq -> d[j].ord )
{
temp = pq -> d[i] ;
pq -> d[i] = pq -> d[j] ;
pq -> d[j] = temp ;
}
}
}
}
}
}
/* removes item from priority queue */
struct data delete ( struct pque *pq )
{
struct data t ;
strcpy ( t.job, "" ) ;
t.prno = 0 ;
t.ord = 0 ;
if ( pq -> front == -1 )
{
printf ( "\nQueue is Empty.\n" ) ;
return t ;
}
t = pq -> d[pq -> front] ;
}
}
/* adds item to the priority queue */
void add ( struct pque *pq, struct data dt )
{
struct data temp ;
int i, j ;
if ( pq -> rear == MAX - 1 )
{
printf ( "\nQueue is full." ) ;
return ;
}
pq -> rear++ ;
pq -> d[pq -> rear] = dt ;
if ( pq -> front == -1 )
pq -> front = 0 ;
for ( i = pq -> front ; i <= pq -> rear ; i++ )
{
for ( j = i + 1 ; j <= pq -> rear ; j++ )
{
if ( pq -> d[i].prno > pq -> d[j].prno )
{
temp = pq -> d[i] ;
pq -> d[i] = pq -> d[j] ;
pq -> d[j] = temp ;
}
else
{
if ( pq -> d[i].prno == pq -> d[j].prno )
{
if ( pq -> d[i].ord > pq -> d[j].ord )
{
temp = pq -> d[i] ;
pq -> d[i] = pq -> d[j] ;
pq -> d[j] = temp ;
}
}
}
}
}
}
/* removes item from priority queue */
struct data delete ( struct pque *pq )
{
struct data t ;
strcpy ( t.job, "" ) ;
t.prno = 0 ;
t.ord = 0 ;
if ( pq -> front == -1 )
{
printf ( "\nQueue is Empty.\n" ) ;
return t ;
}
t = pq -> d[pq -> front] ;
pq -> d[pq -> front] = t ;
if ( pq -> front == pq -> rear )
pq -> front = pq -> rear = -1 ;
else
pq -> front++ ;
return t ;
}
if ( pq -> front == pq -> rear )
pq -> front = pq -> rear = -1 ;
else
pq -> front++ ;
return t ;
}
OUTPUT
Q.16 Write a program that implements a Deque using an array?
Ans.
#include <stdio.h>
#include <conio.h>
#define MAX 10
void addqatbeg ( int *, int, int *, int * ) ;
void addqatend ( int *, int, int *, int * ) ;
int delqatbeg ( int *, int *, int * ) ;
int delqatend ( int *, int *, int * ) ;
void display ( int * ) ;
int count ( int * ) ;
void main( )
{
int arr[MAX] ;
int front, rear, i, n ;
clrscr( ) ;
/* initialises data members */
front = rear = -1 ;
for ( i = 0 ; i < MAX ; i++ )
arr[i] = 0 ;
addqatend ( arr, 17, &front, &rear ) ;
addqatbeg ( arr, 10, &front, &rear ) ;
addqatend ( arr, 8, &front, &rear ) ;
addqatbeg ( arr, -9, &front, &rear ) ;
addqatend ( arr, 13, &front, &rear ) ;
addqatbeg ( arr, 28, &front, &rear ) ;
addqatend ( arr, 14, &front, &rear ) ;
addqatbeg ( arr, 5, &front, &rear ) ;
addqatend ( arr, 25, &front, &rear ) ;
addqatbeg ( arr, 6, &front, &rear ) ;
addqatend ( arr, 21, &front, &rear ) ;
addqatbeg ( arr, 11, &front, &rear ) ;
printf ( "\nElements in a deque: " ) ;
display ( arr ) ;
n = count ( arr ) ;
printf ( "\nTotal number of elements in deque: %d", n ) ;
i = delqatbeg ( arr, &front, &rear ) ;
printf ( "\nItem extracted: %d", i ) ;
i = delqatbeg ( arr, &front, &rear ) ;
printf ( "\nItem extracted:%d", i ) ;
i = delqatbeg ( arr, &front, &rear ) ;
printf ( "\nItem extracted:%d", i ) ;
i = delqatbeg ( arr, &front, &rear ) ;
printf ( "\nItem extracted: %d", i ) ;
printf ( "\nElements in a deque after deletion: " ) ;
display ( arr ) ;
addqatend ( arr, 16, &front, &rear ) ;
addqatend ( arr, 7, &front, &rear ) ;
printf ( "\nElements in a deque after addition: " ) ;
display ( arr ) ;
i = delqatend ( arr, &front, &rear ) ;
printf ( "\nItem extracted: %d", i ) ;
i = delqatend ( arr, &front, &rear ) ;
printf ( "\nItem extracted: %d", i ) ;
printf ( "\nElements in a deque after deletion: " ) ;
#include <conio.h>
#define MAX 10
void addqatbeg ( int *, int, int *, int * ) ;
void addqatend ( int *, int, int *, int * ) ;
int delqatbeg ( int *, int *, int * ) ;
int delqatend ( int *, int *, int * ) ;
void display ( int * ) ;
int count ( int * ) ;
void main( )
{
int arr[MAX] ;
int front, rear, i, n ;
clrscr( ) ;
/* initialises data members */
front = rear = -1 ;
for ( i = 0 ; i < MAX ; i++ )
arr[i] = 0 ;
addqatend ( arr, 17, &front, &rear ) ;
addqatbeg ( arr, 10, &front, &rear ) ;
addqatend ( arr, 8, &front, &rear ) ;
addqatbeg ( arr, -9, &front, &rear ) ;
addqatend ( arr, 13, &front, &rear ) ;
addqatbeg ( arr, 28, &front, &rear ) ;
addqatend ( arr, 14, &front, &rear ) ;
addqatbeg ( arr, 5, &front, &rear ) ;
addqatend ( arr, 25, &front, &rear ) ;
addqatbeg ( arr, 6, &front, &rear ) ;
addqatend ( arr, 21, &front, &rear ) ;
addqatbeg ( arr, 11, &front, &rear ) ;
printf ( "\nElements in a deque: " ) ;
display ( arr ) ;
n = count ( arr ) ;
printf ( "\nTotal number of elements in deque: %d", n ) ;
i = delqatbeg ( arr, &front, &rear ) ;
printf ( "\nItem extracted: %d", i ) ;
i = delqatbeg ( arr, &front, &rear ) ;
printf ( "\nItem extracted:%d", i ) ;
i = delqatbeg ( arr, &front, &rear ) ;
printf ( "\nItem extracted:%d", i ) ;
i = delqatbeg ( arr, &front, &rear ) ;
printf ( "\nItem extracted: %d", i ) ;
printf ( "\nElements in a deque after deletion: " ) ;
display ( arr ) ;
addqatend ( arr, 16, &front, &rear ) ;
addqatend ( arr, 7, &front, &rear ) ;
printf ( "\nElements in a deque after addition: " ) ;
display ( arr ) ;
i = delqatend ( arr, &front, &rear ) ;
printf ( "\nItem extracted: %d", i ) ;
i = delqatend ( arr, &front, &rear ) ;
printf ( "\nItem extracted: %d", i ) ;
printf ( "\nElements in a deque after deletion: " ) ;
display ( arr ) ;
n = count ( arr ) ;
printf ( "\nTotal number of
elements in deque: %d", n ) ;
getch( ) ;
}
/* adds an element at the beginning of a deque */
void addqatbeg ( int *arr, int item, int *pfront, int *prear )
{
int i, k, c ;
if ( *pfront == 0 && *prear == MAX - 1 )
{
printf ( "\nDeque is full.\n" ) ;
return ;
}
if ( *pfront == -1 )
{
*pfront = *prear = 0 ;
arr[*pfront] = item ;
return ;
}
if ( *prear != MAX - 1 )
{
c = count ( arr ) ;
k = *prear + 1 ;
for ( i = 1 ; i <= c ; i++ )
{
arr[k] = arr[k - 1] ;
k-- ;
}
arr[k] = item ;
*pfront = k ;
( *prear )++ ;
}
else
{
( *pfront )-- ;
arr[*pfront] = item ;
}
}
/* adds an element at the end of a deque */
void addqatend ( int *arr, int item, int *pfront, int *prear )
{
int i, k ;
if ( *pfront == 0 && *prear == MAX - 1 )
{
printf ( "\nDeque is full.\n" ) ;
return ;
}
if ( *pfront == -1 )
{
*prear = *pfront = 0 ;
arr[*prear] = item ;
return ;
}
if ( *prear == MAX - 1 )
getch( ) ;
}
/* adds an element at the beginning of a deque */
void addqatbeg ( int *arr, int item, int *pfront, int *prear )
{
int i, k, c ;
if ( *pfront == 0 && *prear == MAX - 1 )
{
printf ( "\nDeque is full.\n" ) ;
return ;
}
if ( *pfront == -1 )
{
*pfront = *prear = 0 ;
arr[*pfront] = item ;
return ;
}
if ( *prear != MAX - 1 )
{
c = count ( arr ) ;
k = *prear + 1 ;
for ( i = 1 ; i <= c ; i++ )
{
arr[k] = arr[k - 1] ;
k-- ;
}
arr[k] = item ;
*pfront = k ;
( *prear )++ ;
}
else
{
( *pfront )-- ;
arr[*pfront] = item ;
}
}
/* adds an element at the end of a deque */
void addqatend ( int *arr, int item, int *pfront, int *prear )
{
int i, k ;
if ( *pfront == 0 && *prear == MAX - 1 )
{
printf ( "\nDeque is full.\n" ) ;
return ;
}
if ( *pfront == -1 )
{
*prear = *pfront = 0 ;
arr[*prear] = item ;
return ;
}
if ( *prear == MAX - 1 )
{
k = *pfront - 1 ;
for ( i = *pfront - 1 ; i < *prear ; i++ )
{
k = i ;
if ( k == MAX - 1 )
arr[k] = 0 ;
else
arr[k] = arr[i + 1] ;
}
( *prear )-- ;
( *pfront )-- ;
}
( *prear )++ ;
arr[*prear] = item ;
}
/* removes an element from the *pfront end of deque */
int delqatbeg ( int *arr, int *pfront, int *prear )
{
int item ;
if ( *pfront == -1 )
{
printf ( "\nDeque is empty.\n" ) ;
return 0 ;
}
item = arr[*pfront] ;
arr[*pfront] = 0 ;
if ( *pfront == *prear )
*pfront = *prear = -1 ;
else
( *pfront )++ ;
return item ;
}
/* removes an element from the *prear end of the deque */
int delqatend ( int *arr, int *pfront, int *prear )
{
int item ;
if ( *pfront == -1 )
{
printf ( "\nDeque is empty.\n" ) ;
return 0 ;
}
item = arr[*prear] ;
arr[*prear] = 0 ;
( *prear )-- ;
if ( *prear == -1 )
*pfront = -1 ;
return item ;
}
/* displays elements of a deque */
void display ( int *arr )
{
int i ;
printf ( "\n front->" ) ;
for ( i = 0 ; i < MAX ; i++ )
k = *pfront - 1 ;
for ( i = *pfront - 1 ; i < *prear ; i++ )
{
k = i ;
if ( k == MAX - 1 )
arr[k] = 0 ;
else
arr[k] = arr[i + 1] ;
}
( *prear )-- ;
( *pfront )-- ;
}
( *prear )++ ;
arr[*prear] = item ;
}
/* removes an element from the *pfront end of deque */
int delqatbeg ( int *arr, int *pfront, int *prear )
{
int item ;
if ( *pfront == -1 )
{
printf ( "\nDeque is empty.\n" ) ;
return 0 ;
}
item = arr[*pfront] ;
arr[*pfront] = 0 ;
if ( *pfront == *prear )
*pfront = *prear = -1 ;
else
( *pfront )++ ;
return item ;
}
/* removes an element from the *prear end of the deque */
int delqatend ( int *arr, int *pfront, int *prear )
{
int item ;
if ( *pfront == -1 )
{
printf ( "\nDeque is empty.\n" ) ;
return 0 ;
}
item = arr[*prear] ;
arr[*prear] = 0 ;
( *prear )-- ;
if ( *prear == -1 )
*pfront = -1 ;
return item ;
}
/* displays elements of a deque */
void display ( int *arr )
{
int i ;
printf ( "\n front->" ) ;
for ( i = 0 ; i < MAX ; i++ )
printf ( "\t%d", arr[i] )
;
printf ( " <-rear" ) ;
}
/* counts the total number of elements in deque */
int count ( int *arr )
{
int c = 0, i ;
for ( i = 0 ; i < MAX ; i++ )
{
if ( arr[i] != 0 )
c++ ;
}
return c ;
}
}
/* counts the total number of elements in deque */
int count ( int *arr )
{
int c = 0, i ;
for ( i = 0 ; i < MAX ; i++ )
{
if ( arr[i] != 0 )
c++ ;
}
return c ;
}
OUTPUT
I like Your Post This is Very Useful info!
ReplyDeleteDHA Gujranwala part was quick to be reported and which is all well and good , it is situated in focal Punjab, Gujranwala is a modern center of Pakistan and is in nearness to the urban communities of Sialkot, Gujrat, Kharian, and Jehlum. This belt is liable for a ton of enlistment inside the Pakistan Military and hence the need to give individuals serving their country a home nearer to their home urban communities.