Program to maintain a heap.

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

void restoreup ( int, int * ) ;
void restoredown ( int, int *, int ) ;
void makeheap ( int *, int ) ;
void add ( int, int *, int * ) ;
int replace ( int, int *, int ) ;
int del ( int *, int * ) ;

void main( )
{
int arr [20] = { 1000, 7, 10, 25, 17, 23, 27, 16,
19, 37, 42, 4, 33, 1, 5, 11 } ;
int i, n = 15 ;

clrscr( ) ;
makeheap ( arr, n ) ;

printf ( "Heap:\n" ) ;
for ( i = 1 ; i <= n ; i++ )
printf ( "%d\t", arr [i] ) ;

i = 24 ;
add ( i, arr, &n ) ;

printf ( "\n\nElement added %d.\n", i ) ;
printf ( "\nHeap after addition of an element:\n" ) ;
for ( i = 1 ; i <= n ; i++ )
printf ( "%d\t", arr [i] ) ;

i = replace ( 2, arr, n ) ;
printf ( "\n\nElement replaced %d.\n", i ) ;
printf ( "\nHeap after replacement of an element:\n" ) ;
for ( i = 1 ; i <= n ; i++ )
printf ( "%d\t", arr [i] ) ;

i = del ( arr, &n ) ;
printf ( "\n\nElement deleted %d.\n", i ) ;
printf ( "\nHeap after deletion of an element:\n" ) ;
for ( i = 1 ; i <= n ; i++ )
printf ( "%d\t", arr [i] ) ;

getch( ) ;
}

void restoreup ( int i, int *arr )
{
int val ;
val = arr [i] ;
while ( arr [i / 2] <= val )
{
arr [i] = arr [i / 2] ;
i = i / 2 ;
}
arr [i] = val ;
}

void restoredown ( int pos, int *arr, int n )
{
int i, val ;
val = arr [pos] ;
while ( pos <= n / 2 )
{
i = 2 * pos ;
if ( ( i < n ) && ( arr [i] < arr [i + 1] ) )
i++ ;
if ( val >= arr [i] )
break ;
arr [pos] = arr [i] ;
pos = i ;
}
arr [pos] = val ;
}

void makeheap ( int *arr, int n )
{
int i ;
for ( i = n / 2 ; i >= 1 ; i-- )
restoredown ( i, arr, n ) ;
}

void add ( int val, int *arr, int *n )
{
( *n ) ++ ;
arr [*n] = val ;
restoreup ( *n, arr ) ;
}
int replace ( int i, int *arr, int n )
{
int r = arr [1] ;
arr [1] = i ;
for ( i = n / 2 ; i >= 1 ; i-- )
restoredown ( i, arr, n ) ;
return r ;
}

int del ( int *arr, int *n )
{
int val ;
val = arr [1] ;
arr [1] = arr [*n] ;
( *n ) -- ;
restoredown ( 1, arr, *n ) ;
return val ;
}

Program which maintains a B-tree of order 5.

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

/* inserts a value in the B-tree*/
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 ;
}

/* sets the value in the node */
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 ;
}
}

/* searches value in the node */
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 ) ;
}
}

/* searches for the node */
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 ;
}
}


/* adjusts the value of the node */
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++ ;
}

/* splits the node */
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-- ;
}

/* deletes value from the node */
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 ;
}

/* helper function for delete( ) */
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 ;
}
}

/* removes the value from the node and adjusts the values */
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-- ;
}

/* copies the successor of the value that is to be deleted */
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] ;
}

/* adjusts the node */
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 ) ;
}
}
}
}

/* adjusts the values and children while shifting the value from parent to right
child */
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-- ;
}

/* adjusts the values and children while shifting the value from parent to left
child */
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] ;
}
}

/* merges two nodes */
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 ) ;
}

/* displays the B-tree */
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] ) ;
}
}

Program to maintain an AVL tree.

#include
#include
#include

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

/* inserts an element into tree */
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 left subtree is higher */
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 the right subtree is higher */
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 ) ;
}

/* deletes an item from the tree */
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 ) ;
}

/* balances the tree, if right sub-tree is higher */
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 ) ;
}

/* balances the tree, if left sub-tree is higher */
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 ) ;
}

/* displays the tree in-order */
void display ( struct AVLNode *root )
{
if ( root != NULL )
{
display ( root -> left ) ;
printf ( "%d\t", root -> data ) ;
display ( root -> right ) ;
}
}

/* deletes the tree */
void deltree ( struct AVLNode *root )
{
if ( root != NULL )
{
deltree ( root -> left ) ;
deltree ( root -> right ) ;
}
free ( root ) ;
}

Program to maintain a threaded binary tree.

#include <"stdio.h">
#include <"conio.h">
#include <"alloc.h">

enum boolean
{
false = 0,
true = 1
} ;

struct thtree
{
enum boolean isleft ;
struct thtree *left ;
int data ;
struct thtree *right ;
enum boolen isright ;
} ;

void insert ( struct thtree **, int ) ;
void delete ( struct thtree **, int ) ;
void search ( struct thtree **, int, struct thtree **,
struct thtree **, int * ) ;
void inorder ( struct thtree * ) ;
void deltree ( struct thtree ** ) ;

void main( )
{
struct thtree *th_head ;

th_head = NULL ; /* empty tree */

insert ( &th_head, 11 ) ;
insert ( &th_head, 9 ) ;
insert ( &th_head, 13 ) ;
insert ( &th_head, 8 ) ;
insert ( &th_head, 10 ) ;
insert ( &th_head, 12 ) ;
insert ( &th_head, 14 ) ;
insert ( &th_head, 15 ) ;
insert ( &th_head, 7 ) ;

clrscr( ) ;
printf ( "Threaded binary tree before deletion:\n" ) ;
inorder ( th_head ) ;

delete ( &th_head, 10 ) ;
printf ( "\nThreaded binary tree after deletion:\n" ) ;
inorder ( th_head ) ;

delete ( &th_head, 14 ) ;
printf ( "\nThreaded binary tree after deletion:\n" ) ;
inorder ( th_head ) ;

delete ( &th_head, 8 ) ;
printf ( "\nThreaded binary tree after deletion:\n" ) ;
inorder ( th_head ) ;

delete ( &th_head, 13 ) ;
printf ( "\nThreaded binary tree after deletion:\n" ) ;
inorder ( th_head ) ;

deltree ( &th_head ) ;

getch( ) ;
}

