LOYOLA INSTITUTE OF TECHNOLOGY

PALANCHUR, CHENNAI

CS3311 - DATA STRUCTURE LABORATORY

(Lab Manual)

DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

III SEMESTER

(2021 REGULATION)
CS3311 DATA STRUCTURES LABORATORY LTPC
0 0 3 1.5
COURSE OBJECTIVES:

• To demonstrate array implementation of linear data structure algorithms.

• To implement the applications using Stack.
• To implement the applications using Linked list
• To implement Binary search tree and AVL tree algorithms.
• To implement the Heap algorithm.
• To implement Dijkstra’s algorithm.
• To implement Prim’s algorithm
• To implement Sorting, Searching and Hashing algorithms.

LIST OF EXERCISES:

1. Array implementation of Stack, Queue and Circular Queue ADTs

2. Implementation of Singly Linked List
3. Linked list implementation of Stack and Linear Queue ADTs
4. Implementation of Polynomial Manipulation using Linked list
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)

TOTAL:45 PERIODS
COURSE OUTCOMES:

At the end of this course, the students will be able to:

CO1: Implement Linear data structure algorithms.

CO2: Implement applications using Stacks and Linked lists
CO3: Implement Binary Search tree and AVL tree operations.
CO4: Implement graph algorithms.
CO5: Analyze the various searching and sorting algorithms.
Institute Vision and Mission:
Vision:
To be a world class institution in creating and disseminating knowledge through a contemporary
and rigorous educational experience that facilitates our students to be technologically competent
and ethically strong to serve the society for the betterment of mankind.
Mission:
We, at Loyola Institute of Technology dedicate and commit ourselves to
• Achieve, sustain and foster unmatched excellence in Technical Education.
• Provide an intellectually inspiring environment for creative learning and research.
• Collaborate with industry and research and development organizations to promote
innovative research, employability and entrepreneurship for nation building.
• Inculcate high regard for ethical practices and understanding human values.

Department Vision and Mission:

Vision:
To be a centre of excellence in providing global standard education through contemporary and
rigorous educational experience in the field of computer science and engineering that facilitates
our students to be competent in technology and responsible professional to serve the society with
ethics.
Mission:
We, at the department of Computer Science and Engineering will strive to:
• Provide quality education in the field of computer science and Engineering that enables
our students to excel in technical education.
• Promote self learning to incorporate new ideas and technologies in Computer Science and
Engineering.
• Integrate research, academics, business practices and innovative solutions for students to
face global challenges and to promote entrepreneurship for nation building.
• Provide an environment that enables our students to be ethically strong to serve the society.
Program Educational Objectives (PEO’s):

After successful completion of the program, the graduates will be able to

PEO 1: Apply the fundamental knowledge of Computer Science and Engineering to analyze and
synthesize the information to arrive optimal solutions for the defined problems.
PEO2: Manifest technical and intellectual sustainability in professionally competent
environments or will become entrepreneurs.
PEO 3: Pursue higher education or engross them in Research and Development establishments to
meet the societal needs.
PEO 4: Exhibit ethical and moral values to work in multidisciplinary environment and provide
solutions to real time problems.

Program Specific Objectives (PSO):

PSO 1: Understand the requirements and identify the appropriate/emerging technologies and
domains with respect to computer science & engineering to get the appropriate/suitable solutions.
PSO 2: Identify the challenges in computation and networking domains and provide
optimal/innovative solutions using appropriate technologies.
PSO 3: Use the technical knowledge to establish new startups to build products and provide web
services.
Program Outcomes (PO’s):
[Link] Program Outcomes
PO 1 Engineering Knowledge: Apply the knowledge of mathematics, science,
engineering fundamentals, and an engineering specialization to the solution of
complex engineering problems.
PO 2 Problem Analysis: Identify, formulate, review research literature, and analyze
complex engineering problems reaching substantiated conclusions using first
principles of mathematics, natural sciences, and engineering sciences.
PO 3 Design / Development of Solutions: Design solutions for complex engineering
problems and design system components or processes that meet the specified needs
with appropriate consideration for the public health and safety, and the cultural,
societal, and environmental considerations.
PO 4 Conduct Investigation of Complex Problems: Use research-based knowledge and
research methods including design of experiments, analysis and interpretation of
data, and synthesis of the information to provide valid conclusions.
PO 5 Modern Tool Usage: Create, select, and apply appropriate techniques, resources,
and modern engineering and IT tools including prediction and modeling to complex
engineering activities with an understanding of the limitations.
PO 6 The Engineer and Society: Apply reasoning informed by the contextual knowledge
to assess societal, health, safety, legal and cultural issues and the consequent
responsibilities relevant to the professional engineering practice.
PO 7 Environment and Sustainability: Understand the impact of the professional
engineering solutions in societal and environmental contexts, and demonstrate the
knowledge of, and need for sustainable development
PO 8 Ethics: Apply ethical principles and commit to professional ethics and
responsibilities and norms of the engineering practice
PO 9 Individual and Team Work: Function effectively as an individual, and as a member
or leader in diverse teams, and in multidisciplinary settings
PO 10 Communication: Communicate effectively on complex engineering activities with
the engineering community and with society at large, such as, being able to
comprehend and write effective reports and design documentation, make effective
presentations, and give and receive clear instructions.
PO 11 Project Management and Finance: Demonstrate knowledge and understanding of
the engineering and management principles and apply these to one’s own work, as a
member and leader in a team, to manage projects and in multidisciplinary
environments.
PO 12 Life-Long Learning: Recognize the need for, and have the preparation and ability
to engage in independent and life-long learning in the broadest context of
technological change.
 COURSE OUTCOME:

Course Code: Year / Sem : II/III

Subject Code / Name : CS3311 / Data Structure Laboratory
At the end of the course, the student will be able to:
C.1 Implement Linear data structure algorithms.
C.2 Implement applications using Stacks and Linked lists
C.3 Implement Binary Search tree.
C.4 Implement AVL tree operations
C.5 Implement graph algorithms.
C.6 Analyse the various searching and sorting algorithms

CO-PO Mapping:

Course PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12 PSO1 PSO2 PSO3

C.1 1 2 2 1 2 1 2 2 2 2 3
C.2 3 3 1 1 1 1 1 3 1 2 2
C.3 2 1 3 1 1 1 2 3 3 3 3
C.4 3 1 3 3 1 2 3 3 2 1 2
C.5 3 2 1 1 2 3 3 3 1 3 1 3
C.6 3 3 1 1 1 2 2 1 1 3 2 3
Ex. No. 1A ARRAY IMPLEMENTATION OF STACK
Date:

Aim
To implement stack operations using array.

Algorithm

