ANGEL

COLLEGE OF ENGINEERING
ANDTECHNOLOGY
TIRUPUR-641 665
(AN ISO 9001:2015 CERTIFIED INSTITUTION)

BONAFIDE CERTIFICATE

Register Number:

This is to certify that the bonafide record work done by

- --------------------------------------------- of B.E-Computer Science and Engineering

branch for the semester Third during the academic year 2023-2024 in the

CS3311 - Data Structures laboratory.

Signature of Signature of
Staff in-charge Head of the Department

Submitted for the University Practical Examination held on

INTERNAL EXAMINER EXTERNAL EXAMINER

 INDEX

EX. DATE NAME OF THE PAGE MARKS SIGN

NO. EXPERIMENT NO.

1. Array implementation of ADTs

1.A Stack ADTs
1.B Queue ADTs
2. Array implementation of List ADT
3. Linked list implementation
3.A.Linked list implementation of Stack ADTs
3.B.Linked list implementation of Queue ADTs
4. Applications of List, Stack and Queue ADTs
4.A. Implementation of Polynomial ADT
4.B. Conversion of Infix into Postfix Expression
5. Implementation of Evaluating Postfix
Expressions, Infix to Postfix conversion
6. Implementation of Binary Search Trees
7. Implementation of AVL Trees
8. Implementation of Heaps using Priority Queues.
9. Implementation of Dijkstra’s Algorithm
10. Implementation of Prim’s Algorithm
11. Implementation of Linear Search and Binary
Search
12. Implementation of Insertion Sort and
Selection Sort
13. Implementation of Merge Sort
14. Implementation of open Addressing(Linear
Probing and Quadratic Probing)
EX.NO:1A ARRAY IMPLEMENTATION OF STACKADT

AIM:

To write a program in C to implement the stack ADT using arrayconceptthat performs all
theoperations of stack.

ALGORITHM:

STEP 1: Define an array to store the element.

STEP 2: Get the users choice.

STEP 3: If the option is 1 perform creation operation and go to step4. If the option is 2 perform
insertion operation and go to step5. If the option is3 perform deletion operation and goto step6: If
the option is 4 perform display operation and go to step7.

STEP 4: Create the stack. Initially get the limit of stack and the get the items. If the limit of stack
is exceeds print the message unable to create the stack.
STEP 5: Get the element to be pushed. If top pointer exceeds stack capacity. Print Error
message that the stack overflow. If not, increment the top pointer by one and store the element
in the position which is denoted bytop pointer.

STEP 6: If the stack is empty, then print error message that stack is empty. If not fetch the
element from the position which is denoted by top pointer and decrement the top pointer byone.
STEP 7:If the top value is not less than the 0 the stack is display otherwise print the message
“stack is empty”.
STEP 8: Stop the execution.
PROGRAM:
#include<stdio.h>
#include<conio.h>
#define max 20
int opt,a[20],i,top=0,n;voidmain()
{
Void create(),push(),pop(),disp();int wish;

do

clrscr();

printf("\nMENU");

printf("\n1.Create\n2.Push\n3.pop\n4.Display\n5.Exit\n");

printf("\nEnteryour option");

scanf("%d",&opt);
switch(opt)
{
case1:create();break;
case 2:push();break;
case 3:pop();break;
case 4:disp();break;
case 5:exit(0);
}
printf("\nDo u want tocontinue(1/0):");
scanf("%d",&wish);
}
while(wish==1);
}
void create()
{
printf("\n Enter thelimit of stack");
scanf("%d",&n);
if(n<max)
{
printf("\nEnter the items");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
top=n-1;
}
else
printf(“Unable to create stack”);
}
void push()
{
int x;
if(top<max)
{
printf("\nEnter the element to be pushed:");
scanf("%d",&x);top=top+1;a[top]=x;
n=top;
}
else
printf("\n Stack is full");
}
void pop()
{
if(top<0)
printf("\n Stack is empty");
else
{
printf("\nThe element popped is %d",a[top]);
top=top-1;
n=top;
}}
void disp()
{
if(top<0)
printf("\n Stackisempty");
else
{
printf("\n The elements inthe stack are:");
for(i=top;i>=0;i--)
printf("\n%d",a[i]);
}}
OUTPUT:

EXPERIMENTAL SETUP 30
EXECUTION OF 30
PROGRAM
CONCLUDING 30
ACTIVITIES
VIVA VOICE 10
TOTAL 100
RESULT:
Thus a C program for Stack using ADT was implemented successfully.
EX. NO: 1B QUEUE ADT USING ARRAY

AIM:
To write a program for Queue using array implementation.

ALGORITHM:

• Define a array which stores queue elements..

• The operations on the queue are
• a)INSERT data into the queue
• b)DELETE data out of queue
• INSERT DATA INTO queue
• Enter the data to be inserted into queue.
• If TOP is NULL
• The input data is the first node in queue.
• The link of the node is NULL.
• TOP points to that node.
• If TOP is NOT NULL
• The link of TOP points to the new node.
• TOP points to that node.
• DELETE DATA FROM queue
• If TOP is NULL the queue is empty
• If TOP is NOT NULL
• The link of TOP is the current TOP.
• The pervious TOP is popped from queue.
• The queue represented by linked list is traversed to display its content.

PROGRAM

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#defineSIZE5
int front=-1;
int rear=-1;
int q[SIZE];
void insert();
void del();
void display();
void main()
{
Int choice;
do
{
printf("\t Menu");
printf("\n1.Insert");
printf("\n 2.Delete");
printf("\n 3. Display");
printf("\n 4. Exit");
printf("\nEnterYour Choice:"); scanf("%d",
&choice);
switch(choice)
{
case 1:
insert( );
display( );
break;
case 2:
del( );
display();
break; case3:
display( );
break;
case 4:
printf("End of Program !!!!");
exit(0);
}}
while(choice!=4);
}
Void insert()
{
int no;
printf("\n Enter No.:");
scanf("%d",&n o);
if(rear< SIZE-1)
{
q[++rear]=no;
if(front== -1)
front=0;//
front=front+1;
}
else
{
printf("\n Queue overflow");
}}
void del( )
{
if(front == - 1)
{
printf("\n Queue Underflow");
return;
}
else
{
printf("\n Deleted Item:-->%d\n", q[front]);
}
if(front == rear)
{
front=-1;
rear=-1;

}
else
{
front = front + 1;
}}
void display( )
{
int i;
if( front == - 1)
{
printf("\nQueue is empty");
return;
}
for(i = front; i<=rear;i++)
printf("\t%d",q[i]);
}

OUTPUT
 EXPERIMENTAL SETUP 30
EXECUTION OF 30
PROGRAM
CONCLUDING 30
ACTIVITIES
VIVA VOICE 10
TOTAL 100

RESULT:

Thus a C program for Queue using ADT was implemented successfully

EX. NO:2 ARRAY IMPLEMENTATION OF LIST ADT

AIM:.
To write a program for List using array implementation.

ALGORITHM:

Step1: Create nodes first, last; next, prev and cur thenset the value as NULL.
Step 2: Read the list operationtype.
Step 3: If operation type is create then process the following steps.
 Allocate memory for node cur.
 Read data in cur's data area.
 Assign cur node as NULL.
 Assign first=last=cur.