/* inserts a node in a threaded binary tree */
void insert ( struct thtree **s, int num )
{
struct thtree *p, *z, *head = *s ;

/* allocating a new node */
z = malloc ( sizeof ( struct thtree ) ) ;

z -> isleft = true ; /* indicates a thread */
z -> data = num ; /* assign new data */
z -> isright = true ; /* indicates a thread */

/* if tree is empty */
if ( *s == NULL )
{
head = malloc ( sizeof ( struct thtree ) ) ;

/* the entire tree is treated as a left sub-tree of the head node */
head -> isleft = false ;
head -> left = z ; /* z becomes leftchild of the head node */
head -> data = -9999 ; /* no data */
head -> right = head ; /* right link will always be pointing
to itself */
head -> isright = false ;

*s = head ;

z -> left = head ; /* left thread to head */
z -> right = head ; /* right thread to head */
}
else /* if tree is non-empty */
{
p = head -> left ;

/* traverse till the thread is found attached to the head */
while ( p != head )
{
if ( p -> data > num )
{
if ( p -> isleft != true ) /* checking for a thread */
p = p -> left ;
else
{
z -> left = p -> left ;
p -> left = z ;
p -> isleft = false ; /* indicates a link */
z -> isright = true ;
z -> right = p ;
return ;
}
}
else
{
if ( p -> data < num )
{
if ( p -> isright != true )
p = p -> right ;
else
{
z -> right = p -> right ;
p -> right = z ;
p -> isright = false ; /* indicates a link */
z -> isleft = true ;
z -> left = p ;
return ;
}
}
}
}
}
}

/* deletes a node from the binary search tree */
void delete ( struct thtree **root, int num )
{
int found ;
struct thtree *parent, *x, *xsucc ;

/* if tree is empty */
if ( *root == NULL )
{
printf ( "\nTree is empty" ) ;
return ;
}

parent = x = NULL ;

/* call to search function to find the node to be deleted */
search ( root, num, &parent, &x, &found ) ;

/* if the node to deleted is not found */
if ( found == false )
{
printf ( "\nData to be deleted, not found" ) ;
return ;
}

/* if the node to be deleted has two children */
if ( x -> isleft == false && x -> isright == false )
{
parent = x ;
xsucc = x -> right ;

while ( xsucc -> isleft == false )
{
parent = xsucc ;
xsucc = xsucc -> left ;
}

x -> data = xsucc -> data ;
x = xsucc ;
}

/* if the node to be deleted has no child */
if ( x -> isleft == true && x -> isright == true )
{
/* if node to be deleted is a root node */
if ( parent == NULL )
{
( *root ) -> left = *root ;
( *root ) -> isleft = true ;

free ( x ) ;
return ;
}

if ( parent -> right == x )
{
parent -> isright = true ;
parent -> right = x -> right ;
}
else
{
parent -> isleft = true ;
parent -> left = x -> left ;
}

free ( x ) ;
return ;
}

/* if the node to be deleted has only rightchild */
if ( x -> isleft == true && x -> isright == false )
{
/* node to be deleted is a root node */
if ( parent == NULL )
{
( *root ) -> left = x -> right ;
free ( x ) ;
return ;
}

if ( parent -> left == x )
{
parent -> left = x -> right ;
x -> right -> left = x -> left ;
}
else
{
parent -> right = x -> right ;
x -> right -> left = parent ;
}

free ( x ) ;
return ;
}

/* if the node to be deleted has only left child */
if ( x -> isleft == false && x -> isright == true )
{
/* the node to be deleted is a root node */
if ( parent == NULL )
{
parent = x ;
xsucc = x -> left ;

while ( xsucc -> right == false )
xsucc = xsucc -> right ;

xsucc -> right = *root ;

( *root ) -> left = x -> left ;

free ( x ) ;
return ;
}

if ( parent -> left == x )
{
parent -> left = x -> left ;
x -> left -> right = parent ;
}
else
{
parent -> right = x -> left ;
x -> left -> right = x -> right ;
}

free ( x ) ;
return ;
}
}

/* returns the address of the node to be deleted, address of its parent and
whether the node is found or not */
void search ( struct thtree **root, int num, struct thtree **par,
struct thtree **x, int *found )
{
struct thtree *q ;

q = ( *root ) -> left ;
*found = false ;
*par = NULL ;

while ( q != *root )
{
/* if the node to be deleted is found */
if ( q -> data == num )
{
*found = true ;
*x = q ;
return ;
}

*par = q ;

if ( q -> data > num )
{
if ( q -> isleft == true )
{
*found = false ;
x = NULL ;
return ;
}
q = q -> left ;
}
else
{
if ( q -> isright == true )
{
*found = false ;
*x = NULL ;
return ;
}
q = q -> right ;
}
}
}

/* traverses the threaded binary tree in inorder */
void inorder ( struct thtree *root )
{
struct thtree *p ;

p = root -> left ;

while ( p != root )
{
while ( p -> isleft == false )
p = p -> left ;

printf ( "%d\t", p -> data ) ;

while ( p -> isright == true )
{
p = p -> right ;

if ( p == root )
break ;

printf ( "%d\t", p -> data ) ;

}
p = p -> right ;
}
}

void deltree ( struct thtree **root )
{
while ( ( *root ) -> left != *root )
delete ( root, ( *root ) -> left -> data ) ;
}

Program to insert and delete a node from the binary search tree.

#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 /* search the node to which new node will be attached */
{
/* if new data is less, traverse to left */
if ( num < ( *sr ) -> data )
insert ( &( ( *sr ) -> leftchild ), num ) ;
else
/* else traverse to right */
insert ( &( ( *sr ) -> rightchild ), num ) ;
}
}

/* deletes a node from the binary search tree */
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 ;

/* call to search function to find the node to be deleted */
search ( root, num, &parent, &x, &found ) ;

/* if the node to deleted is not found */
if ( found == FALSE )
{
printf ( "\nData to be deleted, not found" ) ;
return ;
}

/* if the node to be deleted has two children */
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 the node to be deleted has no child */
if ( x -> leftchild == NULL && x -> rightchild == NULL )
{
if ( parent -> rightchild == x )
parent -> rightchild = NULL ;
else
parent -> leftchild = NULL ;

free ( x ) ;
return ;
}

/* if the node to be deleted has only rightchild */
if ( x -> leftchild == NULL && x -> rightchild != NULL )
{
if ( parent -> leftchild == x )
parent -> leftchild = x -> rightchild ;
else
parent -> rightchild = x -> rightchild ;

free ( x ) ;
return ;
}

/* if the node to be deleted has only left child */
if ( x -> leftchild != NULL && x -> rightchild == NULL )
{
if ( parent -> leftchild == x )
parent -> leftchild = x -> leftchild ;
else
parent -> rightchild = x -> leftchild ;

free ( x ) ;
return ;
}
}

/*returns the address of the node to be deleted, address of its parent and
whether the node is found or not */
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 the node to be deleted is found */
if ( q -> data == num )
{
*found = TRUE ;
*x = q ;
return ;
}

*par = q ;

if ( q -> data > num )
q = q -> leftchild ;
else
q = q -> rightchild ;
}
}

/* traverse a binary search tree in a LDR (Left-Data-Right) fashion */
void inorder ( struct btreenode *sr )
{
if ( sr != NULL )
{
inorder ( sr -> leftchild ) ;

/* print the data of the node whose leftchild is NULL or the path has
already been traversed */
printf ( "%d\t", sr -> data ) ;

inorder ( sr -> rightchild ) ;
}
}