Step 1 - Include all the header files which are used in the program and define a
constant 'SIZE' with specific value.
Step 2 - Declare all the functions used in stack implementation.
Step 3 - Create a one dimensional array with fixed size (int stack[SIZE])
Step 4 - Define a integer variable 'top' and initialize with '-1'. (int top = -1)
Step 5 - In main method, display menu with list of operations and make
suitable function calls to perform operation selected by the user on the stack.

PROGRAM CODE

#include<stdio.h>
#include<conio.h>
#define SIZE 10
void push(int);
void pop();
void display();
int stack[SIZE], top = -1;
void main()
{
int value, choice;
clrscr();
while(1){
printf("\n\n***** MENU *****\n");
printf("1. Push\n2. Pop\n3. Display\n4. Exit");
printf("\nEnter your choice: ");
scanf("%d",&choice);
switch(choice){
case 1: printf("Enter the value to be insert: ");
scanf("%d",&value);
push(value);
break;
case 2: pop();
break;
case 3: display();
break;
case 4: exit(0);
default: printf("\nWrong selection!!! Try again!!!");
}
}
}
void push(int value){
if(top == SIZE-1)
printf("\nStack is Full!!! Insertion is not possible!!!");
else{
top++;
stack[top] = value;
printf("\nInsertion success!!!");
}
}
void pop(){
if(top == -1)
printf("\nStack is Empty!!! Deletion is not possible!!!");
else{
printf("\nDeleted : %d", stack[top]);
top--;
}
}
void display(){
if(top == -1)
printf("\nStack is Empty!!!");
else{
int i;
printf("\nStack elements are:\n");
for(i=top; i>=0; i--)
printf("%d\n",stack[i]);
}
}
OUTPUT

RESULT

Thus the C Program to implement the Stack operation using Arrays are implemented
successfully.
Ex. No. 1B ARRAY IMPLEMENTATION OF QUEUE
Date:

Aim
To implement Queue operations using array.

Algorithm

Step 1: IF REAR = MAX - 1

Write OVERFLOW
Go to step
[END OF IF]
Step 2: IF FRONT = -1 and REAR = -1
SET FRONT = REAR = 0
ELSE
SET REAR = REAR + 1
[END OF IF]
Step 3: Set QUEUE[REAR] = NUM
Step 4: EXIT

PROGRAM CODE

