INDEX

SR. Name of Program Page No. Signature Remarks

NO.

1. To Implement Bubble Sort 2

2. To Implement Insertion Sort 4

3. To Implement Quick Sort 6

4. To Implement Heap Sort 9

5. To Implement Selection Sort 13

6. To Implement Radix Sort 15

7. To Implement Linear Search 18

8. To Implement Binary Search 20

9. To Insertion an element in an Array 23

10. To Deletion an element at a specified 25

location from an Array

11. Array Implementation of Stack 27

12. Array Implementation of Queue 32

13. Array Implementation of Circular Queue 37

14. TO Add, Delete, Search, Display and count 44

the number of nodes using Linked List

15. To perform various operations i.e., 54

insertions and deletions on AVL trees

1
 Program NO. 1
/*Write a program to Implementing Bubble sort in a C Language*/

#include<stdio.h>
#include<conio.h>
void bubble_sort(int a[], int n);
void main( )
{
int i, n, a[30];
clrscr( );
printf("How many elements:-\n");
scanf("%d",&n);
printf("Enter the %d elements\n",n);
for(i = 0; i<n ; i ++)
scanf("%d",&a[i]);
bubble_sort(a,n);
getch( );
}
void bubble_sort(int a[], int n)
{
int i, pass, j, temp;
for(pass = 0 ; pass<n-1; pass + +)
{
for( j = 0 ; j<n-pass; j+ +)
if(a[ j]>a[j+1])
{
temp = a[ j];
a[j] = a[j+1];
a[ j+1] = temp;
}
}
printf("Sorted elements are......\n");
for(i = 0 ; i<n ; i + +)
2
 printf("%5d",a[i]);
}

Output of the program:-

How many elements:-
7
Enter the 7 elements
25 15 89 78 10 45 67
Sorted elements are....
10 15 25 45 67 78 89

3
 Program No. 2
/*Write a program to Implementing Insertion sort in a C Language*/

#include<stdio.h>
#include<conio.h>
void insertion_sort(int a[], int n);
void main( )
{
int i, n, a[30];
clrscr( );
printf("How many elements:-\n");
scanf("%d",&n);
printf("Enter the %d elements\n",n);
for(i = 0; i<n; i ++)
scanf("%d",&a[i]);
insertion_sort(a,n);
getch( );
}
void insertion_sort(int a[], int n)
{
int i, k, ptr, temp;
for(k = 1; k<=n-1; k++)
{
temp = a[k];
ptr = k-1;

4
 while (temp<a[ptr] && ptr>=0)
{
a[ptr+1] = a[ptr];
ptr --;
}
a[ptr+1] = temp;
}
printf("Sorted elements are.....\n");
for(i = 0; i<n; i++)
printf("%5d",a[i]);
}
Output is:-
How many elements
7
Enter the 7 elements
25 15 89 78 10 45 67
Sorted elements are...
10 15 25 45 67 78 89

5
 Program No. 3
/*Write a program to Implementing Quick sort in a C Language*/
#include<stdio.h>
#include<conio.h>
void quick_sort(int a[], int first, int last);
void main( )
{
int i, n, a[30];
clrscr( );
printf("How many elements\n");
scanf("%d",&n);
printf("Enter the %d elements\n",n);
for(i = 0; i<n ; i++)
scanf("%d",&a[i]);
quick_sort(a, 0, n-1);
printf("Sorted elements are...!\n");
for(i = 0; i<n; i + +)
printf("%5d",a[i]);
getch( );
}
void quick_sort(int a[], int first, int last)
{
int i, j, k, temp;
i = first;
j= last;
6
 k = first;
do
{
i++;
while(a[i]<a[k])
i++;
while(a[ j]>a[k])
j--;
if(i<j)
{
temp = a[i];
a[i] = a[j];
a[ j] = temp;
}
}while(i<j);
temp = a[k];
a[k] = a[ j];
a[ j],= temp;
if(first<( j-1))
quick_sort(a, first, j-1);
if(( j+1)<last)
quick_sort(a, j+1, last);
}

7
Output is:-
How many elements
7
Enter the 7 elements
25 15 89 78 10 45 67
Sorted elements are...
10 15 25 45 67 78 89

