IZEE BSCHOOL BANGALORE

DEPARTMENT OF COMPUTER
SCIENCE
Bachelor of Computer Applications

DATA STRUCTURES LAB Manual

1. Given {4,7,3,2,1,7,9,0 } find the location of 7 using linear and binary search and
also display its first occurrence.

void linearsearch(int a[10], int n, int key)

{
int i, found=0;
for(i=0;i<n;i++)
{

,
Qif(key==a[i])
{
printf("\n %d found at %d",key,i+1);
found=1;
break;
}
}
if(found==0)
printf("Element not found in the list\n");
}
void binarysearch(int a[10],int key,int first,int last)
{
int mid;
mid=(first+last)/2;
while (first<=last)
{
if (a[mid]==key)
{
printf("%d found at location %d\n", key, mid+1);
break;
}
else if (a[mid]< key)
{
first = mid + 1;
mid=(first+last)/2;
}
else
{
last = mid - 1;
mid=(first+last)/2;
}
}
if(first>last)
printf("Not found! %d isn't present in the list", key);
}
void display_array(int a[10], int n)
{
int i;
printf("Given Array :\n");
for(i=0;i<n;i++)
{
printf("%3d",a[i]);
}
}
void main()
{
int a[8]={4,7,3,2,1,7,9,0};
int n=8,i,j,temp;
int key=7;
int choice;
clrscr();
printf(" \n 1. Binary search\n");
printf(" 2. linear search\n");
printf(" Enter your choice :\n");
scanf("%d",&choice);
switch(choice)
{
case 1: {
display_array(a,n);
printf("\nArrange the elements in ascending order\n");
for (i=0; i<n-1; i++)
{
for (j=0; j<n-i-1; j++)
{
if (a[j] > a[j+1]) /* For decreasing order use '<' instead of '>' */
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
printf("Sorted list in ascending order:\n");

for (i=0; i<n; i++)

printf("%d\n", a[i]);
binarysearch(a,key,0,n-1);
break;
}
case 2: {
display_array(a,n);
linearsearch(a,n,key);
break;
}
default: printf(" invalid choice\n");
}
getch();
}
Output:
2. Given {5, 3, 1, 6, 0, 2,4} order the numbers in ascending order using Bubble
Sort Algorithm.

#include<stdio.h>
#include<conio.h>
void Bubblesort( int a[], int n)
{
int pass,temp,i,j;
for (pass=1;pass<=n-1;pass++)
{
for(j=0;j<n-pass-1;j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
printf("\n Array after %d pass--->",pass);
for(i=0;i<n;i++)
printf("%d,",a[i]);
}
}
void main()
{
int a[]={5,3,1,6,0,2,4};
int n=7;
clrscr();
printf("\n input arrays:5 3 1 6 0 2 4 ");
Bubblesort(a,n);
getch();
}
 Output:

3(a). Perform the Insertion sort on the input {75,8,1,16,48,3,7,0} and display the
output in descending order.
/*C program to perform Insertion sort */
# include<stdio.h>
# include<conio.h>
void INSERTION_SORT(int a[], int n)
{
int pass,k,temp,i,j;
for(pass=1;pass<n;pass++)
{
k=a[pass];
for(j=pass-1;j>=0 && k<a[j];j--)
{
a[j+1] = a[j];
}
a[j+1]=k;
printf("\n\n Sorted arrays after %d pass -->",pass);
for(i=0;i<n;i++)
printf("%d,",a[i]);
}
printf("\n\n Sorted arrays using Insertion sort in Descending Order\
n"); for(i=n-1;i>=0;i--)
{
printf("%d,",a[i]);
 }
}
void main()
{
int a[8]={75,8,1,16,48,3,7,0};
int n=8;
clrscr();
printf("\n Input arrays :
75,8,1,16,48,3,7,0");
INSERTION_SORT(a,n);
getch();
}

Output:
Output:
3(b). Perform the Selection sort on the input {75,8,1,16,48,3,7,0} and display the
output in descending order.

/*C program to perform Selection

sort*/ # include<stdio.h>
# include<conio.h>
// Selection sort
int MIN(int a[],int k, int n)
{
int loc,j,min;
min=a[k];
loc=k;
for(j=k+1;j<=n-1;j++)
{
if(min>a[j])
{
min=a[j];
loc=j;
}
}
return(loc);
}
void SELECTION_SORT(int a[], int k, int n)
{
int i,loc,temp;
for(k=0;k<n;k++)
{
loc=MIN(a,k,n);
temp=a[k];
a[k]=a[loc];
a[loc]=temp;
printf("\n\nSorted arrays after %d pass:-->",k);
for(i=0;i<n;i++)
printf("%d,",a[i]);
}
printf("\n\n Sorted arrays using Selection sort in Descending Order\n");
 for(i=n-1;i>=0;i--)
{
printf("%d,",a[i]);
}
}
void main()
{
int a[8]={75,8,1,16,48,3,7,0};
int n=8;
clrscr();
printf("\n Input arrays :
75,8,1,16,48,3,7,0");
SELECTION_SORT(a,0,n);
getch();
}

Output:
4. Write a program to insert the elements {61, 16, 8,27} into singly
linked list and delete 8,61,27 from the list. Display your list after each
insertion and deletion.

// C program to insert {61,16,8,27} and delete {8,61,27} from the

list. # include<stdio.h>
# include<conio.h>
# include<alloc.h>
# include<ctype.h>
typedef struct
node
{
int info;
struct node *link;
}NODE;
NODE *header=NULL;
void DISPLAY()
{
NODE *start=header;
printf("\n *** LIST *** : ");
while(start!=NULL)
{
printf("%4d",start->info);
start=start->link;
}
}
void INSERT(int item)
{
NODE *newnode,*curptr;
newnode = (NODE *)
malloc(sizeof(NODE)); newnode-
>info=item;
newnode->link=NULL;
if(header==NULL)
header=newnode;
 else
{
curptr=header;
while(curptr->link !
=NULL)
{
curptr=curptr->link;
}
curptr->link=newnode;
}
DISPLAY();
}
void DELETE(int item)
{
NODE *curptr=header,
*prevptr=header; if(header==NULL)
{
printf("\n EMPTY LIST");
}
else if(header->info==item)
{
header=header->link;
free(curptr);
}
else
{
while(curptr!=NULL)
{
if(curptr->info==item)
{
prevptr->link=curptr->link;
free(curptr);
curptr=curptr->link->link;
}
else
 {
prevptr=curptr;
curptr=curptr->link;
}
}
}
DISPLAY();
}
void main()
{
int item,choice;
clrscr();
printf("\n Insertion
:"); INSERT(61);
INSERT(16);
INSERT(8);
INSERT(27);
printf("\n Deletion :");
DELETE(8);
DELETE(61);
DELETE(27);
getch();
}

Output:
5. Write a program to insert the elements {61,16,8,27} into linear queue
and delete three elements from the list. Display your list after each insertion
and deletion.

// Program to insert the elements {61,16,8,27} into linear queue

// delete three elements from the
list #include <stdio.h>
#define MAX 50
int queue_array[MAX];
int rear = - 1;
int front = - 1;
void display()
{
int i;
if (front == - 1) printf("\
nQueue is empty \n"); else
{
printf("\nQueue is : \n");
for (i = front; i <= rear; i++)
printf("%d ", queue_array[i]);
}
getch();
}
void insert_Q(int item)
{
if (rear == MAX - 1)
printf("Queue Overflow \n");
else
{
if (front == - 1)
front = 0;
rear = rear + 1;
queue_array[rear] = item;
 }
display();
}
void delete_Q()
{
if (front == - 1 || front > rear)
{
printf("\nQueue Underflow ");
return ;
}
else
{
printf("\nElement deleted from queue is : %d", queue_array[front]);
front = front + 1;
}
display();
}
void main()
{
int choice;
clrscr();
insert_Q(61);
insert_Q(16);
insert_Q(8);
insert_Q(27);
delete_Q();
delete_Q();
delete_Q();
getch();
}
Output:

6. Write a program to insert the elements {61, 16,8,27} into circular queue and
delete 4 elements from the list.Display your list after each insertion and deletion.

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<malloc.h>
void CQdisplay();
void CQdelete();
void CQinsert(int item);

struct queue
{
int info;
struct queue *link;
};
struct queue *front=NULL,*rear=NULL;
void CQinsert(int item)
{
struct queue *newnode;
newnode=(struct queue*)malloc(sizeof(struct
queue)); newnode->info=item;
newnode->link=NULL;
if(front==NULL && rear==NULL)
{
front=rear=newnode;
rear->link=front;
}
else
{
rear->link=newnode;
rear=newnode;
rear->link=front;
}
}
void CQdelete()
{
struct queue *ptr;
ptr=front;
if(front==NULL && rear==NULL)
printf("\n Queue is empty");
else if(front==rear)
{
front=rear=NULL;
printf("\n the value being deleted is: %d",ptr->info);
free(ptr);
}
else
{
front=front->link;
rear->link=front;
printf("\n thevalue being deleted is :%d",ptr->info);
free(ptr);
}
}
void CQdisplay()
{
struct queue *ptr;
ptr=front;
if(front==NULL&&rear==NULL) printf("\
n Queue is empty");
else
{
printf("\n the queue elements are:");
do
{
printf("%d\t",ptr->info);
ptr=ptr->link;
}while(ptr!=front);
}
}
void main()
{
int val,choice;
clrscr();
do
{
printf("\n 1. Insert 2.delete 3.display
4.exit"); printf("\n Enter your choice: ");
scanf("%d",&choice);
switch(choice)
{
case 1: printf(" \n Enter the elemnets to insert into queue:");
scanf("%d",&val);
CQinsert(val);

break;
case 2: CQdelete();

break;

case 3:
CQdisplay();
break;
}
}while(choice!=4);
getch();
}
Output:
7. Write a program to insert the elements {61, 16, 8,27} into ordered singly
linked list and delete 8,61,27 from the list. Display your list after each insertion
and deletion.

// C program to insert {61, 16, 8, 27} in the ordered singly linked list
// and delete 8,61,27 from the
list. # include<stdio.h>
# include<conio.h>
typedef struct
node
{
int info;
 struct node *link;
}NODE;
NODE *header;
void CREATE_HEADER()
{
header = (NODE *)
malloc(sizeof(NODE)); header->info=0;
header->link=NULL;
}
void INSERT_ORDERLIST(int item)
{
NODE *NEWNODE, *PREVPTR, *CURPTR;
NEWNODE = (NODE *)
malloc(sizeof(NODE)); NEWNODE->info =
item;
NEWNODE->link = NULL;
if(header->link==NULL)
{
header->link=NEWNODE;
}
else if(item < header->info)
{
NEWNODE->link=header;
header=NEWNODE;
}
else
{
PREVPTR=header;
CURPTR=header->link;
while(CURPTR!=NULL && item > CURPTR->info)
{
PREVPTR=CURPTR;
CURPTR=CURPTR->link;
}
PREVPTR->link=NEWNODE;
NEWNODE->link=CURPTR;
}
}
void DISPLAY_NODE()
{
NODE *CURPTR;
CURPTR=header->link;
printf("\n LIST : ");
while(CURPTR!=NULL)
{
printf("%d->",CURPTR->info);
CURPTR=CURPTR->link;
}
}
void DELETE_NODE(int item)
{
NODE *PREVPTR, *CURPTR;
PREVPTR=header;
CURPTR=header->link;
if(item == header->info)
{
header=CURPTR;
free(PREVPTR);
}
else
{
while(CURPTR!=NULL && CURPTR->info !=item)
{ PREVPTR=CURPT
R;
CURPTR=CURPTR->link;
} if(CURPTR!
=NULL)
{
PREVPTR->link=CURPTR->link;
free(CURPTR);
}
 else
printf("\n Data not found");
}
}
void main()
{
clrscr();
CREATE_HEADER();
printf("\n *** INSERTING 61,16,8,27 : ***");
INSERT_ORDERLIST(61);
DISPLAY_NODE();
INSERT_ORDERLIST(16);
DISPLAY_NODE();
INSERT_ORDERLIST(8);
DISPLAY_NODE();
INSERT_ORDERLIST(27);
DISPLAY_NODE();
printf("\n *** DELETE 8,61,27 : ***");
DELETE_NODE(8);
DISPLAY_NODE();
DELETE_NODE(61);
DISPLAY_NODE();
DELETE_NODE(27);
DISPLAY_NODE();
getch();
}
Output:
8. Write a program to add 6x3+10x2+0x+5 and 4x2+2x+1 using linked list.
/*WAP to add Polynomial using linked
list*/ #include<stdio.h>
#include<stdlib.h>
#include<conio.h>
struct polynomial
{
int coeff;
int power;
struct polynomial *LINK;
};
typedef struct polynomial NODE;
NODE *poly1=NULL,*poly2=NULL,*poly3 = NULL;
NODE *create_poly();
NODE *add_poly(NODE *poly1,NODE *poly2);
void display_poly(NODE *ptr);
NODE *create_poly()
{
int flag;
int coeff,pow;
NODE *tmp_node =(NODE *)malloc(sizeof(NODE));//create thefirst node
NODE *poly=tmp_node;
do
{
printf("\n Enter coeff:");
scanf("%d",&coeff);
tmp_node->coeff=coeff;
printf("\n Enter Pow:");
scanf("%d",&pow);
tmp_node->power = pow;
tmp_node->LINK=NULL;
printf("\n Do you want to add more terms? (Y=1/N=0):");
scanf("%d",&flag);
if(flag==1)
{
tmp_node->LINK=(NODE *) malloc(sizeof(NODE));
tmp_node = tmp_node->LINK;
tmp_node -> LINK = NULL;
}
} while(flag);
return poly;
}
NODE *add_poly(NODE *poly1, NODE *poly2)
{
NODE *tmp_node,*poly;//Temporary storage for the linked list
tmp_node=(NODE *)malloc(sizeof(NODE));
tmp_node->LINK = NULL;
poly3=tmp_node;
while(poly1&&poly2)
{
if(poly1->power > poly2->power)
{
tmp_node->power=poly1->power;
tmp_node->coeff=poly1->coeff;
poly1=poly1->LINK;
}
else if (poly1->power < poly2->power)
{
tmp_node->power = poly2->
power; tmp_node->coeff =poly2-
>coeff; poly2 = poly2->LINK;
}
else
{
tmp_node->power = poly1->power;
tmp_node->coeff = poly1->coeff+poly2->coeff;
poly1=poly1->LINK;
poly2=poly2->LINK;
}
if(poly1&&poly2)
{
tmp_node->LINK=(NODE *)malloc(sizeof(NODE));
tmp_node=tmp_node->LINK;
tmp_node->LINK=NULL;
}
}
while(poly1||poly2)
{
tmp_node->LINK =(NODE
*)malloc(sizeof(NODE)); tmp_node=tmp_node-
>LINK;
tmp_node->LINK=NULL;
if(poly1)
{
tmp_node->power=poly1->power;
tmp_node->coeff=poly1->coeff;
poly1=poly1->LINK;
}
if(poly2)
{
tmp_node->power=poly2->power;
tmp_node->coeff=poly2->coeff;
poly2=poly2->LINK;
}
}
}
void display(NODE *ptr)
{
while(ptr!=NULL)
{
printf("%dX^%d",ptr->coeff,ptr->power);
ptr=ptr->LINK;
if(ptr!=NULL)
printf(" + ");
}
}
void main()
{
clrscr();
printf("\n Create 1st Polynomial: ");
poly1=create_poly();
printf("\n First polynomial : ");
display(poly1);
printf("\n Create 2nd Polynomial:");
poly2=create_poly();
printf("\n Second polynomial :");
display(poly2);
add_poly(poly1,poly2);
printf("\n Addition of Two polynomials :
"); display(poly3);
getch();
}

Output:
 9. Write a program to push 5, 9,34,17,32 into stack and pop 3 times from the stack,
also display the poppednumbers
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define MAXSTK 5
int TOP=-1;
int s[MAXSTK];
void push();
void pop();
void display();
void main()
{
int choice;
clrscr();
while(1)
{
printf(" 1.push 2.pop 3.display 4.quit\n");
printf("Enter your choice");
scanf("%d",&choice);
switch(choice)
{
case 1: push();
break;
case 2: pop();
break;
case 3: display();
break;
case 4: exit(1);
default : printf(" wrong choice \n");
}
}
getch();
}
void push()
{
int item;
if(TOP==(MAXSTK-1))
printf(" stack overflow \n");
else
{
printf(" Enter the item to be pushed in stack:");
scanf(" %d",&item);
TOP=TOP+1;
s[TOP]=item;
}
}
void pop()
{
if(TOP==-1)
printf("stack underflow\n");
else
{
printf("popped element is : %d \n",s[TOP]);
TOP=TOP-1;
}
}
void display()
{
int i;
if(TOP==-1)
printf("Stack is empty \n");
else
{
printf("Stack elements :\
n"); for(i=TOP;i>=0;i--)
printf("%d\n",s[i]);
}
}
Output:
10. Write a recursive program to find GCD of 4,6,8.
// C program to find GCD (4,6,8) using recursion.
# include<stdio.h>
# include<conio.h>
int GCD(int m, int n)
{
if(n==0)
return(m);
else if(n>m)
return(GCD(n,m));
else
return(GCD(n,m%n));
}
void main()
{
int gcd12, gcd3;
clrscr();
gcd12=GCD(4,6);
printf("\n GCD between 4 & 6 =
%d",gcd12); gcd3=(GCD(gcd12,8));
printf("\n GCD between 4,6 & 8 =
%d",gcd3); getch();
}
Output:

11. Write a program to insert the elements {5,7,0,6,3,9} into circular queue
and delete 6,9&5 from it( using linked list implementation)…

#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#include<stdlib.h>
struct queue
{
int info;
struct queue *link;
};
struct queue *front=NULL,*rear=NULL;
void Qinsert(int item)
{
struct queue *new_node;
new_node=(struct queue*)malloc(sizeof(struct
queue)); new_node->info=item;
new_node->link=NULL;
if(front==NULL && rear==NULL)
{
front=rear=new_node;
rear->link=front;
}
else
{
rear->link=new_node;
rear=new_node;
rear->link=front;
}
}
void Qdelete()
{
struct queue *ptr;
ptr=front;
if(front==NULL && rear==NULL)
printf("\n Queue is empty");
else if(front==rear)
{
front=rear=NULL;
printf("\n The value being deleted is : %d", ptr->info);
free(ptr);
}
else
{
front=front->link;
rear->link=front;
printf("\n the value being deleted is : %d",ptr->info);
free(ptr);
}
}
void display()
{
struct queue *ptr;
ptr=front;
if(front==NULL && rear== NULL)
printf("\n Queue is empty:");
else
{
printf("\n The queue elements are
:"); do
{
printf("%d\t",ptr->info);
ptr=ptr->link;
}while(ptr!=front);
}
}
void main()
{
int val, choice;
clrscr();
do
{
printf("\n ***** main
menu************"); printf("\n 1. insert
2.delete 3.display 4.exit"); printf("\n Enter
your choice:");
scanf("%d",&choice);
switch(choice)
{
case 1: printf("\n Enter the number to insert into queue:");
scanf("%d",&val);
Qinsert(val);
break;
case 2: Qdelete();
break;
case 3: display();
break;
}
}while(choice!=4);
getch();
}
Output:
12. Write a program to convert an infix expression x^y/(5*z)+2 to its
postfix expression.
#include <stdio.h>
#include <ctype.h>
#define SIZE 50
char stack[SIZE];
int top=-1;
int push(char elem)
{
stack[++top]=elem;
return 0;
}
char pop()
{
return(stack[top--]);
}
int pr(char symbol)
{
if(symbol == '^')
{
return(3);
}
else if(symbol == '*' || symbol == '/')
{
return(2);
}
else if(symbol == '+' || symbol == '-')
{
return(1);
}
else
{
return(0);
}
}
void main()
{
char infix[50],postfix[50],ch,elem;
int i=0,k=0;
clrscr();
printf("Enter Infix Expression : ");
scanf("%s",infix);
push('#');
while( (ch=infix[i++]) != '\0')
{
if( ch == '(') push(ch);
else
if(isalnum(ch)) postfix[k++]=ch;
else
if( ch == ')')
{
while( stack[top] != '(')
postfix[k++]=pop();
elem=pop();
}
else
{
while( pr(stack[top]) >= pr(ch)
) postfix[k++]=pop();
push(ch);
}
}
while( stack[top] != '#')
postfix[k++]=pop();
postfix[k]='\0';
 printf("\nPostfix Expression = %s\n",postfix);
getch();
}
Output:

13. Write a program to evaluate a postfix expression 5 3+8 2 -

*. #include<stdio.h>
#include<conio.h>
int stack[20];
int top = -1;
void push(int
x)
{
stack[++top] = x;
}
int pop()
{
return stack[top--];
}
void main()
{
char *postfix;
int A,B,RES,num;
clrscr();
printf("Enter the expression ::
"); scanf("%s",postfix);
while(*postfix != '\0')
{
if(isdigit(*postfix))
{
num = *postfix - 48; // converting char into num
push(num);
}
 else
{
A = pop();
B = pop();
switch(*postfix)
{
case '+': RES = B + A; break;
case '-': RES = B - A; break;
case '*': RES = B * A; break;
case '/': RES = B / A; break;
}
push(RES);
}
postfix++;
}
printf("\nThe result of expression = %d\n\n",pop());
getch();
}
Output:

15. Write a program to create binary search tree with the elements {2,5,1,3,9,0,6} and perform
inorder, preorderand post order traversal.
#include<stdio.h>
#include<stdlib.h>
void inorder( );
void preorder();
void postorder();
void disp();
void create();
struct node
{
struct node *left;
struct node * right;
int info;
};
typedef struct node NODE;
NODE *root=NULL;
void main()
{
int item, ch,n,i;
clrscr();
printf(" binary search
tree"); while(1)
{
printf(" \n1.insert 2.display 3.inorder 4.preorder 5. postorder 6.exit");
printf("\n enter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1 : printf("\n enter the no of nodes:");
scanf("%d", &n);
for(i=0;i<n;i++)
{
printf(" \n enter the data for node: ");
scanf("%d",&item);
create(item);
}
break;
case 2: printf(" \n the binary tree nodes:\n\n\n\n");
disp(root,1);
break;
case 3 : printf("\n preorder traversal is: ");
preorder(root);
break;
case 4 : printf("\n inorder traversal is:");
inorder(root);
break;
case 5 : printf(" \n post order traversal is: ");
postorder(root);
break;
case 6 : exit(1);
}
}
}
void create(int item)
{

NODE *newnode, *currptr, *ptr;

newnode=(NODE
*)malloc(sizeof(NODE)); newnode-
>info=item;
newnode->left=NULL;
newnode->right=NULL;
if(root==NULL)
root=newnode;
else
{
currptr=root; while(currptr!
=NULL)
{
ptr=currptr;
currptr=(item>currptr->info)? currptr->right:currptr->left;
}
if(item<ptr->info)
ptr->left=newnode;
else
ptr->right=newnode;
}
}
void disp(struct node * ptr,int level)
{
int i; if(ptr!
=NULL)
{
disp(ptr->right,level+1);
for(i=0;i<level;i++)
printf(" "); printf("%2d\
n",ptr->info); disp(ptr-
>left, level+1);
}
}
void preorder( struct node *ptr)
{
if(ptr)
{
printf("%d\t", ptr->info);
preorder(ptr->left);
preorder(ptr->right);
}
}
void inorder(struct node *ptr)
{
if(ptr)
{
inorder(ptr->left);
printf("%d\t", ptr->info);
inorder(ptr->right);
}
}
void postorder(struct node *ptr)
{
if(ptr)
{
postorder(ptr->left);
postorder(ptr->right);
printf("%d\t",ptr->info);
}
}
Output:
16. Write a program to Sort the following elements using heap sort {9.16, 32, 8, 4,
1, 5, 8, 0}

// Heap Sort
# include<stdio.h>
void heapify(int a[], int n, int i)
{
int largest = i;
int left = 2 * i + 1;
int right = 2 * i +
2;
if(left < n && a[left] > a[largest])
{
largest = left;
}
if(right < n && a[right] > a[largest])
{
largest = right;
}
if(largest !=i)
{
int temp;
temp = a[i];
a[i] = a[largest];
a[largest] = temp;
heapify(a,n,largest);
}
}
void HEAPSORT(int a[], int n)
{
int i;
for(i=n/2-1; i>=0;i--)
heapify(a,n,i);
for( i=n-1; i>=0; i--)
{
int temp;
temp = a[0];
a[0] = a[i];
a[i] = temp;
heapify(a,i,0);
}
}
void printArr(int arr[], int n)
{
int i;
for( i=0; i<n; ++i)
{
printf("%4d",arr[i]);
}
}
void main()
{
int a[] = { 9,16,32,8,4,1,5,8,0 };
int n = sizeof(a) /
sizeof(a[0]); clrscr();
printf("\n Before sorting :
"); printArr(a,n);
HEAPSORT(a,n);
printf("\n After sorting : ");
printArr(a,n);
getch();
}
Output:

17. Given S1={“Flowers”} ; S2={“are beautiful”}

I. Find the length of S1
II. Concatenate S1 and S2
III. Extract the substring “low” from S1
IV. Find “are” in S2 and replace it with “is”.

# include<stdio.h>
# include<conio.h>
#
include<string.h>
int LENGTH(char *str)
{
int i=0, len=0;
while(str[i]!='\0')
{
len++;
i++;
}
return(len);
}
void CONCAT(char *str1, char *str2)
{
int i=0,j=0;
while(str1[i]!='\0')
{ i+
+;
}
while(str2[j]!='\0')
{
 str1[i]=str2[j];
i++;
j++;
}
str1[i]='\0';
printf("\n Concatenated string = %s",str1);
}
void EXTRACT(char *str,int pos, int elen)
{
int i=0,j=0;
char substr[10];
for(i=pos;i<=elen;i++)
{
substr[j]=str[i];
j++;
}
substr[j]='\0';
printf("\n Substring = %s",substr);
}
void REPLACE(char *str, char *sstr, char *rstr, int pos)
{
char output[50];
int i=0,j=0,k=0;
for(i=0;i<LENGTH(str);i++)
{
if(i==pos)
{
for(k=pos;k<LENGTH(rstr);k++)
{
output[j]=rstr[k];
j++;
i++;
}
}
else
{
output[j]=str[i];
j++;
}
}
output[j]='\0';
printf("\n Output =
%s",output); getch();
}
void main()
{
char *S1,*S2;
int len,choice,pos,elen;
while(1)
{
clrscr();
strcpy(S1,"Flowers");
strcpy(S2,"are beautiful");
printf("\n S1 = %s S2 = %s",S1,S2);
printf("\n 1. Length 2.Concatenate 3.Extract Substring 4.REPLACE 5.Exit\n");
printf("\n Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1 : {
len = LENGTH(S1);
printf("\n Length of %s = %d",S1,len);
}break;
case 2: {
CONCAT(S1,S2);
}break;
case 3: { printf("\n Enter position & length of substring in S1 : ");
scanf("%d %d",&pos,&elen);
EXTRACT(S1,pos,elen);
}break;
 case 4: {
REPLACE(S2,"are","is",0);
}break;
case 5: exit(0);
default : printf("\n Invalid option");
}
getch();
}
}

Output: