COCHIN UNIVERSITY OF SCIENCE AND TECHNOLOGY

DEPARTMENT OF COMPUTER APPLICATIONS

KOCHI, KERALA, INDIA

DATA STRUCTURES
LABORATORY RECORD
COCHIN UNIVERSITY OF SCIENCE AND TECHNOLOGY
DEPARTMENT OF COMPUTER APPLICATIONS
KOCHI, KERALA, INDIA

DATA STRUCTURES
LABORATORY RECORD

Name: Yathunadh Krishnan P U

Register No:
Semester & Course: MCA Semester 1
Year: 2023

Certified that this is a bonafide record of work done by Mr. Yathunadh Krishnan P U
in the Data Structures laboratory of Department of Computer Applications, Cochin
University of Science and Technology.

Faculty in Charge
Serial Topic Page
No: No:

1. Write a C program to evaluate the arithmetic expression ((a -b / c * d + e)

4
* (f +g)) and display its solution.

2. Create a C Program to read 3 integer values, find the largest among them. 5

3 Develop a C program to check if the number is Prime or not. 6

4 Develop a program to check whether the given number is armstrong or

8
not.

5 Write a c program to read a string and count the number of vowels,

10
consonants and spaces in it.

6 Using structure, write a program to read and print data of n employees

12
(Name, EmployeeId and Salary)

7 Write a C program to create a fibonacci series using recursive function. 14

8 Find the factorial of a given Natural Number n using

i) a non recursive function 15
ii) a recursive function

9 Do the following using pointers

i) add two numbers 17
ii) swap two numbers using user defined function

10 Construct binary search trees to perform insertion, deletion, search 19

11 Apply Queue and stack in Breadth First Search and Depth First Search
23
respectively

12 Write a program to create a binary search tree and find the number of leaf
29
nodes

13 Create a binary search tree with the following operations:

i)Insert a new node
ii)Inorder traversal
32
iii)Preorder traversal
iv)Postorder traversal
v) Delete a node.
14 Design, develop, and execute a program in C to create a max heap and
perform the following operations
i)Insertion
ii)Deletion
iii)Print Largest Value

15 Write a program to implement Depth First Search (DFS)

graph traversalmethods.

16 Write a program to implement Breadth First Search

(BFS) graph traversal methods.

17 Create a text file containing the name, height, weight of the students in a
class. Perform Quick sort and Merge sort on this data and store the
resultant data in two separate files. Also write the time taken by the two
sorting methods into the respective files.
Sony Mathew 5.5 60
Arun Sajeev 5.7 58
Rajesh Kumar 6.1 70
18 Write a program to sort a set of numbers using Heap sort and find a
particular number from the sorted set using Binary Search.

19 Implement a Hash table using Chaining method. Let the size of hash
table be 10 so that the index varies from 0 to 9.

20 Implement a Hash table that uses Linear Probing for collision resolution
1. Write a C program to evaluate the arithmetic expression ((a -b / c * d + e) * (f +g)) and
display its solution.

Algorithm

Step 1: Start
Step 2: Declare variables a, b, c, d, e, f, g and result.
Step 3: Read variables a, b, c, d, e, f, g.
Step 4: If c == 0 : print(“Zero Division Error”) and go to step 6..
Step 5: Else evaluate the expression and store it in result.
Step 6: Print the result.
Step 7: Stop.

Code

#include <stdio.h>
int main()
{
int a, b, c, d, e, f, g, res;
printf("Enter the values for a,b,c,d,e,f,g: ");
scanf("%d %d %d %d %d %d %d", &a, &b, &c, &d, &e, &f, &g);
if(c == 0)
printf("Zero Division Error !\n");
else
{
res = (a - ((b / c) * d) + e) * (f + g);
printf("(a - b / c * d + e) * (f + g) = %d\n", res);
}
return 0;
}

Output

2. Create a C Program to read 3 integer values, find the largest among them.
Algorithm

Step 1: Start
Step 2: Accept 3 numbers
Step 3: if n1 >= n2 && n1 >= n3
Step 4: print “n1 is greater”
Step 5: else if n2 >= n2 is greater
Step 6: print “n2 is greater”
Step 7: else print “ n3 is greater”
Step 8: Stop

Code

#include <stdio.h>
int main()
{
int n1, n2, n3, max;
printf("Enter the 3 numbers: ");
scanf("%d %d %d", &n1, &n2, &n3);
if(n1>n2 && n1>n3)
printf("%d is the largest no.\n", n1);
else if(n2>n1 && n2>n3)
printf("%d is the largest no.\n", n2);
else if(n3>n1 && n3>n2)
printf("%d is the largest no.\n", n3);
return 0;
}

Output

3. Develop a C program to check if the number is prime or not.

Algorithm

Step 1: Start
Step 2: Accept a number
Step 3: Set f=0
Step 4: Iterate a for loop from 2 to (num/2)
Step 5: if num%i == 0
Step 6: f=1, break
Step 7: if f=0
Step 8: print “prime number”
Step 9: else print “Not a prime number”
Step 10: Stop

Code

#include <stdio.h>
void main()
{
int num, f=0;
printf("Enter a number : ");
scanf("%d", &num);
for(int i = 2; i<num; i++)
{
if(num%i == 0)
{
f=1;
break;
}
}
if(f==0)
printf("%d is a prime no.\n", num);
else
printf("%d is not a prime no.\n", num);
}

Output

4. Develop a program to check whether the given number is Armstrong or not.

Algorithm

Step 1: Start
Step 2: Input num
Step 3: Initialize n=num,m=num,s=0,p=0
Step 4: Repeat steps 5 to 6 while(n!=0)
Step 5: n=n/10
Step 6: p=p+1
Step 7: Repeat steps 8 to 10 while(num!=0)
Step 8: r=num%10
Step 9: s=s+pow(r,p)
Step 10: num=num/10
Step 11: if(m==s)
Step 12: print “Armstrong number”
Step 13: else print “Not an Armstrong number”
Step 14: Stop

Code

#include <stdio.h>
#include <math.h>
void main()
{
int num,n,m,s=0,p=0,r;
printf("Enter a number: ");
scanf("%d", &num);
n=num;
m=num;
while(n!=0)
{
n=n/10;
p++;
}
while (num!=0)
{
r=num%10;
s+=pow(r,p);
num=num/10;
}
if (m==s)
printf("%d is an Armstrong Number.", m);
else
printf("%d is not an Armstrong Number.", m);
}
Output

5. Write a c program to read a string and count the number of vowels, consonants
and spaces in it.

Algorithm

Step 1: Start
Step 2: Enter an alphabetical string
Step 3: Initialize v=0,c=0,s=0,i=0
Step 4: Repeat steps 5 to 8 while str[i]!=’\0’
Step 5: Check if str[i] is vowel
Step 6: increment v
Step 7: else if str[i] is’ ‘
Step 8: increment s
Step 9: else increment c
Step 10: i=i+1
Step 11: Print v,c,s
Step 12: Stop

Code

#include <stdio.h>
void main()
{
char str[150];
int v,c,s;
v=c=s= 0;
printf("Enter the string: ");
gets(str);
for (int i = 0; str[i] != '\0'; ++i)
{
if (str[i] == 'a' || str[i] == 'e' || str[i] == 'i' || str[i] == 'o' || str[i] == 'u')
{
++v;
}
else if ((str[i] >= 'a' && str[i] <= 'z'))
{
++c;
}
else if (str[i] == ' ')
{
++s;
}
}
printf("Vowels: %d", v);
printf("\nConsonants: %d", c);
printf("\nWhite spaces: %d", s);

Output

6. Using structure, write a program to read and print data of n employees (Name,
EmployeeId and Salary)

Algorithm

Step 1: Start
Step 2: Create a structure employee with name, empid, salary
Step 3: Create an array of employee
Step 4: Accept n
Step 5: Repeat steps 6 to 7 for i=0 to n-1
Step 6: Read details each employee
Step 7: i=i+1
Step 8: Repeat steps 9 to 10, for i=0 to n-1
Step 9: print the details of employee
Step 10: i=i+1
Step 11: Stop
Code

#include <stdio.h>
struct Employee
{
char name[20];
char empid[5];
double sal;
}a[50];
void main()
{
int n, i;
printf("Enter no. of Employees : ");
scanf("%d", &n);
for(i = 0; i<n; i++)
{
printf("\nEnter the employee %d details :\n", i+1);
printf("Employee Name : ");
scanf("%s",&a[i].name);
printf("Employee Id : ");
scanf("%s",&a[i].empid);
printf("Employee Salary : ");
scanf("%lf",&a[i].sal);
}
for(i = 0; i<n; i++)
{
printf("\n---Employee %d Details---\n", i+1);
printf("NAME : %s\t",a[i].name);
printf("ID : %s\t", a[i].empid);
printf("SALARY : %lf\t", a[i].sal);
}
}
Output

7. Write a C program to create a Fibonacci series using recursive function.

Algorithm

Main program:
Step 1: Start
Step 2: Accept n
Step 3: Repeat steps 4 to while(i<=num)
Step 4: print fib(n)
Step 5: Stop

fib(n):
Step 1: if n>0 print ‘0’
Step 2: else if n>1 print ‘1’
Step 3: else fib(n-1) + fib(n-2)
Code

#include <stdio.h>
int fib(int num)
{
if (num == 0)
{
return 0;
}
else if (num == 1)
{
return 1;
}
else
{
return fib(num - 1) + fib(num - 2);
}
}
void main()
{
int num;
printf("Enter the no.of elements to be in the series : ");
scanf("%d", &num);
for (int i = 0; i < num; i++)
{
printf("%d ", fib(i));
}
}

Output

8. Find the factorial of a given Natural Number using

i) A non-recursive function
ii) A recursive function
Algorithm
Main program:
Step 1: Start
Step 2: Declare num.
Step 3: Read num.
Step 4: Call fact()
Step 5: Call recFact()
Step 6: Exit
fact(num);
Step 1: Declare i, fact.
Step 2: Assign fact = 1 and i = 1.
Step 3: Repeat steps 4 to 5 until i<=num
Step 4: fact = fact * i
Step 5: i=i+1
Step 6: Print fact.
Step 7: Exit
recFact(num):
Step 1: if num <= 1, return 1
Step 2: else return(num * recFact (num-1))

Code
#include <stdio.h>
int fact(int);
int recFact(int);
void main()
{
int n;
printf("Enter a positive integer:");
scanf("%d",&n);
printf("Factorial without recursion:%d",fact(n)) ;
printf("\nFactorial using recursion:%d",recFact(n)) ;
}
int fact(int n)
{
int i=1,f=1;
while(i<=n)
{
f=f*i;
i++;
}
return f;
}
int recFact(int n)
{
if (n==1)
return 1;
else
return n*recFact(n-1);
}
Output

9. Do the following using pointers

i) Add two numbers
ii) Swap two numbers using user defined function
Algorithm
Main Program
Step 1: Start
Step 2: Declare variables num1 and num2 as int.
Step 3: Read num1 and num2.
Step 4: Call add(&num1, &num2).
Step 5: Print value of num1 and num2 befoe
Step 6: Call swap(&num1, &num2).
Step 7: Print value of num1 and num2 after swapping.
Step 8: STOP.

add(*num1, *num2) :
Step 1: Return *num1 + *num2.
swap(*num1, *num2) :
Step 1: Declare temp as int.
Step 2: Assign temp = *num1.
Step 3: *num1 = *num2
Step 4: *num2 = temp.

Code
#include <stdio.h>
int add(int *n1, int *n2);
void swap(int *n1, int *n2);
void main()
{
int n1, n2;
printf("Enter n1 : ");
scanf("%d", &n1);
printf("Enter n2 : ");
scanf("%d", &n2);
printf("Before Swapping\n");
printf("n1 = %d, n2 = %d\n", n1, n2);
swap(&n1, &n2);
printf("After Swapping\n");
printf("n1 = %d, n2 = %d\n", n1, n2);
printf("Addition result : %d\n", add(&n1, &n2));
}
int add(int *n1, int *n2)
{
return *n1 + *n2;
}
void swap(int *n1, int *n2)
{
int temp;
temp = *n1;
*n1 = *n2;
*n2 = temp;
}
Output

10. Construct binary search trees to perform insertion, deletion, search

Algorithm
Step 1: Start
Step 2: Declare ‘struct NODE’ with fields:
I. struct NODE pointer left, right.
II. integer ‘data’
Step 3: Declare a struct NODE pointer ‘root’, integer ‘ch’ and ‘data’.
Step 4: Assign root = NULL in the beginning.
Step 5: Repeat steps 5 to 6 infinitely till user exits:
Step 6: Read ‘ch’.
Step 7: Check ch:
I. if ch == 1 :
Read ‘data’. Call insert()
II. if ch == 2 :
Read ‘data’. Call delete()
III. if ch == 3 :
Read ‘data’. Call search()
IV. if ch == 4 :
call inorder()
V. Exit.
Step 8: Exit
Insert(node, data) :
Step 1: If node == NULL : return a newnode with data as ‘data’
Step 2: Otherwise if data < root->data : call insert(node->left, data).
Step 3: Otherwise if data > root->data : call insert(node->right, data).
Step 4: Exit
Delete(root, data) :
Step 1: If root === NULL : return ‘data not found’.
Step 2: Otherwise if data < root->data : call delete(node->left, data)
Step 3: Otherwise if data > root->data : call delete(node->right, data)
Step 4: Otherwise if :
a.if root->left = NULL. struct NODE *temp = root->right. free(root). Return temp
b.if root->right = NULL. struct NODE *temp = root->left. free(root). Return temp
c.else temp = inorderSuccessor of root. Exchange the values of root and temp.
Delete inorder successor
Return root.
Step 5: Exit
Search(root, data):
Step 1: Repeat steps 2 to till root != NULL.
Step 2: If data < root->data : root = root->left
Step 3: Otherwise data > root->data : root->right
Step 4: Otherwise print(“data found”)
Step 5: Exit

