DataStructure 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++ ;
}
}

DataStructure Program to merge two 1-D arrays

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

#include <alloc.h>
#define MAX1 5
#define MAX2 7
int *arr ;
int* create ( int ) ;
void sort ( int *, int ) ;
void display ( int *, int ) ;
int* merge ( int *, int * ) ;
void main( )
{
int *a, *b, *c ;
clrscr( ) ;
printf ( "\nEnter elements for first array: \n\n" ) ;
a = create ( MAX1 ) ;
printf ( "\nEnter elements for second array: \n\n" ) ;
b = create ( MAX2 ) ;
sort ( a, MAX1 ) ;
sort ( b, MAX2 ) ;
printf ( "\nFirst array: \n" ) ;
display ( a, MAX1 ) ;
printf ( "\n\nSecond array: \n" ) ;
display ( b, MAX2 ) ;
printf ( "\n\nAfter Merging: \n" ) ;
c = merge ( a, b ) ;
display ( c, MAX1 + MAX2 ) ;
getch( ) ;
}
/* creates array of given size, dynamically */
int* create ( int size )
{
int *arr, i ;
arr = ( int * ) malloc ( sizeof ( int ) * size ) ;
for ( i = 0 ; i < size ; i++ )
{
printf ( "Enter the element no. %d: ", i + 1 ) ;
scanf ( "%d", &arr[i] ) ;
}
return arr ;
}
/* sorts array in ascending order */
void sort ( int *arr, int size )
{
int i, temp, j ;
for ( i = 0 ; i < size ; i++ )
{
for ( j = i + 1 ; j < size ; j++ )
{
if ( arr[i] > arr[j] )
{
temp = arr[i] ;
arr[i] = arr[j] ;
arr[j] = temp ;
}
}
}
}
/* displays the contents of array */
void display ( int *arr, int size )
{
int i ;
for ( i = 0 ; i < size ; i++)
printf ( "%d\t", arr[i] ) ;
}
/* merges two arrays of different size */
int* merge ( int *a, int *b )
{
int *arr ;
int i, k, j ;
int size = MAX1 + MAX2 ;
arr = ( int * ) malloc ( sizeof ( int ) * ( size ) ) ;
for ( k = 0, j = 0, i = 0 ; i <= size ; i++ )
{
if ( a[k] < b[j] )
{
arr[i] = a[k] ;
k++ ;
if ( k >= MAX1 )
{
for ( i++ ; j < MAX2 ; j++, i++ )
arr[i] = b[j] ;
}
}
else
{
arr[i] = b[j] ;
j++ ;
if ( j >= MAX2 )
{
for ( i++ ; k < MAX1 ; k++, i++ )
arr[i] = a[k] ;
}
}
}
return arr ;
}

DataStructure-Program to merge two linked list

 

#include <stdio.h>
#include <conio.h>
#include <alloc.h>
/* structure containing a data part and link part */
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 ) ) ;
}
/* adds node to an ascending order linked list */
void add ( struct node **q, int num )
{
struct node *r, *temp = *q ;
r = malloc ( sizeof ( struct node ) ) ;
r -> data = num ;
/* if list is empty or if new node is to be inserted before the first node */
if ( *q == NULL || ( *q ) -> data > num )
{
*q = r ;
( *q ) -> link = temp ;
}
else
{
/* traverse the entire linked list to search the position to insert the new node */
while ( temp != NULL )
{
if ( temp -> data < num && ( temp -> link -> data > num || temp -> link == NULL ))
{
r -> link = temp -> link ;
temp -> link = r ;
return ;
}
temp = temp -> link ; /*go to next node */
}
r -> link = NULL ;
temp -> link = r ;
}
}
/* displays the contents of the linked list */
void display ( struct node *q )
{
printf ( "\n" ) ;
/* traverse the entire linked list */
while ( q != NULL )
{
printf ( "%d ", q -> data ) ;
q = q -> link ;
}
}
/* counts the number of nodes present in the linked list */
int count ( struct node * q )
{
int c = 0 ;
/* traverse the entire linked list */
while ( q != NULL )
{
q = q -> link ;
c++ ;
}
return c ;
}
/* merges the two linked lists, restricting the common elements to occur only once in the final list */
void merge ( struct node *p, struct node *q, struct node **s )
{
struct node *z ;
z = NULL ;
/* if both lists are empty */
if ( p == NULL && q == NULL )
return ;
/* traverse both linked lists till the end. If end of any one list is reached loop is terminated */
while ( p != NULL && q != NULL )
{
/* if node being added in the first node */
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 ;
}
}
}
}
/* if end of first list has not been reached */
while ( p != NULL )
{
z -> link = malloc ( sizeof ( struct node ) ) ;
z = z -> link ;
z -> data = p -> data ;
p = p -> link ;
}
/* if end of second list has been reached */
while ( q != NULL )
{
z -> link = malloc ( sizeof ( struct node ) ) ;
z = z -> link ;
z -> data = q -> data ;
q = q -> link ;
}
z -> link = NULL ;
}