Program to implement a binary search tree.

#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 ; /* empty tree */

clrscr( ) ;
printf ( "Specify the number of items to be inserted: " ) ;
scanf ( "%d", &req ) ;

while ( i++ <= req )
{
printf ( "Enter the data: " ) ;
scanf ( "%d", &num ) ;
insert ( &bt, num ) ;
}

printf ( "\nIn-order Traversal: " ) ;
inorder ( bt ) ;

printf ( "\nPre-order Traversal: " ) ;
preorder ( bt ) ;

printf ( "\nPost-order Traversal: " ) ;
postorder ( 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 ;
return ;
}
else /* search the node to which new node will be attached */
{
/* if new data is less, traverse to left */
if ( num < ( *sr ) -> data )
insert ( &( ( *sr ) -> leftchild ), num ) ;
else
/* else traverse to right */
insert ( &( ( *sr ) -> rightchild ), num ) ;
}
return ;
}

/* traverse a binary search tree in a LDR (Left-Data-Right) fashion */
void inorder ( struct btreenode *sr )
{
if ( sr != NULL )
{
inorder ( sr -> leftchild ) ;

/* print the data of the node whose leftchild is NULL or the path
has already been traversed */
printf ( "\t%d", sr -> data ) ;

inorder ( sr -> rightchild ) ;
}
else
return ;
}

/* traverse a binary search tree in a DLR (Data-Left-right) fashion */
void preorder ( struct btreenode *sr )
{
if ( sr != NULL )
{
/* print the data of a node */
printf ( "\t%d", sr -> data ) ;
/* traverse till leftchild is not NULL */
preorder ( sr -> leftchild ) ;
/* traverse till rightchild is not NULL */
preorder ( sr -> rightchild ) ;
}
else
return ;
}


/* traverse a binary search tree in LRD (Left-Right-Data) fashion */
void postorder ( struct btreenode *sr )
{
if ( sr != NULL )
{
postorder ( sr -> leftchild ) ;
postorder ( sr -> rightchild ) ;
printf ( "\t%d", sr -> data ) ;
}
else
return ;
}

Program to build a binary search tree from an array.

#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 a[ ] = {
'A', 'B', 'C', 'D', 'E', 'F', 'G', '\0', '\0', 'H', '\0',
'\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0'
} ;

void main( )
{
struct node *root ;

clrscr( ) ;

root = buildtree ( 0 ) ;
printf ( "In-order Traversal:\n" ) ;
inorder ( root ) ;

getch( ) ;
}
struct node * buildtree ( int n )
{
struct node *temp = NULL ;
if ( a[n] != '\0' )
{
temp = ( struct node * ) malloc ( sizeof ( struct node ) ) ;
temp -> left = buildtree ( 2 * n + 1 ) ;
temp -> data = a[n] ;
temp -> right = buildtree ( 2 * n + 2 ) ;
}
return temp ;
}

void inorder ( struct node *root )
{
if ( root != NULL )
{
inorder ( root -> left ) ;
printf ( "%c\t", root -> data ) ;
inorder ( root -> right ) ;
}
}

Program to build a binary search tree from arrays.

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

Program to insert and delete a node from the binary search tree

#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 /* search the node to which new node will be attached */
{
/* if new data is less, traverse to left */
if ( num < ( *sr ) -> data )
insert ( &( ( *sr ) -> leftchild ), num ) ;
else
/* else traverse to right */
insert ( &( ( *sr ) -> rightchild ), num ) ;
}
}

/* deletes a node from the binary search tree */
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 ;

/* call to search function to find the node to be deleted */
search ( root, num, &parent, &x, &found ) ;

/* if the node to deleted is not found */
if ( found == FALSE )
{
printf ( "\nData to be deleted, not found" ) ;
return ;
}

/* if the node to be deleted has two children */
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 the node to be deleted has no child */
if ( x -> leftchild == NULL && x -> rightchild == NULL )
{
if ( parent -> rightchild == x )
parent -> rightchild = NULL ;
else
parent -> leftchild = NULL ;

free ( x ) ;
return ;
}

/* if the node to be deleted has only rightchild */
if ( x -> leftchild == NULL && x -> rightchild != NULL )
{
if ( parent -> leftchild == x )
parent -> leftchild = x -> rightchild ;
else
parent -> rightchild = x -> rightchild ;

free ( x ) ;
return ;
}

/* if the node to be deleted has only left child */
if ( x -> leftchild != NULL && x -> rightchild == NULL )
{
if ( parent -> leftchild == x )
parent -> leftchild = x -> leftchild ;
else
parent -> rightchild = x -> leftchild ;

free ( x ) ;
return ;
}
}

/*returns the address of the node to be deleted, address of its parent and
whether the node is found or not */
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 the node to be deleted is found */
if ( q -> data == num )
{
*found = TRUE ;
*x = q ;
return ;
}

*par = q ;

if ( q -> data > num )
q = q -> leftchild ;
else
q = q -> rightchild ;
}
}

/* traverse a binary search tree in a LDR (Left-Data-Right) fashion */
void inorder ( struct btreenode *sr )
{
if ( sr != NULL )
{
inorder ( sr -> leftchild ) ;

/* print the data of the node whose leftchild is NULL or the path has
already been traversed */
printf ( "%d\t", sr -> data ) ;

inorder ( sr -> rightchild ) ;
}
}

Program to reconstruct a binary search tree.

#include <"stdio.h">
#include <"conio.h">
#include <"alloc.h">

#define MAX 101

struct node
{
struct node *left ;
int data ;
struct node *right ;
} ;

void insert ( struct node **, int ) ;
void preorder ( struct node * ) ;
void postorder ( struct node * ) ;
void inorder ( struct node * ) ;
struct node * recons ( int *, int *, int ) ;
void deltree ( struct node * ) ;

int in[MAX], pre[MAX], x ;

void main( )
{
struct node *t, *p, *q ;
int req, i, num ;

t = NULL ; /* empty tree */

clrscr( ) ;
printf ( "Specify the number of items to be inserted: " ) ;
while ( 1 )
{
scanf ( "%d", &req ) ;
if ( req >= MAX || req <= 0 )
printf ( "\nEnter number between 1 to 100.\n" ) ;
else
break ;
}

for ( i = 0 ; i < req ; i++ )
{
printf ( "Enter the data: " ) ;
scanf ( "%d", &num ) ;
insert ( &t, num ) ;
}

printf ( "\nIn-order Traversal:\n" ) ;
x = 0 ;
inorder ( t ) ;

printf ( "\nPre-order Traversal:\n" ) ;
x = 0 ;
preorder ( t ) ;

printf ( "\nPost-order Traversal:\n" ) ;
x = 0 ;
postorder ( t ) ;

deltree ( t ) ;
t = NULL ;
t = recons ( in, pre, req ) ;

printf ( "\n\nAfter reconstruction of the binary tree.\n" ) ;

x = 0 ;
printf ( "\nIn-order Traversal:\n" ) ;
inorder ( t ) ;

x = 0 ;
printf ( "\nPre-order Traversal:\n" ) ;
preorder ( t ) ;
x = 0 ;
printf ( "\nPost-order Traversal:\n" ) ;
postorder ( t ) ;

deltree ( t ) ;
getch( ) ;
}