Step 4: If operation type is Insert then process the following steps.
 Allocate memory for node cur.
 Read data in cur's data area.
 Read the position the Data to be insert.
 Availability of the position is true then assing cur's node as firstand first=cur.
 If availability of position is false then do following steps.
 Assign next as cur and count as zero.
 Repeat the following steps until count less than postion.
 Assign prev as next
 Next as prev of node.
 Add count by one.
 If prev as NULL then display the messageINVALID POSITION.
 If prev not qual to NULL then do the followingsteps.
 Assign cur's node as prev's node.
 Assign prev's node as cur.
Step5: If operation type is delete then do the following steps.
 Read the position .
 Check list is Empty .If it is true display the message List empty.
 If position is first.
 Assign cur as first.
 Assign First as first of node.
 Reallocatethe cur from memory.
 If position is last.
 Move the current node to prev.
 cur's node as Null.
 Reallocate the Last from memory.
 Assign last as cur.
 If position is enter Mediate.
 Move the cur to required postion.
 Move the Previous to cur's previous position
 Move the Next to cur's Next position.
 Now Assign previous of node as next.
 Reallocatethe cur from memory.
Step 6: If operation is traverse
 Assign current as first.
 Repeat the following steps untill cur becomes NULL.

PROGRAM:

#include<stdio.h>
#include<conio.h>
#define MAX 10 Void
create();

void insert();

void deletion();

voidsearch();

void display();

int a,b[20], n,p, e, f, i, pos;

void main()
{
clrscr();

int ch;

char g='y';

do

printf("\n main Menu");printf("\n 1.Create\n 2.Delete\n 3.Search\n 4.Insert\n5.Display\n 6.Exit\n");

printf("\nEnter yourChoice");

scanf("%d",&ch);

switch(ch)

{
case 1:
create();
break;
case 2:
deletion();
break;
case 3:
search();
break;
case 4:
insert();
break;
case5:
display();

break;

case 6:

exit();

break;

default:
printf("\n Enter the correct choice:");
}
printf("\n Do u want to continue:::");
scanf("\n%c",&g);
}
while(g=='y'||g=='Y');
getch();
}
void create()
{
printf("\n Enter the number of nodes");
scanf("%d", &n);for(i=0;i<n;i++)
{
printf("\n Enter the Element:",i+1);
scanf("%d",&b[i]);
}
}
void deletion()
{
printf("\n Enter the position u want to delete::");
scanf("%d", &pos);
if(pos>=n)
{
printf("\n Invalid Location::");
}
else
{
for(i=pos+1;i<n;i++)
{
b[i-1]=b[i];
}
n--;
}
printf("\n The Elementsafter deletion");
for(i=0;i<n;i++)
{
printf("\t%d", b[i]);
}
}
void search()
{
printf("\n Enter the Element to be searched:");
scanf("%d", &e);for(i=0;i<n;i++)
{
if(b[i]==e)
{
printf("Value is in the %d Position", i);
}}}

void insert()
{
printf("\n Enter the position u need to insert::");
scanf("%d", &pos);
if(pos>=n)
{
printf("\n invalid Location::");
}
else
{
for(i=MAX-1;i>=pos-1;i--)
{

b[i+1]=b[i];
}
printf("\n Enter the elementto insert::\n");
scanf("%d",&p);b[pos]=p;
n++;
}
printf("\n The list afterinsertion::\n");
display();
}
void display()
{
printf("\n The Elements of The list ADT are:");
for(i=0;i<n;i++)
{
printf("\n\n%d", b[i]);
}}
OUTPUT:

EXPERIMENTAL SETUP 30
EXECUTION OF 30
PROGRAM
CONCLUDING 30
ACTIVITIES
VIVA VOICE 10
TOTAL 100

RESULT:

Thus the C program for array implementation of List ADTwas created, executedand output was
verified successfully.
EX. NO: 3A STACK ADT USING LINKED LIST

AIM:
To write a C program for stack ADT using linked list implementation.

ALGORITHM:

Define a struct for each node in the stack. Each node in the stack contains data and link to the nextnode.

TOP pointer points to last node inserted in the stack.

• The operations on the stack are
• PUSH data into the stack
• POP data out of stack
PUSH DATA INTO STACK
• Enter the data to be inserted into stack.
• If TOP is NULL
• The input data is the first node in stack.
• The link of the node is NULL.
• TOP points to that node.
• If TOP is NOT NULL
• The link of TOP points to the new node.
• TOP points to that node.
POP DATA FROM STACK
4a.If TOP is NULL the stack is empty
4b.If TOP is NOT NULL
The link of TOP is the current TOP. The pervious TOP is popped from stack.
The stack represented by linked list is traversed to display its content.

PROGRAM:

#include<stdio.h>
#include<conio.h>
#include<alloc.h> struct
node
{
int data;
struct node *next;
}
*top,*new1,*first;void
main()
{
int wish,opt;
void create(),push(),pop(),view();do
{
clrscr();
printf("Stack using linked list menu");
printf("\n1.Create\n2.Push\n3.Pop\n4.View\n5.Exit\n");
printf("\nEnter youroption(1,2,3,4,5):");
scanf("%d",&wish);
switch(wish)
{
case 1:create();break;
case 2:push();break;
case 3:pop();break;
case4:view();break;
case 5:exit(0);
}

printf("\nDo you wnat tocontinue(0/1):");

scanf("%d",&opt);
}
while(opt==1);
}
void create()
{
int ch;
top=(struct node*)malloc(sizeof(structnode));
top->next=NULL;
do
{
clrscr();
printf("Enter the data:\n");
scanf("%d",&top->data);
printf("Do you want to insert another(1/0)\n");
scanf("%d",&ch);if(ch==1)
{
}
Else
new1=(structnode*)malloc(sizeof(struct node));
new1->next=top;
top=new1;
first=top;
break;
}
while(ch==1);
}
void push()
{
top=first;
new1=(struct node*)malloc(sizeof(struct node));

printf("Enter theelementto be pushed:");

scanf("%d",&new1->data);
new1->next=top;
top=new1;
first=top;
}

void pop()
{
clrscr();
top=first;
if(top==NULL) printf("\nStack
is empty");
else
{
printf("\nThe element popped out from stackis %d",top->data);
top=top->next;
first=top;
}
}
void view()
{
printf("\nStack contents\n");
while(top->next!=NULL)
{printf("%d->",top->data);
top=top->next;
}
printf("%d\n",top->data);

getch();
}
OUTPUT:
 EXPERIMENTAL SETUP 30
EXECUTION OF 30
PROGRAM
CONCLUDING 30
ACTIVITIES
VIVA VOICE 10
TOTAL 100

RESULT:
Thus the C program for array implementation of Stack ADTwas created, executedand output was
verified successfully
EX. NO :3B QUEUE ADT USING LINKED LIST

AIM:
To write a C program for Queue using Linked implementation.

ALGORITHM:
• Define a struct for each node in the queue. Each node in the queuecontains data and link to thenext
node. Front and rear pointer points to first andlast node inserted in the queue.

• The operations on the queue are

• INSERT data into the queue
• DELETE data out of queue
• INSERT DATA INTO queue
• Enter the data to be inserted into queue.
• If TOP is NULL
• Theinput data is thefirst node in queue.
• ii. The link of the node is NULL.
• TOP points to that node.
• c. IfTOP is NOTNULL
• The link of TOP points to the new node.
• ii.TOP points to that node

PROGRAM:
#include<stdio.h>
#include<conio.h>struct
node
{
int info;
struct node *link;
}
*front = NULL, *rear = NULL;
void insert(); void
delet(); void
display();int item;
void main()
{
int ch;do
{
printf("\n\n1.\tEnqueue\n2.\tDequeue\n3.\tDisplay\n4.\tExit\n");
printf("\nEnter your choice: ");
scanf("%d",&ch);
switch(ch)
{
case 1:insert();break;

case 2:delet();break;
case3:display();break;
case 4:exit(0);
default:
printf("\n\nInvalid choice. Please try again...\n");}
} while(1);
getch();
}
void insert()
{
printf("\n\nEnter ITEM: ");
scanf("%d",&item); if(rear
== NULL)
{
rear=(structnode*)malloc(sizeof(struct node));rear->info = item;
rear->link=NULL;front=rear;
}
else
{
rear->link=(struct node*)malloc(sizeof(struct node));
rear = rear->link;
rear->info= item;rear->link = NULL;
}}
void delet()
{
struct node*ptr;
if(front==NULL)
printf("\n\nQueue is empty.\n");
else
{
ptr = front;
item=front->info;
front=front->link;
free(ptr);
printf("\nItem deleted: %d\n", item);
if(front==NULL)
rear = NULL;
}}
voiddisplay()
{
struct node*ptr = front;
if(rear ==NULL)
printf("\n\nQueue is empty.\n");
else
{
printf("\n\n");
while(ptr!=NULL)
{
printf("%d\t",ptr->info);
ptr = ptr->link;
}}}
OUTPUT:

EXPERIMENTAL SETUP 30
EXECUTION OF 30
PROGRAM
CONCLUDING 30
ACTIVITIES
VIVA VOICE 10
TOTAL 100

RESULT:
Thus the C programfor array implementation of Queue ADT wascreated, executed andoutput was verified
successfully
EXNO:4 REPRESENT A POLYNOMIAL AS A LINKED LIST

AIM:
To write programin C to convert given infix expression in to postfix notation

ALGORITHM:
• Get the two polynomials. First polynomial is P1 and second polynomial is P2
• For addition of two polynomials if exponents of both the polynomialsare same then we
adthe coefficients. For storing the result we will create the third linked lists say P3.
• If Exponent of P2 is greater than exponent of P1 then keep the P3 as P2.
• If Exponent of P2 is greater than exponent of P1 then keep the P3 as P1
• If Exponent of P2 is equal to the exponent of P1 then add thecoefficient of P1
andcoefficient of P2 as coefficient of P3.
• Continue the above step from 3 to 5 until end o the two polynomials.
• If anyof the polynomial is ended keep P3 as the remaining polynomial.
• Stop the execution.

PROGRAM:
#include<stdio.h>
#include<conio.h>
main()
{
int a[10], b[10], c[10],m,n,k,k1,i,j,x;clrscr();
printf("\n\tPolynom ial Addition\n");
printf("\t===================\n");
printf("\n\tEnter theno. of terms of thepolynomial:");scanf("%d", &m);
printf("\n\tEnter the degrees and coefficients:");for(i=0;i<2*m;i++)
scanf("%d",&a[i]); printf("\n\tFirstpolynomial
is:");k1=0;
if(a[k1+1]==1)
print f("x^%d",a[k1]);else
printf("%dx^%d",a[k1+1],a[k1]); k1+=2;
while(k1<i)
{
printf("+%dx^%d",a[k1+1],a[k1]);
k1+=2;
}
printf("\n\n\n\tEnter theno. of terms of 2nd polynomial:");scanf("%d", &n);
printf("\n\tEnter the degreesand co-efficients:");for(j=0;j<2*n;j++) scanf("%d",
&b[j]); printf("\n\tSecond
polynomial is:");k1=0;
if(b[k1+1]==1)
print f("x^%d",b[k1]);else
printf("%dx^%d",b[k1+1],b[k1]);k1+=2;
while (k1<2*n)
{
printf("+%dx^%d",b[k1+1],b[k1]);k1+=2;
} i=0;
j=0;
k=0;
while (m>0 && n>0)
{
if (a[i]==b[j])
{ c[k+1]=a[i+1]+b[j+1];
c[k]=a[i];m--;
n--;
i+=2;
j+=2;
}
else if (a[i]>b[j])
{ c[k+1]=a[i+1];
c[k]=a[i];m--;
i+=2;

}
else
{ c[k+1]=b[j+1];
c[k]=b[j];n--;
j+=2;
}
k+=2;
}
while (m>0)
{ c[k+1]=[i+1];
c[k]=a[i];
k+=2; i+=2;
m--;
}
while (n>0)
{c[k+1]=b[j+1];
c[k]=b[j];
k+=2; j+=2;
n--;
}
printf("\n\n\n\n\tSumof the twopolynomials is:");k1=0; if
(c[k1+1]==1)
print f("x^%d",c[k1]);else
printf("%dx^%d",c[k1+1],c[k1]); k1+=2;
while(k1<k)
{
if (c[k1+1]==1)
 printf("+x^%d",c[k1]);else
printf("+%dx^%d",c[k1+1], c[k1]);k1+=2;
}
getch();
return 0;
}

OUTPUT

EXPERIMENTAL SETUP 30
EXECUTION OF 30
PROGRAM
CONCLUDING 30
ACTIVITIES
VIVA VOICE 10
TOTAL 100

RESULT:
Thus the programin C to Polynomial linked list was created,executed and outputwas verified successfully
EXNO:5 IMPLEMENTATION OF EVALUATING POSTFIX EXPRESSIONS,
INFIX TO POSTFIX CONVERSION
AIM
To write a C program Implementation Binary Tree And Operations Of Binary Trees

ALGORITHM
• Start from root.
• Compare the inserting element with root, if less than root, then recurse forleft, else recurse
forright.
• If element to search is found anywhere, return true, else return false

PROGRAM

#include<stdio.h>
#include<stdlib.h>
struct tree { int data;
structtree*left;
structtree*right;
}
*root = NULL, *node = NULL, *temp = NULL;
struct tree* insert(int key,struct tree *leaf)
{
if(leaf == 0)
{
struct tree *temp;
temp=(structtree*)malloc(sizeof(struct tree));temp->data = key;
temp->left = 0;
temp->right =0; printf("Data
inserted!\n");returntemp;
}
else
{
if(key < leaf->data)
leaf->left=insert(key,leaf->left);
}
else
leaf->right = insert(key,leaf->right);return leaf;
}
struct tree* search(int key,struct tree *leaf)
{
if(leaf != NULL)
{
if(key ==leaf->data)
{
printf("Datafound!\n");
returnleaf;
}
else
{
if(key < leaf->data)
return search(key,leaf->left);else
{
return search(key,leaf->right);printf("Datanot
found!\n"); return NULL;
}}
struct tree* minvalue(struct tree *node)
{
if(node == NULL)
return NULL;
if(node->left)
returnminvalue(node->left);
}
returnnode;
/* Function for find maximum value fromthe Tree */struct tree*
maxvalue(structtree *node)
{
if(node == NULL)
return NULL;
if(node->right)
return maxvalue(node->right);
}
returnnode;
void preorder(structtree*leaf)
{
if(leaf ==NULL)
return;
printf("%d\n",leaf->data);
preorder(leaf->left); preorder(leaf-
>right); inorder(structtree*leaf)
{
if(leaf== NULL)
return;
}
preorder(leaf->left);
printf("%d\n",leaf->data);
preorder(leaf->right);
postorder(struct tree*leaf)
{
if(leaf ==NULL) return;
preorder(leaf->left);
preorder(leaf->right);
printf("%d\n",leaf->data);
}
struct tree* delete(struct tree*leaf, int key)
{
if(leaf ==NULL)
printf("Element Not Found!\n");else if(key <leaf-
>data)
leaf->left = delete(leaf->left, key);else if(key > leaf-
>data)
leaf->right = delete(leaf->right, key);else
{
if(leaf->right && leaf->left)
{
temp = minvalue(leaf->right);leaf->data
=temp->data;
leaf->right= delete(leaf->right,temp->data);
}
else
{
temp = leaf;
if(leaf->left == NULL)leaf =
leaf->right;
else if(leaf->right == NULL)leaf = leaf-
>left; free(temp);
printf("Data delete successfully!\n");int main()
{
int key,choice; while(choice!=7)
{
printf("1. Insert\n2. Search\n3. Delete\n4. Display\n5.Min Value\n6.MaxValue\n7. Exit\n");
printf("Enteryour choice:\n");
scanf("%d", &choice);
switch(choice)
{
case 1:
printf("\nEnter the value to insert:\n");
scanf("%d",&key);
root=insert(key, root);
break;
case 2:
printf("\nEnter the value to search:\n");
scanf("%d",&key);
search(key,root);
break;
case 3:
printf("\nEnter the value to delete:\n");
scanf("%d",&key);
delete(root,key);
break;
case 4:
printf("Preorder:\n");
preorder(root);
printf("Inorder:\n");
inorder(root);
printf("Post order:\n");
postorder(root);
break;
case 5:
if(minvalue(root) == NULL)
printf("Tree is empty!\n");
else
printf("Minimum valueis %d\n",minvalue(root)->data);
break;
case 6:
if(maxvalue(root) == NULL)
printf("Tree is empty!\n");
else
printf("Maximum value is %d\n",maxvalue(root)- >data);
break;
case 7:
printf("Bye Bye!\n");
exit(0);
break;
default:
printf("Invalid choice!\n");
}
}
return 0;
}
OUTPUT

EXPERIMENTAL SETUP 30
EXECUTION OF 30
PROGRAM
CONCLUDING 30
ACTIVITIES
VIVA VOICE 10
TOTAL 100

Result:

Thus the program in C for BinaryTree and Operations ofBinary Trees was created,executed and
output was verified successfully
EX. NO: 6 IMPLEMENTATION OF BINARY SEARCH TREE

AIM:
To write a C programto implementation of binary search tree.

ALGORITHM:

• Declare function create (), search (), delete (), Display ().
• Create a structure for a tree contains left pointer and right pointer.
• Insert an element is by checking the top nodeand the leaf node and theoperation will be
performed.
• Deleting an element contains searching the tree and deleting the item.
• Display the Tree elements.

PROGRAM:

#include<stdio.h>
#include<conio.h>
#include<process.h>
#include<alloc.h>
structtree
{
int data;
structtree*lchild;
structtree*rchild;
}
*t,*temp;
int element;
void inorder(struct tree *); void
preorder(struct tree *);void
postorder(struct tree *);
struct tree *create(struct tree *, int); struct tree *
find(struct tree *, int); struct tree * insert(struct tree *,
int);struct tree * del(struct tree *, int); struct tree *
findmin(struct tree *); struct tree * findmax(struct tree
*);
void main()
{
int ch;do

{
printf("\n\t\t\tBINARY SEARCH TREE");
printf("\n\t\t\t****************");printf("\nMainMenu\n");
printf("\n1.Create\n2.Insert\n3.Delete\n4.Find\n5.FindMin\n6.FindMax");
printf("\n7.Inorder\n8.Preorder\n9.Postorder\n10.Exit\n"); printf("\nEnter ur choice :");scanf("%d",&ch);
switch(ch)
{
case 1:
printf("\nEnter the data:");
scanf("%d",&element);
t=create(t,element); inorder(t);
break;
case 2:
printf("\nEnter the data:");
scanf("%d",&element);
t=insert(t,element); inorder(t);
break;
case 3:
printf("\nEnter the data:");
scanf("%d",&element);
t=del(t,element); inorder(t);
break;
case 4:
printf("\nEnter the data:");
scanf("%d",&element);
temp=find(t,element); if(temp-
>data==element)
printf("\nElement %d isat %d",element,temp);break;case
5:
printf("\nElement is notfound");
temp=findmin(t);
printf("\nMaxelement=%d",temp->data);break;case 6:
temp=findmax(t);
printf("\nMaxelement=%d",temp->data);break;case 7:
inorder(t);
break; case
8:
preorder(t);break;
case 9: postorder(t);
break;
case 10:
exit(0);
}
}
while(ch<=10);
}
struct tree * create(struct tree *t, int element)
{
t=(struct tree*)malloc(sizeof(struct tree));t->data=element;t-
>lchild=NULL;
t->rchild=NULL;return t;
}
struct tree * find(struct tree *t, int element)
{ if(t==NULL)
return NULL;
if (element<t->d at a) return(find(t-
>lchild,element)); else if(element>t->data)
return(find(t->rchild,element)); else
}
return t;
struct tree*findmin(struct tree*t)
{ if(t==NULL)
return NULL;
}
if(t->lchild==NULL) return t;
return(findmin(t->lchild));
struct tree *findmax(struct tree *t)
{ if(t!=NULL)
{
while(t->rchild!=NULL) t=t-
>rchild;
}
return t;
struct tree *insert(struct tree *t,int element)
{ if(t==NULL)
{
t=(struct tree *)malloc(sizeof(struct tree));t->data=element;t-
>lchild=NULL; t-
>rchild=NULL;
returnt;
}
else
{
if(element<t->data)
{
}
else
t->lchild=insert(t->lchild,element); if(element>t-
>data)
{
}
else
t->rchild=insert(t->rchild,element); if(element==t-
>data)
{
printf("elementalreadypresent\n");
}
return t;
}
}
struct tree * del(struct tree *t, int element)
{ if(t==NULL)
printf("elementnotfound\n");
if(element<t->data)
(t->lchild,element);
if(element>t->data)
t->rchild=del(t->rchild,element); if(t-
>lchild&&t->rchild)
{
else
{
temp=t;
if(t->lchild==NULL)
 t=t->rchild;
return t;
}
else
}
if(t->rchild==NULL)
temp=findmin(t->rchild);
t->data=temp->data;
t->rchild=del(t->rchild,t->data);
t=t->lchild;
free(temp);
voidinorder(struct tree *t)
{ if(t==NULL)
return;
else
{
inorder(t->lchild);
printf("\t%d",t->data);
inorder(t->rchild);
voidpreorder(struct tree*t)
{ if(t==NULL)
return;
else
{}
}
printf("\t%d",t->data);preorder(t->lchild);preorder(t-
>rchild);
voidpostorder(struct tree*t)
{ if(t==NULL)
return;
else
{
postorder(t->lchild);
postorder(t->rchild);
printf("\t%d",t->data);

}}

OUTPUT:
 EXPERIMENTAL SETUP 30
EXECUTION OF 30
PROGRAM
CONCLUDING 30
ACTIVITIES
VIVA VOICE 10
TOTAL 100

RESULT:
Thus the C programfor binary search tree was created,executed and output wasverified successfully.
EX NO:7 INSERTION OF AVL TREE IMPLEMENTATION

AIM:-

To write a C programto implement insertion in AVL trees.

ALGORITHM:-

• Initialize all variables and functions.

• To insert and element read the value.
• Check whether root is null
• If yes make the new value as root.
• Else check whether the value is equal to root value.
• if yes, print “duplicate value”.
• Otherwise insert the value at its proper position and balance the tree usingrotations.
• To display the tree values check whether the tree is null.
• If yes, print “tree is empty”.
• Else print all the values in the tree form and in order of the tree.
• Repeat the steps 2 to 10 for more values.

PROGRAM

#include<stdio.h>
#include<malloc.h>typedef
enum
{ FALSE ,TRUE }
bool; struct
node
{
int info; int balance;
structnode*lchild;
structnode*rchild;
};
struct node *insert (int , struct node *,int *);structnode* search(struct
node*,int);
main()
{
boolht_inc;int
info; int choice;
struct node *root = (struct node *)malloc(sizeof(structnode));root =NULL;
while(1)
{
printf("1.Insert\n");
printf("2.Display\n"); printf("3.Quit\n");
printf("Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("Enter the value to be inserted : ");
scanf("%d",&info);
if( search(root,info) == NULL ) root=
insert(info, root, &ht_inc);else
printf("Duplicatevalue ignored\n");break;
case 2:
if(root==NULL)
{
printf("Treeisempty\n");continue;
}
printf("Treeis :\n"); display(root, 1);
printf("\n\n"); printf("InorderTraversal is:
");inorder(root);
printf("\n");
break;
case 3:
exit(1);
default:
printf("Wrongchoice\n");
}/*End of switch*/
}/*End of while*/
}/*End of main()*/
struct node* search(struct node *ptr,int info)
{
if(ptr!=NULL) if(info
<ptr->info)
ptr=search(ptr->lchild,info);else
if( info > ptr->info) ptr=search(ptr-
>rchild,info);return(ptr);
}/*End of search()*/
struct node *insert (int info, struct node *pptr, int *ht_inc)
{
structnode*aptr;
structnode*bptr;
if(pptr==NULL)
{
pptr = (struct node *) malloc(sizeof(struct node));
pptr->info = info;
pptr->lchild =NULL;
pptr->rchild=NULL;
pptr->balance= 0;
*ht_inc=TRUE;
return(pptr);
}
if(info < pptr->info)
{
pptr->lchild = insert(info, pptr->lchild,ht_inc);
if(*ht_inc==TRUE)
{
switch(pptr->balance)
{
case -1: /* Right heavy */
pptr->balance = 0;
*ht_inc=FALSE;break; case
0: /*Balanced*/
pptr->balance =1;
break;
case 1:/* Leftheavy*/aptr= ptr->lchild;
if(aptr->balance== 1)
{
printf("Left toLeft Rotation\n");
pptr->lchild= aptr->rchild;
aptr->rchild =pptr;pptr-
>balance= 0; aptr-
>balance=0; pptr=aptr;
}
else
{
printf("Left to right rotation\n");bptr= aptr-
>rchild;
aptr->rchild =bptr->lchild;bptr-
>lchild =aptr;
pptr->lchild =bptr->rchild;bptr-
>rchild =pptr; if(bptr->balance ==1 )
pptr->balance=-1;
else
pptr->balance= 0;
if(bptr->balance ==-1)aptr-
>balance=1;
else
ptr->balance=0; bptr-
>balance=0;
pptr=bptr;
}
*ht_inc = FALSE;
}/*End of switch */
}/*End of if */
}/*End of if*/ if(info>pptr-
>info)
{
pptr->rchild = insert(info, pptr->rchild, ht_inc);if(*ht_inc==TRUE)
{
switch(pptr->balance)
{
case 1:
/* Leftheavy*/ pptr-
>balance = 0;
*ht_inc=FALSE;break; case
0: /*Balanced*/
pptr->balance =-1;break;
case -1:
/* Rightheavy */ aptr =
pptr->rchild;
if(aptr->balance== -1)
{
printf("Right to Right Rotation\n");pptr->rchild=aptr-
>lchild;
aptr->lchild = pptr;pptr-
>balance = 0; aptr-
>balance=0; pptr = aptr;
}
else
{
printf("Right to Left Rotation\n");bptr = aptr-
>lchild;
aptr->lchild =bptr->rchild;bptr-
>rchild =aptr;
pptr->rchild =bptr->lchild;
bptr->lchild =pptr; if(bptr->balance ==-1)pptr->balance=1;
else
pptr->balance= 0;
if(bptr->balance == 1)
aptr->balance = -1;else
aptr->balance=0;bptr-
>balance=0;
pptr=bptr;
}/*End of else*/
*ht_inc= FALSE;
}/*End of switch */
}/*End of if*/
}
/*End of if*/return(pptr);
}/*End of insert()*/ display(structnode *ptr,int level)
{
int i;
if ( ptr!=NULL )
{
display(ptr->rchild, level+1);printf("\n");for (i
=0; i <level;i++)printf(""); printf("%d",ptr-
>info);
display(ptr->lchild, level+1);
}/*End of if*/
}/*End of display(
)*/ inorder(struct node*ptr)
{
if(ptr!=NULL)
{
inorder(ptr->lchild); printf("%d
",ptr->info);inorder(ptr-
>rchild);
}}/*Endofinorder()*/

OUTPUT
 EXPERIMENTAL SETUP 30
EXECUTION OF 30
PROGRAM
CONCLUDING 30
ACTIVITIES
VIVA VOICE 10
TOTAL 100

RESULT
Thus the ‘C’ programto implement an AVL trees was created,executed and output was

verified successfully.
EXNO:8 IMPLEMENTATION OF PRIORITY QUEUE USING HEAPS

AIM:

To write a C program to implement Priority Queue using BinaryHeaps.

ALGORITHM:

• Initialize all necessary variables and functions.

• Read the choices.
• For insertion, read the element to be inserted.
• If root is NULL, assign the given element as root.
• If the element is equal to the root, print “Duplicate value”.
• Else if element value is less than the root value, insert element at the left of the root.
• Else insert right side of the root.
• For deletion, get the priority for maximum or minimum.
• If maximum, it deletes the root and rearranges the tree.
• If minimum, it deletes the leaf.
• End of the program

PROGRAM
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
enum{FALSE=0,TRUE=-1};
struct Node
{
struct Node*Previous;
int Data;
struct Node *Next;
}
Current;
struct Node*head;
structNode*ptr;
static int NumOfNodes; int
PriorityQueue(void);int
Maximum(void);
int Minimum(void);
voidInsert(int); int
Delete(int);
voidDisplay(void);int
Search(int); voidmain()
{
int choice;int
DT;
PriorityQueue();
while(1)
{
printf("\nEnter ur Choice:");
printf("\n1.Insert\n2.Display\n3.Delete\n4.Search\n5.Exit\n");scanf("%d",&choice);
switch(choice)
{
case 1:
printf("\nEnter a data to enter Queue");
scanf("%d",&DT);
Insert(DT);
break;
case 2:
Display();
break; case 3:
{
int choice,DataDel; printf("\nEnter ur
choice:");
printf("\n1.Maximum Priority queue\n2.Minimum priorityQueue\n");scanf("%d",&choice);switch(choice)
{
case 1:
DataDel=Maximum();
Delete(DataDel);
printf("\n%d is deleted\n",DataDel);break;
case2:
DataDel=Minimum();
Delete(DataDel);
printf("\n%disdeleted\n",DataDel);break;
default:
printf("\nSorry Not a correct Choice\n");
}
}
break;
case 4:
printf("\nEnter a data toSearch in Queue:");scanf("%d",&DT);
if(Search(DT)!=FALSE)
printf("\n %d is present in queue",DT);else printf("\n%d
is not present in queue",DT);break;case 5:
exit(0);
default:
printf("\nCannot process ur choice\n");
}}}
int PriorityQueue(void)
{
Current.Previous=NULL; printf("\nEnter
first element of Queue:");
scanf("%d",&Current.Data); Current.Next=NULL;
head=&Current;
ptr=head;
NumOfNodes++;
return;
}
int Maximum(void)
{
int Temp; ptr=head;
Temp=ptr->Data;
while(ptr->Next!=NULL)
{
if(ptr->Data>Temp)
Temp=ptr->Data;
ptr=ptr->Next;
}
if(ptr->Next==NULL && ptr->Data>Temp)
Temp=ptr->Data;
return(Temp);
}
int Minimum(void)
{
int Temp; ptr=head;
Temp=ptr->Data;
while(ptr->Next!=NULL)
if(ptr->Data<Temp)
Temp=ptr->Data;
ptr=ptr->Next;
}
if(ptr->Next==NULL && ptr->Data<Temp)
Temp=ptr->Data;
return(Temp);
}
void Insert(int DT)
{
struct Node*newnode;
newnode=(struct Node*)malloc(sizeof(struct Node));newnode-
>Next=NULL;
newnode->Data=DT;
while(ptr->Next!=NULL)
ptr=ptr->Next;
if(ptr->Next==NULL)
{
newnode->Next=ptr->Next;ptr-
>Next=newnode;
}
NumOfNodes++;
}
int Delete(int DataDel)
{
structNode*mynode,*temp;ptr=head;
if(ptr->Data==DataDel)
{
temp=ptr; ptr=ptr-
>Next;
ptr->Previous=NULL;
head=ptr; NumOfNodes--
; return(TRUE);
}
else
{
while(ptr->Next->Next!=NULL)
{
if(ptr->Next->Data==DataDel)
{
mynode=ptr;
temp=ptr->Next;
mynode->Next=mynode->Next->Next;
mynode->Next->Previous=ptr; free(temp);
NumOfNodes--;
return(TRUE);
}
ptr=ptr->Next;
}
if(ptr->Next->Next==NULL && ptr->Next->Data==DataDel)
{
temp=ptr->Next;
free(temp); ptr-
>Next=NULL;
NumOfNodes--; return(TRUE);
}
}
return(FALSE);
}
int Search(int DataSearch)
{
ptr=head;
while(ptr->Next!=NULL)
{
if(ptr->Data==DataSearch)return
ptr->Data; ptr=ptr->Next;
}
if(ptr->Next==NULL && ptr->Data==DataSearch)returnptr-
>Data;
return(FALSE);
}
void Display(void)
{
ptr=head;
printf("\nPriority Queue isas Follows:-\n");while(ptr!=NULL)
{
printf("\t\t%d",ptr->Data); ptr=ptr-
>Next;
}
}
OUTPUT
 EXPERIMENTAL SETUP 30
EXECUTION OF 30
PROGRAM
CONCLUDING 30
ACTIVITIES
VIVA VOICE 10
TOTAL 100

RESULT:
Thus the Priority Queue using Binary Heap is implemented and the resultis
verifiedsuccessfully.
Ex:9 IMPLEMENTATION OF DIJKSTRA'S ALGORITHM

Aim:

To write a C program implement dijkstra's algorithm.

ALGORITHM:

• Dijkstra's Algorithm is a popular algorithm for finding shortest path.

• This algorithm is called single source shortest path algorithm because in this algorithm,
for a given vertex called source the shortest path to all other verticesis obtained.
• This algorithm applicable to graphs with non-negative weights only.

PROGRAM:

#include <limits.h>
#include <stdbool.h>
#include <stdio.h>

// Number of vertices in the graph

#define V 9

// A utility function to find the vertex with minimum

// distance value, from the set of vertices not yet included
// in shortest path tree
int minDistance(int dist[], bool sptSet[])
{
// Initialize min value
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (sptSet[v] == false && dist[v] <= min)min = dist[v], min_index = v;return
min_index;
}

// A utility function to print the constructed distance

// array
void printSolution(int dist[])
{
printf("Vertex \t\t Distance from Source\n");
for (int i = 0; i < V; i++) printf("%d
\t\t\t\t %d\n", i, dist[i]);
}
// Function that implements Dijkstra's single source
// shortest path algorithm for a graph represented using
// adjacency matrix representation void dijkstra(int graph[V][V], int src)
{
int dist[V];
// The output array. dist[i] will hold the
// shortest
// distance from src to i

bool sptSet[V];
// sptSet[i] will be true if vertex i is

// included in shortest
// path tree or shortest distance from src to i is
// finalized

// Initialize all distances as INFINITE and stpSet[] as

// false
for (int i = 0; i < V; i++)
dist[i] = INT_MAX, sptSet[i] = false;

// Distance of source vertex from itself is always 0dist[src] = 0;

// Find shortest path for all vertices

for (int count = 0; count < V - 1; count++) {
// Pick the minimum distance vertex from the set of
// vertices not yet processed. u is always equal to
// src in the first iteration.
int u = minDistance(dist, sptSet);

// Mark the picked vertex as processedsptSet[u] = true;

// Update dist value of the adjacent vertices of the

// picked vertex.
for (int v = 0; v < V; v++)

// Update dist[v] only if is not in sptSet,

// there is an edge from u to v, and total
// weight of path from src to v through u is
// smaller than current value of dist[v]if (!sptSet[v] && graph[u][v]&&
dist[u] != INT_MAX
&& dist[u] + graph[u][v] < dist[v])dist[v] = dist[u] + graph[u][v];
}

// print the constructed distance arrayprintSolution(dist);

}

// driver's codeint main()

{

/* Let us create the example graph discussed above */int graph[V][V] = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },

{ 4, 0, 8, 0, 0, 0, 0, 11, 0 },
{ 0, 8, 0, 7, 0, 4, 0, 0, 2 },
{ 0, 0, 7, 0, 9, 14, 0, 0, 0 },
{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },
{ 0, 0, 4, 14, 10, 0, 2, 0, 0 },
{ 0, 0, 0, 0, 0, 2, 0, 1, 6 },
{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },
{ 0, 0, 2, 0, 0, 0, 6, 7, 0 } };

// Function call dijkstra(graph, 0);

return 0;
}

OUTPUT:
 EXPERIMENTAL SETUP 30
EXECUTION OF 30
PROGRAM
CONCLUDING 30
ACTIVITIES
VIVA VOICE 10
TOTAL 100

RESULT:

Thus the C program implemented for Dijkstra's Algorithm.

EX.NO.10 IMPLEMENTATION OF PRIM'S ALGORITHM

Aim:

To write a C program implement Prim's algorithm.

ALGORITHM:

• Step 1: Select a starting vertex

• Step 2: Repeat Steps 3 and 4 until there are fringe vertices
• Step 3: Select an edge 'e' connecting the tree vertex and fringe vertex that hasminimum
weight
• Step 4: Add the selected edge and the vertex to the minimum spanning tree T[END OF
LOOP]
• Step 5: EXIT
PROGRAM
#include <stdio.h>

#include <limits.h>#define

vertices 5
int minimum_key(int k[], int mst[])
{
int minimum = INT_MAX, min,i;for (i =0;
i < vertices; i++)
if (mst[i] == 0 && k[i] < minimum )minimum =
k[i], min = i;
return min;
}
void prim(int g[vertices][vertices])
{

int parent[vertices];int
k[vertices];
int mst[vertices]; int i,
count,edge,v;
for (i = 0; i < vertices; i++)
{
k[i] = INT_MAX;
mst[i] = 0;
}
k[0] = 0;

parent[0] = -1;
for (count = 0; count < vertices-1; count++)
{
edge = minimum_key(k, mst);
mst[edge] = 1;
for (v = 0; v < vertices; v++)
{
k[v])
}
}
if (g[edge][v] && mst[v] == 0 && g[edge][v] <
{
parent[v] = edge, k[v] = g[edge][v];
}

printf("\n Edge \t Weight\n");for (i = 1; i

< vertices; i++)
printf(" %d <-> %d%d \n", parent[i], i,g[i][parent[i]]);

}
int main()
{
int g[vertices][vertices] = {{0, 0, 3, 0, 0},
{0, 0, 10, 4, 0},
{3, 10, 0, 2, 6},
{0, 4, 2, 0, 1},
{0, 0, 6, 1, 0},
};
prim(g);return
0;
}

OUTPUT

EXPERIMENTAL SETUP 30
EXECUTION OF PROGRAM 30
CONCLUDING ACTIVITIES 30
VIVA VOICE 10
TOTAL 100

RESULT:

Thus the C program implemented for Prim's algorithm.

Ex:11 IMPLEMENTATION OF SEARCHING LINEAR SEARCH ANDBINARY SEARCH

AIM:

To write a C Program to implement different searching techniques – Linear andBinarysearch.

ALGORITHM:
Linear Search:
• Read the search element from the user
• Compare, the search element with the first element in the list.
• If both are matching, then display "Given element found!!!" and terminate thefunction
• If both are not matching, then compare search element with the next element inthe list.
• Repeat steps 3 and 4 until the search element is compared with the last element inthe list.
• If the last element in the list is also doesn't match, then display "Element notfound!!!"
andterminate the function.
Binary search is implemented using following steps...

• Read the search element fromthe user

• Find the middle element in the sorted list
• Compare, the search element with the middle element in the sorted list.
• If both are matching, then display "Given element found!!!" and terminate thefunction
• If both are not matching, then check whether the search element is smalleror larger than
middleelement.
• If the search element is smaller than middle element, then repeat steps 2,3, 4 and 5 for the
leftsublist of the middle element.
• If the search element is larger than middle element, then repeat steps 2, 3,4 and 5 for the
rightsublist of the middle element.
• Repeat the same process until we find the search element in the list or untilsublist contains
onlyone element.

• If that element also doesn't match with the search element, then display"Element not found
in thelist!!!" and terminate the function.

PROGRAM
#include <stdio.h> if
void sequential_search(int array[], int size, int n) (arra
{ y[i]
int i; ==
for (i = 0; i < size; i++) n)
{
{ >
printf("%d found at location %d.\n", n, i+1);break; last
} )
}
if (i == size)
printf("Not found! %d is not present in the list.\n", n);
}

void binary_search(int array[], int size, int n)

{
int i, first, last, middle; first = 0;last = size - 1;
middle = (first+last) / 2;

while (first <= last) {if

(array[middle]
<
n)first
=
middle
+ 1;
else if (array[middle] == n) {

printf("%d found at location %d.\n",n, middle+1);break;

}
else
last = middle - 1;

middle = (first + last) / 2;

}
if( first

printf("Not found! %d is not present in the list.\n",n)

;int main()
{
int a[200], i, j, n,size;
printf("Enter the size of the list:")
;scanf("%d",&size);
printf("Enter %d Integers in ascendingorder\n", size);
for (i = 0; i < size;i++)
scanf("%d",&a[i]);
printf("Entervalue to find\n");
scanf("%d", &n);
printf("Sequent ial search\n");
sequential_sear ch(a, size,n);
printf("Binary search\n");
binary_search(a,size, n);
return 0;
}

OUTPUT

EXPERIMENTAL SETUP 30
EXECUTION OF 30
PROGRAM
CONCLUDING 30
ACTIVITIES
VIVA VOICE 10
TOTAL 100

RESULT

Thus the C Programto implement different searching techniques – Linear andBinarysearch

wasexecuted successfully.
Ex. No: 12.A IMPLEMENTATION OF INSERTION SORT

AIM:
To write a C programto implement the concept of insertion sort.

ALGORITHM:

INSERTION SORT:
Step 1 - If the element is the first element, assume that it is already sorted. Return 1.Step2 - Pick thenext

element, and store it separately in a key.

Step3 - Now, compare the key with all elements in the sorted array.

Step 4 - If the element in the sorted array is smaller than the current element, then move to the nextelement.
Else, shift greater elements in the array towards the right.

Step 5 - Insert the value.

Step 6 - Repeat until the array is sorted.SELECTION SORT:

Step 1 − Set min to the first location

Step 2 − Search the minimum element in the array

Step 3 – swap the first location with the minimum value in the arrayStep 4 – assign the second

element as min.

Step 5 − Repeat the process until we get a sorted array.

PROGRAM:

// C program for insertion sort#include <math.h>#include <stdio.h>

/* Function to sort an array using insertion sort*/void insertionSort(intarr[], int n)

{
int i, key, j;
for (i = 1; i < n; i++) {key = arr[i];j = i - 1;
/* Move elements of arr[0..i-1], that are greater than key, to one positionaheadof their current position */while (j
>= 0 && arr[j] > key) {arr[j + 1] = arr[j];j = j - 1;
}
arr[j + 1] = key;
}
}

// A utility function to print an array of size nvoid printArray(int arr[],int n)

{
int i;
for (i = 0; i < n; i++) printf("%d ", arr[i]);printf("\n");
}

/* Driver program to test insertion sort */int main()

{
int arr[] = { 12, 11, 13, 5, 6 };
int n = sizeof(arr) / sizeof(arr[0]); insertionSort(arr, n);printArray(arr, n);

return 0;
}

OUTPUT
 EXPERIMENTAL SETUP 30
EXECUTION OF 30
PROGRAM
CONCLUDING 30
ACTIVITIES
VIVA VOICE 10
TOTAL 100

RESULT:

Thus a C program for the concept of insertion sort was implemented successfully.
Ex. No: 12.B IMPLEMENTATION OF SELECTION SORT

AIM:
To write a C program to implement the concept of selection sort.

ALGORITHM:

SELECTION SORT:
Step 1 − Set min to the first location

Step 2 − Search the minimum element in the array

Step 3 – swap the first location with the minimum value in the array

Step 4 – assign the secondelement as min.

Step 5 − Repeat the process until we get a sorted array.

PROGRAM:

#include <stdio.h>int main()

{
int a[100], n, i, j, position, swap; printf("Enter number of elementsn");scanf("%d", &n);printf("Enter %d
Numbersn", n);for (i = 0; i < n; i++)
scanf("%d", &a[i]); for(i = 0; i < n - 1; i++)
{
position=i;
for(j = i + 1; j < n; j++)
{
if(a[position] > a[j])position=j;
}
if(position != i)
{
swap=a[i]; a[i]=a[position]; a[position=swap;
}
}
printf("Sorted Array:n");for(i = 0; i < n; i++) printf("%dn", a[i]); return 0;
}
OUTPUT

EXPERIMENTAL SETUP 30
EXECUTION OF 30
PROGRAM
CONCLUDING 30
ACTIVITIES
VIVA VOICE 10
TOTAL 100

RESULT:

Thus a C program for the concept of selection sort was implemented successfully.
Ex. No:13 IMPLEMENTATION OF MERGE SORT

AIM:

To write a C Program to implement the concept of merge sort.

ALGORITHM:
1: Start.

2: First you divide the number of elements by 2 andseperate themas two.

3: Divide those two which aredivided by 2.

4: Divide themuntil you get a single element.

5: Start comparing the starting two pair of elements with each other and place them inascending order.

6: When you combine them compare themso that you make sure they are sorted.
7: When all the elements are compared the array will be surely sorted in an ascending order.

8: Stop.

PROGRAM:
#include<stdio.h>

#include<conio.h>

void merge(int [],int ,int ,int);void

part(int[],int ,int );

void main()

int arr[30];int

i,size;

printf("\n\t ------- Merge sorting method\n\n");

printf("Enter total no.of elements : ");

scanf("%d",&size);

for(i=0; i<size;i++)
{

printf("Enter %d element :",i+1);

scanf("%d",&arr[i]);

}
part(arr,0,size-1);

printf("\n\t -------- Merge sorted elements \n\n");for(i=0; i<size; i++)

printf("%d ",arr[i]);

getch();

}
void part(int arr[],int min,intmax)

int mid;

if(min<max)

mid=(min+max)/2;

part(arr,min,mid);

part(arr,mid+1,max);

merge(arr,min,mid,max);

void merge(int arr[],intmin,int mid,int max)

inttmp[30];

int i,j,k,m;
j=min;
m=mid+1;
for(i=min; j<=mid && m<=max ; i++)

if(arr [j]<=arr [m])

{

tmp[i]=arr[j];j++;
}

else

{
tmp[i]=arr[m];

m++;

}}

if(j>mid)

for(k=m; k<=max; k++)

tmp[i]=arr[k];i++;
}}

Else

for(k=j; k<=mid; k++)

tmp[i]=arr[k];i++;
}}

for(k=min;k<=max; k++)

arr[k]=tmp[k];

OUTPUT
 EXPERIMENTAL SETUP 30
EXECUTION OF 30
PROGRAM
CONCLUDING 30
ACTIVITIES
VIVA VOICE 10
TOTAL 100

RESULT:

Thus a C program for the concept of merge sort was implementedsuccessfully.

Ex. No:14 IMPLEMENTATION OF OPEN ADDRESSING

AIM:
To write a C programto implement the concept of Open addressing(LinearProbing and
Quadratic Probing)

ALGORITHM:

1: Start.

2: Choose anyelement of the arrayto be the pivot.

3: Divide all other elements (except the pivot) into two partitions.

• All elements less than the pivot must be in the first partition.

• All elements greater than the pivot must be in the second partition.

4: Use recursion to sort both partitions.

5: Join the first sorted partition, the pivot, and thesecond sorted partition.6: Stop

PROGRAM:

// C program for the above approach#include <stdio.h>#include <stdlib.h>

struct HashNode {int key;int value;

};

const int capacity = 20;int size =

0;

struct HashNode** arr;struct

HashNode* dummy;

// Function to add key value pairvoid insert(int

key, int V)
{

struct HashNode* temp= (struct HashNode*)malloc(sizeof(struct HashNode));temp->key = key;temp-

>value = V;

// Apply hash function to find

// index for given key
int hashIndex = key % capacity;

// Find next free space

while (arr[hashIndex] != NULL&& arr[hashIndex]->key != key && arr[hashIndex]-
>key != -1)
{
hashIndex++; hashIndex %=
capacity;
}

// If new node to be inserted

// increase the current size
if (arr[hashIndex] == NULL|| arr[hashIndex]->key == -1)size++;

arr[hashIndex] = temp;
}

// Function to delete a key value pairint delete (int key)

{
// Apply hash function to find
// index for given key
int hashIndex = key % capacity;

// Finding the node with given

// key

while (arr[hashIndex] != NULL) {

// if node found
if (arr[hashIndex]->key == key) {
// Insert dummy node here
// for further use arr[hashIndex] = dummy;

// Reduce sizesize--;

// Return the value of the keyreturn 1;

}
hashIndex++; hashIndex %=
capacity;
}

// If not found return nullreturn 0;

}

// Function to search the value

// for a given keyint find(int key)
{
// Apply hash function to find
// index for given key
int hashIndex = (key % capacity);int counter = 0;

// Find the node with given key while (arr[hashIndex] != NULL) {int counter = 0;
// If counter is greater than
// capacity
if (counter++ > capacity)break;

// If node found return its

// value
if (arr[hashIndex]->key == key) return arr[hashIndex]->value;

hashIndex++; hashIndex %=
capacity;
}

// If not found return

// -1
return -1;
}

// Driver Codeint main()

{

// Space allocation
arr = (struct HashNode**)malloc(sizeof(struct HashNode*)
* capacity);
// Assign NULL initially
for (int i = 0; i < capacity; i++)arr[i] = NULL;

dummy
= (struct HashNode*)malloc(sizeof(struct HashNode));

dummy->key = -1;
dummy->value = -1;

insert(1, 5);
insert(2, 15);
insert(3, 20);
insert(4, 7);

if (find(4) != -1)
printf("Value of Key 4 = %d\n", find(4));elseprintf("Key 4
does not exists\n");

if (delete (4))
printf("Node value of key 4 is deleted ""successfully\n");else {
printf("Key does not exists\n");
}

if (find(4) != -1)
printf("Value of Key 4 = %d\n", find(4));elseprintf("Key 4
does not exists\n");
}
OUTPUT

EXPERIMENTAL SETUP 30
EXECUTION OF 30
PROGRAM
CONCLUDING 30
ACTIVITIES
VIVA VOICE 10
TOTAL 100

RESULT:

Thus the C program to implement the concept of Open addressing(Linear Probingand Quadratic
Probing) executed successfully.