Code
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *left,*right;
}*root=NULL;
void insert();
void search();
void del();
void main()
{
int c;
while(1){
printf("\n1.Insert\n2.Search\n3.Delete\n4.Exit\nEnter the option:");
scanf("%d",&c);
switch(c)
{
case 1:insert();
break;
case 2:search();
break;
case 3: del();
break;
case 4:exit(0);
break;
default:printf("Invalid input!!!!");
}
}
}
void insert()
{
int data;
struct node *ptr,*q,*p;
ptr=(struct node*) malloc(sizeof(struct node));
if(ptr==NULL)
{
printf("Overflow");
exit(0);
}
printf("Enter the data:");
scanf("%d",&data);
ptr->data=data;
ptr->left=NULL;
ptr->right=NULL;
if(root==NULL)
{
root=ptr;
return;
}
q=root;
while(q!=NULL)
{
p=q;
if(data<q->data)
{
q=q->left;
}
else if(data>q->data)
{
q=q->right;
}
else{
printf("Duplication not allowed");
return;
}
}
if(data<p->data)
{
p->left=ptr;
}
else
{
p->right=ptr;
}
}
void search()
{
int data;
printf("Enter the item to search:");
scanf("%d",&data);
struct node *q;
q=root;
while(q!=NULL)
{
if(data<q->data)
{
q=q->left;
}
else if(data>q->data)
{
q=q->right;
}
else{
printf("Item found");
return;
}
}
printf("Item not found");
}
void del()
{
struct node *p,*q,*par=NULL;
int item;
printf("Enter the key to be deleted:");
scanf("%d",&item);
q=root;
while(q!=NULL)
{
if(item==q->data)
break;
par=q;
if(item<q->data)
q=q->left;
else if(item>q->data)
q=q->right;
}
if(q->left==NULL && q->right==NULL)
{
if(par==NULL)
{
root=NULL;
return;
}
}
if(par->left==q)
{
printf("%d is deleted\n",q->data);
par->left=NULL;
return;
}
if(par->right==q)
{
printf("%d is deleted\n",q->data);
par->right=NULL;
return;
}
else if(q->left!=NULL && q->right==NULL)
{
if(par==NULL)
{
root=root->left;
return;
}
else if(par->left==q)
{
printf("%d is deleted\n",q->data);
par->left=q->left;
return;
}
else if(par->right==q)
{
printf("%d is deleted\n",q->data);
par->right=q->left;
}
}
else if(q->right!=NULL && q->left==NULL)
{
if(par==NULL)
{
root=root->right;
return;
}
else if(par->left==q)
{
printf("%d is deleted\n",q->data);
par->left=q->right;
return;
}
else if(par->right==q)
{
printf("%d is deleted\n",q->data);
par->right=q->right;
return;
}
}
else
{
struct node *succ,*parsucc,*child;
succ=q->right;
while(succ->left!=NULL)
{
parsucc=succ;
succ=succ->left;
}
q->data=succ->data;
child=succ->right;
if(parsucc->left==succ)
parsucc->left=child;
else
parsucc->right=child;
}
}
Output

11. Apply Queue and stack in Breadth First Search and Depth First Search respectively

Algorithm

Main program:
Step 1: Start
Step 2: Declare a struct NODE with fields data as integer, next as struct node *.
Step 3: Create a stack, queue and a visited array.
Step 4: Get the graph.
Step 5: Apply bfs(). Apply dfs()
Step 6: Stop.
dfs(graph, vertex v) :
Step 1: if the vertex v is not visited print ‘v’.
Step 2: Repeat steps 3 to 4 until all the adjacent vertex are not visited.
Step 3: Explore the adjacent vertices to ‘v’.
Step 4: If adjacent vertex is not visited: push ‘v’ in the stack.Call dfs(graph, adjacent vertex)
Step 5: If stack is not empty : dfs(pop the stack)
Step 6: Exit
bfs(graph, vertex v) :
Step 1: If the vertex v is not visited print ‘v’.
Step 2: Repeat the steps 3 to 4 until all the adjacent vertices are not visited.
Step 3: Explore the adjacent vertices to ‘v’.
Step 4: If adjacent vertex is not visited : push ‘adjacent vertex’ to queue.
Step 5: If queue is not empty apply bfs(dequeue())
Step 6: Exit

Code
#include <stdio.h>
#include <stdlib.h>
struct NODE
{
int data;
struct NODE *next;
};
struct NODE *top;
struct NODE *front, *rear;
void displayAdjMat(int **graph);
void dfs(int **graph, int);
void bfs(int **graph, int);
int n, *visited;
int main()
{
int i, **graph, edge, vertex;
char ch;
printf("Enter no. of vertices : ");
scanf("%d", &n);
visited = (int *) calloc(n, sizeof(int));
graph = (int **) calloc(n, sizeof(int *));
for(i = 0; i<n; i++)
*(graph + i) = (int *) calloc(n, sizeof(int));
for(vertex = 0; vertex<n; vertex++)
{
printf("\nLink Vertex %d(y/n) : ", vertex);
scanf(" %c", &ch);
while((ch == 'y') || (ch == 'Y'))
{
do{
printf("Vertex no.(0 - %d) : ", n-1);
scanf("%d", &edge);
}while((edge<0) || (edge>=n));
graph[vertex][edge] = 1;
printf("Link More(y/n) : ");
scanf(" %c", &ch);
}
}
displayAdjMat(graph);
do{
for(i = 0; i<n; i++)
visited[i] = 0;
printf("\nChoose starting vertex for DFS : ");
scanf("%d", &vertex);
dfs(graph, vertex);
for(i = 0; i<n; i++)
visited[i] = 0;
printf("\nChoose starting vertex for BFS : ");
scanf("%d", &vertex);
bfs(graph, vertex);
printf("Traverse again(y/n) : ");
scanf(" %c", &ch);
} while (ch == 'y' || ch == 'Y');
return 0;
}
void displayAdjMat(int **graph)
{
int i, j;
printf("\n...Adjacency Matrix...\n");
for(i = 0; i<n; i++)
printf("\t%d", i);
printf("\n");
for(i = 0; i<n; i++)
{
printf("%d\t", i);
for(j = 0; j<n; j++)
printf("%d\t", graph[i][j]);
printf("\n");
}
}
void push(int data)
{
struct NODE * temp;
temp = (struct NODE *) malloc(sizeof(struct NODE));
temp->data = data;
temp->next = top;
top = temp;
}
int pop()
{
struct NODE *temp;
int data;
if(top == NULL)
return -1;
data = top->data;
top = top->next;
return data;
}
void enqueue(int data)
{
struct NODE *temp;
temp = (struct NODE *) malloc(sizeof(struct NODE));
temp->data = data;
temp->next = NULL;
if(front == NULL)
front = rear = temp;
else
{
rear->next = temp;
rear = temp;
}
}
int dequeue(){
int data;
if(front == NULL)
return -1;
data = front->data;
if(front == rear)
front = rear = NULL;
else
front = front->next;
return data;
}
void dfs(int **graph, int v)
{
int i, data;
if(visited[v] == 0)
{
printf("%d\t", v);
visited[v] = 1;
}
for(i = 0; i<n; i++)
{
if(graph[v][i] == 1 && visited[i] == 0)
{
visited[i] = 1;
printf("%d\t", i);
push(v);
dfs(graph, i);
}
}
data = pop();
if(data != -1)
dfs(graph, data);
}
void bfs(int **graph, int v)
{
int i, data;
if(visited[v] == 0)
{
visited[v] = 1;
printf("%d\t", v);
enqueue(v);
}
for(i = 0; i<n; i++)
{
if(graph[v][i] == 1 && visited[i] == 0)
{
visited[i] = 1;
printf("%d\t", i);
enqueue(i);
}
}
data = dequeue();
if(data != -1)
bfs(graph, data);
}

Output
12. Write a program to create a binary search tree and find the number of leaf nodes

Algorithm
Step 1: Start
Step 2: Declare ‘struct NODE’ with fields:
I. struct NODE pointer left, right.
II. integer ‘data’
Step 3: Declare a struct NODE pointer ‘root’, integer ‘ch’ and ‘data’.
Step 4: Assign root = NULL in the beginning.
Step 5: Repeat steps 5 to 6 infinitely till user exits:
Step 6: Read ‘ch’.
Step 7: Check ch:
I . if ch == 1 :
Read ‘data’. Call insert()
II. if ch == 2 :
Read ‘data’. Call delete()
III. if ch == 3 :
Read ‘data’. Call search()
IV. if ch == 4 :
call inorder()
V. if ch == 5:
Call countLeafNode(root)
VI. Exit.
Step 8: Exit
Insert(node, data) :
Step 1: If node == NULL : return a newnode with data as ‘data’
Step 2: Otherwise if data < root->data : call insert(node->left, data).
Step 3: Otherwise if data > root->data : call insert(node->right, data).
Step 4: Exit
Delete(root, data) :
Step 1: If root === NULL : return ‘data not found’.
Step 2: Otherwise if data < root->data : call delete(node->left, data)
Step 3: Otherwise if data > root->data : call delete(node->right, data)
Step 4: Otherwise if :
a.if root->left = NULL. struct NODE *temp = root->right. free(root). Return temp
b.if root->right = NULL. struct NODE *temp = root->left. free(root). Return temp
c.else temp = inorderSuccessor of root. Exchange the values of root and temp.
Delete inorder successor
Return root.
Step 5: Exit
countLeafNode(root) :
Step 1: If root != NULL then proceed otherwise return
Step 2: Call countLeafNode(root->left)
Step 3: If root is a leaf node: Increment a counter
Step 4: Call countLeafNode(root->right)
Step 5: Return counter