/* inserts a new node in a binary search tree */
void insert ( struct node **sr, int num )
{
if ( *sr == NULL )
{
*sr = ( struct node * ) malloc ( sizeof ( struct node ) ) ;

( *sr ) -> left = NULL ;
( *sr ) -> data = num ;
( *sr ) -> right = NULL ;
return ;
}
else /* search the node to which new node will be attached */
{
/* if new data is less, traverse to left */
if ( num < ( *sr ) -> data )
insert ( &( ( *sr ) -> left ), num ) ;
else
/* else traverse to right */
insert ( &( ( *sr ) -> right ), num ) ;
}
}

void preorder ( struct node *t )
{
if ( t != NULL )
{
printf ( "%d\t", pre[x++]= t -> data ) ;
preorder ( t -> left ) ;
preorder ( t -> right ) ;
}
}

void postorder ( struct node *t )
{
if ( t != NULL )
{
postorder ( t -> left ) ;
postorder ( t -> right ) ;
printf ( "%d\t", t -> data ) ;
}
}

void inorder ( struct node *t )
{
if ( t != NULL )
{
inorder ( t -> left ) ;
printf ( "%d\t", in[x++]= t -> data ) ;
inorder ( t -> right ) ;
}
}

struct node * recons ( int *inorder, int *preorder, int noofnodes )
{
struct node *temp, *left, *right ;
int tempin[100], temppre[100], i, j ;

if ( noofnodes == 0 )
return NULL ;

temp = ( struct node * ) malloc ( sizeof ( struct node ) ) ;
temp -> data = preorder[0] ;
temp -> left = NULL ;
temp -> right = NULL ;

if ( noofnodes == 1 )
return temp ;
for ( i = 0 ; inorder[i] != preorder[0] ; )
i++ ;

if ( i > 0 )
{
for ( j = 0 ; j <= i ; j++ )
tempin[j] = inorder[j] ;

for ( j = 0 ; j < i ; j++ )
temppre[j] = preorder[j + 1] ;
}

left = recons ( tempin, temppre, i ) ;
temp -> left = left ;

if ( i < noofnodes - 1 )
{
for ( j = i ; j < noofnodes - 1 ; j++ )
{
tempin[j - i] = inorder[j + 1] ;
temppre[j - i] = preorder[j + 1] ;
}
}

right = recons ( tempin, temppre, noofnodes - i - 1 ) ;
temp -> right = right ;

return temp ;
}

void deltree ( struct node *t )
{
if ( t != NULL )
{
deltree ( t -> left ) ;
deltree ( t -> right ) ;
}
free ( t ) ;
}

Program that implements a priority queue using an array.

#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' ) ;
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] ;
pq -> d[pq -> front] = t ;
if ( pq -> front == pq -> rear )
pq -> front = pq -> rear = -1 ;
else
pq -> front++ ;

return t ;
}

Program that implements deque using an array.

#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: " ) ;
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 )
{
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 ;
}

Program that implements circular queue as an array.

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

#define MAX 10

void addq ( int *, int, int *, int * ) ;
int delq ( int *, int *, int * ) ;
void display ( int * ) ;

void main( )
{
int arr[MAX] ;
int i, front, rear ;

clrscr( ) ;

/* initialise data member */
front = rear = -1 ;
for ( i = 0 ; i < MAX ; i++ )
arr[i] = 0 ;

addq ( arr, 14, &front, &rear ) ;
addq ( arr, 22, &front, &rear ) ;
addq ( arr, 13, &front, &rear ) ;
addq ( arr, -6, &front, &rear ) ;
addq ( arr, 25, &front, &rear ) ;

printf ( "\nElements in the circular queue: " ) ;
display ( arr ) ;

i = delq ( arr, &front, &rear ) ;
printf ( "Item deleted: %d", i ) ;

i = delq ( arr, &front, &rear ) ;
printf ( "\nItem deleted: %d", i ) ;

printf ( "\nElements in the circular queue after deletion: " ) ;
display ( arr ) ;

addq ( arr, 21, &front, &rear ) ;
addq ( arr, 17, &front, &rear ) ;
addq ( arr, 18, &front, &rear ) ;
addq ( arr, 9, &front, &rear ) ;
addq ( arr, 20, &front, &rear ) ;

printf ( "Elements in the circular queue after addition: " ) ;
display ( arr ) ;

addq ( arr, 32, &front, &rear ) ;

printf ( "Elements in the circular queue after addition: " ) ;
display ( arr ) ;

getch( ) ;
}

/* adds an element to the queue */
void addq ( int *arr, int item, int *pfront, int *prear )
{
if ( ( *prear == MAX - 1 && *pfront == 0 ) || ( *prear + 1 == *pfront ) )
{
printf ( "\nQueue is full." ) ;
return ;
}

if ( *prear == MAX - 1 )
*prear = 0 ;
else
( *prear )++ ;

arr[*prear] = item ;

if ( *pfront == -1 )
*pfront = 0 ;
}

/* removes an element from the queue */
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 = -1 ;
*prear = -1 ;
}
else
{
if ( *pfront == MAX - 1 )
*pfront = 0 ;
else
( *pfront )++ ;
}
return data ;
}

/* displays element in a queue */
void display ( int * arr )
{
int i ;
printf ( "\n" ) ;
for ( i = 0 ; i < MAX ; i++ )
printf ( "%d\t", arr[i] ) ;
printf ( "\n" ) ;
}

Program that implements queue as a linked list.

#include
#include

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 ) ;
}
}

Program that implements queue as an array.

#include
#include

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

/* adds an element to the queue */
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 ;
}

/* removes an element from the queue */
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 ;
}

Program to evaluate an epression entered in postfix form

#include <"stdio.h">
#include <"conio.h">
#include <"stdlib.h">
#include <"math.h">
#include <"ctype.h">

#define MAX 50

struct postfix
{
int stack[MAX] ;
int top, nn ;
char *s ;
} ;

void initpostfix ( struct postfix * ) ;
void setexpr ( struct postfix *, char * ) ;
void push ( struct postfix *, int ) ;
int pop ( struct postfix * ) ;
void calculate ( struct postfix * ) ;
void show ( struct postfix ) ;

void main( )
{
struct postfix q ;
char expr[MAX] ;

clrscr( ) ;

initpostfix ( &q ) ;


printf ( "\nEnter postfix expression to be evaluated: " ) ;
gets ( expr ) ;

setexpr ( &q, expr ) ;
calculate ( &q ) ;
show ( q ) ;

getch( ) ;
}