DataStructure Program to maintain an AVL tree

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

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

DataStructure Program to implement a circular queue as a linked list

DataStructure-Program to implement a circular queue as a linked list.

#include <stdio.h>
#include <conio.h>
#include <alloc.h>
/* structure containing a data part and link part */
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 ) ;
}
/* adds a new element at the end of queue */
void addcirq ( struct node **f, struct node **r, int item )
{
struct node *q ;
/* create new node */
q = malloc ( sizeof ( struct node ) ) ;
q -> data = item ;
/* if the queue is empty */
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 queue is empty */
if ( *f == NULL )
printf ( "queue is empty" ) ;
else
{
if ( *f == *r )
{
item = ( *f ) -> data ;
free ( *f ) ;
*f = NULL ;
*r = NULL ;
}
else
{
/* delete the node */
q = *f ;
item = q -> data ;
*f = ( *f ) -> link ;
( *r ) -> link = *f ;
free ( q ) ;
}
return ( item ) ;
}
return NULL ;
}
/* displays whole of the queue */
void cirq_display ( struct node *f )
{
struct node *q = f, *p = NULL ;
/* traverse the entire linked list */
while ( q != p )
{
printf ( "%d\t", q -> data ) ;
q = q -> link ;
p = f ;
}
}

DataStructure Program to maintain a double linked list

#include <stdio.h>
#include <conio.h>
#include <alloc.h>
/* structure representing a node of the doubly linked list */
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 ) ) ;
}
/* adds a new node at the end of the doubly linked list */
void d_append ( struct dnode **s, int num )
{
struct dnode *r, *q = *s ;
/* if the linked list is empty */
if ( *s == NULL )
{
/*create a new node */
*s = malloc ( sizeof ( struct dnode ) ) ;
( *s ) -> prev = NULL ;
( *s ) -> data = num ;
( *s ) -> next = NULL ;
}
else
{
/* traverse the linked list till the last node is reached */
while ( q -> next != NULL )
q = q -> next ;
/* add a new node at the end */
r = malloc ( sizeof ( struct dnode ) ) ;
r -> data = num ;
r -> next = NULL ;
r -> prev = q ;
q -> next = r ;
}
}
/* adds a new node at the begining of the linked list */
void d_addatbeg ( struct dnode **s, int num )
{
struct dnode *q ;
/* create a new node */
q = malloc ( sizeof ( struct dnode ) ) ;
/* assign data and pointer to the new node */
q -> prev = NULL ;
q -> data = num ;
q -> next = *s ;
/* make new node the head node */
( *s ) -> prev = q ;
*s = q ;
}
/* adds a new node after the specified number of nodes */
void d_addafter ( struct dnode *q, int loc, int num )
{
struct dnode *temp ;
int i ;
/* skip to desired portion */
for ( i = 0 ; i < loc ; i++ )
{
q = q -> next ;
/* if end of linked list is encountered */
if ( q == NULL )
{ printf ( "\nThere are less than %d elements", loc );
return ;
}
}
/* insert new node */
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 ;
}
/* displays the contents of the linked list */
void d_display ( struct dnode *q )
{
printf ( "\n" ) ;
/* traverse the entire linked list */
while ( q != NULL )
{
printf ( "%2d\t", q -> data ) ;
q = q -> next ;
}
}
/* counts the number of nodes present in the linked list */
int d_count ( struct dnode * q )
{
int c = 0 ;
/* traverse the entire linked list */
while ( q != NULL )
{
q = q -> next ;
c++ ;
}
return c ;
}
/* deletes the specified node from the doubly linked list */
void d_delete ( struct dnode **s, int num )
{
struct dnode *q = *s ;
/* traverse the entire linked list */
while ( q != NULL )
{
/* if node to be deleted is found */
if ( q -> data == num )
{
/* if node to be deleted is the first node */
if ( q == *s )
{
*s = ( *s ) -> next ;
( *s ) -> prev = NULL ;
}
else
{
/* if node to be deleted is the last node */
if ( q -> next == NULL )
q -> prev -> next = NULL ;
else
/* if node to be deleted is any intermediate node */
{
q -> prev -> next = q -> next ;
q -> next -> prev = q -> prev ;
}
free ( q ) ;
}
return ; /* return back after deletion */
}
q = q -> next ; /* go to next node */
}
printf ( "\n%d not found.", num ) ;
}