8
 Program No. 4
/*Write a program to Implementing Heap sort in a C Language*/

#include<stdio.h>
#include<conio.h>
void heap_create(int a[], int n);
void heap_sort(int a[], int n);
void main( }
{
int i,n, a[ 30];
clrscr( );
printf("How many elements\n");
scanf("%d",&n);
printf("Enter the %d elements\n",n);
for(i = 1; i<=n; i++)
scanf("%d",&a[i]);
heap_sort(a,n);
printf("Sorted elements are... In");
for(i = 1; i<=n; i++)
printf("%5d",a[i]);
getch( );
}
void heap_sort(int a[], int n)
{

9
int i, j, k, temp;
heap_create(a,n);
for(k = n; k>=2; k --)
{
temp = a[1];
a[1] = a[k];
a[k] = temp;
temp = a[1];
i = 1;
j= 2;
if(( j+1)<k)
if(a[ j+1]>a[ j])
j+ +;
while(( j<=k-1) && (a[ j]>temp))
{
a[i] = a[ j];
i = j;
j=2*i;
if(( j+1)<k)
if(a[ j+1]>a[ j])
j+ +;
elsė
if( j>n)
j= n;

10
a[i] = temp;
}
}
}
void heap_create(int a[], int n)
{
int i, j, k, temp;
for(k = 2; k<=n; k ++)
{
j = k;
temp = a[k];
i = j/2;
while(( j>1) && (temp>a[i]))
{
a[ j]=a[i];
j = i;
i = j/2;
if(i<1)
i = 1;
}
a[ j] = temp;
}
}

11
Output is:-
How manyelements
10
Enter the 10 elements
12 24 13 8 19 14 11 26 7 16
Sorted elements are......
7 8 11 12 13 14 16 19 24 26

12
 Program No. 5