Code

#include <stdio.h>
#include <stdlib.h>
struct NODE{
struct NODE *left,*right;
int data;};
struct NODE * create(int);
struct NODE * insert(struct NODE *, int);
struct NODE * delete(struct NODE *, int);
struct NODE * inorderSuccessor(struct NODE *);
int cntLeaf(struct NODE *);
void inorder(struct NODE *);
int cnt = 0;
int main()
{
struct NODE *root;
int ch, data,n;
root = NULL;
while(1){
printf("\n1. Insert\n2. Deletion\n3. Search\n4. Display(Inorder Traversal)\n5. Count
Leaf\n6. Exit\nEnter your option: ");
scanf("%d", &ch);
switch(ch){
case 1 : printf("Enter the no.of nodes:");
scanf("%d",&n);
for(int i=0;i<n;i++){
printf("Enter data : ");
scanf("%d", &data);
root = insert(root, data);
printf("%d insertd...\n", data); }
break;
case 2 :if(root == NULL)
printf("Empty BST...\n");
else{
printf("Enter data : ");
scanf("%d", &data);
root = delete(root, data);
}
break;
case 4 : printf("\nDisplay : ");
inorder(root);
break;
case 5 : printf("No. of leaf nodes : %d\n", cntLeaf(root));
case 6 : exit(0);
default : printf("\n! Invalid input !!! !\n");
}
}
return 0;
}
struct NODE * create(int data){
struct NODE *newNode;
newNode = (struct NODE *) malloc(sizeof(struct NODE));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
struct NODE * insert(struct NODE *root, int data){
if(root == NULL)
return(create(data));
if(data < root->data)
root->left = insert(root->left, data);
else if(data > root->data)
root->right = insert(root->right, data);
return root;
}
void inorder(struct NODE *root){
if(root != NULL){
inorder(root->left);
printf("%d\t", root->data);
inorder(root->right);
}
}
struct NODE * delete(struct NODE *root, int data){
struct NODE *temp;
if(root == NULL)
printf("%d not found...\n", data);
else if(data == root->data){
if(root->left == NULL){
temp = root->right;
free(root);
return(temp);
}
else if(root->right == NULL){
temp = root->left;
free(root); return temp;
}
temp = inorderSuccessor(root->right);
root->data = temp->data;
root->right = delete(root->right, temp->data);
}
else if(data > root->data)
root->right = delete(root->right, data);
else
root->left = delete(root->left, data);
return root;
}
struct NODE * inorderSuccessor(struct NODE *root){
if(root->left == NULL)
return(root);
return(inorderSuccessor(root->left));
}
int cntLeaf(struct NODE *root){
if(root != NULL){
cntLeaf(root->left);
if(root->left == NULL && root->right == NULL)
cnt++;
cntLeaf(root->right);
}
return cnt;
}

Output

13. Create a binary search tree with the following operations:

i) Insert a new node ii) Inorder traversal iii) Preorder traversal iv) Postorder traversal
v) Delete a node.
Algorithm
Step 1: Start
Step 2: Declare ‘struct NODE’ with fields:
I. struct NODE pointer left, right.
II. integer ‘data’
Step 3: Declare a struct NODE pointer ‘root’, integer ‘ch’ and ‘data’.
Step 4: Assign root = NULL in the beginning.
Step 5: Repeat steps 5 to 6 infinitely till user exits:
Step 6: Read ‘ch’.
Step 7: Check ch:
I . if ch == 1 :
Read ‘data’. Call insert()
II. if ch == 2 :
Call inorder()
III. if ch == 3 :
Call preorder()
IV. if ch == 4 :
call inorder()
V. if ch == 5 :
Call postorder()
VI. Exit.
Step 8: Exit
Insert(node, data) :
Step 1: If node == NULL : return a newnode with data as ‘data’
Step 2: Otherwise if data < root->data : call insert(node->left, data).
Step 3: Otherwise if data > root->data : call insert(node->right, data).
Step 4: Exit
Delete(root, data) :
Step 1: If root === NULL : return ‘data not found’.
Step 2: Otherwise if data < root->data : call delete(node->left, data)
Step 3: Otherwise if data > root->data : call delete(node->right, data)
Step 4: Otherwise if :
a.if root->left = NULL. struct NODE *temp = root->right. free(root). Return temp
b.if root->right = NULL. struct NODE *temp = root->left. free(root). Return temp
c.else temp = inorderSuccessor of root. Exchange the values of root and temp.
Delete inorder successor
Return root.
Step 5: Exit
Preorder(root) :
Step 1: If root != NULL then proceed otherwise return
Step 2: Print root -> data.
Step 3: Call preorder(root->left)
Step 4: Call preorder(root->right)
Step 5: Return.
Inorder(root) :
Step 1: If root != NULL then proceed otherwise return
Step 2: Call inorder(root->left)
Step 3: Print root->data.
Step 4: Call inorder(root->right)
Step 5: Return.
Postorder(root) :
Step 1: If root != NULL then proceed otherwise return
Step 2: Call postorder(root->left)
Step 3: Call postorder(root->right)
Step 4: Print root->data
Step 5: Return
Code
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *left,*right;
}*root=NULL;
void insert();
void pre(struct node *);
void in(struct node *);
void post(struct node *);
void del();
void main()
{
int c,n;
while(1){
printf("\n1.Insert\t2.Inorder\t3.Preorder\t4.Postorder\t5.Delete\t6.Exit\nEnter the option:");
scanf("%d",&c);
switch(c)
{
case 1: printf("Enter the no.of nodes:");
scanf("%d",&n);
for(int i=0;i<n;i++)
insert();
break;

case 2:in(root);
break;
case 3:pre(root);
break;
case 4:post(root);
break;
case 5:del();
break;
case 6:exit(0);
break;
default:printf("Invalid input!!!");
}
}
}
void insert()
{
int data;
struct node *ptr,*q,*p;
ptr=(struct node*) malloc(sizeof(struct node));
if(ptr==NULL)
{
printf("Overflow");
exit(0);
}
printf("Enter the data:");
scanf("%d",&data);
ptr->data=data;
ptr->left=NULL;
ptr->right=NULL;
if(root==NULL)
{
root=ptr;
return;
}
q=root;
while(q!=NULL)
{
p=q;
if(data<q->data)
{
q=q->left;
}
else if(data>q->data)
{
q=q->right;
}
else{
printf("Duplication not allowed");
return;
}
}
if(data<p->data)
{
p->left=ptr;
}
else
{
p->right=ptr;
}
}
void pre(struct node *ptr)
{
if(ptr==NULL)
return;
printf("%d\t",ptr->data);
pre(ptr->left);
pre(ptr->right);
}
void in(struct node *ptr)
{
if(ptr==NULL)
return;
in(ptr->left);
printf("%d\t",ptr->data);
in(ptr->right);
}
void post(struct node *ptr)
{
if(ptr==NULL)
return;
post(ptr->left);
post(ptr->right);
printf("%d\t",ptr->data);
}
void del()
{
struct node *p,*q,*par=NULL;
int item;
printf("Enter the key to be deleted:");
scanf("%d",&item);
q=root;
while(q!=NULL)
{
if(item==q->data)
break;
par=q;
if(item<q->data)
q=q->left;
else if(item>q->data)
q=q->right;
}
if(q->left==NULL && q->right==NULL)
{
if(par==NULL)
{
root=NULL;
return;
}
}
if(par->left==q)
{
printf("%d is deleted\n",q->data);
par->left=NULL;
return;
}
if(par->right==q)
{
printf("%d is deleted\n",q->data);
par->right=NULL;
return;
}
else if(q->left!=NULL && q->right==NULL)
{
if(par==NULL)
{
root=root->left;
return;
}
else if(par->left==q)
{
printf("%d is deleted\n",q->data);
par->left=q->left;
return;
}
else if(par->right==q)
{
printf("%d is deleted\n",q->data);
par->right=q->left;
}
}
else if(q->right!=NULL && q->left==NULL)
{
if(par==NULL)
{
root=root->right;
return;
}
else if(par->left==q)
{
printf("%d is deleted\n",q->data);
par->left=q->right;
return;
}
else if(par->right==q)
{
printf("%d is deleted\n",q->data);
par->right=q->right;
return;
}
}
else
{
struct node *succ,*parsucc,*child;
succ=q->right;
while(succ->left!=NULL)
{
parsucc=succ;
succ=succ->left;
}
q->data=succ->data;
child=succ->right;
if(parsucc->left==succ)
parsucc->left=child;
else
parsucc->right=child;
}
}
Output