/* initializes data members */
void initpostfix ( struct postfix *p )
{
p -> top = -1 ;
}

/* sets s to point to the given expr. */
void setexpr ( struct postfix *p, char *str )
{
p -> s = str ;
}

/* adds digit to the stack */
void push ( struct postfix *p, int item )
{
if ( p -> top == MAX - 1 )
printf ( "\nStack is full." ) ;
else
{
p -> top++ ;
p -> stack[p -> top] = item ;
}
}

/* pops digit from the stack */
int pop ( struct postfix *p )
{
int data ;

if ( p -> top == -1 )
{
printf ( "\nStack is empty." ) ;
return NULL ;
}

data = p -> stack[p -> top] ;
p -> top-- ;

return data ;
}

/* evaluates the postfix expression */
void calculate( struct postfix *p )
{
int n1, n2, n3 ;
while ( *( p -> s ) )
{
/* skip whitespace, if any */
if ( *( p -> s ) == ' ' || *( p -> s ) == '\t' )
{
p -> s++ ;
continue ;
}

/* if digit is encountered */
if ( isdigit ( *( p -> s ) ) )
{
p -> nn = *( p -> s ) - '0' ;
push ( p, p -> nn ) ;
}
else
{
/* if operator is encountered */
n1 = pop ( p ) ;
n2 = pop ( p ) ;
switch ( *( p -> s ) )
{
case '+' :
n3 = n2 + n1 ;
break ;

case '-' :
n3 = n2 - n1 ;
break ;

case '/' :
n3 = n2 / n1 ;
break ;

case '*' :
n3 = n2 * n1 ;
break ;

case '%' :
n3 = n2 % n1 ;
break ;

case '$' :
n3 = pow ( n2 , n1 ) ;
break ;

default :
printf ( "Unknown operator" ) ;
exit ( 1 ) ;
}

push ( p, n3 ) ;
}
p -> s++ ;
}
}

/* displays the result */
void show ( struct postfix p )
{
p.nn = pop ( &p ) ;
printf ( "Result is: %d", p.nn ) ;
}

Program to convert an expression in postfix form to an infix form

#include
#include
#include

#define MAX 50

struct postfix
{
char stack[MAX][MAX], target[MAX] ;
char temp1[2], temp2[2] ;
char str1[MAX], str2[MAX], str3[MAX] ;
int i, top ;
} ;

void initpostfix ( struct postfix * ) ;
void setexpr ( struct postfix *, char * ) ;
void push ( struct postfix *, char * ) ;
void pop ( struct postfix *, char * ) ;
void convert ( struct postfix * ) ;
void show ( struct postfix ) ;

void main( )
{
struct postfix q ;
char expr[MAX] ;

clrscr( ) ;

initpostfix ( &q ) ;

printf ( "\nEnter an expression in postfix form: " ) ;
gets ( expr ) ;

setexpr ( &q, expr ) ;
convert ( &q ) ;

printf ( "\nThe infix expression is: " ) ;
show ( q ) ;

getch( ) ;
}

/* initializes data member */
void initpostfix ( struct postfix *p )
{
p -> i = 0 ;
p -> top = -1 ;
strcpy ( p -> target, "" ) ;
}

/* copies given expression to target string */
void setexpr ( struct postfix *p, char *c )
{
strcpy ( p -> target, c ) ;
}

/* adds an expr. to the stack */
void push ( struct postfix *p, char *str )
{
if ( p -> top == MAX - 1 )
printf ( "\nStack is full." ) ;
else
{
p -> top++ ;
strcpy ( p -> stack[p -> top], str ) ;
}
}

/* pops an expr. from the stack */
void pop ( struct postfix *p, char *a )
{
if ( p -> top == -1 )
printf ( "\nStack is empty." ) ;
else
{
strcpy ( a, p -> stack[p -> top] ) ;
p -> top-- ;
}
}

/* converts given expr. to infix form */
void convert ( struct postfix *p )
{
while ( p -> target[p -> i] )
{
/* skip whitespace, if any */
if( p -> target[p -> i] == ' ' )
p -> i++ ;
if ( p -> target[p -> i] == '%' || p -> target[p -> i] == '*' ||
p -> target[p -> i] == '-' || p -> target[p -> i] == '+' ||
p -> target[p -> i] == '/' || p -> target[p -> i] == '$' )
{
pop ( p, p -> str2 ) ;
pop ( p, p -> str3 ) ;
p -> temp1[0] = p -> target[p -> i] ;
p -> temp1[1] = '\0' ;
strcpy ( p -> str1, p -> str3 ) ;
strcat ( p -> str1, p -> temp1 ) ;
strcat ( p -> str1, p -> str2 ) ;
push ( p, p -> str1 ) ;
}
else
{
p -> temp1[0] = p -> target[p -> i] ;
p -> temp1[1] = '\0' ;
strcpy ( p -> temp2, p -> temp1 ) ;
push ( p, p -> temp2 ) ;
}
p -> i++ ;
}
}

/* displays the expression */
void show ( struct postfix p )
{
char *t ;
t = p.stack[0] ;
while ( *t )
{
printf ( "%c ", *t ) ;
t++ ;
}
}

Program to convert expression in postfix form to prefix form

#include <"stdio.h">
#include <"conio.h">
#include <"string.h">

#define MAX 50

struct postfix
{
char stack[MAX][MAX], target[MAX] ;
char temp1[2], temp2[2] ;
char str1[MAX], str2[MAX], str3[MAX] ;
int i, top ;
} ;

void initpostfix ( struct postfix * ) ;
void setexpr ( struct postfix *, char * ) ;
void push ( struct postfix *, char * ) ;
void pop ( struct postfix *, char * ) ;
void convert ( struct postfix * ) ;
void show ( struct postfix ) ;

void main( )
{
struct postfix q ;
char expr[MAX] ;

clrscr( ) ;

initpostfix ( &q ) ;

printf ( "\nEnter an expression in postfix form: " ) ;
gets ( expr ) ;

setexpr ( &q, expr ) ;
convert ( &q ) ;

printf ( "\nThe Prefix expression is: " ) ;
show ( q ) ;

getch( ) ;
}

/* initializes the elements of the structure */
void initpostfix ( struct postfix *p )
{
p -> i = 0 ;
p -> top = -1 ;
strcpy ( p -> target, "" ) ;
}

/* copies given expr. to target string */
void setexpr ( struct postfix *p, char *c )
{
strcpy ( p -> target, c ) ;
}

/* adds an operator to the stack */
void push ( struct postfix *p, char *str )
{
if ( p -> top == MAX - 1 )
printf ( "\nStack is full." ) ;
else
{
p -> top++ ;
strcpy ( p -> stack[p -> top], str ) ;
}
}

/* pops an element from the stack */
void pop ( struct postfix *p, char *a )
{
if ( p -> top == -1 )
printf ( "\nStack is empty." ) ;
else
{
strcpy ( a, p -> stack[p -> top] ) ;
p -> top-- ;
}
}