/*Write a program to Implementing Selection sort in a C Language*/
#include<stdio.h>
#include<conio.h>
void selection_sort(int a[], int n);
void main( )
{
int i, n, a[30];
clrscr( );
printf("How many elements\n");
scanf("%d",&n);
printf("Enter the %d elements\n",n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
selection_sort(a,n);
getch( );
}
void selection_sort(int a[], int n)
{
int smallest, loc, i, pass, j, temp;
for(pass=0;pass<=n-2;pass++)
{
smallest = a[pass];
loc = pass;

13
for(j = pass+i;j<=n-1:j++)
if(a[j]<smallest)
{
smallest = a[j];
loc = j;
}
temp = a[pass];
a[pass] = a[loc];
a[loc] = temp; .
}
printf("Sort elements are...\n");
for(i=0;i<n;i++)
printf("%5d",a[i]);
}
Output of the program is:-
How many elements
10
Enter the 10 elements ·
75 67 54 26 85 19 37 98 43 11
Sort elements are.....
11 19 26 37 43 54 67 75 85 98

14
 Program No. 6
/*Write a program to Implementing Radix sort in a C Language*/

#include<stdio.h>

// Function to find largest element

int largest(int a[], int n)
{
int large = a[0], i;
for(i = 1; i < n; i++)
{
if(large < a[i])
large = a[i];
}
return large;
}

// Function to perform sorting

void RadixSort(int a[], int n)
{
int bucket[10][10], bucket_count[10];
int i, j, k, remainder, NOP=0, divisor=1, large, pass;
large = largest(a, n);
printf("The large element %d\n",large);
while(large > 0)
{
NOP++;
large/=10;
}

for(pass = 0; pass < NOP; pass++)

{
for(i = 0; i < 10; i++)
{
bucket_count[i] = 0;
}
15
 for(i = 0; i < n; i++)
{
remainder = (a[i] / divisor) % 10;
bucket[remainder][bucket_count[remainder]] = a[i];
bucket_count[remainder] += 1;
}

i = 0;
for(k = 0; k < 10; k++)
{
for(j = 0; j < bucket_count[k]; j++)
{
a[i] = bucket[k][j];
i++;
}
}
divisor *= 10;

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

printf("%d ",a[i]);
printf("\n");
}
}

//program starts here

int main()
{
int i, n, a[10];
printf("Enter the number of elements :: ");
scanf("%d",&n);
printf("Enter the elements :: ");
for(i = 0; i < n; i++)
{
scanf("%d",&a[i]);
}
RadixSort(a,n);
printf("The sorted elements are :: ");
16
 for(i = 0; i < n; i++)
printf("%d ",a[i]);
printf("\n");
return 0;
}

OUTPUT:
Enter the number of elements :: 7
Enter the elements :: 21 32 11 58 98 45 21
The large element 98
21 11 21 32 45 58 98
11 21 21 32 45 58 98
The sorted elements are :: 11 21 21 32 45 58 98

Program No. 7
17
/*Write a program to Implementing Linear Search in a C Language*/

#include<stdio.h>
#include<conio.h>
void main( )
{
int loc, i, n, k, a[30], data;
clrscr( );
printf("How many elements:-\n");
scanf("%d", &n);
printf("Enter the %d elements:-\n",n);
for(i =1; i<=n; i + +)
scanf("%d",&a[i]);
printf("Enter the element to be searched:-\n");
scanf("%d",&data);
k= 1;
loc = 0;
while(loc = = 0 && k<=n)
{
if (a[k]= =data)
loc = k;
k++;
}
if(loc = = 0)
printf("Data not found");
18
else
printf("Data found at location %d",loc);
getch( );
}

Output of the program is:-

How many elements:-

7
Enter the 7 elements:-
25 88 66 77 11 22 10
Enter the element to be searched:-
10 11 22 25 66 77 88

19
 Program No. 8
/*Write a program to Implementing Binary Search in a C Language*/

#include<stdio.h>
#include<conio.h>
void main( )
{
char found;
int i, n, a[30], data, low, high, mid;
clrscr( );
printf("How many elements\n");
scanf("%d",&n);
printf("Enter the %d elements\n",n);
for(i = 0; i<n; i + +)
scanf("%d",&a[i]);
printf("Enter the element to be searched\n");
scanf("%d",&data);
low = 0;
high = n-1;
found = 'n';
while(found = = 'n' && low<=high)
{
mid = (low+high)/2;
if(data>a[mid])
low = mid+1;
20
if(data<a[mid])
high = mid-1;
if (data = = a[mid])
found = 'y';
if(found = = 'y')
printf("Data found at location %d ",mid+1);
else
printf("Data not found");
getch( );
}

Output of the program:-

How many elements
Output of the program is:-
Enter the 9 elements.
How many elements
9
Enter the 9 elements
11 22 33 44 55 66 77 88 99
Enter the element to be searched
55
Data found at location 5
How many elements
Enter the 9 elements
21
11 22 33 44 55 6677 88 99
Enter the element to be searched
98
Data not found

22
 Program No.9
/*Write a program to Insert an element in one dimensional array in C
Language*/

#include<stdio.h>
#include<conio.h>
void main( )
{
int a[100], k, item, n, j, i;
clrscr( );
printf("Enter how many elements\n");
scanf("%d",&n);
printf("Enter the %d elements\n",n);
for(i = 0; i<n; i++)
scanf("%d",&a[i]);
printf("Enter the location\n");
scanf("%d",&k);
printf("Enter the item to be inserted at a[%d] \n",k);
scanf("%d",&item);
j = n - 1;
while (j>=k)
{
a[ j+1] = a[j]; .
;
}

23
a[k] = item;
n++;
printf("Resultant array is ..\n");
for (i = 0; i<n; i++)
printf("%4d",a[i]);
getch( );
}

Output of the program is :

Enter how many elements

5
Enter the 5 elements
11 22 33 44 55
Enter the location
3
Enter the item to be inserted at a[3]
66
Resultant array is ....
11 22 33 66 44 55

24
 Program No. 10
/*Write a program to Delete an element at location K in one
dimensional array in C Language*/
#include<stdio.h>
#include<conio.h>
void main( )
{
int a[100], k, item, n, j, i;
clrscr( );
printf("Enter how many elements\n");
scanf("%d",&n);
printf("Enter the %d elements\n",n);
for(i = 0; i<n; i++)
scanf("%d",&a[i]);
printf("Enter the location of number you want to delete\n");
scanf("%d",&k);
item = a[k];
printf("Deleted item is =%d\n",item);
for(j =k; j<=n-1; j++)
a[j] = a[j+1];
n--;
printf("Resultant array is ..\n");
for (i = 0; i<n; i++)
printf("%4d",a[i]);
getch( );
25
}
Output of the program is:

Enter how many elements

5
Enter the 5 elements
11 22 33 44 55
Enter the location of number you want to delete
1
Deleted item is =22
Resultant array is....
11 33 44 55

26
 Program No. 11
/*Write a program for Array implementation of Stack in C Language*/

#include<stdio.h>
#include<conio.h>
#define SIZE 10
void push(int stack[], int item);
void pop(int stack[]);
void display(int stack[]);
int top;
void main()
{
int stack[SIZE], val, element, choice;
clrscr();
printf("MAIN MENU\n");
printf("For Push operation enter choice =1\n");
printf("For Pop operation enter choice =2\n");
printf("For exit enter choice =3\n"};
top=-1;
do
{
printf("Enter your choice:\n");
scanf("%d",&choice);
if(choice==1)
{
27
printf("Enter the element to push\n");
scanf("%d",&element);
push(stack,element);
else if (choice==2)
{
pop(stack);
}
} while(choice==1 || choice==2);
}
void push(int stack[], int item).
{
if(top==SIZE-1)
{
printf("Stack is full\n");
}
else
{
top++;
stack[top]=item;
display(stack);
}
void pop(int stack[])
{
int val;
if(top== -1)
28
{
printf("Stack is empty\n");
}
else
{
val=stack[top];
top--;
printf("The popped item is = %d\n",val);
display(stack);
}
}
void display(int stack[])
{
int i;
printf("Stack elements are.....\n");
for(i=top; i>=0;i--)
printf("%d\n", stack[i]);
}

Output of the program is:-

MAIN MENU
For Push operation enter choice =1
For Pop operation enter choice =2
For exit enter choice =3
Enter your choice:
29
Stack is empty
Enter your choice:
1
Enter the element to push
11
Stack elements are....
11
Enter your choice:
1
Enter the element to push
22
Stack elements are....
22
11
Enter your choice:
1
Enter the element to push
33
Stack elements are.....
33
22
11
Enter your choice:
2
The popped item is = 33
30
Stack elements are.....
22
11
Enter your choice:
3

31
 Program No. 12
/*Write a program for Array implementation of Queue in C
Language*/

#include<stdio.h>
#include<conio.h>
#define SIZE 4
void qinsert(int q[], int item);
void qdelete(int q[]);
void display(int q[]);
int front, rear;
void main()
{
int q[SIZE], val, element, choice;
clrscr();
front = -1;
rear = -1;
printf("MAIN MENU\n");
printf("For Insert operation enter choice =1\n");
printf("For Delete operation enter choice =2\n");
printf("For exit enter choice =3\n");
do
{
printf("Enter your choice: ");
scanf("%d",&choice);
32
if(choice ==1)
{
printf("Enter the element to insert ");
scanf("%d", &element);
qinsert(q, element);
}
else if (choice ==2)
{
qdelete(q);
}
} while(choice ==1 || choice ==2);
}
void qinsert(int q[], int val)
{
if(rear == SIZE-1)
{
printf("Queue is full\n");
}
else
{
if(rear == -1 && front == -1)
{
front = 0;
rear = 0;

33
q[rear] = val;
}
else
{
rear + +;
q[rear] = val;
}
display(q);
}
}
void qdelete(int q[])
{
int val;
if(rear = = -1)
{
printf("Queue is empty\n");
}
else if(rear ==front)
{
val=q[front];
front = -1;
rear = -1;
printf("The deleted item is = %d\n",val);
}

34
else

{
val = q[front];
front ++;
printf("The deleted item is = %d\n",val);
display(q);
}
}
void display(int q[])
{
int i;
printf("Queue elements are.... \n ");
printf("Front--->");
for(i = front ; i<= rear ; i++)
printf("%4d", q[i]);
printf(" <---Rear");
printf("\n");
}

Output of the program is ....

MAIN MENU
For Insert operation enter choice =1
For Delete operation enter choice =2

35
For exit enter choice = 3
Enter the element to insert 11
Enter your choice: 2
Queue is empty
Enter your choice: 1
Enter the element to insert 11
Queue elements are....
Front---> 11 <---Rear
Enter your choice: 1
Enter the element to insert 22
Queue elements are....
Front---> 11 22 <---Rear
Enter your choice: 1
Enter the element to insert 33
Queue elements are....
Front---> 11 22 33 <---Rear
Enter your choice: 2
The deleted item is = 11
Queue elements are....
Front---> 22 33 <---Rear
Enter your choice: 1
Enter the element to insert 44
Queue elements are....
Front---> 22 33 44 <---Rear

36
 Enter your choice: 1
Enter the element to insert 55
Queue is full
Enter your choice: 3

Program No. 13
/*Write a program for Array implementation of Circular Queue in C
Language*/
#include<stdio.h>
#include<conio.h>
#define SIZE 4
void cqinsert(int cq[]), int item);
void cqdelete(int cq[]);
void display(int cq[]);
int front,rear;
void main()
{
int cq[SIZE], val, element, choice;
clrscr();
front = -1;
rear = -1;
printf("MAIN MENU\n");
printf("For Insert operation enter choice =1\n");
printf("For Delete operation enter choice =2\n");
printf("For exit enter choice =3\n");
37
do
{
printf("Enter your choice: ");
scanf("%d",&choice);
if(choice == 1)
{
printf("Enter the element to`insert "):
scanf("%d",&element);
cqinsert(cq,element);
}
else if (choice == 2)
{
cqdelete(cq);
}
} while(choice == 1 || choice == 2);
}
void cqinsert(int cq[], int val)
{
if((front ==0 && rear==SIZE-1) || (front == (rear +1)))
{
printf("Circular Queue is full\n");
}
else
{

38
if((rear == -1 && front == -1)
front = 0;
rear = 0;
cq[rear] = val;
}
else if(rear == SIZE-1)
{
rear = 0;
cq[rear] = val;
}
else
{
rear + +;
cq[rear] = val;
}
display(cq);
}
}
void cqdelete(int cq[])
{
int val;
if(rear == -1 && front == -1)
{
printf("Circular Queue is empty\n");

39
}
Else if(rear == front)
{
val = cq[front];
front = -1;
rear = -1;

printf("The deleted item is = %d\n",val);

}
else if(front == SIZE-1)
{
val = cq[front];
front = 0;
printf("The deleted item is %d\n",val);
display(cq);
}
else
{
val= cq[front];
front + +;
printf("The deleted item is = %d\n",val);
display(cq);
}
}

40
void display(int cq[])
{
int i;
printf("Circular Queue elements are.... \n ");
printf("Front--->");
if(rear<front)
{
For( i= front; i<SIZE; i++)
printf("%4d",cq[i]);
for(i=0; i<=rear; i++)
printf("%4d",cq[i]);
}
else
for(i = front; i <=rear; i + +)
printf("%4d", cq[i]);
printf(" <---Rear");
printf("\n");
}
Output of the program is :-
MAIN MENU
For Insert operation enter choice =1
For Delete operation enter choice =2
For exit enter choice =3
Enter your choice: 2

41
Circular Queue is empty
Enter your choice: 1
Enter the element to insert 11
Circular Queue elements are....
Front---> 11 <---Rear
Enter your choice: 1
Enter the element to insert 22
Circular Queue elements are....
Front---> 11 22 <---Rear
Enter your choice: 1
Enter the element to insert 33
Circular Queue elements are....
Front---> 11 22 33 <---Rear
Enter your choice: 2
The deleted item is = 11
Circular Queue elements are....
Front---> 22 33 <---Rear
Enter your choice: 1
Enter the element to insert 44
Circular Queue elements are....
Front---> 22 33 44 <---Rear
Enter your choice: 1
Enter the element to insert 55
Circular Queue elements are....

42
Front---> 22 33 44 55 <---Rear
Enter your choice: 1
Enter the element to insert 66
Circular Queue is full
Enter your choice: 3

43
 Program No. 14
/*Write a program to add, delete, search, display and count the
number of nodes using linked list in C Language*/

#include<stdio.h>
#include<alloc.h>
typedef struct node
{
int info;
struct node *next;
}NODE;
void create_append(NODE ** first);
void del_node(NODE **first);
void display(NODE *ptr);
int count(NODE *ptr);
void search(NODE *ptr);
void main( )
{
int choice;
NODE *list = NULL;
clrscr( );
44
printf("M A IN MENU\n");
printf("==============================\n”);
printf("1. CREATE or APPEND THE LINLKED LIST\n");
printf("2. DELETE A NODE\n");
printf("3. SEARCH A NODE\n");
printf("4. DISPLAY THE LIST\n");
printf("5. COUNT THE NODES\n");
printf("6. EXIT\n");
while(1)
{
printf("Enter your choice ");
scanf("%d",&choice);
switch(choice)
{
case 1: create_append(&list);
break;
case 2: del_node(&list):
break;
case 3: search(list);
break;
case 4: display(list);
break;
case 5: printf(" Number of nodes in the list = %d\n",count(list));
break;
case 6: exit( );
45
default: printf("WRONG CHOICE\n");
}
}
}
void create_append(NODE ** first)
{
NODE *z, * ptr;
int data;
printf("Enter the value(s), (-1 to exit)\n ");
while(data ! = - 1)
{
scanf("%d",&data);
if (data ! = - 1)
{
if (*first == NULL)
{
*first = (NODE *)malloc(sizeof(NODE));
(*first)->info = data;
(*first)->next = NULL;
}
else
{
z = *first;
while(z->next ! = NULL)
z= z->next;
46
z->next = (NODE *)malloc(sizeof (NODE)):
z= z->next;
z->info = data;
z->next = NULL;
}
}
}
}
void display(NODE *first)
{
NODE *ptr;
ptr = first;
printf("first->");
while(ptr ! = NULL)
{
printf("%d->",ptr->info);
ptr = ptr->next;
}
printf("NULL\n");
printf("Press any key to continue..\n");
getch( );
}
void del_node(NODE **first)
{
NODE *ptr, *back;
47
int val;
printf("Enter the value you want to delete: ");
scanf("%d",&val);
if(*first = = NULL)
{
printf("list empty, Press any key to continue...\n");
getch( );
}
else
if(*first)->info == val)
{
ptr = *first;
*first = (*first)->next;
free(ptr);
}
else
{
back = * first;
ptr = (* first)->next;
while(ptr ! = NULL)
{
if(ptr->info = val)
{
back->next = ptr->next;
free(ptr);
48
break;
}
else
{
back = ptr;
ptr = ptr->next;
if(ptr == NULL)
{
printf("Node not found. ");
printf("Press any key to continue\n");
getch( );
}
}
}
}
}
}
void search(NODE *first)
{
int data;
if(first = = NULL)
printf("List empty, Press any key to continue\n");
getch( );
}
else
49
{
printf("Enter the value of node you want to search "):
scạnf("%d",&data);
while((first ! = NULL) && (first->info ! = data))
first = first->next;
if (first == NULL)
{
printf("Data not found, Press any key to continue...\n");
getch( );
}
else
{
printf("Data found, Press any key to continue...\n");
getch( );
}
}
}
int count(NODE *first)
{
int i = 0;
while(first ! = NULL)
{
i++;
first = first->next;
}
50
return(i);
}

Output of the program:-

MAIN MENU
=================================
1 CREATE or APPEND THE LINLKED LIST
2. DELETE A NODE
3. SEARCH A NODE
4. DISPLAY THE LIST
5. COUNT THE NODES
6. EXIT
Enter your choice 2
Enter the value you want to delete: 22
list empty, Press any key to continue...
Enter your choice 3
List empty, Press any key to continue
Enter your choice 4
first->NULL
Press any key to continue...
Enter your choice 5
Number of nodes in the list=0

51
Enter your choice 7
WRONG CHOICE
Enter your choice 1
Enter the value(s), (-1 to exit)
11 22 33 44 55 -1
Enter your choice 4
first->11->22->33->44->55->NULL
Press any key to continue.....
Enter your choice 2
Enter the value you want to delete: 22
Enter your choice 4
first->11->33->44->55->NULL
Press any key to continue....
Enter your choice 2
Enter the value you want to delete: 45
Node not found. Press any key to continue
Enter your choice 3
Enter the value of node you want to search 44
Data found, Press any key to continue...
Enter your choice 3
Enter the value of node you want to search 23
Data not found, Press any key to continue...
Enter your choice 1
Enter the value(s), (-1 to exit)

52
66 77 -1
Enter your choice 4
first->11->33->44->55->66->77->NULL
Press any key to continue...
Enter your choice 5
Number of nodes in the list=6
Enter your choice 6

53
 PROGRAM:- 15

/* To perform various operations i.e., insertions and deletions on

AVL trees */

#include<stdio.h>
typedef struct node
{ int data;
struct node *left,*right;
int ht;
}node;

node *insert(node *,int);

node *Delete(node *,int);
void preorder(node *);
void inorder(node *);
int height( node *);
node *rotateright(node *);
node *rotateleft(node *);
node *RR(node *);
node *LL(node *);
node *LR(node *);
node *RL(node *);
int BF(node *);

54
void main()
{
node *root=NULL;
int x,n,i,op;
do
{
printf("\n1)Create : ");
printf("\n2)Insert : ");
printf("\n3)Delete : ");
printf("\n4)Print : ");
printf("\n5)Quit : ");
printf("\nEnter Your Choice : ");
scanf("%d",&op);
switch(op)
{
case 1:printf("\nEnter no.of elements :");
scanf("%d",&n);
printf("\n Enter tree data :");
root=NULL;
for(i=0;i<n;i++)
{
scanf("%d",&x);
root=insert(root,x);
}
55
 break;
case 2:printf("\nEnter a data : ");
scanf("%d",&x);
root=insert(root,x);
break;
case 3:printf("\nEnter a data : ");
scanf("%d",&x);
root=Delete(root,x);
break;
case 4: printf("\nPreorder sequence :\n");
preorder(root);
printf("\nInorder sequence :\n");
inorder(root);
break;
}

}while(op!=5);

}
node * insert(node *T,int x)
{
if(T==NULL)
{
T=(node*)malloc(sizeof(node));
T->data=x;
56
 T->left=NULL;
T->right=NULL;
}
else
if(x > T->data) // insert in right subtree
{
T->right=insert(T->right,x);
if(BF(T)==-2)
if(x>T->right->data)
T=RR(T);
else
T=RL(T);
}
else
if(x<T->data)
{
T->left=insert(T->left,x);
if(BF(T)==2)
if(x < T->left->data)
T=LL(T);
else
T=LR(T);
}
T->ht=height(T);
return(T);
57
}

node * Delete(node *T,int x)

{ node *p;

if(T==NULL)
{
return NULL;
}
else

if(x > T->data) // insert in right subtree

{
T->right=Delete(T->right,x);
if(BF(T)==2)
if(BF(T->left)>=0)
T=LL(T);
else
T=LR(T);
}
else
if(x<T->data)
{
T->left=Delete(T->left,x);
if(BF(T)==-2)//Rebalance during windup
58
 if(BF(T->right)<=0)
T=RR(T);
else
T=RL(T);
}
else
{
//data to be deleted is found
if(T->right !=NULL)
{ //delete its inorder succesor
p=T->right;
while(p->left != NULL)
p=p->left;

T->data=p->data;
T->right=Delete(T->right,p->data);
if(BF(T)==2)//Rebalance during windup
if(BF(T->left)>=0)
T=LL(T);
else
T=LR(T);
}
else
return(T->left);

59
 }
T->ht=height(T);
return(T);
}

int height(node *T)

{
int lh,rh;
if(T==NULL)
return(0);
if(T->left==NULL)
lh=0;
else
lh=1+T->left->ht;
if(T->right==NULL)
rh=0;
else
rh=1+T->right->ht;
if(lh>rh)
return(lh);
return(rh);
}
node * rotateright(node *x)
{
node *y;
60
 y=x->left;
x->left=y->right;
y->right=x;
x->ht=height(x);
y->ht=height(y);
return(y);
}
node * rotateleft(node *x)
{
node *y;
y=x->right;
x->right=y->left;
y->left=x;
x->ht=height(x);
y->ht=height(y);
return(y);
}
node * RR(node *T)
{
T=rotateleft(T);
return(T);
}
node * LL(node *T)
{
T=rotateright(T);
61
 return(T);
}
node * LR(node *T)
{
T->left=rotateleft(T->left);
T=rotateright(T);
return(T);
}
node * RL(node *T)
{
T->right=rotateright(T->right);
T=rotateleft(T);
return(T);
}
int BF(node *T)
{
int lh,rh;
if(T==NULL)
return(0);
if(T->left==NULL)
lh=0;
else
lh=1+T->left->ht;
if(T->right==NULL)
rh=0;
62
 else
rh=1+T->right->ht;
return(lh-rh);
}
void preorder(node *T)
{
if(T!=NULL)
{
printf(" %d(Bf=%d)",T->data,BF(T));
preorder(T->left);
preorder(T->right);
}
}
void inorder(node *T)
{
if(T!=NULL)
{
inorder(T->left);
printf(" %d(Bf=%d)",T->data,BF(T));
inorder(T->right);
}}

63
Output@avl tree:
1)Create : 1)Create : 1)Create :
2)Insert : 2)Insert : 2)Insert :
3)Delete : 3)Delete : 3)Delete :
4)Print : 4)Print : 4)Print :
5)Quit : 5)Quit : 5)Quit :
Enter Your Choice : 1 Enter Your Choice : 4
Enter no.of elements :6 Preorder sequence : Enter Your
Choice : 3
Enter tree data :10 5 1 6 10(Bf=0) 5(Bf=0)
13 17 1(Bf=0) 6(Bf=0) Enter a data : 17
13(Bf=-1) 17(Bf=0)
Inorder sequence :
1(Bf=0) 5(Bf=0)
6(Bf=0) 10(Bf=0)
13(Bf=-1) 17(Bf=0)
1)Create : 1)Create : 1)Create :
2)Insert : 2)Insert : 2)Insert :
3)Delete : 3)Delete : 3)Delete :
4)Print : 4)Print : 4)Print :
5)Quit : 5)Quit : 5)Quit :
Enter Your Choice : 4 Enter Your Choice : 2 Enter Your
Choice : 4