14. Design, develop, and execute a program in C to create a max heap and perform the
following operations :
i) Insertion ii) Deletion iii) Print Largest Value

Algorithm
Step 1: Start
Step 2: Declare ‘heap’ as an array of integers.
Step 3: Repeat steps 3 to till user exits
Step 4: Read ch.
Step 5: If ch == 1: call insert() to construct the heap
Step 6: Otherwise if ch == 2 : insert a new element to the heap.
Step 7: Otherwise if ch == 3 : call displayHeap()
Step 8: Otherwise if ch == 4 : call deleteHeap()
Step 9: Otherwise if ch == 5 : exit the program
Step10: Exit
insert() :
Step 1: Read all the elements in an array.
Step 2: Assign i = sizeof(heap)/2
Step 3: Repeat steps 4 to 5 till i>0
Step 4: Apply heapify(i)
Step 5: Decrement i
Step 6: Exit
delete() :
Step 1: If size of array = 0 print “Heap empty” and go to the last step
Step 2: Otherwise Replace the root element with the last leaf node and delete the last index.
Step 3: Apply heapify(1) on the first index
heapify() :
Step 1: Check if the root node is greater than the left and right child.
Step 2: If not, exchange with the child, and apply heapify() on the position where you
exchanged from.

Code
#include <stdio.h>
#include <stdlib.h>
int t_size = 1, u_size = 0;
void displayHeap(int *);
int * insert(int *, int);
void heapify(int *, int);
int main(){
int *heap, data, i, ch, rootIndex, childIndex, temp,n;
char c;
while(1){
printf("\n1. Create Heap\t2. Insert\t3. Display\t4. Delete\t5. Print Largest Value\t6.
Exit\nEnter youe option: ");
scanf(" %d", &ch);
switch(ch){
case 1 :printf("Enter the no.of nodes:");
scanf("%d", &n);
for(int i=0;i<n;i++){
printf("Enter data : ");
scanf("%d", &data);
heap = insert(heap, data);
}
for(i = u_size/2; i>0; i--)
heapify(heap, i);
break;
case 2 :t_size++; u_size++;
if(u_size == 1)
heap = (int *) calloc(t_size, sizeof(int));
else
heap = (int *) realloc(heap, t_size * sizeof(int));
printf("Enter data to insert : ");
scanf("%d", &data);
heap[u_size] = data;
childIndex = u_size;
rootIndex = u_size/2;
while(heap[childIndex] > heap[rootIndex] && rootIndex > 0){
temp = heap[childIndex];
heap[childIndex] = heap[rootIndex];
heap[rootIndex] = temp;
childIndex /= 2;
rootIndex /= 2;
}
break;
case 3 : displayHeap(heap);
break;
case 4 : if(u_size == 0)
printf("Heap empty...\n");
else{
data = heap[1];
heap[1] = heap[u_size];
t_size--; u_size--;
heap = (int *) realloc(heap, t_size *
sizeof(int));
if(heap != NULL)
heapify(heap, 1);
printf("%d deleted...\n", data);
}
break;
case 5 : if(u_size == 0)
printf("Heap Empty...\n");
else{printf("Largest value : %d\n", heap[1]);}
break;
case 6 : exit(0);
default : printf("! INVALID CHOICE !\n");
}}
return 0;
}
void displayHeap(int *heap){
int i;
printf("INDEX : ");
for(i = 0; i<t_size; i++)
printf("%d\t", i);
printf("\nVALUE : ");
for(i = 0; i<t_size; i++)
printf("%d\t", heap[i]);
printf("\n");
}
int * insert(int *heap, int data){
u_size++; t_size++;
if(u_size == 1)
heap = (int *) calloc(t_size, sizeof(int));
else
heap = (int *) realloc(heap, t_size * sizeof(int));
*(heap + u_size) = data;
return heap;
}
void heapify(int *heap, int index){
int lchild, rchild, largestIndex, temp;
lchild = 2*index; rchild = 2*index + 1;
largestIndex = index;
if(lchild <= u_size && heap[lchild] > heap[index])
largestIndex = lchild;
if(rchild <= u_size && heap[rchild] > heap[largestIndex])
largestIndex = rchild;
if(largestIndex != index){
temp = heap[index];
heap[index] = heap[largestIndex];
heap[largestIndex] = temp;
heapify(heap, largestIndex);
}
}
Output

15. Write a program to implement Depth First Search (DFS) graph traversal methods.
Algorithm
Step 1: Start
Step 2: Declare a struct NODE with fields data as integer, next as struct node *.
Step 3: Create a stack and a visited array.
Step 4: Get the graph.
Step 5: Apply dfs()
Step 6: Exit.
dfs(graph, vertex v) :
Step 1: If the vertex v is not visited print ‘v’.
Step 2: Repeat steps 3 to 4 until all the adjacent vertex are not visited.
Step 3: Explore the adjacent vertices to ‘v’.
Step 4: If adjacent vertex is not visited :push ‘v’ in the stack.Call dfs(graph, adjacent vertex)
Step 5: If stack is not empty : dfs(pop the stack)
Step 6: Exit

Code
#include <stdio.h>
#include <stdlib.h>
struct NODE{
int data;
struct NODE *next;
};
struct NODE *top = NULL;
int *visited;
void push(int);
int pop();
struct NODE * createNode(int);
int searchNode(struct NODE *, int);
void dispAdjList(struct NODE **, int);
void dfs(struct NODE **, int);
int main(){
struct NODE **adjList, *curr;
int n, i, vertex, found;
char ch;
printf("Enter no. of vertices : ");
scanf("%d", &n);
visited = (int *) calloc(n, sizeof(int));
adjList = (struct NODE **) calloc(n, sizeof(struct NODE *));
for(i = 0; i<n; i++)
adjList[i] = NULL;
for(i = 0; i<n; i++){
printf("\nLink node %d (y/n) : ", i);
scanf(" %c", &ch);
while(ch == 'y' || ch == 'Y'){
do{
printf("Node no.(0-%d) : ", n-1);
scanf("%d", &vertex);
} while (vertex < 0 || vertex >= n);
if(adjList[i] == NULL)
adjList[i] = createNode(vertex);
else{
found = searchNode(adjList[i], vertex);
if(!found)
{
curr = adjList[i];
while(curr->next != NULL)
curr = curr->next;
curr->next = createNode(vertex);
}
else
printf("Already linked...\n");
}
printf("Link More(y/n) : ");
scanf(" %c", &ch);
}}
printf("\nDisplaying adjList\n");
dispAdjList(adjList, n);
do{
for(i = 0; i<n; i++)
visited[i] = 0;
printf("Choose starting vertex for DFS : ");
scanf("%d", &vertex);
dfs(adjList, vertex);
printf("\nTraverse it again(y/n) : ");
scanf(" %c", &ch);
} while (ch == 'y' || ch == 'Y');
return 0;
}
struct NODE * createNode(int data){
struct NODE *newNode;
newNode = (struct NODE *) malloc(sizeof(struct NODE));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
void dispAdjList(struct NODE **adjList, int n){
int i;
struct NODE *curr;
for(i = 0; i<n; i++){
printf("%d : ", i);
curr = adjList[i];
while(curr != NULL){
printf("%d => ", curr->data);
curr = curr->next;
} printf(" N");
printf("\n");
}
}
int searchNode(struct NODE * node, int data){
if(node == NULL)
return 0;
else{
while(node != NULL){
if(node->data == data)
return 1;
node = node->next;
}
return 0;
}
}
void push(int n){
struct NODE * temp;
temp = createNode(n);
temp->next = top;
top = temp;
}
int pop(){
int data = -1;
if(top != NULL){
data = top->data;
top = top->next;
}
return data;
}
void dfs(struct NODE **adjList, int v){
struct NODE *vertex;
int n;
if(visited[v] == 0){
printf("%d => ", v);
visited[v] = 1;
}
vertex = adjList[v];
while(vertex != NULL){
n = vertex->data;
if(visited[n] == 0){
push(v);
dfs(adjList, n);
}
vertex = vertex->next;
}
v = pop();
if(v != -1)
dfs(adjList, v);
}
Output

16. Write a program to implement Breadth First Search (BFS) graph traversal methods.

Algorithm

Step 1: Start
Step 2: Declare a struct NODE with fields data as integer, next as struct node *.
Step 3: Create a stack and a visited array.
Step 4: Get the graph.
Step 5: Apply bfs()
Step 6: Exit.
bfs(graph, vertex v)
Step 1: If the vertex v is not visited print ‘v’.
Step 2: Repeat the steps 3 to 4 until all the adjacent vertices are not visited.
Step 3: Explore the adjacent vertices to ‘v’.
Step 4: If adjacent vertex is not visited : push ‘adjacent vertex’ to queue.
Step 5: If queue is not empty apply bfs(dequeue())
Step 6: Exit

Code
#include <stdio.h>
#include <stdlib.h>
struct NODE{
int data;
struct NODE *next; };
struct NODE *front = NULL, *rear = NULL;
int n, *visited;
void enqueue(int);
int dequeue();
struct NODE * createNode(int);
int searchNode(struct NODE *, int);
void insertNode(struct NODE *, int);
void bfs(struct NODE **, int);
int main(){
struct NODE **adjList, *curr;
int i, vertex, v;
char ch;
printf("Enter no. of vertices : ");
scanf("%d", &n);
adjList = (struct NODE **) calloc(n, sizeof(struct NODE *));
for(i = 0; i<n; i++)
adjList[i] = NULL;
visited = (int *) calloc(n, sizeof(int));
for(vertex = 0; vertex < n; vertex++){
printf("Want to link %d (y/n) : ", vertex);
scanf(" %c", &ch);
while(ch == 'y' || ch == 'Y'){
do{ printf("Link with(0 - %d) : ", n-1);
scanf("%d", &v);
} while (v < 0 || v >= n);
if(adjList[vertex] == NULL)
adjList[vertex] = createNode(v);
else{
if(searchNode(adjList[vertex], v) == -1)
insertNode(adjList[vertex], v);
else
printf("Duplicate(%d) not allowed...\n", v);
}
printf("Link More(y/n) : ");
scanf(" %c", &ch);
}
}
for(i = 0; i<n; i++){
printf("%d : ", i);
curr = adjList[i];
while(curr != NULL){
printf("%d -> ", curr->data);
curr = curr->next;
}
printf("N\n");
}
do{
for(i = 0; i<n; i++)
visited[i] = 0;
printf("Enter a vertex to start BFS : ");
scanf("%d", &v);
bfs(adjList, v);
printf("N");
printf("\nPerform BFS again(y/n) : ");
scanf(" %c", &ch);
} while (ch == 'y' || ch == 'Y');
return 0; }
void enqueue(int data){
struct NODE * newNode;
newNode = createNode(data);
if(front == NULL)
front = rear = newNode;
else{
rear->next = newNode;
rear = newNode;
}}
int dequeue(){
int data;
if(front == NULL)
return -1;
data = front->data;
if(front == rear)
front = rear = NULL;
else
front = front->next;
return data; }
struct NODE * createNode(int data){
struct NODE * temp;
temp = (struct NODE *) malloc(sizeof(struct NODE));
temp->data = data;
temp->next = NULL;
return temp; }
int searchNode(struct NODE * node, int data){
while(node != NULL){
if(node->data == data)
return 1;
node = node->next;
}
return -1; }
void insertNode(struct NODE * node, int data){
while(node->next != NULL)
node = node->next;
node->next = createNode(data);
}
void bfs(struct NODE **adjList, int v){
struct NODE *curr;
if(visited[v] == 0){
visited[v] = 1;
printf("%d -> ", v);
}
curr = adjList[v];
while(curr != NULL){
if(visited[curr->data] == 0){
printf("%d -> ", curr->data);
visited[curr->data] = 1;
enqueue(curr->data);
}
curr = curr->next; }
v = dequeue();
if(v != -1)
bfs(adjList, v);
}
Output
17. Create a text file containing the name, height, weight of the students in a class.
Perform Quick sort and Merge sort on this data and store the resultant data in two
separate files. Also write the time taken by the two sorting methods into the respective
files.
Sony Mathew 5.5 60 Arun Sajeev 5.7 58 Rajesh Kumar 6.1 70

Algorithm
Step 1: Start
Step 2: Open file1.txt and file2.txt with “a+”(append and read) option, so that the previous
content of the file is not deleted. If files don’t exist, they will be created.
Step 3: Explicitly write a newline (“\n”) to the destination file to enhance readability.
Step 4: Write content from source file to destination file.
Step 5: Display the contents in file2.txt to console (stdout).
Quick sort :
Step 1: Pick an element, called a pivot, from the array.
Step 2: Partition the array into two halves, the left side of the array containing
Step 3: Elements less than the pivot element, and the right side of the array containing
elements greater than the pivot element.
Step 4: Recursively sort the left side of the array and the right side of the array.
Step 5: Return the array.
Merge sort :
Step 1: Start
Step 2: Declare an array and left, right, mid variable
Step 3: Perform merge function.
mergesort(array,left,right)
mergesort (array, left, right)
if left > right
return
else
mid= (left+right)/2
mergesort(array, left, mid)
mergesort(array, mid+1, right)
merge(array, left, mid, right)
Step 4: Stop

Code
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int partition(int, int);
void quickSort(int, int);
struct stud
{
char name[20];
float hgt, wgt;
}s[10];
struct Name
{
char st_name[10];
} name[10], copy[10];
void quickSort(int low, int high){
int pIndex;
if (low<high){
pIndex = partition(low, high);
quickSort(low, pIndex-1);
quickSort(pIndex+1, high);
}
}
int partition(int low, int high){
char pivot[10], temp[10];
int i, j;
strcpy(pivot, name[low].st_name);
i = low; j = high;
while(i<j){
while(strcmp(name[i].st_name, pivot) == 0 || strcmp(name[i].st_name, pivot) == -1)
i++;
while(strcmp(name[j].st_name, pivot) == 1)
j--;
if(i<j){
strcpy(temp, name[i].st_name);
strcpy(name[i].st_name, name[j].st_name);
strcpy(name[j].st_name, temp);
}
}
strcpy(temp, name[j].st_name);
strcpy(name[j].st_name, name[low].st_name);
strcpy(name[low].st_name, temp);
return j;
}
void merge(int l, int m, int r){
int i, j, k;
int n1 = m - l + 1, n2 = r - m;
struct Name L[10], R[10];
for (i = 0; i < n1; i++)
strcpy(L[i].st_name,name[l + i].st_name);
for (j = 0; j < n2; j++)
strcpy(R[j].st_name, name[m + 1 + j].st_name);
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2) {
if (strcmp(L[i].st_name,R[j].st_name) == -1) {
strcpy(name[k].st_name, L[i].st_name);
i++;
}
else {
strcpy(name[k].st_name, R[j].st_name);
j++;
}
k++;
}
while (i < n1) {
strcpy(name[k].st_name, L[i].st_name);
i++;
k++;
}
while (j < n2) {
strcpy(name[k].st_name, R[j].st_name);
j++;
k++;
}
}
void mergeSort(int l, int r){
int m;
if (l < r) {
m = l + (r - l) / 2;
mergeSort(l, m); mergeSort(m + 1, r); merge(l, m, r);
}
}
int main(){
FILE *fp;
int i,n, k;
char c, str[100];
fp = fopen("student.txt", "w");
printf("Enter record of student:\n\n");
printf("Enter no. of entries : ");
scanf("%d", &n);
for(i = 0; i<n; i++)
{
printf("\nEnter name of %d th student: ",i+1);
scanf(" %s", s[i].name);
fprintf(fp, "%s ",s[i].name);
}
fprintf(fp, "\n");
for(i = 0; i<n; i++){
printf("\nEnter height of %d th student: ",i+1);
scanf(" %f", &s[i].hgt);
fprintf(fp, "%f ",s[i].hgt);
}
fprintf(fp, "\n");
for(i = 0; i<n; i++){
printf("\nEnter weight of %d th student: ",i+1);
scanf(" %f", &s[i].wgt);
fprintf(fp, "%f ",s[i].wgt);
}
printf("\nRecord stored in file...\n");
fclose(fp);
fp = fopen("student.txt", "r");
i = 0; k = 0;
while((c = getc(fp)) != '\n'){
if (c == ' '){
str[i] = '\0';
strcpy(name[k].st_name, str);
i = 0;
k++;
}
else{
str[i] = c; i++;
}
}
fclose(fp);
fp = fopen("student.txt", "r");
while((c = getc(fp)) != EOF)
printf("%c", c);
fclose(fp);
quickSort(0, n-1);
printf("\n");
for(i = 0; i<n; i++)
printf("%s\t", name[i].st_name);
fp = fopen("quickSortFile.txt", "w");
for(i = 0; i<n; i++)
fprintf(fp, "%s\t", name[i].st_name);
fclose(fp);
printf("\nQuicksort writing is done\n");
fp = fopen("student.txt", "r");
i = 0;
k = 0;
while((c = getc(fp)) != '\n'){
if (c == ' '){
str[i] = '\0';
strcpy(name[k].st_name, str);
i = 0;
k++;
}
else{
str[i] = c;
i++;
}
}
fclose(fp);
mergeSort(0,n- 1);
printf("\n");
for(i = 0; i<n; i++)
printf("%s\t", name[i].st_name);
fp = fopen("mergedSortFile.txt", "w");
for(i = 0; i<n; i++)
fprintf(fp, "%s\t", name[i].st_name);
fclose(fp);
printf("\nMergesort writing is done\n");
return 0;
}

Output
18. Write a program to sort a set of numbers using Heap sort and find a particular
number from the sorted set using Binary Search.

Algorithm

Step 1: Start
Step 2: Declare ‘heap’ as an array of integers.
Step 3: Repeat steps 3 to till user exits
Step 4: Read ch.
Step 5: If ch == 1: call insert() to construct the heap
Step 6: Otherwise if ch == 2 : call displayHeap().
Step 7: Otherwise if ch == 3 : call heapSort().
Step 8: Otherwise if ch == 4 : binarySearch()
Step 9: Otherwise if ch == 5 : exit the program
Step10: Exit

Insert(data) :
Step 1: Read all the elements in an array.
Step 2: Assign i = sizeof(heap)/2
Step 3: Repeat steps 4 to 5 till i>0
Step 4: Apply heapify(i)
Step 5: Decrement i
Step 6: Exit

Delete(data) :
Step 1: If size of array = 0 print “Heap empty” and go to the last step
Step 2: Otherwise Replace the root element with the last leaf node and delete the last
index.
Step 3: Apply heapify(1) on the first index

Heapify(index) :
Step 1: Check if the root node is greater than the left and right child.
Step 2: If not, exchange with the child, and apply heapify() on the position where you
exchanged from.

HeapSort() :
Step 1: Declare an array ‘sortedArray’.
Step 2: Continuously apply delete() on the heap and store the deleted element in the
‘sortedArray’, till the heap becomes empty.

BinarySearch(data, low, high) :

Step 1: Repeat steps 2 to 5 till low<=high
Step 2: Assign mid = (low+high) /2
Step 3: If data < arr[mid] : low = mid+1
Step 4: Otherwise if data > arr[mid] : high = mid-1
Step 5: Otherwise print ‘data found at the respective position’ and return
Step 6: Print ‘data not found’
Step 7: Exit

Code

#include <stdio.h>
#include <stdlib.h>
int t_size = 1, u_size = 0;
int array_size;
void displayHeap(int *);
int * insert(int *, int);
void heapify(int *, int);
void binarySearch(int *, int);
int main(){
int *heap, *sortedArray, i, ch, rootIndex, childIndex, temp, data,n;
char c;
while(1){
printf("\n1. Create Heap\t2. Display\t3. Heap Sort\t4. Binary Search\t5. Exit\nEnter your
option : ");
scanf(" %d", &ch);
switch(ch){
case 1 :printf("Enter the no.of nodes:");
scanf("%d",&n);
for(int i=0;i<n;i++){
printf("Enter data : ");
scanf("%d", &data);
heap = insert(heap, data); }
for(i = u_size/2; i>0; i--)
heapify(heap, i);
break;
case 2 : displayHeap(heap);
break;
case 3 : if(u_size == 0)
printf("Heap empty...\n");
else{
sortedArray = (int *) calloc(u_size, sizeof(int));
array_size = u_size;
for(i = 0; i<array_size; i++){
sortedArray[i] = heap[1];
heap[1] = heap[u_size];
t_size--; u_size--;
heap = (int *) realloc(heap, t_size * sizeof(int));
if(heap != NULL)
heapify(heap, 1);
}
}
printf("\nSorted Array : ");
for(i = 0; i<array_size; i++)
printf("%d\t", sortedArray[i]);
break;
case 4 : if(heap == NULL)
printf("Empty Heap...\n");
else{
do{
printf("Size of the array : %d\n", array_size);
printf("Enter the data to search : ");
scanf("%d", &data);
binarySearch(sortedArray, data);
printf("Want to search again(y/n) : ");
scanf(" %c", &ch);
} while (ch == 'y' || ch == 'Y');
}
case 5 : exit(0);
default : printf("! INVALID CHOICE !\n"); }
}
return 0;
}
void displayHeap(int *heap){
int i;
printf("INDEX : ");
for(i = 0; i<t_size; i++)
printf("%d\t", i);
printf("\nVALUE : ");
for(i = 0; i<t_size; i++)
printf("%d\t", heap[i]);
printf("\n");
}
int * insert(int *heap, int data){
u_size++; t_size++;
if(u_size == 1)
heap = (int *) calloc(t_size, sizeof(int));
else
heap = (int *) realloc(heap, t_size * sizeof(int));
*(heap + u_size) = data;
return heap;
}
void heapify(int *heap, int index){
int lchild, rchild, largestIndex, temp;
lchild = 2*index; rchild = 2*index + 1;
largestIndex = index;
if(lchild <= u_size && heap[lchild] > heap[index])
largestIndex = lchild;
if(rchild <= u_size && heap[rchild] > heap[largestIndex])
largestIndex = rchild;
if(largestIndex != index){
temp = heap[index];
heap[index] = heap[largestIndex];
heap[largestIndex] = temp;
heapify(heap, largestIndex); }

}
void binarySearch(int *arr, int elem){
int low, high, mid;
low = 0; high = array_size-1;
while(low <= high){
mid = (low+high)/2;
if(elem < arr[mid])
low = mid+1;
else if(elem > arr[mid])
high = mid - 1;
else{
printf("Element %d found at position %d.\n", elem, mid+1);
break;
}}
if(low > high)
printf("Element %d not found...\n", elem);
}
Output

19. Implement a Hash table using Chaining method. Let the size of hash table be 10 so
that the index varies from 0 to 9.

Algorithm

Step 1: Start
Step 2: Declare a structure NODE with fields int ‘data’, struct NODE * left, *right.
Step 3: Declare ‘hashTable’ as an array of pointers to struct NODE.
Step 4: Read the elements.
Step 5: Hash the element to the respective position in the hashtable using function hash(x)
= x%10.
Step 6: Read the ‘elem’ to be searched. Generate the key and search the element in the
hashtable.
Step 7: Read the ‘elem’ to be dropped. Generate the key and delete the element in the
Hashtable
Step 8: Stop

Code

#include <stdio.h>
#include <stdlib.h>
#define HASH(x) x%n
struct NODE {
int data;
struct NODE *next;
};
int main(){
struct NODE **hashTable, *temp, *curr, *prev;
int ch, n, i, num, key, elemCnt,n1;
printf("Size of the HashTable : ");
scanf("%d", &n);
hashTable = (struct NODE **) calloc(n, sizeof(struct NODE *));
for(i = 0; i<n; i++)
*(hashTable + i) = NULL;
elemCnt = 0;
while(1)
{
printf("\nHASH TABLE MENU \n");
printf("1. Insert\t2. Remove\t3. Display\t4. DisplaySize\t5. Exit\nChoose your option : ");
scanf("%d", &ch);
switch(ch){
case 1 :printf("Enter the no.of nodes:");
scanf("%d",&n1);
for(i=0;i<n1;i++){
printf("Enter data : ");
scanf("%d", &num);
temp = (struct NODE *) calloc(1, sizeof(struct NODE));
temp->data = num;
temp->next = NULL;
key = HASH(num);
if(*(hashTable + key) == NULL)
*(hashTable + key) = temp;
else{
curr = *(hashTable + key);
while(curr->next != NULL)
curr = curr->next;
curr->next = temp;
}
printf("%d successfully hashed...\n", num);
elemCnt++; }
break;
case 2 : printf("Element to remove : ");
scanf("%d", &num);
key = HASH(num);
curr = *(hashTable + key);
while(curr != NULL){
if(curr->data == num){
temp = curr;
if(curr == *(hashTable + key))
*(hashTable + key) = curr->next;
else
prev->next = curr->next;
free(curr);
printf("%d removed ...\n", num);
break;
}
prev = curr;
curr = curr->next;
}
if(curr == NULL)
printf("! Value not found !\n");
break;
case 3 : for(i = 0; i<n; i++){
printf("%d : ", i);
curr = *(hashTable + i);
while(curr != NULL){
printf("%d -> ", curr->data);
curr = curr->next;
}
printf("N\n");
}
break;
case 4 : printf("Element Count : %d\n", elemCnt);
break;
case 5 : exit(0);
default : printf("\n! Invalid input!!!");
}}
return 0;
}

Output
20. Implement a Hash table that uses Linear Probing for collision resolution.

Algorithm

Step 1: Start
Step 2: Create an array of structure (i.e a hash table).
Step 3: Take a key and a value to be stored in hash table as input.
Step 4: Corresponding to the key, an index will be generated i.e every key is stored in a
particular array index.
Step 5: Using the generated index, access the data located in that array index.
Step 6: In case of absence of data, create one and insert the data item (key and value) into
it and increment the size of hash table.
Step 7: In case the data exists, probe through the subsequent elements (looping back if
necessary) for free space to insert new data item.
Step 8: To display all the elements of hash table, element at each index is accessed (via for
loop).
Step 9: To remove a key from hash table, we will first calculate its index and delete it if
key matches, else probe through elements until we find key or an empty space
where not a single data has been entered (means data does not exist in the hash
table).
Step 10: Exit

Code

#include <stdio.h>
#include <stdlib.h>
struct item{
int key;
int value;
};
struct hashtable_item{
int flag;
struct item *data;
};
struct hashtable_item *array;
int size = 0;
int max = 10;
void init_array(){
int i;
for (i = 0; i < max; i++){
array[i].flag = 0;
array[i].data = NULL;
}
}
int hashcode(int key){
return (key % max);
}
void insert(int key, int value){
int index = hashcode(key);
int i = index;
struct item *new_item = (struct item *)malloc(sizeof(struct item));
new_item->key = key;
new_item->value = value;
while (array[i].flag == 1){
if (array[i].data->key == key){
printf("\n Key already exists, hence updating its value \n");
array[i].data->value = value;
return;
}
i = (i + 1) % max;
if (i == index){
printf("\n Hash table is full, cannot insert any more item \n");
return;
}
}
array[i].flag = 1;
array[i].data = new_item;
size++;
printf("\n Key (%d) has been inserted \n", key);
}
void remove_element(int key){
int index = hashcode(key);
int i = index;
while (array[i].flag != 0){
if (array[i].flag == 1 && array[i].data->key == key){
array[i].flag = 2;
array[i].data = NULL;
size--;
printf("\n Key (%d) has been removed \n", key);
return;
}
i = (i + 1) % max;
if (i == index)
{
break;
}
}
printf("\n This key does not exist \n");
}
void display(){
int i;
for (i = 0; i < max; i++){
struct item *current = (struct item *)array[i].data;
if (current == NULL){
printf("\n Array[%d] has no elements \n", i);
}
else{
printf("\n Array[%d] has elements -: \n %d (key) and %d(value) ", i, current->key, current-
>value);
}
}
}
int size_of_hashtable(){return size;}
int main(){
int choice, key, value, n, c;
array = (struct hashtable_item *)malloc(max * sizeof(struct hashtable_item));
init_array(); while(1){
printf("1.Inserting \t2.Removing item \t3.Size of Hashtable \t4.Display \n Please enter your
choice-:");
scanf("%d", &choice);
switch (choice){
case 1: printf("Enter the no.of elements:");
scanf("%d",&c);
for(int i=0;i<c;i++){
printf("Enter key and value-:\t");
scanf("%d %d", &key, &value);
insert(key, value);
}
break;
case 2: printf("Deleting in Hashtable \n Enter the key to delete-:");
scanf("%d", &key);
remove_element(key);
break;
case 3: n = size_of_hashtable();
printf("Size of Hashtable is-:%d\n", n);
break;
case 4: display();
break;
case 5: exit(0);
default: printf("Wrong Input\n");
}
}
return 0;
}

Output