/* converts given expr. to prefix form */
void convert ( struct postfix *p )
{
while ( p -> target[p -> i] != '\0' )
{
/* skip whitespace, if any */
if ( p -> target[p -> i] == ' ')
p -> i++ ;
if( p -> target[p -> i] == '%' || p -> target[p -> i] == '*' ||
p -> target[p -> i] == '-' || p -> target[p -> i] == '+' ||
p -> target[p -> i] == '/' || p -> target[p -> i] == '$' )
{
pop ( p, p -> str2 ) ;
pop ( p, p -> str3 ) ;
p -> temp1[0] = p -> target[ p -> i] ;
p -> temp1[1] = '\0' ;
strcpy ( p -> str1, p -> temp1 ) ;
strcat ( p -> str1, p -> str3 ) ;
strcat ( p -> str1, p -> str2 ) ;
push ( p, p -> str1 ) ;
}
else
{
p -> temp1[0] = p -> target[p -> i] ;
p -> temp1[1] = '\0' ;
strcpy ( p -> temp2, p -> temp1 ) ;
push ( p, p -> temp2 ) ;
}
p -> i++ ;
}
}

/* displays the prefix form of expr. */
void show ( struct postfix p )
{
char *temp = p.stack[0] ;
while ( *temp )
{
printf ( "%c ", *temp ) ;
temp++ ;
}

}

Program to convert an Infix form to Postfix form

#include
#include
#include
#include

#define MAX 50

struct infix
{
char target[MAX] ;
char stack[MAX] ;
char *s, *t ;
int top ;
} ;

void initinfix ( struct infix * ) ;
void setexpr ( struct infix *, char * ) ;
void push ( struct infix *, char ) ;
char pop ( struct infix * ) ;
void convert ( struct infix * ) ;
int priority ( char ) ;
void show ( struct infix ) ;

void main( )
{
struct infix p ;
char expr[MAX] ;

initinfix ( &p ) ;

clrscr( ) ;

printf ( "\nEnter an expression in infix form: " ) ;
gets ( expr ) ;

setexpr ( &p, expr ) ;
convert ( &p ) ;

printf ( "\nThe postfix expression is: " ) ;
show ( p ) ;

getch( ) ;
}

/* initializes structure elements */
void initinfix ( struct infix *p )
{
p -> top = -1 ;
strcpy ( p -> target, "" ) ;
strcpy ( p -> stack, "" ) ;
p -> t = p -> target ;
p -> s = "" ;
}

/* sets s to point to given expr. */
void setexpr ( struct infix *p, char *str )
{
p -> s = str ;
}

/* adds an operator to the stack */
void push ( struct infix *p, char c )
{
if ( p -> top == MAX )
printf ( "\nStack is full.\n" ) ;
else
{
p -> top++ ;
p -> stack[p -> top] = c ;
}
}

/* pops an operator from the stack */
char pop ( struct infix *p )
{
if ( p -> top == -1 )
{
printf ( "\nStack is empty.\n" ) ;
return -1 ;
}
else
{
char item = p -> stack[p -> top] ;
p -> top-- ;
return item ;
}
}

/* converts the given expr. from infix to postfix form */
void convert ( struct infix *p )
{
char opr ;

while ( *( p -> s ) )
{
if ( *( p -> s ) == ' ' || *( p -> s ) == '\t' )
{
p -> s++ ;
continue ;
}
if ( isdigit ( *( p -> s ) ) || isalpha ( *( p -> s ) ) )
{
while ( isdigit ( *( p -> s ) ) || isalpha ( *( p -> s ) ) )
{
*( p -> t ) = *( p -> s ) ;
p -> s++ ;
p -> t++ ;
}
}
if ( *( p -> s ) == '(' )
{
push ( p, *( p -> s ) ) ;
p -> s++ ;
}

if ( *( p -> s ) == '*' || *( p -> s ) == '+' || *( p -> s ) == '/' || *( p -> s ) == '%' || *( p -> s ) == '-' || *( p -> s ) == '$' )
{
if ( p -> top != -1 )
{
opr = pop ( p ) ;
while ( priority ( opr ) >= priority ( *( p -> s ) ) )
{
*( p -> t ) = opr ;
p -> t++ ;
opr = pop ( p ) ;
}
push ( p, opr ) ;
push ( p, *( p -> s ) ) ;
}
else
push ( p, *( p -> s ) ) ;
p -> s++ ;
}

if ( *( p -> s ) == ')' )
{
opr = pop ( p ) ;
while ( ( opr ) != '(' )
{
*( p -> t ) = opr ;
p -> t++ ;
opr = pop ( p ) ;
}
p -> s++ ;
}
}

while ( p -> top != -1 )
{
char opr = pop ( p ) ;
*( p -> t ) = opr ;
p -> t++ ;
}

*( p -> t ) = '\0' ;
}

/* returns the priority of an operator */
int priority ( char c )
{
if ( c == '$' )
return 3 ;
if ( c == '*' || c == '/' || c == '%' )
return 2 ;
else
{
if ( c == '+' || c == '-' )
return 1 ;
else
return 0 ;
}
}

/* displays the postfix form of given expr. */
void show ( struct infix p )
{
printf ( " %s", p.target ) ;
}

Program to convert an Infix expression to Prefix form.

#include <"stdio.h">
#include <"conio.h">
#include <"string.h">
#include <"ctype.h">

#define MAX 50

struct infix
{
char target[MAX] ;
char stack[MAX] ;
char *s, *t ;
int top, l ;
} ;

void initinfix ( struct infix * ) ;
void setexpr ( struct infix *, char * ) ;
void push ( struct infix *, char ) ;
char pop ( struct infix * ) ;
void convert ( struct infix * ) ;
int priority ( char c ) ;
void show ( struct infix ) ;

void main( )
{
struct infix q ;
char expr[MAX] ;

clrscr( ) ;

initinfix ( &q ) ;

printf ( "\nEnter an expression in infix form: " ) ;
gets ( expr ) ;

setexpr ( &q, expr ) ;
convert ( &q ) ;

printf ( "The Prefix expression is: " ) ;
show ( q ) ;

getch( ) ;
}

/* initializes elements of structure variable */
void initinfix ( struct infix *pq )
{
pq -> top = -1 ;
strcpy ( pq -> target, "" ) ;
strcpy ( pq -> stack, "" ) ;
pq -> l = 0 ;
}

/* reverses the given expression */
void setexpr ( struct infix *pq, char *str )
{
pq -> s = str ;
strrev ( pq -> s ) ;
pq -> l = strlen ( pq -> s ) ;
*( pq -> target + pq -> l ) = '\0' ;
pq -> t = pq -> target + ( pq -> l - 1 ) ;
}

/* adds operator to the stack */
void push ( struct infix *pq, char c )
{
if ( pq -> top == MAX - 1 )
printf ( "\nStack is full.\n" ) ;
else
{
pq -> top++ ;
pq -> stack[pq -> top] = c ;
}
}