Preorder sequence : Enter a data : 16

Preorder
10(Bf=1) 5(Bf=0)
sequence :
1(Bf=0) 6(Bf=0) 13(Bf=0)

64
Inorder sequence : 10(Bf=0)
5(Bf=0) 1(Bf=0)
1(Bf=0) 5(Bf=0) 6(Bf=0)
6(Bf=0) 13(Bf=-
10(Bf=1) 13(Bf=0)
1) 16(Bf=0)
Inorder
sequence :
1(Bf=0) 5(Bf=0)
6(Bf=0)
10(Bf=0)
13(Bf=-1)
16(Bf=0)

1)Create : 1)Create : 1)Create :

2)Insert : 2)Insert : 2)Insert :
3)Delete : 3)Delete : 3)Delete :
4)Print : 4)Print : 4)Print :
5)Quit : 5)Quit : 5)Quit :
Enter Your Choice : 2 Enter Your Choice : 4 Enter Your
Choice :5

Enter a data : 17 Preorder sequence :

10(Bf=0) 5(Bf=0)
1(Bf=0) 6(Bf=0)
16(Bf=0) 13(Bf=0)
17(Bf=0)
Inorder sequence :
1(Bf=0) 5(Bf=0)
6(Bf=0) 10(Bf=0)
13(Bf=0) 16(Bf=0)

65
17(Bf=0)

66
// Program to find the average of n numbers using arrays

#include <stdio.h>
int main() {
int marks[10], i, n, sum = 0;
double average;
printf("Enter number of elements: ");
scanf("%d", &n);
for(i=0; i < n; ++i) {
printf("Enter number%d: ",i+1);
scanf("%d", &marks[i]);
sum += marks[i];
} average = (double) sum / n;
printf("Average = %.2lf", average);
return 0;
}
O/P
Enter number of elements: 5
Enter number 1: 10
Enter number 1: 20
Enter number 1: 30
Enter number 1: 40
Enter number 1: 50
Average =30.0

67