#include<stdio.h>
#include<stdlib.h>
#define maxsize 5
void insert();
void delete();
void display();
int front = -1, rear = -1;
int queue[maxsize];
void main ()
{
int choice;
while(choice != 4)
{
printf("\n*************************Main
Menu*****************************\n");

printf("\n==================================================
===============\n");
printf("\[Link] an element\[Link] an element\[Link] the
queue\[Link]\n");
printf("\nEnter your choice ?");
scanf("%d",&choice);
switch(choice)
 {
case 1:
insert();
break;
case 2:
delete();
break;
case 3:
display();
break;
case 4:
exit(0);
break;
default:
printf("\nEnter valid choice??\n");
}
}
}
void insert()
{
int item;
printf("\nEnter the element\n");
scanf("\n%d",&item);
if(rear == maxsize-1)
{
printf("\nOVERFLOW\n");
return;
}
if(front == -1 && rear == -1)
{
front = 0;
rear = 0;
}
else
{
rear = rear+1;
}
queue[rear] = item;
printf("\nValue inserted ");

}
void delete()
{
int item;
if (front == -1 || front > rear)
{
printf("\nUNDERFLOW\n");
return;

}
 else
{
item = queue[front];
if(front == rear)
{
front = -1;
rear = -1 ;
}
else
{
front = front + 1;
}
printf("\nvalue deleted ");
}

void display()
{
int i;
if(rear == -1)
{
printf("\nEmpty queue\n");
}
else
{ printf("\nprinting values .....\n");
for(i=front;i<=rear;i++)
{
printf("\n%d\n",queue[i]);
} }}

OUTPUT:
*************Main Menu**************
==============================================
[Link] an element
[Link] an element
[Link] the queue
[Link]
Enter your choice ?1
Enter the element
123
Value inserted

Result
Thus the C Program to implement the Queue operations using array was
executed successfully.
Ex. No. 1C ARRAY IMPLEMENTATION OF CIRCULAR QUEUE
Date:

Aim
To implement Circular Queue operations using array.

Algorithm

Step 1: IF (REAR+1)%MAX = FRONT

Write " OVERFLOW "
Goto step 4
[End OF IF]

Step 2: IF FRONT = -1 and REAR = -1

SET FRONT = REAR = 0
ELSE IF REAR = MAX - 1 and FRONT ! = 0
SET REAR = 0
ELSE
SET REAR = (REAR + 1) % MAX
[END OF IF]

Step 3: SET QUEUE[REAR] = VAL

Step 4:Exit

PROGRAM CODE

#include <stdio.h>
# define max 6
int queue[max]; // array declaration
int front=-1;
int rear=-1;
// function to insert an element in a circular queue
void enqueue(int element)
{
if(front==-1 && rear==-1) // condition to check queue is empty
{
front=0;
rear=0;
queue[rear]=element;
}
else if((rear+1)%max==front) // condition to check queue is full
{
printf("Queue is overflow..");
}
else
{
rear=(rear+1)%max; // rear is incremented
queue[rear]=element; // assigning a value to the queue at the rear position.
 }
}

// function to delete the element from the queue

int dequeue()
{
if((front==-1) && (rear==-1)) // condition to check queue is empty
{
printf("\nQueue is underflow..");
}
else if(front==rear)
{
printf("\nThe dequeued element is %d", queue[front]);
front=-1;
rear=-1;
}
else
{
printf("\nThe dequeued element is %d", queue[front]);
front=(front+1)%max;
}
}
// function to display the elements of a queue
void display()
{
int i=front;
if(front==-1 && rear==-1)
{
printf("\n Queue is empty..");
}
else
{
printf("\nElements in a Queue are :");
while(i<=rear)
{
printf("%d,", queue[i]);
i=(i+1)%max;
}
}
}
int main()
{
int choice=1,x; // variables declaration

while(choice<4 && choice!=0) // while loop

{
printf("\n Press 1: Insert an element");
printf("\nPress 2: Delete an element");
printf("\nPress 3: Display the element");
printf("\nEnter your choice");
 scanf("%d", &choice);

switch(choice)
{

case 1:

printf("Enter the element which is to be inserted");

scanf("%d", &x);
enqueue(x);
break;
case 2:
dequeue();
break;
case 3:
display();

}}
return 0;
}
OUTPUT:

RESULT
Thus the C program to implement the circular queue operations are executed
successfully.
Ex. No. 2 IMPLEMENTATION OF SINGLY LINKED LIST
Date:

AIM
To implement Singly linked list in C.

ALGORITHM

Step 1 - Include all the header files which are used in the program.
Step 2 - Declare all the user defined functions.
Step 3 - Define a Node structure with two members data and next
Step 4 - Define a Node pointer 'head' and set it to NULL.
Step 5 - Implement the main method by displaying operations menu and make
suitable function calls in the main method to perform user selected operation.

PROGRAM CODE
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

void insertAtBeginning(int);
void insertAtEnd(int);
void insertBetween(int,int,int);
void display();
void removeBeginning();
void removeEnd();
void removeSpecific(int);

struct Node
{
int data;
struct Node *next;
}*head = NULL;

void main()
{
int choice,value,choice1,loc1,loc2;
clrscr();
while(1){
mainMenu: printf("\n\n****** MENU ******\n1. Insert\n2. Display\n3.
Delete\n4. Exit\nEnter your choice: ");
scanf("%d",&choice);
switch(choice)
{
case 1: printf("Enter the value to be insert: ");
 scanf("%d",&value);
while(1){
printf("Where you want to insert: \n1. At Beginning\n2. At End\n3.
Between\nEnter your choice: ");
scanf("%d",&choice1);
switch(choice1)
{
case 1: insertAtBeginning(value);
break;
case 2: insertAtEnd(value);
break;
case 3: printf("Enter the two values where you wanto insert: ");
scanf("%d%d",&loc1,&loc2);
insertBetween(value,loc1,loc2);
break;
default: printf("\nWrong Input!! Try again!!!\n\n");
goto mainMenu;
}
goto subMenuEnd;
}
subMenuEnd:
break;
case 2: display();
break;
case 3: printf("How do you want to Delete: \n1. From Beginning\n2. From
End\n3. Spesific\nEnter your choice: ");
scanf("%d",&choice1);
switch(choice1)
{
case 1: removeBeginning();
break;
case 2: removeEnd();
break;
case 3: printf("Enter the value which you wanto delete: ");
scanf("%d",&loc2);
removeSpecific(loc2);
break;
default: printf("\nWrong Input!! Try again!!!\n\n");
goto mainMenu;
}
break;
case 4: exit(0);
default: printf("\nWrong input!!! Try again!!\n\n");
}
}
}

void insertAtBeginning(int value)

{
struct Node *newNode;
 newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
if(head == NULL)
{
newNode->next = NULL;
head = newNode;
}
else
{
newNode->next = head;
head = newNode;
}
printf("\nOne node inserted!!!\n");
}
void insertAtEnd(int value)
{
struct Node *newNode;
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
if(head == NULL)
head = newNode;
else
{
struct Node *temp = head;
while(temp->next != NULL)
temp = temp->next;
temp->next = newNode;
}
printf("\nOne node inserted!!!\n");
}
void insertBetween(int value, int loc1, int loc2)
{
struct Node *newNode;
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
if(head == NULL)
{
newNode->next = NULL;
head = newNode;
}
else
{
struct Node *temp = head;
while(temp->data != loc1 && temp->data != loc2)
temp = temp->next;
newNode->next = temp->next;
temp->next = newNode;
}
printf("\nOne node inserted!!!\n");
}

void removeBeginning()
{
if(head == NULL)
printf("\n\nList is Empty!!!");
else
{
struct Node *temp = head;
if(head->next == NULL)
{
head = NULL;
free(temp);
}
else
{
head = temp->next;
free(temp);
printf("\nOne node deleted!!!\n\n");
}
}
}
void removeEnd()
{
if(head == NULL)
{
printf("\nList is Empty!!!\n");
}
else
{
struct Node *temp1 = head,*temp2;
if(head->next == NULL)
head = NULL;
else
{
while(temp1->next != NULL)
{
temp2 = temp1;
temp1 = temp1->next;
}
temp2->next = NULL;
}
free(temp1);
printf("\nOne node deleted!!!\n\n");
}
}
void removeSpecific(int delValue)
{
struct Node *temp1 = head, *temp2;
while(temp1->data != delValue)
 {
if(temp1 -> next == NULL){
printf("\nGiven node not found in the list!!!");
goto functionEnd;
}
temp2 = temp1;
temp1 = temp1 -> next;
}
temp2 -> next = temp1 -> next;
free(temp1);
printf("\nOne node deleted!!!\n\n");
functionEnd:
}
void display()
{
if(head == NULL)
{
printf("\nList is Empty\n");
}
else
{
struct Node *temp = head;
printf("\n\nList elements are - \n");
while(temp->next != NULL)
{
printf("%d --->",temp->data);
temp = temp->next;
}
printf("%d --->NULL",temp->data);
}
}
OUTPUT

RESULT:
Thus the C program to implement the singly linked list was executed successfully
Ex. No. 3 LINKED LIST IMPLEMENTATION OF STACK AND LINEAR QUEUE

Date:

AIM
To implement linked list implementation of stack and linear queue

ALGORITHM

Step 1 - Include all the header files which are used in the program. And declare all
the user defined functions.
Step 2 - Define a 'Node' structure with two members data and next.
Step 3 - Define a Node pointer 'top' and set it to NULL.
Step 4 - Implement the main method by displaying Menu with list of operations and
make suitable function calls in the main method.

PROGRAM CODE

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

struct Node
{
int data;
struct Node *next;
}*top = NULL;

void push(int);
void pop();
void display();

void main()
{
int choice, value;
clrscr();
printf("\n:: Stack using Linked List ::\n");
while(1){
printf("\n****** MENU ******\n");
printf("1. Push\n2. Pop\n3. Display\n4. Exit\n");
printf("Enter your choice: ");
scanf("%d",&choice);
switch(choice){
case 1: printf("Enter the value to be insert: ");
scanf("%d", &value);
push(value);
break;
case 2: pop(); break;
case 3: display(); break;
 case 4: exit(0);
default: printf("\nWrong selection!!! Please try again!!!\n");
}
}
}
void push(int value)
{
struct Node *newNode;
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
if(top == NULL)
newNode->next = NULL;
else
newNode->next = top;
top = newNode;
printf("\nInsertion is Success!!!\n");
}
void pop()
{
if(top == NULL)
printf("\nStack is Empty!!!\n");
else{
struct Node *temp = top;
printf("\nDeleted element: %d", temp->data);
top = temp->next;
free(temp);
}
}
void display()
{
if(top == NULL)
printf("\nStack is Empty!!!\n");
else{
struct Node *temp = top;
while(temp->next != NULL){
printf("%d--->",temp->data);
temp = temp -> next;
}
printf("%d--->NULL",temp->data);
}
}
OUTPUT

stack program implemented using linked list

RESULT:
Thus the C program to implement the stack using linked list was executed
successfully
 Ex. No. 4 IMPLEMENTATION OF POLYNOMIAL MANIPULATION USING
LINKED LIST

Date:

Aim
To implement polynomial manipulation using linked list

Algorithm:

Step 1:- Initialize the Structure with coefficient and power also pointer to next
position.
Step 2:- Write a Function create_node to create new node.
Step 3:- Create a node to store power and coeff of a variable.
Step 4:- Write a Function polyadd to add two polynomial numbers.
Step 5:- If power of 1st polynomial is greater then 2nd, then store 1st as it is and
move its pointer
Step 6:- If power of both polynomial numbers is same then add their coefficients
Step 7:- Finally display resultant Linked List.

PROGRAM:

struct Node
{
int coeff; int pow;
struct Node *next;
};
// Function to create new node
void create_node(int x, int y, struct Node **temp)
{ struct Node *r, *z; z = *temp;
if(z == NULL)
{ r =(struct Node*)malloc(sizeof(struct Node)); r->coeff = x;
r->pow = y;
*temp = r;
r->next = (struct Node*)malloc(sizeof(struct Node)); r = r->next;
r->next = NULL;

}
else
{
}
}
r->coeff = x; r->pow = y;
r->next = (struct Node*)malloc(sizeof(struct Node)); r = r->next;
r->next = NULL;

// Function Adding two polynomial numbers

void polyadd(struct Node *poly1, struct Node *poly2, struct Node *poly)
{
while(poly1->next && poly2->next)
{
if(poly1->pow > poly2->pow)
{
poly->pow = poly1->pow; poly->coeff = poly1->coeff; poly1 = poly1->next;
}
else if(poly1->pow < poly2->pow)
{
poly->pow = poly2->pow; poly->coeff = poly2->coeff; poly2 = poly2->next;
}
else
{ poly->pow = poly1->pow;
poly->coeff = poly1->coeff+poly2->coeff; poly1 = poly1->next;
poly2 = poly2->next;
}
// Dynamically create new node
poly->next = (struct Node *)malloc(sizeof(struct Node)); poly = poly->next;
poly->next = NULL;
}
while(poly1->next || poly2->next)
{
if(poly1->next)
{
poly->pow = poly1->pow; poly->coeff = poly1->coeff; poly1 = poly1->next;
}
if(poly2->next)
{
poly->pow = poly2->pow; poly->coeff = poly2->coeff;
poly2 = poly2->next;
}
poly->next = (struct Node *)malloc(sizeof(struct Node));
poly = poly->next;
poly->next = NULL;
}
}

// Display Linked list

void show(struct Node *node)

{ while(node->next != NULL)
{ printf("%dx^%d", node->coeff, node->pow); node = node->next;
if(node->next != NULL) printf(" + ");
}
}

// Driver program
int main()
{ struct Node *poly1 = NULL, *poly2 = NULL, *poly = NULL;
// Create first list of 5x^2 + 4x^1 + 2x^0 create_node(5,2,&poly1);
create_node(4,1,&poly1); create_node(2,0,&poly1);
// Create second list of 5x^1 + 5x^0 create_node(5,1,&poly2);
create_node(5,0,&poly2);

printf("1st Polynomial Equation: "); show(poly1);

printf("\n2nd Polynomial Equation: "); show(poly2);
poly = (struct Node *)malloc(sizeof(struct Node));
// Function add two polynomial numbers polyadd(poly1, poly2, poly);
// Display resultant List printf("\nAdded polynomial: "); show(poly);
return 0;
}

OUTPUT:

1st Polynomial Equation: 5x^2 + 4x^1 + 2x^0

2nd Polynomial Equation: 5x^1 + 5x^0
Added polynomial: 5x^2 + 9x^1 + 7x^0

RESULT:

Thus the above c program to implement Polynomial ADT is executed successfully.

 Ex. No. 5 IMPLEMENTATION OF EVALUATING POSTFIX
EXPRESSION
Date:

Aim
To implement evaluating postfix expression

Algorithm

Step 1:- Make an empty Stack.

Step 2:- Read an expression.
Step 3:- Scan the expression from left to right and repeat steps 2 & 3 for each
element in the expression.
Step 4:- If an operand is encountered, push it on to the stack.
Step 5:- If an operator is encounters, then
a) Remove the two top elements from the stack.
b) Perform the required operation.
c) Place the result back on to the stack.
Step 6:- Set ‘value’ equal to the top most element on stack.
Step 7:- Terminate the execution.

PROGRAM

#include<stdio.h>
#include<string.h>
#include<ctype.h>
int pop();
int i,l,top=-1,value[25],val,p,q,r;
char a[25],x;
void main()
{
printf("\nEnter the postfix expression\n");
gets(a);
l=strlen(a);
for(i=0;i<l;i++)
{ if(isalpha(a[i]))
{
printf("\nEnter the value for %c",a[i]);
scanf("%d",&val);
top=top+1; value[top]=val;
}
else
{
x=a[i];

p=pop();
q=pop(); switch(x)
{
case '+': r=p+q;
top=top+1; value[top]=r; break;
case '-': r=q-p;
top=top+1; value[top]=r; break;
case '*': r=p*q;
top=top+1; value[top]=r; break;
case '/': r=q/p;
top=top+1; value[top]=r; break;
}
}
}
r=value[top];
printf("\nValue of expression is %d",r);
}

int pop()
{
int ch; ch=value[top]; top=top-1; return ch;
}

OUTPUT

Enter the postfix expression abc/+

Enter the value for a 130 Enter the value for b 4 Enter the value for c 2
Value of expression is 132

RESULT:

Thus the above c program to evaluate a postfix expression using Stack is executed
successfully.
Ex. No. 6 IMPLEMENTATION OF BINARY SEARCH TREE

Date:

Aim
To write a C program to implement Binary Search Tree using C.

Algorithm:

Step 1:- Initialize the Structure with value and pointers for left- right node.

Step 2:- Three (preorder, postorder and inorder) operations for depth-first traversal of a
tree.

Step 2.1 :- Preorder: Visit a node before traversing it’s sub-trees.

Step 2.2:- Inorder: Visit a node after traversing it’s left subtree but before

traversing it’s right sub-tree.

Step 2.3:- Postorder: Visit a node after traversing all of it’s subtrees.

Step 3:- To find search smallest and largest element compare and go to the left sub tree
to find the min element .

Step 4:- Write a Function to search the appropriate position to insert the new node .

Step 5:- Write a Function to delete a node given by user.

Step 6:- Terminate the execution.
Program:

#include <stdio.h>
#include <stdlib.h>

struct btnode
{
int value;
struct btnode *l;
struct btnode *r;
}*root = NULL, *temp = NULL, *t2, *t1;

void delete1();
void insert();
void delete();
void inorder(struct btnode *t);
void create();
void search(struct btnode *t);
void preorder(struct btnode *t);
void postorder(struct btnode *t);
void search1(struct btnode *t,int data);
int smallest(struct btnode *t);
int largest(struct btnode *t);

int flag = 1;void main()

{
int ch;

printf("\nOPERATIONS ---");
printf("\n1 - Insert an element into tree\n");
printf("2 - Delete an element from the tree\n");
printf("3 - Inorder Traversal\n");
printf("4 - Preorder Traversal\n");
printf("5 - Postorder Traversal\n");
printf("6 - Exit\n");
while(1)
{
printf("\nEnter your choice : ");
scanf("%d", &ch);
switch (ch)
{
case 1:
insert();
break;
case 2:
delete();
break;
case 3:
inorder(root);
break;
case 4:
preorder(root);
break;
case 5:
postorder(root);
break;
case 6:
exit(0);
default :
printf("Wrong choice, Please enter correct choice ");
break;
}
}
}/* To insert a node in the tree */
void insert()
{
create();
if (root == NULL)
 root = temp;
else
search(root);
}

/* To create a node */
void create()
{
int data;

printf("Enter data of node to be inserted : ");

scanf("%d", &data);
temp = (struct btnode *)malloc(1*sizeof(struct btnode));
temp->value = data;
temp->l = temp->r = NULL;
}

/* Function to search the appropriate position to insert the new node */

void search(struct btnode *t)
{
if ((temp->value > t->value) && (t->r != NULL)) /* value more than root node value insert
at right */
search(t->r);
else if ((temp->value > t->value) && (t->r == NULL))
t->r = temp;
else if ((temp->value < t->value) && (t->l != NULL)) /* value less than root node value
insert at left */
search(t->l);
else if ((temp->value < t->value) && (t->l == NULL))
t->l = temp;
}

/* recursive function to perform inorder traversal of tree */

void inorder(struct btnode *t)
{
if (root == NULL)
{
printf("No elements in a tree to display");
return;
}
if (t->l != NULL)
inorder(t->l);
printf("%d -> ", t->value);
if (t->r != NULL)
inorder(t->r);
}

/* To check for the deleted node */

void delete()
{
int data;

if (root == NULL)
{
printf("No elements in a tree to delete");
return;
}
printf("Enter the data to be deleted : ");
scanf("%d", &data);
t1 = root;
t2 = root;
search1(root, data);
}

/* To find the preorder traversal */

void preorder(struct btnode *t)
{
if (root == NULL)
{
printf("No elements in a tree to display");
return;
}
printf("%d -> ", t->value);
if (t->l != NULL)
preorder(t->l);
if (t->r != NULL)
preorder(t->r);
}

/* To find the postorder traversal */

void postorder(struct btnode *t)
{
if (root == NULL)
{
printf("No elements in a tree to display ");
return;
}
if (t->l != NULL)
postorder(t->l);
if (t->r != NULL)
postorder(t->r);
 printf("%d -> ", t->value);
}

/* Search for the appropriate position to insert the new node */

void search1(struct btnode *t, int data)
{
if ((data>t->value))
{
t1 = t;
search1(t->r, data);
}
else if ((data < t->value))
{
t1 = t;
search1(t->l, data);
}
else if ((data==t->value))
{
delete1(t);
}
}

/* To delete a node */
void delete1(struct btnode *t)
{
int k;

/* To delete leaf node */

if ((t->l == NULL) && (t->r == NULL))
{
if (t1->l == t)
{
t1->l = NULL;
}
else
{
t1->r = NULL;
}
t = NULL;
free(t);
return;
}

/* To delete node having one left hand child */

else if ((t->r == NULL))
{
if (t1 == t)
{
root = t->l;
 t1 = root;
}
else if (t1->l == t)
{
t1->l = t->l;

}
else
{
t1->r = t->l;
}
t = NULL;
free(t);
return;
}

/* To delete node having right hand child */

else if (t->l == NULL)
{
if (t1 == t)
{
root = t->r;
t1 = root;
}
else if (t1->r == t)
t1->r = t->r;
else
t1->l = t->r;
t == NULL;
free(t);
return;
}

/* To delete node having two child */

else if ((t->l != NULL) && (t->r != NULL))
{
t2 = root;
if (t->r != NULL)
{
k = smallest(t->r);
flag = 1;
}
else
{
k =largest(t->l);
flag = 2;
}
search1(root, k);
t->value = k;
 }

/* To find the smallest element in the right sub tree */

int smallest(struct btnode *t)
{
t2 = t;
if (t->l != NULL)
{
t2 = t;
return(smallest(t->l));
}
else
return (t->value);
}

/* To find the largest element in the left sub tree */

int largest(struct btnode *t)
{
if (t->r != NULL)
{
t2 = t;
return(largest(t->r));
}
else
return(t->value);
}

OUTPUT :

OPERATIONS ---
1 - Insert an element into tree
2 - Delete an element from the tree
3 - Inorder Traversal
4 - Preorder Traversal
5 - Postorder Traversal
6 - Exit

Enter your choice : 1

Enter data of node to be inserted : 207

Enter your choice : 1

Enter data of node to be inserted : 10

Enter your choice : 1

 Enter data of node to be inserted : 30

Enter your choice : 1

Enter data of node to be inserted : 50

Enter your choice : 3

10 -> 30 -> 50 -> 207 ->
Enter your choice : 4
207 -> 10 -> 30 -> 50 ->
Enter your choice : 5
50 -> 30 -> 10 -> 207 ->
Enter your choice : 2
Enter the data to be deleted : 10

Enter your choice : 6

RESULT:
Thus the above c program to implement Binary Search Tree is executed successfully
Ex. No. 7 IMPLEMENTATION OF AVL TREE

Date:

Aim:
To write a C program to implement AVL Tree.
Algorithm:
Step 1:- Initialize the Structure with balance and pointer for left, right node
.
Step 2:- Write a Function for insertion operation.
Step 3:- Read the insert element from the user
Step 4:- Insert the new element into the tree using Binary Search Tree
insertion logic. Step 5:- After insertion, check the Balance Factor of every
node.
Step 6:- If the Balance Factor of every node is 0 or 1 or -1 then go for next
operation.
Step 7:- If the Balance Factor of any node is other than 0 or 1 or -1 then tree
is said to be imbalanced.
Step 8:- Then perform the suitable single(LL or RR) or double(LR or RL)
Rotation to make it balanced. And then terminate the program.

PROGRAM:
#include<stdio.h>
#include<malloc.h>
typedef enum { FALSE ,TRUE } bool;
struct node
{
int info;
int balance;
struct node *lchild; struct node *rchild;
};
struct node *insert (int , struct node *, int *);
struct node* search(struct node *,int);
int main()
{
bool ht_inc; int info ;
int choice;
struct node *root = (struct node *)malloc(sizeof(struct node)); root = NULL;

while(1)
{
printf("[Link]\n"); printf("[Link]\n"); printf("[Link]\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("Duplicate value ignored\n"); break;
case 2:
if(root==NULL)
{
printf("Tree is empty\n"); continue;
}
printf("Tree is :\n"); display(root, 1); printf("\n\n");
printf("Inorder Traversal is: "); inorder(root);
printf("\n"); break;
case 3:
exit(1); default:
printf("Wrong choice\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)
{
struct node *aptr; struct node *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: /* Left heavy */ aptr = pptr->lchild; if(aptr->balance == 1)
{
printf("Left to Left 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
aptr->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: /* Left heavy */ pptr->balance = 0;
*ht_inc = FALSE; break;
case 0: /* Balanced */ pptr->balance = -1; break;
case -1: /* Right heavy */ 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(struct node *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);

}
}/*End of inorder()*/

OUTPUT:

[Link]
[Link] [Link]
Enter your choice : 1
Enter the value to be inserted : 201
[Link]
[Link] [Link]
Enter your choice : 1
Enter the value to be inserted : 300
[Link]
[Link] [Link]
Enter your choice : 1
Enter the value to be inserted : 1001
Right to Right Rotation
[Link] [Link] [Link]
Enter your choice : 2 Tree is :

1001
300
201

Inorder Traversal is: 201 300 1001 [Link]

[Link] [Link]
Enter your choice : 1
Enter the value to be inserted : 10 [Link]
[Link] [Link]
Enter your choice : 2
Tree is :

1001
300
201
10

Inorder Traversal is: 10 201 300 1001 [Link]

[Link] [Link]
Enter your choice : 3

RESULT:
Thus the above c program to implement AVL Tree is executed successfully.
Ex. No. 8 IMPLEMENTATION OF HEAP USING PRIORITY QUEUE
Date:

Aim:
To write a C program to implement heap using priority Queue

Algorithm:
Step 1:- Initialize the Structure with priority, information and pointer to
next node .

Step 2:- Write a Function for insertion, deletion and display operation.
Step 3:- Read the insert element and its priority from the user.
Step 4:- Insert the element according to the priority in appropriate node.

Step 5:- Delete the queue using del function, display “QUEUE
UNDERFLOW” if null.
Step 6:- Display the queue with separate function and terminate the
execution.

PROGRAM:
#include<stdio.h>
#include<malloc.h>
void insert();
void del();
void display();
struct node
{

int priority; int info;

struct node *next;

}*start=NULL,*q,*temp,*new; typedef struct node N;

int main()

int ch; do
{

printf("\n[1] INSERTION\t[2] DELETION\t[3] DISPLAY [4] EXIT\t:");

scanf("%d",&ch); switch(ch)
{

case 1:insert(); break;

case 2:del(); break;
case 3:display(); break;
case 4:

break;

while(ch<4);

void insert()

int item,itprio; new=(N*)malloc(sizeof(N));

printf("ENTER THE [Link] BE INSERTED :\t");

scanf("%d",&item);

printf("ENTER ITS PRIORITY :\t");

scanf("%d",&itprio); new->info=item; new->priority=itprio; new->next=NULL;

if(start==NULL )
{

//new->next=start; start=new;
}

else if(start!=NULL&&itprio<=start->priority)

{ new->next=start; start=new;
}

else

q=start;

while(q->next != NULL && q->next->priority<=itprio)

{q=q->next;}

new->next=q->next; q->next=new;
}

}
void del()

if(start==NULL)

printf("\nQUEUE UNDERFLOW\n");

else

new=start;

printf("\nDELETED ITEM IS %d\n",new->info); start=start->next;

//free(start);

void display()

temp=start; if(start==NULL)
printf("QUEUE IS EMPTY\n"); else
{

printf("QUEUE IS:\n"); if(temp!=NULL)

for(temp=start;temp!=NULL;temp=temp->next)

printf("\n%d priority =%d\n",temp->info,temp->priority);

//temp=temp->next;

}
OUTPUT:
[1] INSERTION

[2] DELETION
[3] DISPLAY
[4] EXIT

:1
ENTER THE [Link] BE INSERTED : 7
ENTER ITS PRIORITY : 3

[1] INSERTION [2] DELETION [3] DISPLAY [4] EXIT

:1
ENTER THE [Link] BE INSERTED : 13 ENTER ITS PRIORITY : 1

[1] INSERTION [2] DELETION [3] DISPLAY [4] EXIT

:1
ENTER THE [Link] BE INSERTED : 10
ENTER ITS PRIORITY : 2

[1] INSERTION [2] DELETION [3] DISPLAY [4] EXIT

:3
QUEUE IS:

13 priority =1

10 priority =2

7 priority =3

[1] INSERTION [2] DELETION [3] DISPLAY [4] EXIT

:2

DELETED ITEM IS 13
[1] INSERTION [2] DELETION [3] DISPLAY [4] EXIT

RESULT:
Thus the above c program to implement heap using priority Queue is
executed successfully.
Ex. No. 9 IMPLEMENTATION OF DIJIKSTRAS ALGORITHM
Date:

Aim
To implement Dijkstra’s algorithm in C

Algorithm

Step 1 - Create cost matrix C[ ][ ] from adjacency matrix adj[ ][ ]. C[i][j] is the
cost of going from vertex i to vertex j. If there is no edge between vertices i and
j then C[i][j] is infinity.
Step 2 - Array visited[ ] is initialized to zero.
for(i=0;i<n;i++)
visited[i]=0;
Step 3 - If the vertex 0 is the source vertex then visited[0] is marked as 1.
Step 4 - Create the distance matrix, by storing the cost of vertices from vertex
no. 0 to n-1 from the source vertex 0.
for(i=1;i<n;i++)
distance[i]=cost[0][i];
Step 5: if(visited[v]==0)
distance[v]=min(distance[v],
distance[w]+cost[w][v])

PROGRAM CODE:

#include<stdio.h>
#include<conio.h>
#define INFINITY 9999
#define MAX 10

void dijkstra(int G[MAX][MAX],int n,int startnode);

int main()
{
int G[MAX][MAX],i,j,n,u;
printf("Enter no. of vertices:");
scanf("%d",&n);
printf("\nEnter the adjacency matrix:\n");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&G[i][j]);
printf("\nEnter the starting node:");
scanf("%d",&u);
dijkstra(G,n,u);
return 0;
}

void dijkstra(int G[MAX][MAX],int n,int startnode)

{

int cost[MAX][MAX],distance[MAX],pred[MAX];
int visited[MAX],count,mindistance,nextnode,i,j;
//pred[] stores the predecessor of each node
//count gives the number of nodes seen so far
//create the cost matrix
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(G[i][j]==0)
cost[i][j]=INFINITY;
else
cost[i][j]=G[i][j];
//initialize pred[],distance[] and visited[]
for(i=0;i<n;i++)
{
distance[i]=cost[startnode][i];
pred[i]=startnode;
visited[i]=0;
}
distance[startnode]=0;
visited[startnode]=1;
count=1;
while(count<n-1)
{
mindistance=INFINITY;
//nextnode gives the node at minimum distance
for(i=0;i<n;i++)
if(distance[i]<mindistance&&!visited[i])
{
mindistance=distance[i];
nextnode=i;
}
//check if a better path exists through nextnode
visited[nextnode]=1;
for(i=0;i<n;i++)
if(!visited[i])
if(mindistance+cost[nextnode][i]<distance[i])
{
distance[i]=mindistance+cost[nextnode][i];
pred[i]=nextnode;
}
count++;
}

//print the path and distance of each node

for(i=0;i<n;i++)
 if(i!=startnode)
{
printf("\nDistance of node%d=%d",i,distance[i]);
printf("\nPath=%d",i);
j=i;
do
{
j=pred[j];
printf("<-%d",j);
}while(j!=startnode);
}
}

OUTPUT

RESULT:
Thus the C program to implement Dijkstra’s algorithm is done successfully.
Ex. No. 10 IMPLEMENTATION OF PRIMS ALGORITHM

Date:

Aim
To implement prims algorithm in C

Algorithm

Step 1 - Start
Step 2 - Create edge list of given graph, with their weights.
Step 3 -Draw all nodes to create skeleton for spanning tree.
Step 4 - Select an edge with lowest weight and add it to skeleton and delete
edge from edge list.
Step 5 - Add other edges. While adding an edge take care that the one end of
the edge should always be in the skeleton tree and its cost should be minimum.
Step 6: Repeat step 5 until n-1 edges are added.

PROGRAM CODE

#include<stdio.h>
#include<stdlib.h>

#define infinity 9999

#define MAX 20

int G[MAX][MAX],spanning[MAX][MAX],n;

int prims();

int main()
{
int i,j,total_cost;
printf("Enter no. of vertices:");
scanf("%d",&n);
printf("\nEnter the adjacency matrix:\n");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&G[i][j]);
total_cost=prims();
printf("\nspanning tree matrix:\n");
for(i=0;i<n;i++)
{
printf("\n");
for(j=0;j<n;j++)
printf("%d\t",spanning[i][j]);
}
printf("\n\nTotal cost of spanning tree=%d",total_cost);
return 0;
}

int prims()
{
int cost[MAX][MAX];
int u,v,min_distance,distance[MAX],from[MAX];
int visited[MAX],no_of_edges,i,min_cost,j;
//create cost[][] matrix,spanning[][]
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if(G[i][j]==0)
cost[i][j]=infinity;
else
cost[i][j]=G[i][j];
spanning[i][j]=0;
}
//initialise visited[],distance[] and from[]
distance[0]=0;
visited[0]=1;
for(i=1;i<n;i++)
{
distance[i]=cost[0][i];
from[i]=0;
visited[i]=0;
}
min_cost=0; //cost of spanning tree
no_of_edges=n-1; //no. of edges to be added
while(no_of_edges>0)
{
//find the vertex at minimum distance from the tree
min_distance=infinity;
for(i=1;i<n;i++)
if(visited[i]==0&&distance[i]<min_distance)
{
v=i;
min_distance=distance[i];
}
u=from[v];
//insert the edge in spanning tree
spanning[u][v]=distance[v];
spanning[v][u]=distance[v];
no_of_edges--;
visited[v]=1;
//updated the distance[] array
for(i=1;i<n;i++)
if(visited[i]==0&&cost[i][v]<distance[i])
{
distance[i]=cost[i][v];
from[i]=v;
}
min_cost=min_cost+cost[u][v];
}
return(min_cost);
}

OUTPUT

Enter no. of vertices:6

Enter the adjacency matrix:

031600
305030
150564
605002
036006
004260

spanning tree matrix:

031000
300030
100004
000002
030000
004200

Total cost of spanning tree=13

RESULT:

Thus the C program to implement the Prims algorithm was done successfully.
Ex. No. 11A IMPLEMENTATION OF LINEAR SEARCH

Date:

Aim
To implement Linear search using C

Algorithm

Step1:- Get the total number of elements and the elements.

Step2:- Get the key to be searched.
Step3:- Each element in the array is checked with the key.
Step4:- If the element is equal to key, the element is found and displays the
location of the key.
Step5:-Otherwise, the element is not found.

Program
#include<stdio.h>
void main()
{
int array[100],s
search,c,n;
printf("Enter the Number of elements\n");
scanf("%d",&n);
printf("Enter the Elements\n");
for (c=0; c<n;c++)
scanf("%d", &array[c]);
printf("Enter the number to search\n");
scanf("%d", &search);
for(c=0;c<n;c++)
{
if(array[c] == search)
{
printf("%d is present at location %d.\n",search,c+1); break;
}
}

if(c==n)
{
printf("%d is not present in array.\n",search);
}
//return 0;
}
OUTPUT

Enter the Number of elements

10
Enter the Elements 10
-100
09
8
7
6
5
101
203
12
Enter the number to search 8
8 is present at location 4.

RESULT:
Thus the above c program to implement linear search is executed successfully.
 Ex. No. 11B IMPLEMENTATION OF BINARY SEARCH

Date:

Aim
To implement Binary Search in C

Algorithm

Step1:-Get the number of elements, elements and the key to be searched.

Step2:-Sort the list in non-decreasing order.
Step 3:-Initialize low = 0, high = number_of_elements and mid =
floor((low+high)/2).
(i) If the middle element (mid) is less than key then key has to present
in range [mid+1 , high], so low=mid+1, high remains unchanged and mid
is adjusted accordingly
(ii)If middle element is the key, then the element is found.
(iii)If the middle element is greater than key then key has to be
present in the range [low,mid-1], so high=mid-1, low remains unchanged
and mid is adjusted accordingly.
Step 4:-Repeat the step until low is less than or equal to high or the position of the
‘input key’ has been found

PROGRAM CODE

#include<stdio.h>
int BinarySearch(int *array, int n, int key)
{
int low = 0, high = n-1,
mid; while(low <= high)
{
mid = (low + high)/2;
if(array[mid] < key)
{
low = mid + 1;
}
else if(array[mid] == key)
 {
return mid;
}
else if(array[mid] > key)
{
high = mid-1;
}
}
return -1;
}
int main()
{
int n=5;
int array[n];
int
i,key,index;
printf("\nEnter the 5 elements");
//scanf("%d",&n);
printf("\nEnter the
elements");for(i = 0;i < n;i++)
{
scanf("%d",&array[i]);
}
for(i = 1;i < n;i++)
{
if(array[i] < array[i - 1])
{
printf("Given input is not
sorted\n"); return 0;
}
}
printf("Enter the key to be
searched"); scanf("%d",&key);
index =
BinarySearch(array,n,key);
if(index==-1)
{
printf("Element not found\n");
}
else
{
printf("Element is at index %d\n",index);
}
return 0;
}

OUTPUT

Enter the 5 elements

Enter the elements -20 10 25 30 100
Enter the key to be searched 25
Element is at index 2

RESULT
Thus the program to implement binary Search was executed successfully.
Ex. No. 12A IMPLEMENTATION OF INSERTION SORT

Date:

Aim
To implement insertion sort using C

Algorithm
Step 1 − If it is the first element, it is already
sorted. return 1; Step 2 − Pick next element
Step 3 − Compare with all elements in the sorted sub-list
Step 4 − Shift all the elements in the sorted sub-list that is greater than the
value to be sorted
Step 5 − Insert the value
Step 6 − Repeat until list is sorted

PROGRAM CODE

#include<stdio.h>
int main()
{
int data[100],n,temp,i,j;
printf("Enter number of terms(should be less than 100): ");
scanf("%d",&n);
printf("Enter elements: ");
for(i=0;i<n;i++)
{
scanf("%d",&data[i]);
}
for(i=1;i<n;i++)
{
temp = data[i];
j=i-1;
while(temp<data[j] && j>=0)
/*To sort elements in descending order, change temp<data[j] to temp>data[j] in above line.*/
{
data[j+1] = data[j];
--j;
}
data[j+1]=temp;
}
printf("In ascending order: ");
for(i=0; i<n; i++)
printf("%d\t",data[i]);
return 0;
 }

OUTPUT :

Enter number of terms(should be less than

100): 7Enter elements: 100
20
30
40
-70
60
12
In ascending order: -70 12 20 30 40 60 100

RESULT:

The given program was executed and the output of the program was verified.
Ex. No. 12A IMPLEMENTATION OF SELECTION SORT

Date:

Aim
To implement selection sort using C

Algorithm

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 second element as min.

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

PROGRAM CODE

#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

RESULT:
The given program was executed and the output of the program was verified.
Ex. No. 13 IMPLEMENTATION OF MERGE SORT

Date:

Aim
To implement merge sort using C

Algorithm
Step 1: Declare left variable to 0 and right variable to n-1
Step 2: Find mid by medium formula. mid = (left+right)/2
Step 3: Call merge sort on (left,mid)
Step 4:Call merge sort on (mid+1,rear)
Step 5:Continue till left is less than right
Step 6:Then call merge function to perform merge sort.

PROGRAM CODE

#include <stdio.h>

#define max 10

int a[11] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 0 };
int b[10];

void merging(int low, int mid, int high) {

int l1, l2, i;

for(l1 = low, l2 = mid + 1, i = low; l1 <= mid && l2 <= high; i++) {
if(a[l1] <= a[l2])
b[i] = a[l1++];
else
b[i] = a[l2++];
}

while(l1 <= mid)

b[i++] = a[l1++];

while(l2 <= high)

b[i++] = a[l2++];

for(i = low; i <= high; i++)

 a[i] = b[i];
}

void sort(int low, int high) {

int mid;

if(low < high) {

mid = (low + high) / 2;
sort(low, mid);
sort(mid+1, high);
merging(low, mid, high);
} else {
return;
}
}

int main() {
int i;

printf("List before sorting\n");

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

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

sort(0, max);

printf("\nList after sorting\n");

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

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

OUTPUT

List before sorting

10 14 19 26 27 31 33 35 42 44 0
List after sorting
0 10 14 19 26 27 31 33 35 42 44

RESULT
The given program was executed and the output of the program was verified.
 Ex. No. 14 IMPLEMENTATION OF HASHING USING OPEN ADDRESSING

Date:

Aim
To implement HASHING USING OPEN ADDRESSING using C.

Algorithm

Step1:- For linear probing, calculate a hash code

from the key
Step 2:- Access that hash element
▪ If the hash element is empty, add straight away
▪ If not, probe through subsequent elements (looping back if necessary), trying
to find afree place
▪ If a free place is found, add the data at that position
▪ If no free place is found, the add will fail.
Step 3:- Quadratic probing operates by taking the original hash value
Step 4:- Then add successive values of an arbitrary quadratic polynomial to the
starting [Link] 5:- Terminate the execution.

PROGRAM CODE

#include
<stdio.h>int
tsize;
int hasht(int key)
{
int i ;
i = key%tsize
; return i;
}

//-------LINEAR PROBING-------
int rehashl(int key)
{
int i ;
i=
(key+1)%tsize ;
return i ;
}
 //-------QUADRATIC PROBING-------
int rehashq(int key, int j)
{
int i ;
i=
(key+(j*j))%tsize ;
return i ;
}
void main()
{
int key,arr[20],hash[20],i,n,s,op,j,k ;

printf ("Enter the size of the hash table: ");

scanf ("%d",&tsize);

printf ("\nEnter the number of

elements: "); scanf ("%d",&n);

for (i=0;i<tsize;i++)
hash[i]=-1 ;
printf ("Enter Elements:
"); for (i=0;i<n;i++)
scanf("%d",&arr[i]);

do
{
printf("\n\[Link] Probing\[Link] Probing \[Link] \nEnter your option: ");
scanf("%d",&op
); switch(op)
{
case
1: for
(i=0;i<tsize;i++)
hash[i]=-1 ;
for(k=0;k<n;k++)
{
 key=arr[k] ;
i = hasht(key); while (hash[i]!=-
1)
{
i = rehashl(i);
}
hash[i]=key ;
}
printf("\nThe elements in the array are: "); for
(i=0;i<tsize;i++)
printf("\n Element at position %d:%d",i,hash[i]); break ;

case 2:
for (i=0;i<tsize;i++)
hash[i]=-1 ;
for(k=0;k<n;k++)
{
j=1;
key=arr[k] ;
i = hasht(key); while (hash[i]!=-
1)
{
i = rehashq(i,j); j++ ;
}
hash[i]=key ;
}
printf("\nThe elements in the array are: "); for
(i=0;i<tsize;i++)
{
printf("\n Element at position %d: %d",i,hash[i]);
}
break ;

}
}while(op!=3);

Output:

Enter the size of the hash table: 10 Enter the

number of elements: 7
Enter Elements: 110 200 1001 2001 30 25 1
[Link] Probing [Link]
Probing [Link]
Enter your option: 1

The elements in the array are: Element at

position 0: 110
Element at position 1: 200
Element at position 2: 1001Element at position 3: 2001
Element at position 4: 30
Element at position 5: 25
Element at position 6: 1
Element at position 7: -1
Element at position 8: -1
Element at position 9: -1

[Link] Probing [Link]

Probing [Link]
Enter your option: 2

The elements in the array are: Element at

position 0: 110
Element at position 1: 200
Element at position 2: 1001
Element at position 3: -1
Element at position 4: -1
Element at position 5: 30
Element at position 6: 2001
Element at position 7: 1
Element at position 8: -1
Element at position 9: 25

1. Linear Probing [Link]

[Link]
Enter your option: 3

Result:
Thus the above c program to implement Hashing using Linear and Quatratic Probing is executed
successfully.