/* pops an operator from the stack */
char pop ( struct infix *pq )
{
if ( pq -> top == -1 )
{
printf ( "Stack is empty\n" ) ;
return -1 ;
}
else
{
char item = pq -> stack[pq -> top] ;
pq -> top-- ;
return item ;
}
}

/* converts the infix expr. to prefix form */
void convert ( struct infix *pq )
{
char opr ;

while ( *( pq -> s ) )
{
if ( *( pq -> s ) == ' ' || *( pq -> s ) == '\t' )
{
pq -> s++ ;
continue ;
}

if ( isdigit ( *( pq -> s ) ) || isalpha ( *( pq -> s ) ) )
{
while ( isdigit ( *( pq -> s ) ) || isalpha ( *( pq -> s ) ) )
{
*( pq -> t ) = *( pq -> s ) ;
pq -> s++ ;
pq -> t-- ;
}
}

if ( *( pq -> s ) == ')' )
{
push ( pq, *( pq -> s ) ) ;
pq -> s++ ;
}

if ( *( pq -> s ) == '*' || *( pq -> s ) == '+' || *( pq -> s ) == '/' ||
*( pq -> s ) == '%' || *( pq -> s ) == '-' || *( pq -> s ) == '$' )
{
if ( pq -> top != -1 )
{
opr = pop ( pq ) ;

while ( priority ( opr ) > priority ( *( pq -> s ) ) )
{
*( pq -> t ) = opr ;
pq -> t-- ;
opr = pop ( pq ) ;
}
push ( pq, opr ) ;
push ( pq, *( pq -> s ) ) ;
}
else
push ( pq, *( pq -> s ) ) ;
pq -> s++ ;
}

if ( *( pq -> s ) == '(' )
{
opr = pop ( pq ) ;
while ( opr != ')' )
{
*( pq -> t ) = opr ;
pq -> t-- ;
opr = pop ( pq ) ;
}
pq -> s++ ;
}
}

while ( pq -> top != -1 )
{
opr = pop ( pq ) ;
*( pq -> t ) = opr ;
pq -> t-- ;
}
pq -> t++ ;
}

/* returns the priotity of the operator */
int priority ( char c )
{
if ( c == '$' )
return 3 ;
if ( c == '*' || c == '/' || c == '%' )
return 2 ;
else
{
if ( c == '+' || c == '-' )
return 1 ;
else
return 0 ;
}
}

/* displays the prefix form of given expr. */
void show ( struct infix pq )
{
while ( *( pq.t ) )
{
printf ( " %c", *( pq.t ) ) ;
pq.t++ ;
}
}

Program implements linked list as a stack.

#include <"stdio.h">
#include <"conio.h">
#include <"alloc.h">

/* structure containing data part and linkpart */
struct node
{
int data ;
struct node *link ;
} ;

void push ( struct node **, int ) ;
int pop ( struct node ** ) ;
void delstack ( struct node ** ) ;

void main( )
{
struct node *s = NULL ;
int i ;

clrscr( ) ;

push ( &s, 14 ) ;
push ( &s, -3 ) ;
push ( &s, 18 ) ;
push ( &s, 29 ) ;
push ( &s, 31 ) ;
push ( &s, 16 ) ;

i = pop ( &s ) ;
printf ( "\nItem popped: %d", i ) ;

i = pop ( &s ) ;
printf ( "\nItem popped: %d", i ) ;

i = pop ( &s ) ;
printf ( "\nItem popped: %d", i ) ;

delstack ( &s ) ;

getch( ) ;
}

/* adds a new node to the stack as linked list */
void push ( struct node **top, int item )
{
struct node *temp ;
temp = ( struct node * ) malloc ( sizeof ( struct node ) ) ;

if ( temp == NULL )
printf ( "\nStack is full." ) ;

temp -> data = item ;
temp -> link = *top ;
*top = temp ;
}

/* pops an element from the stack */
int pop ( struct node **top )
{
struct node *temp ;
int item ;

if ( *top == NULL )
{
printf ( "\nStack is empty." ) ;
return NULL ;
}

temp = *top ;
item = temp -> data ;
*top = ( *top ) -> link ;

free ( temp ) ;
return item ;
}

/* deallocates memory */
void delstack ( struct node **top )
{
struct node *temp ;

if ( *top == NULL )
return ;

while ( *top != NULL )
{
temp = *top ;
*top = ( *top ) -> link ;
free ( temp ) ;
}
}

Program implements array as a stack.

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

#define MAX 10

struct stack
{
int arr[MAX] ;
int top ;
} ;

void initstack ( struct stack * ) ;
void push ( struct stack *, int item ) ;
int pop ( struct stack * ) ;

void main( )
{
struct stack s ;
int i ;

clrscr( ) ;

initstack ( &s ) ;

push ( &s, 11 ) ;
push ( &s, 23 ) ;
push ( &s, -8 ) ;
push ( &s, 16 ) ;
push ( &s, 27 ) ;
push ( &s, 14 ) ;
push ( &s, 20 ) ;
push ( &s, 39 ) ;
push ( &s, 2 ) ;
push ( &s, 15 ) ;
push ( &s, 7 ) ;

i = pop ( &s ) ;
printf ( "\n\nItem popped: %d", i ) ;

i = pop ( &s ) ;
printf ( "\nItem popped: %d", i ) ;

i = pop ( &s ) ;
printf ( "\nItem popped: %d", i ) ;

i = pop ( &s ) ;
printf ( "\nItem popped: %d", i ) ;

i = pop ( &s ) ;
printf ( "\nItem popped: %d", i ) ;

getch( ) ;
}

/* intializes the stack */
void initstack ( struct stack *s )
{
s -> top = -1 ;
}

/* adds an element to the stack */
void push ( struct stack *s, int item )
{
if ( s -> top == MAX - 1 )
{
printf ( "\nStack is full." ) ;
return ;
}
s -> top++ ;
s -> arr[s ->top] = item ;
}

/* removes an element from the stack */
int pop ( struct stack *s )
{
int data ;
if ( s -> top == -1 )
{
printf ( "\nStack is empty." ) ;
return NULL ;
}
data = s -> arr[s -> top] ;
s -> top-- ;
return data ;
}

Program to store sparse matrix as a linked list

#include <"stdio.h">
#include <"conio.h">
#include <"alloc.h">

#define MAX1 3
#define MAX2 3

/* structure for col headnode */
struct cheadnode
{
int colno ;
struct node *down ;
struct cheadnode *next ;
} ;

/* structure for row headnode */
struct rheadnode
{
int rowno ;
struct node * right ;
struct rheadnode *next ;
} ;

/* structure for node to store element */
struct node
{
int row ;
int col ;
int val ;
struct node *right ;
struct node *down ;
} ;

/* structure for special headnode */
struct spmat
{
struct rheadnode *firstrow ;
struct cheadnode *firstcol ;
int noofrows ;
int noofcols ;
} ;

struct sparse
{
int *sp ;
int row ;
struct spmat *smat ;
struct cheadnode *chead[MAX2] ;
struct rheadnode *rhead[MAX1] ;
struct node *nd ;
} ;

void initsparse ( struct sparse * ) ;
void create_array ( struct sparse * ) ;
void display ( struct sparse ) ;
int count ( struct sparse ) ;
void create_triplet ( struct sparse *, struct sparse ) ;
void create_llist ( struct sparse * ) ;
void insert ( struct sparse *, struct spmat *, int, int, int ) ;
void show_llist ( struct sparse ) ;
void delsparse ( struct sparse * ) ;

void main( )
{
struct sparse s1, s2 ;

clrscr( ) ;

initsparse ( &s1 ) ;
initsparse ( &s2 ) ;

create_array ( &s1 ) ;

printf ( "\nElements in sparse matrix: " ) ;
display ( s1 ) ;

create_triplet ( &s2, s1 ) ;

create_llist ( &s2 ) ;
printf ( "\n\nInformation stored in linked list : " ) ;
show_llist ( s2 ) ;

delsparse ( &s1 ) ;
delsparse ( &s2 ) ;

getch( ) ;
}

/* initializes structure elements */
void initsparse ( struct sparse *p )
{
int i ;
/* create row headnodes */
for ( i = 0 ; i < MAX1 ; i++ )
p -> rhead[i] = ( struct rheadnode * ) malloc ( sizeof ( struct rheadnode ) ) ;

/* initialize and link row headnodes together */
for ( i = 0 ; i < MAX1 - 1 ; i++ )
{
p -> rhead[i] -> next = p -> rhead[i + 1] ;
p -> rhead[i] -> right = NULL ;
p -> rhead[i] -> rowno = i ;
}
p -> rhead[i] -> right = NULL ;
p -> rhead[i] -> next = NULL ;

/* create col headnodes */
for ( i = 0 ; i < MAX1 ; i++ )
p -> chead[i] = ( struct cheadnode * ) malloc ( sizeof ( struct cheadnode ) ) ;

/* initialize and link col headnodes together */
for ( i = 0 ; i < MAX2 - 1 ; i++ )
{
p -> chead[i] -> next = p -> chead[i + 1] ;
p -> chead[i] -> down = NULL ;
p -> chead[i] -> colno = i ;
}
p -> chead[i] -> down = NULL ;
p -> chead[i] -> next = NULL ;

/* create and initialize special headnode */
p -> smat = ( struct spmat * ) malloc ( sizeof ( struct spmat ) ) ;
p -> smat -> firstcol = p -> chead[0] ;
p -> smat -> firstrow = p -> rhead[0] ;
p -> smat -> noofcols = MAX2 ;
p -> smat -> noofrows = MAX1 ;
}

/* creates, dynamically the matrix of size MAX1 x MAX2 */
void create_array ( struct sparse *p )
{
int n, i ;

p -> sp = ( int * ) malloc ( MAX1 * MAX2 * sizeof ( int ) ) ;

/* get the element and store it */
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 of triplet containing info. about non-zero elements */
void create_triplet ( struct sparse *p, struct sparse s )
{
int r = 0 , c = -1, l = -1, i ;

p -> row = count ( s ) ;
p -> sp = ( int * ) malloc ( p -> row * 3 * sizeof ( int ) ) ;

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 ) ;
}
}
}

/* stores information of triplet in a linked list form */
void create_llist ( struct sparse *p )
{
int j = 0, i ;
for ( i = 0 ; i < p -> row ; i++, j+= 3 )
insert ( p, p -> smat, * ( p -> sp + j ), * ( p -> sp + j + 1 ),
* ( p -> sp + j + 2) ) ;
}

/* inserts element to the list */
void insert ( struct sparse *p, struct spmat *smat , int r, int c, int v )
{
struct node *temp1, *temp2 ;
struct rheadnode *rh ;
struct cheadnode *ch ;
int i, j ;

/* allocate and initialize memory for the node */
p -> nd = ( struct node * ) malloc ( sizeof ( struct node ) ) ;
p -> nd -> col = c ;
p -> nd -> row = r ;
p -> nd -> val = v ;

/* get the first row headnode */
rh = smat -> firstrow ;

/* get the proper row headnode */
for ( i = 0 ; i < r ; i++ )
rh = rh -> next ;
temp1 = rh -> right ;

/* if no element added in a row */
if ( temp1 == NULL )
{
rh -> right = p -> nd ;
p -> nd -> right = NULL ;
}
else
{
/* add element at proper position */
while ( ( temp1 != NULL ) && ( temp1 -> col < c ) )
{
temp2 = temp1 ;
temp1 = temp1 -> right ;
}
temp2 -> right = p -> nd ;
p -> nd -> right = NULL ;
}

/* link proper col headnode with the node */
ch = p -> smat -> firstcol ;
for ( j = 0 ; j < c ; j++ )
ch = ch -> next ;
temp1 = ch -> down ;

/* if col not pointing to any node */
if ( temp1 == NULL )
{
ch -> down = p -> nd ;
p -> nd -> down = NULL ;
}
else
{
/* link previous node in column with next node in same column */
while ( ( temp1 != NULL ) && ( temp1 -> row < r ) )
{
temp2 = temp1 ;
temp1 = temp1 -> down ;
}
temp2 -> down = p -> nd ;
p -> nd -> down = NULL ;
}
}

void show_llist ( struct sparse s )
{
struct node *temp ;
/* get the first row headnode */
int r = s.smat -> noofrows ;
int i ;

printf ( "\n" ) ;

for ( i = 0 ; i < r ; i++ )
{
temp = s.rhead[i] -> right ;
if ( temp != NULL )
{
while ( temp -> right != NULL )
{
printf ( "Row: %d Col: %d Val: %d\n", temp -> row, temp -> col,
temp -> val ) ;
temp = temp -> right ;
}
if ( temp -> row == i )
printf ( "Row: %d Col: %d Val: %d\n", temp -> row, temp -> col,
temp -> val ) ;
}
}
}

/* deallocates memory */
void delsparse ( struct sparse *p )
{
int r = p -> smat -> noofrows ;
struct rheadnode *rh ;
struct node *temp1, *temp2 ;
int i, c ;

/* deallocate memeory of nodes by traversing rowwise */
for ( i = r - 1 ; i >= 0 ; i-- )
{
rh = p -> rhead[i] ;
temp1 = rh -> right ;

while ( temp1 != NULL )
{
temp2 = temp1 -> right ;
free ( temp1 ) ;
temp1 = temp2 ;
}
}

/* deallocate memory of row headnodes */
for ( i = r - 1 ; i >= 0 ; i-- )
free ( p -> rhead[i] ) ;

/* deallocate memory of col headnodes */
c = p -> smat -> noofcols ;
for ( i = c - 1 ; i >= 0 ; i-- )
free ( p -> chead[i] ) ;
}

Program to multiply two sparse matrices

#include
#include
#include

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