MAHAKAVI BHARATHIYAR COLLEGE OF

ENGINEERING AND TECHNOLOGY

VASUDEVANALLUR-627 758.

LABORATORY RECORD NOTE

STUDENT NAME : …………………………………………………………………

REGISTER NO : …………………………………………………………………

YEAR : …………………………………………………………………

SEMESTER : …………………………………………………………………

BRANCH : …………………………………………………………………

LABORATORY CODE/ NAME : …………………………………………………………………

 MAHAKAVI BHARATHIYAR COLLEGE OF
ENGINEERING AND TECHNOLOGY
VASUDEVANALLUR- 627 758.

Name :

Year/Semester :

Department :

Register No :

BONAFIDE CERTIFICATE

Certified that this record is the bonafide record work of the above Student in the CS3362
C PROGRAMMING AND DATA STRUCTURES Laboratory during the academic year
2024-2025.

Staff in-charge Head of the Department

Submitted for the University Semester Practical Examination held on ………………

Internal Examiner External Examiner

2
 INDEX

S.NO DATE PAGE MARKS SIGN

LIST OF EXPERIMENTS / PROGRAMS
NO

1. CONCEPT OF STATEMENTS AND

EXPRESSIONS, DECISION MAKING AND
ITERATIVE STATEMENTS.

2. FUNCTIONS AND ARRAYS

3. POINTERS AND STRUCTURES

4. FILES

5. DEVELOPMENT OF REAL TIME C

APPLICATIONS

6. ARRAY IMPLEMENTATION OF LIST ADT

7. ARRAY IMPLEMENTATION OF STACK AND

QUEUE ADTS

8. LINKED LIST IMPLEMENTATION OF LIST,

STACK AND QUEUE ADTS

9. APPLICATIONS OF LIST, STACK AND

QUEUE ADTS

10. IMPLEMENTATION OF BINARY TREES AND

OPERATIONS

11. IMPLEMENTATION OF BINARY SEARCH

TREES

12. IMPLEMENTATION OF SEARCHING

TECHNIQUES

13. IMPLEMENTATION OF SORTING

ALGORITHMS

14. IMPLEMENTATION OF HASHING

3
EX.NO:1 PRACTICE OF C PROGRAMMING USING STATEMENTS AND
DATE: EXPRESSIONS, DECISION MAKING AND ITERATIVE STATEMENTS

AIM:
To write a C program to illustrate the concept of Statements and Expressions, Decision
making and iterative statements.
1a. Area and Circumference of A Circle
ALGORITHM:
Step 1: Start
Step 2: Read the input r
Step 3: Calculate area = pi * r * r
Step 4: Calculate circum = 2 * pi * r
Step 5: print area, circum , Step 6: Stop
PROGRAM:
#include <stdio.h>
int main()
{
float radius;
double area, circumference;
printf("\n Enter the radius of the circle : ");
scanf("%f", &radius);
area = 3.14 * radius * radius;
circumference=2*3.14*radius;
printf(" \n Area = %lf", area);
printf(" \n Circumference = %lf", circumference);
return 0;
}
OUTPUT:
Enter the radius of the circle : 3
Area = 28.260000
Circumference = 18.840000

4
1b. Addition of Two Numbers C=A+B
ALGORITHM:
Step 1: Start
Step 2: Declare variables num1, num2 and sum.
Step 3: Read values for num1, num2.
Step 4: Add num1 and num2 and assign the result to a variable sum.
Step 5: Display sum
Step 6: Stop

PROGRAM:
#include <stdio.h>
int main()
{
int number1, number2, sum;
printf("Enter two integers: ");
scanf("%d %d", &number1, &number2);
sum = number1 + number2;
printf("Sum of two numbers: ");
printf("%d + %d = %d", number1, number2, sum);
return 0;
}
OUTPUT:
Enter two integers: 4 5
Sum of two numbers: 4 + 5 = 9

5
1c. Sum and Average of Three Numbers
ALGORITHM:
Step 1: Start
Step 2: Read the three number let "a","b","c" form the user.
Step 3: Declared a variable "sum” and "Avg".
Step 4: sum=a+b+c;
Step 5: Avg=sum/3;
Step 6: Display "sum” and "Avg".
Step 7: End
PROGRAM:
#include <stdio.h>
int main()
{
int a,b,c;
float sum;
float avg;
printf("\nEnter First Number : ");
scanf("%d", &a);
printf("\nEnter Second Number : ");
scanf("%d",&b);
printf("\nEnter Third Number : ");
scanf("%d",&c);
sum=a+b+c;
printf("\nsum: %.2f",sum);
avg=sum/3.0;
printf("\nAverage of Three Numbers : %.2f",avg);
return 0;
}
OUTPUT:
Enter First Number : 5
Enter Second Number : 7
Enter Third Number : 9
sum: 21.00
Average of Three Numbers : 7.00

6
1d. If-Else Statement - Number Is Even or Odd
ALGORITHM:
Step 1: Input a number N
Step 2: if (N%2==0)
Step 3: print <Even Number=
Step 4: else Step
5: Print <Odd number
Step 6: Exit
PROGRAM:
#include <stdio.h>
int main()
{
int a;
printf("\n Enter the value of a : ");
scanf("%d", &a);
if(a%2==0)
printf("\n %d is even", a);
else printf("\n %d is odd", a);
return 0;
}

OUTPUT:
Enter the value of a : 6
6 is even
Enter the value of a : 61
61 is odd

7
1e. If–Else–If Statement -C Program to check whether a number is negative, positive or zero
using if–else–if Statement
ALGORITHM:
1. Input a number from the user.
2. If number is less than zero, then it is a negative integer.
3. Else if number is greater than zero, then it is a positive integer.
4. Else, the number is equal to zero.
5. End.
PROGRAM:
#include <stdio.h>
int main()
{
int num;
printf("\n Enter any number : ");
scanf("%d", &num);
if(num==0)
printf("\n The value is equal to zero");
else if(num>0)
printf("\n The number is positive");
else printf("\n The number is negative");
return 0;
}

OUTPUT:
Enter any number : -50
The number is negative Enter any number : 9
The value is equal to zero

8
1f. Switch–Case Statement- Check whether entered character is a vowel or not using switch–
case Statement
ALGORITHM:
Step 1: Start
Step 2: Declare character type variable ch and Read ch from User
Step 3: Checking both lower and upper case vowels. Print "Vowel" ELSE Print "Consonant"
Step 4: Stop
PROGRAM:
#include <stdio.h>
int main()
{
char c;
printf("Enter an Alphabet\n");
scanf("%c", &c);
switch(c)
{
case 'a':
case 'A':
case 'e':
case 'E':
case 'i':
case 'I':
case 'o':
case 'O':
case 'u':
case 'U':
printf("%c is VOWEL", c);
break;
default: printf("%c is CONSONANT", c);
}
return 0;
}

9
OUTPUT:

Enter an Alphabet e
e is VOWEL
Enter an Alphabet Z
Z is CONSONANT

RESULT:
Thus the C program to illustrate the concept of Statements and Expressions, Decision making
and iterative statements.

10
EX.NO:2
PRACTICE OF C PROGRAMMING USING FUNCTIONS AND ARRAYS
DATE:

AIM:
2 a. Find the Factorial of a given number using Recursive function.
ALGORITHM:
Step 1: Start the Program
Step 2: Declare and Initialize the input variables
Step 3: Enter the numberCall the Recursive Function passing the number to the recursive function as
an Argument.
Step 5: If the entered number is equal to one, then return one to Main function
Step 6: If the number is less greater than one then call Recursive.
Step 7: Print the Factorial value of the number
Step 8: Stop

PROGRAM:
#include <stdio.h>
#include <conio.h>
int recur(int b);
void main()
{
clrscr();
int num, a;
printf("Enter the Number"); scanf("%d", &num);
a = recur(num);
printf("The Factorial of the number %d is %d", num, a); getch();
}
int recur(int no) {
int fact;
if(no == 1)
return(1); else
fact = no * recur(no - 1); return(fact);
}
OUTPUT:
Enter a Positive integer: 6
Factorial of 6 =720

11
2b. To add two matrices using array.

ALGORITHM:
Step 1: Start the Program
Step 2: Input matrix 1 and matrix 2.
Step 3: If the number of rows and number of columns of matrix 1 and matrix 2 is equal,
Step 4: for i=1 to rows[matrix 1]
Step 5: for j=1 to columns [matrix 1]
Step 6: Input matrix 1 [i,j]
Step 7: Input matrix 2 [i,j]
Step 8: matrix 3 [i,j]= matrix 1 [i,j]+ matrix 2 [i,j];
Step 9: Display matrix 3 [i,j];
Step 10: Stop

PROGRAM:
#include < stdio.h >
int main()
{
int m, n, c, d, first[10][10], second[10][10], sum[10][10];
printf("Enter the number of rows and columns of matrix\n");
scanf("%d%d", & m, & n);
printf("Enter the elements of first matrix\n");
for (c = 0; c < m; c++)
for (d = 0; d < n; d++) scanf("%d", & first[c][d]);
printf("Enter the elements of second matrix\n");
for (c = 0; c < m; c++)
for (d = 0; d < n; d++) scanf("%d", & second[c][d]);
printf("Sum of entered matrices:-\n");
for (c = 0; c < m; c++)
{
for (d = 0; d < n; d++)
{
sum[c][d] = first[c][d] + second[c][d];
printf("%d\t", sum[c][d]);
}
printf("\n");
}

12
return 0;
}

OUTPUT:

RESULT:
Thus the C program to illustrate the concept of Practice of C Programming Using Functions
and Arrays was written, executed and the output was verified successfully.

13
EX.NO:3
IMPLEMENT C PROGRAMS USING POINTERS AND STRUCTURES
DATE:

AIM:
To write a C program to illustrate the concept to Implement Pointers and Structures.

ALGORITHM:
Step 1: Start the Program
Step 2: Declare and Initialize the input variables
Step 3: Enter the numberCall the Recursive Function passing the number to the recursive function as
an Argument.
Step 5: If the entered number is equal to one, then return one to Main function
Step 6: If the number is less greater than one then call Recursive.
Step 7: Print the Factorial value of the number
Step 8: Stop

PROGRAM:

#include <stdio.h>
#include <stdlib.h>
struct person {
int age;
float weight;
char name[30];
};
int main()
{
struct person *ptr;
int i, n;
printf("Enter the number of persons: ");
scanf("%d", &n);
ptr = (struct person*) malloc(n * sizeof(struct person));
for(i = 0; i < n; ++i)
{
printf("Enter first name and age respectively: ");

14
 scanf("%s %d", (ptr+i)->name, &(ptr+i)->age);
}
printf("Displaying Information:\n");
for(i = 0; i < n; ++i)
printf("Name: %s\tAge: %d\n", (ptr+i)->name, (ptr+i)->age);
return 0;
}

OUTPUT:

Enter the number of persons: 2

Enter first name and age respectively: karthi 23 naya 18
Enter first name and age respectively: Displaying Information:
Name: karthi Age: 23
Name: naya Age: 18

RESULT:
Thus the C program to illustrate the concept to Implement Pointers and Structures was
written, executed and the output was verified successfully.

15
EX.NO:4
IMPLEMENT C PROGRAMS USING FILES
DATE:
AIM:
To write a C program to illustrate the concept to Read and Write the Contents of a File.

ALGORITHM:

Step 1: Start the Program

Step 2: Initialize the File Pointer
Step 3: Open the File in the Write Mode Using File Pointer
Step 4: Enter the Data
Step 5: Store the input data in the file using the putc() statement
Step 6: Close the File
Step 7: Open the File in the Read Mode using the File Pointer
Step 8: Print the data in the file

PROGRAM:
#include <stdio.h>
#include <stdlib.h> struct person
{ int id;
char fname[20];
char lname[20]; };
int main () {
FILE *infile; struct person input;
infile = fopen ("person.dat", "r"); if (infile == NULL)
{
fprintf(stderr, "\nError opening file\n"); exit (1);
}
while(fread(&input, sizeof(struct person), 1, infile))
printf ("id = %d name = %s %s\n", input.id, input.fname, input.lname);
fclose (infile);
return 0;
}
OUTPUT:
id = 1 name = rohan sharma
id = 2 name = mahendra dhoni

RESULT:
Thus the C program to Read and Write the Contents of a File was written, executed and the
output was verified successfully.

16
EX.NO:5
DEVELOPMENT OF REAL TIME C APPLICATIONS
DATE:

AIM:
To development of real time C applications.

ALGORITHM:

Step 1: Start the Program

Step 2: Initialize the structure
Step 3: Get the input data.
Step 4: Print the output.
Step 5: Stop

PROGRAM:

#include<stdio.h>
#include <conio.h>
#include<stdlib.h>
typedef struct Customer
{
int account_no;
char name[20];
int balance;
char city [20]:
}cust;
cust c[10];
int main()
int n.i
printf("\n Enter the total number of Customers");
scanf("%d",&n);
printf("\n Enter Each customer's record");
printf("\n Acc_noNameCity\n");
for(i=0;i<n;i++)
{
scanf("%d",&c[i] account_no);
scanf("%s".c[i].name);
scanf("%d",&c[i].balance);
scanf("%s",c[i] city);

17
}
printf("\n Each record is");
printf("\n---------------------------“);
printf("\n Acc_no Name Balance city”);
printf("\n----------------------------“);
for(i=0;i<n;i++)
printf("\n %d\t \t%d \t%s", c[i] account_no,c[i].name, c[i].balance, c[i].city);
return 0;

OUTPUT:

Enter the total number of Customers 2

Enter each customer's record
Acc_no Name Balance city

1 Anu 1000 Coimbatore

2 banu 2000 Madurai

Each Record is
Acc_no Name Balance city

1 Anu 1000 Coimbatore

2 banu 2000 Madurai

RESULT:

Thus the development of real time C applications was written, executed and the output was
verified successfully.

18
EX.NO:6
ARRAY IMPLEMENTATION OF LIST ADT
DATE:

AIM:

To create a list using array and perform operations such as display, insertions and deletions.

ALGORITHM:

Step 1: Start
Step2: Define list using an array of size n.
Step3: First item with subscript or position = 0
Step4: Display menu on list operation
Step5: Accept user choice
Step6: If choice = 1 then
Step 7: Locate node after which insertion is to be done
Step8: Create an empty location in array after the node by moving the existing elements one
position ahead.
Step 9: Insert the new element at appropriate position
Step 10: Else if choice = 2
Step11: Get element to be deleted.
Step 12: Locate the position of the element replace the element with the element in thefollowing
position.
Step13: Repeat the step for successive elements until end of the array.
Step14: Else
Step15: Traverse the list from position or subscript 0 to n.
Step16: Stop

PROGRAM:

#include<stdio.h>
#include<conio.h>
#define MAX 10
void create(); void insert(); void deletion(); void search();
void display(); int a,b[20], n, p, e, f, i, pos;
void main() {
//clrscr();
int ch; char g='y';
do {
printf("\n main Menu");

19
printf("\n 1.Create \n 2.Delete \n 3.Search \n 4.Insert \n 5.Display\n 6.Exit \n");
printf("\n Enter your Choice"); scanf("%d", &ch);
switch(ch) {
case 1: create(); break;
case 2: deletion(); break;
case 3: search(); break;
case 4: insert(); break;
case 5: display(); break;
case 6: exit(); break;
default:
printf("\n Enter the correct choice:");
}
printf("\n Do u want to continue:::");
scanf("\n%c", &g); } while(g=='y'||g=='Y'); getch();
}
void create() {
printf("\n Enter the number of nodes"); scanf("%d", &n);
for(i=0;i<n;i++) {
printf("\n Enter the Element:",i+1); scanf("%d", &b[i]);
}
}
void deletion()
{
printf("\n Enter the position u want to delete::"); scanf("%d", &pos);
if(pos>=n) {
printf("\n Invalid Location::");
} else {
for(i=pos+1;i<n;i++) {
b[i-1]=b[i]; } n --; }
printf("\n The Elements after deletion"); for(i=0;i<n;i++)
{
printf("\t%d", b[i]); }
}
void search() {
printf("\n Enter the Element to be searched:"); scanf("%d", &e);
for(i=0;i<n;i++) {
if(b[i]==e) {

20
printf("Value is in the %d Position", i);
} else {
printf("Value %d is not in the list::", e); continue;
}
}}
void insert() {
printf("\n Enter the position u need to insert::"); scanf("%d", &pos);
if(pos>=n) {
printf("\n invalid Location::"); }
else {
for(i=MAX-1;i>=pos-1;i--) {
b[i+1]=b[i]; }
printf("\n Enter the element to insert::\n"); scanf("%d",&p);
b[pos]=p; n++;
}
printf("\n The list after insertion::\n"); display();
}
void display() {
printf("\n The Elements of The list ADT are:"); for(i=0;i<n;i++)
{
printf("\n\n%d", b[i]); }
}
OUTPUT:
Array of 10 numbers: Input elements:
12456789
10
11
Current array: 1 2 4 5 6 7 8 9 10 11
Would you like to enter another element? [1/0]: 1
Input element: 3
Input position: 2
Current array: 1 2 3 4 5 6 7 8 9 10

RESULT:
Thus the array implementation of list was written, executed and the output was verified
successfully.

21
EX.NO:7
ARRAY IMPLEMENTATION OF STACK AND QUEUE ADTS
DATE:

AIM:
To implement stack operations using array.
ALGORITHM:
Step 1: Start
Step 2: Define a array stack of size max = 5
Step3: Initialize top = -1
Step4: Display a menu listing stack operations
Step5: Accept choice
Step 6: If choice = 1 then
Step7: If top < max -1
Step8: Increment top
Step9: Store element at current position of top
Step10: Else
Step11: Print Stack overflow
Step12: If choice = 2 then
Step13: If top < 0 then
Step14: Print Stack underflow
Step15: Else
Step16: Display current top element
Step17: Decrement top
Step18: If choice = 3 then
Step19: Display stack elements starting from top
Step20: Stop

PROGRAM:
#include <stdio.h>
#include <conio.h>
#define max 5
static int stack[max];
int top = -1;
void push(int x) {
stack[++top] = x;
} int pop() {
return (stack[top--]); }

22
void view() {
int i;
if (top < 0)
printf("\n Stack Empty \n");
else {
printf("\n Top-->"); for(i=top; i>=0; i--) {
printf("%4d", stack[i]);
} printf("\n");
} } main() {
int ch=0, val; clrscr(); while(ch != 4) {
printf("\n STACK OPERATION \n"); printf("1.PUSH ");
printf("2.POP "); printf("3.VIEW "); printf("4.QUIT \n"); printf("Enter Choice : "); scanf("%d", &ch);
switch(ch)
{
case 1:
if(top < max-1) {
printf("\nEnter Stack element : "); scanf("%d", &val);
push(val);
} else
printf("\n Stack Overflow \n");
break; case 2:
if(top < 0)
printf("\n Stack Underflow \n"); else
{
val = pop();
printf("\n Popped element is %d\n", val);
} break;
case 3: view(); break;
case 4:
exit(0); default:
printf("\n Invalid Choice \n"); }
}
}
OUTPUT:
STACK OPERATION
1.PUSH 2.POP 3.VIEW 4.QUIT
Enter Choice : 1

23
Enter Stack element : 12
STACK OPERATION
1.PUSH 2.POP 3.VIEW 4.QUIT
Enter Choice : 1
Enter Stack element : 23
STACK OPERATION
1.PUSH 2.POP 3.VIEW 4.QUIT
Enter Choice : 1
Enter Stack element : 34
STACK OPERATION
1.PUSH 2.POP 3.VIEW 4.QUIT Enter
Choice : 1
Enter Stack element : 45
STACK OPERATION
1.PUSH 2.POP 3.VIEW 4.QUIT
Enter Choice : 3 Top--> 45 34 23 12
STACK OPERATION
1.PUSH 2.POP 3.VIEW 4.QUIT
Enter Choice : 2
Popped element is 45
STACK OPERATION
1.PUSH 2.POP 3.VIEW 4.QUIT Enter
Choice : 3 Top--> 34 23 12
STACK OPERATION
1.PUSH 2.POP 3.VIEW 4.QUIT
Enter Choice : 4

7b. To implement queue operations using array.

ALGORITHM:

Step 1. Start
Step 2. Define a array queue of size max = 5
Step 3. Initialize front = rear = –1
Step 4. Display a menu listing queue operations
Step 5. Accept choice
Step 6. If choice = 1 then
Step 7. If rear < max -1

24
Step 8. Increment rear
Step 9. Store element at current position of rear
Step 10. Else
Step 11. Print Queue Full
Step 12. If choice = 2 then
Step 13. If front = –1 then
Step 14. Print Queue empty
Step 15. Else
Step 16. Display current front element
Step 17. Increment front
Step 18. If choice = 3 then
Step 19. Display queue elements starting from front to rear.
Step 20. Stop

PROGRAM:
#include <stdio.h>
#include <conio.h>
#define max 5
static int queue[max]; int front = -1; int rear = -1;
void insert(int x) {
queue[++rear] = x; if (front == -1) front = 0;
} int remove() {
int val;
val = queue[front]; if (front==rear && rear==max-1)
front = rear = -1; else
front ++; return (val);
}
void view() {
int i;
if (front == -1)
printf("\n Queue Empty \n"); else
{
printf("\n Front-->"); for(i=front; i<=rear; i++) printf("%4d", queue[i]); printf(" <--Rear\n");
} } main() {
int ch= 0,val; clrscr(); while(ch != 4) {
printf("\n QUEUE OPERATION \n"); printf("1.INSERT "); printf("2.DELETE "); printf("3.VIEW ");
printf("4.QUIT\n");

25
printf("Enter Choice : "); scanf("%d", &ch); switch(ch)
{ case 1:
if(rear < max-1) {
printf("\n Enter element to be inserted : "); scanf("%d", &val);
insert(val);
} else
printf("\n Queue Full \n"); break;
case 2:
if(front == -1)
printf("\n Queue Empty \n"); else
{
val = remove();
printf("\n Element deleted : %d \n", val); }
break; case 3:
view();
break; case 4:
exit(0); default:
printf("\n Invalid Choice \n"); }
}
}

OUTPUT:
QUEUE OPERATION
1.INSERT 2.DELETE 3.VIEW 4.QUIT
Enter Choice : 1
Enter element to be inserted : 12
QUEUE OPERATION
1.INSERT 2.DELETE 3.VIEW 4.QUIT
Enter Choice : 1
Enter element to be inserted : 23
QUEUE OPERATION
1.INSERT 2.DELETE 3.VIEW 4.QUIT
Enter Choice : 1
Enter element to be inserted : 34
QUEUE OPERATION
1.INSERT 2.DELETE 3.VIEW 4.QUIT
Enter Choice : 1

26
Enter element to be inserted : 45
QUEUE OPERATION
1.INSERT 2.DELETE 3.VIEW 4.QUIT
Enter Choice : 1
Enter element to be inserted : 56
QUEUE OPERATION
1.INSERT 2.DELETE 3.VIEW 4.QUIT
Enter Choice : 1
Queue Full
QUEUE OPERATION
1.INSERT 2.DELETE 3.VIEW 4.QUIT
Enter Choice : 3 Front--> 12 23 34 45 56 <--Rear

RESULT:
Thus insert and delete operations of a queue was written, executed and the output was verified
successfully.

27
EX.NO:8 LINKED LIST IMPLEMENTATION OF LIST, STACK AND QUEUE
DATE: ADTS

AIM:

To define a singly linked list node and perform operations such as insertions and deletions
dynamically.

ALGORITHM:

Step 1. Start
Step2. Define single linked list node as self referential structure
Step3. Create Head node with label = -1 and next = NULL using
Step4. Display menu on list operation
Step5. Accept user choice
Step6. If choice = 1 then
Step7. Locate node after which insertion is to be done
Step8. Create a new node and get data part
Step9. Insert the new node at appropriate position by manipulating address
Step10. Else if choice = 2
Step11. Get node's data to be deleted.
Step12. Locate the node and delink the node
Step13. Rearrange the links
Step14. Else
Step15. Traverse the list from Head node to node which points to null
Step16. Stop

PROGRAM:

#include <stdio.h>
#include <conio.h>
#include <process.h>
#include <alloc.h>
#include <string.h>
struct node {
int label;
struct node *next; };
main() {
int ch, fou=0; int k;
struct node *h, *temp, *head, *h1; /* Head node construction */

28
head = (struct node*) malloc(sizeof(struct node)); head->label = -1;
head->next = NULL; while(-1)
{ clrscr();
printf("\n\n SINGLY LINKED LIST OPERATIONS \n"); printf("1->Add ");
printf("2->Delete "); printf("3->View "); printf("4->Exit \n"); printf("Enter your choice : ");
scanf("%d", &ch); switch(ch)
{
/* Add a node at any intermediate location */ case 1:
printf("\n Enter label after which to add : "); scanf("%d", &k);
h = head; fou = 0;
if (h->label == k) fou = 1;
while(h->next != NULL) {
if (h->label == k)
{ fou=1; break;
}
h = h->next; }
if (h->label == k) fou = 1;
if (fou != 1)
printf("Node not found\n"); else
{
temp=(struct node *)(malloc(sizeof(struct node))); printf("Enter label for new node : ");
scanf("%d" , &temp->label); temp->next = h->next;
h->next = temp;
} break;
/* Delete any intermediate node */ case 2:
printf("Enter label of node to be deleted\n"); scanf("%d", &k);
fou = 0;
h = h1 = head;
while (h->next != NULL) {
h = h->next; if (h->label == k)
{
fou = 1; break;
}}
if (fou == 0)
printf("Sorry Node not found\n"); else
{
while (h1->next != h) h1 = h1->next;

29
h1->next = h->next; free(h);
printf("Node deleted successfully \n");
} break;
case 3:
printf("\n\n HEAD -> "); h=head;
while (h->next != NULL) {
h = h->next;
printf("%d -> ",h->label);
} printf("NULL");
break; case 4:
exit(0); }
}}

OUTPUT:

SINGLY LINKED LIST OPERATIONS

1->Add 2->Delete 3->View 4->Exit
Enter your choice : 1
Enter label after which new node is to be added : -1
Enter label for new node : 23
SINGLY LINKED LIST OPERATIONS
1->Add 2->Delete 3->View 4->Exit
Enter your choice : 1
Enter label after which new node is to be added : 23
Enter label for new node : 67
SINGLY LINKED LIST OPERATIONS
1->Add 2->Delete 3->View 4->Exit
Enter your choice : 3
HEAD -> 23 -> 67 -> NULL

30
8b. To implement stack operations using linked list.
ALGORITHM:
Step 1. Start
Step2. Define a singly linked list node for stack
Step3. Create Head node
Step4. Display a menu listing stack operations
Step5. Accept choice
Step6. If choice = 1 then
Step7. Create a new node with data
Step8. Make new node point to first node
Step9. Make head node point to new node
Step10. If choice = 2 then
Step11. Make temp node point to first node
Step12. Make head node point to next of temp node
Step13. Release memory
Step14. If choice = 3 then
Step15. Display stack elements starting from head node till null
Step16. Stop
Program
#include <stdio.h>
#include <conio.h>
#include <process.h>
#include <alloc.h>
struct node
{
int label;
struct node *next; };
main() {
int ch = 0; int k;
struct node *h, *temp, *head; /* Head node construction */
head = (struct node*) malloc(sizeof(struct node)); head->next = NULL;
while(1) {
printf("\n Stack using Linked List \n"); printf("1->Push ");
printf("2->Pop "); printf("3->View "); printf("4->Exit \n"); printf("Enter your choice : "); scanf("%d",
&ch); switch(ch)
{ case 1:
/* Create a new node */

31
temp=(struct node *)(malloc(sizeof(struct node))); printf("Enter label for new node : ");
scanf("%d", &temp->label); h = head;
temp->next = h->next; h->next = temp;
break; case 2:
/* Delink the first node */ h = head->next;
head->next = h->next;
printf("Node %s deleted\n", h->label); free(h);
break; case 3:
printf("\n HEAD -> "); h = head;
/* Loop till last node */ while(h->next != NULL) {
h = h->next;
printf("%d -> ",h->label); }
printf("NULL \n"); break;
case 4: exit(0);
}
}
}
OUTPUT:
Stack using Linked List
1->Push 2->Pop 3->View 4->Exit
Enter your choice : 1
Enter label for new node : 23
New node added Stack using Linked List
1->Push 2->Pop 3->View 4->Exit
Enter your choice : 1
Enter label for new node : 34 Stack using Linked List 1->Push 2->Pop 3->View 4->Exit
Enter your choice : 3 HEAD -> 34 -> 23 -> NULL

8c. To implement queue operations using linked list.

ALGORITHM:

Step 1. Start
Step2. Define a singly linked list node for stack
Step3. Create Head node
Step4. Display a menu listing stack operations
Step5. Accept choice
Step6. If choice = 1 then

32
Step7. Create a new node with data
Step8. Make new node point to first node
Step9. Make head node point to new node
Step10. If choice = 2 then
Step11. Make temp node point to first node
Step12. Make head node point to next of temp node
Step13. Release memory
Step14. If choice = 3 then
Step15. Display stack elements starting from head node till null
Step16. Stop

PROGRAM:

#include <stdio.h>
#include <conio.h>
#include <process.h>
#include <alloc.h>
struct node
{
int label;
struct node *next; };
main() {
int ch=0; int k;
struct node *h, *temp, *head; /* Head node construction */
head = (struct node*) malloc(sizeof(struct node)); head->next = NULL;
while(1) {
printf("\n Queue using Linked List \n"); printf("1->Insert ");
printf("2->Delete "); printf("3->View ");
printf("4->Exit \n"); printf("Enter your choice : "); scanf("%d", &ch); switch(ch)
{ case 1:
/* Create a new node */
temp=(struct node *)(malloc(sizeof(struct node))); printf("Enter label for new node : ");
scanf("%d", &temp->label); /* Reorganize the links */ h = head;
while (h->next != NULL) h = h->next;
h->next = temp; temp->next = NULL; break;
case 2:
/* Delink the first node */ h = head->next;
head->next = h->next; printf("Node deleted \n"); free(h);

33
break; case 3:
printf("\n\nHEAD -> "); h=head;
while (h->next!=NULL) {
h = h->next;
printf("%d -> ",h->label); }
printf("NULL \n"); break;
case 4: exit(0);
}
}
}

OUTPUT:
Queue using Linked List
1->Insert 2->Delete 3->View 4->Exit Enter your choice : 1
Enter label for new node : 12
Queue using Linked List
1->Insert 2->Delete 3->View 4->Exit Enter your choice : 1
Enter label for new node : 23
Queue using Linked List
1->Insert 2->Delete 3->View 4->Exit Enter your choice : 3
HEAD -> 12 -> 23 -> NULL

RESULT:
Thus Linked List Implementation of List, Stack and Queue ADTswas written, executed and
the output was verified successfully.

34
EX.NO:9
APPLICATIONS OF LIST, STACK AND QUEUE ADTS
DATE:

AIM:

To store a polynomial using linked list. Also, perform addition and subtraction on two
polynomials.

ALGORITHM:

Step 1: Start the program

Step 2:Let p and q be the two polynomials represented by linked lists
Step 3: while p and q are not null, repeat step 4.
Step 4: If powers of the two terms are equal then
Step5: If the terms do not cancel theninsert the sum of the terms into the sum Polynomial Advance p
Advance q
Step6: Else if the power of the first polynomial> power of second Then Insert the term from first
polynomial into sum polynomialAdvance p
Step7: Elseinsert the term from second polynomial into sum polynomial Advance q 3.
Step8: Copy the remaining terms from the non-empty polynomial into the sum polynomial.
Step9: The third step of the algorithm is to be processed till the end of the polynomials has not been
reached.

PROGRAM:

#include <stdio.h>
#include <conio.h>
#include <malloc.h>
struct node
{
int num; int coeff;
struct node *next; };
struct node *start1 = NULL; struct node *start2 = NULL; struct node *start3 = NULL; struct node
*start4 = NULL; struct node *last3 = NULL;
struct node *create_poly(struct node *); struct node *display_poly(struct node *);
struct node *add_poly(struct node *, struct node *, struct node *); struct node *sub_poly(struct node
*, struct node *, struct node *); struct node *add_node(struct node *, int, int);
int main() {
int option; clrscr();
do {

35
printf("\n******* MAIN MENU *******"); printf("\n 1. Enter the rst polynomial"); printf("\n 2.
Display the rst polynomial"); printf("\n 3. Enter the second polynomial"); printf("\n 4. Display the
second polynomial"); printf("\n 5. Add the polynomials"); printf("\n 6. Display the result");
printf("\n 7. Subtract the polynomials"); printf("\n 8. Display the result"); printf("\n 9. EXIT");
printf("\n\n Enter your option : "); scanf("%d", &option); switch(option)
{
case 1:
start1 = create_poly(start1); break;
case 2:
start1 = display_poly(start1);
break; case 3:
start2 = create_poly(start2); break;
case 4:
start2 = display_poly(start2); break;
case 5:
start3 = add_poly(start1, start2, start3); break;
case 6:
start3 = display_poly(start3); break;
case 7:
start4 = sub_poly(start1, start2, start4); break;
case 8:
start4 = display_poly(start4); break;
} }while(option!=9); getch();
return 0; }
struct node *create_poly(struct node *start) {
struct node *new_node, *ptr; int n, c;
printf("\n Enter the number : "); scanf("%d", &n);
printf("\t Enter its coef cient : ");
scanf("%d", &c); while(n != –1)
{
if(start==NULL) {
new_node = (struct node *)malloc(sizeof(struct node)); new_node ->num = n;
new_node ->coeff = c; new_node ->next = NULL; start = new_node;
} else {
ptr = start;
while(ptr ->next != NULL) ptr = ptr ->next; new_node = (struct node *)malloc(sizeof(struct node));
new_node ->num = n;

36
new_node ->coeff = c; new_node ->next = NULL; ptr ->next = new_node;
}
printf("\n Enter the number : "); scanf("%d", &n);
if(n == –1) break;
printf("\t Enter its coef cient : ");
scanf("%d", &c); } return start;
}
struct node *display_poly(struct node *start) {
struct node *ptr; ptr = start; while(ptr != NULL) {
printf("\n%d x %d\t", ptr ->num, ptr ->coeff); ptr = ptr ->next;
}
return start; }
struct node *add_poly(struct node *start1, struct node *start2, struct node *start3) {
struct node *ptr1, *ptr2;
int sum_num, c;
ptr1 = start1, ptr2 = start2;
while(ptr1 != NULL && ptr2 != NULL) {
if(ptr1 ->coeff == ptr2 ->coeff) {
sum_num = ptr1 ->num + ptr2 ->num;
start3 = add_node(start3, sum_num, ptr1 ->coeff); ptr1 = ptr1 ->next; ptr2 = ptr2 ->next;
}
else if(ptr1 ->coeff > ptr2 ->coeff) {
start3 = add_node(start3, ptr1 ->num, ptr1 ->coeff); ptr1 = ptr1 ->next;
}
else if(ptr1 ->coeff < ptr2 ->coeff) {
start3 = add_node(start3, ptr2 ->num, ptr2 ->coeff); ptr2 = ptr2 ->next;
}}
if(ptr1 == NULL) {
while(ptr2 != NULL) {
start3 = add_node(start3, ptr2 ->num, ptr2 ->coeff); ptr2 = ptr2 ->next;
}}
if(ptr2 == NULL) {
while(ptr1 != NULL) {
start3 = add_node(start3, ptr1 ->num, ptr1 ->coeff); ptr1 = ptr1 ->next;
}
} return start3; }
struct node *sub_poly(struct node *start1, struct node *start2, struct node *start4) {

37
struct node *ptr1, *ptr2; int sub_num, c;
ptr1 = start1, ptr2 = start2;
do {
if(ptr1 ->coeff == ptr2 ->coeff) {
sub_num = ptr1 ->num – ptr2 ->num;
start4 = add_node(start4, sub_num, ptr1 ->coeff); ptr1 = ptr1 ->next; ptr2 = ptr2 ->next;
}
else if(ptr1 ->coeff > ptr2 ->coeff) {
start4 = add_node(start4, ptr1 ->num, ptr1 ->coeff); ptr1 = ptr1 ->next;
}
else if(ptr1 ->coeff < ptr2 ->coeff) {
start4 = add_node(start4, ptr2 ->num, ptr2 ->coeff); ptr2 = ptr2 ->next;
}
}while(ptr1 != NULL || ptr2 != NULL); if(ptr1 == NULL)
{
while(ptr2 != NULL) {
start4 = add_node(start4, ptr2 ->num, ptr2 ->coeff); ptr2 = ptr2 ->next;
}}
if(ptr2 == NULL) {
while(ptr1 != NULL) {
start4 = add_node(start4, ptr1 ->num, ptr1 ->coeff); ptr1 = ptr1 ->next;
}}
return start4; }
struct node *add_node(struct node *start, int n, int c) {
struct node *ptr, *new_node; if(start == NULL)
{
new_node = (struct node *)malloc(sizeof(struct node)); new_node ->num = n;
new_node ->coeff = c; new_node ->next = NULL; start = new_node;
} else {
ptr = start;
while(ptr ->next != NULL) ptr = ptr ->next;
new_node = (struct node *)malloc(sizeof(struct node));
new_node ->num = n;
new_node ->coeff = c; new_node ->next = NULL; ptr ->next = new_node;
}
return start;
}

38
OUTPUT:
******* MAIN MENU *******
1. Enter the 1rst polynomial
2. Display the 1rst polynomial
–––––––––––––––––––––––––––––––
9. EXIT
Enter your option: 1
Enter the number: 6
Enter its coefficient: 2
Enter the number: 5
Enter its coefficient: 1
Enter the number: –1
Enter your option: 2
6x25x1
Enter your option: 9

39
9b. To convert infix expression to its postfix form using stack operations.

ALGORITHM:

Step 1. Start
Step2. Define a array stack of size max = 20
Step3. Initialize top = -1
Step4. Read the infix expression character-by-character
Step5. If character is an operand print it
Step6. If character is an operator
Step7. Compare the operator’s priority with the stack[top] operator.
Step8. If the stack [top] operator has higher or equal priority than the inputoperator,Pop it from the
stack and print it.
Step9. Else
Step10. Push the input operator onto the stack
Step11. If character is a left parenthesis, then push it onto the stack.
Step12. If the character is a right parenthesis, pop all the operators from the stack andprint ituntil a
left parenthesis is encountered. Do not print the parenthesis.

PROGRAM:

#include <stdio.h>
#include <conio.h>
#include <string.h>
#define MAX 20
int top = -1;
char stack[MAX]; char pop();
void push(char item); int prcd(char symbol)
{ switch(symbol) {
case '+': case '-':
return 2; break;
case '*': case '/':
return 4; break;
case '^': case '$':
return 6; break;
case '(': case ')':
case '#':
return 1; break;
}}

40
int isoperator(char symbol) {
switch(symbol) {
case '+': case '-': case '*': case '/': case '^': case '$': case '(': case ')':
return 1; break;
default:
return 0; }
}
void convertip(char infix[],char postfix[]) {
int i,symbol,j = 0; stack[++top] = '#'; for(i=0;i<strlen(infix);i++) {
symbol = infix[i]; if(isoperator(symbol) == 0) {
postfix[j] = symbol; j++;
} else {
if(symbol == '(') push(symbol);
else if(symbol == ')') {
while(stack[top] != '(') {
postfix[j] = pop(); j++;
}
pop(); //pop out (.
} else

{
if(prcd(symbol) > prcd(stack[top])) push(symbol);
else {
while(prcd(symbol) <= prcd(stack[top])) {
postfix[j] = pop(); j++;
} push(symbol);
}}
}}
while(stack[top] != '#') {
postfix[j] = pop(); j++;
}
postfix[j] = '\0';
} main() {
char infix[20],postfix[20]; clrscr();
printf("Enter the valid infix string: "); gets(infix);
convertip(infix, postfix);
printf("The corresponding postfix string is: "); puts(postfix);

41
getch(); }
void push(char item) {
top++; stack[top] = item;
}
char pop() {
char a;
a = stack[top]; top--;
return a; }

OUTPUT:

Enter the valid infix string: (a+b*c)/(d$e)

The corresponding postfix string is: abc*+de$/
Enter the valid infix string: a*b+c*d/e
The corresponding postfix string is: ab*cd*e/+
Enter the valid infix string: a+b*c+(d*e+f)*g
The corresponding postfix string is: abc*+de*f+g*+

42
9c. To evaluate the given postfix expression using stack operations.

ALGORITHM:

Step 1. Start
Step2. Define a array stack of size max = 20
Step3. Initialize top = -1
Step4. Read the postfix expression character-by-character
Step5. If character is an operand push it onto the stack
Step6. If character is an operator
Step7. Pop topmost two elements from stack.
Step8. Apply operator on the elements and push the result onto the stack,eventually only result will
be in the stack at end of the expression.
Step9. Pop the result and print it.

PROGRAM:

#include <stdio.h>
#include <conio.h>
struct stack
{
int top; float a[50];
}s; main() {
char pf[50]; float d1,d2,d3;
int i; clrscr(); s.top = -1;
printf("\n\n Enter the postfix expression: "); gets(pf);
for(i=0; pf[i]!='\0'; i++)
{ switch(pf[i]) {
case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9':
s.a[++s.top] = pf[i]-'0';
break; case '+':
d1 = s.a[s.top--];
d2 = s.a[s.top--]; s.a[++s.top] = d1 + d2;
break; case '-':
d2 = s.a[s.top--]; d1 = s.a[s.top--]; s.a[++s.top] = d1 - d2;
break; case '*':
d2 = s.a[s.top--]; d1 = s.a[s.top--]; s.a[++s.top] = d1*d2;
break; case '/':
d2 = s.a[s.top--]; d1 = s.a[s.top--]; s.a[++s.top] = d1 / d2; break;

43
}}
printf("\n Expression value is %5.2f", s.a[s.top]); getch();
}

OUTPUT:

Enter the postfix expression: 6523+8*+3+*

Expression value is 288.00

RESULT:
Thus the Applications of List, Stack and Queue ADTswas evaluated using stack was written,
executed and the output was verified successfully.

44
EX.NO:10 IMPLEMENTATION OF BINARY TREES AND OPERATIONS OF
DATE: BINARY TREES

AIM:

To write a Program in C to Implement Binary-Tree and operations of Binary Trees

ALGORITHM:

Step 1: Start the Program

Step 2: Declare a Template for Key and Elements
Step 3: Insert the Key-Element Pair into the Tree, overwriting Existing pair, if any, with same key
Step 4: Find place to Insert. While P != NULL
Step 5: Examine Element pointed to by Pair. Move P to a Child
Step 6: If Pair First Element is Less Than Element of first P, assign P as Left Child.
Step 7: If Pair First Element is Greater than Element of first P, assign P as Right Child
Step 8: Else, Replace Old Value
Step 9: Retrieve a Node for the Pair and assign to Pair Pointer Element
Step 10: If Root != NULL, the tree is not Empty.
Step 11: Now, Handle Input Operation – Insert, Delete, ListOrder Accordingly
Step 12: If Pair First Element is Less Than Pair Pointer First Element; LeftChildNode = NewNode
Step 13: Else, Pair Pointer First Element RightChildNode = NewNode. Else, Root = NewNode
Step 14: Insert Operation into Tree Successful.
Step 15: Stop

PROGRAM:

# include <stdio.h>
# include <malloc.h>
struct node {
int info;
struct node *lchild;
struct node *rchild; }*root;
void find(int item,struct node **par,struct node **loc) {
struct node *ptr,*ptrsave;
if(root==NULL) /*tree empty*/ {
*loc=NULL; *par=NULL;
return; }
if(item==root->info) /*item is at root*/ {
*loc=root; *par=NULL; return;
}

45
/*Initialize ptr and ptrsave*/
if(item<root->info) ptr=root->lchild;
else
ptr=root->rchild; ptrsave=root;
while(ptr!=NULL) {
if(item==ptr->info) { *loc=ptr;
*par=ptrsave; return;
} ptrsave=ptr;
if(item<ptr->info) ptr=ptr->lchild;
else
ptr=ptr->rchild; }/*End of while */
*loc=NULL;
*par=ptrsave; }/*End of find()*/
void insert(int item)
{ struct node *tmp,*parent,*location;
find(item,&parent,&location);
if(location!=NULL) {
printf("Item already present"); return;
}
tmp=(struct node *)malloc(sizeof(struct node)); tmp->info=item;
tmp->lchild=NULL; tmp->rchild=NULL;
if(parent==NULL) root=tmp;
else
if(item<parent->info) parent->lchild=tmp;
else
parent->rchild=tmp; }/*End of insert()*/
void case_a(struct node *par,struct node *loc ) {
if(par==NULL) /*item to be deleted is root node*/ root=NULL;
else
if(loc==par->lchild) par->lchild=NULL;
else
par->rchild=NULL; }/*End of case_a()*/
void case_b(struct node *par,struct node *loc) {
struct node *child;
/*Initialize child*/
if(loc->lchild!=NULL) /*item to be deleted has lchild */ child=loc->lchild;
else

46
/*item to be deleted has rchild */
child=loc->rchild;
if(par==NULL ) /*Item to be deleted is root node*/
root=child;
else
if( loc==par->lchild) /*item is lchild of its parent*/ par->lchild=child;
else /*item is rchild of its parent*/ par->rchild=child;
}/*End of case_b()*/
void case_c(struct node *par,struct node *loc) {
struct node *ptr,*ptrsave,*suc,*parsuc;
/*Find inorder successor and its parent*/ ptrsave=loc;
ptr=loc->rchild; while(ptr->lchild!=NULL) {
ptrsave=ptr; ptr=ptr->lchild;
}
suc=ptr; parsuc=ptrsave;
if(suc->lchild==NULL && suc->rchild==NULL) case_a(parsuc,suc);
else
case_b(parsuc,suc);
if(par==NULL) /*if item to be deleted is root node */ root=suc;
else
if(loc==par->lchild) par->lchild=suc;
else
par->rchild=suc;
suc->lchild=loc->lchild; suc->rchild=loc->rchild;
}/*End of case_c()*/ int del(int item)
{
struct node *parent,*location; if(root==NULL)
{
printf("Tree empty"); return 0;
}
find(item,&parent,&location);
if(location==NULL) {
printf("Item not present in tree"); return 0;
}
if(location->lchild==NULL && location->rchild==NULL) case_a(parent,location);
if(location->lchild!=NULL && location->rchild==NULL) case_b(parent,location);
if(location->lchild==NULL && location->rchild!=NULL) case_b(parent,location);

47
if(location->lchild!=NULL && location->rchild!=NULL) case_c(parent,location);
free(location); }/*End of del()*/
int preorder(struct node *ptr) {
if(root==NULL) {
printf("Tree is empty"); return 0;
} if(ptr!=NULL) {
printf("%d ",ptr->info); preorder(ptr->lchild); preorder(ptr->rchild);
}
}/*End of preorder()*/
void inorder(struct node *ptr) {
if(root==NULL) {
printf("Tree is empty"); return;
} if(ptr!=NULL) {
inorder(ptr->lchild); printf("%d ",ptr->info); inorder(ptr->rchild);
}
}/*End of inorder()*/
void postorder(struct node *ptr) {
if(root==NULL) {
printf("Tree is empty"); return;
} if(ptr!=NULL) {
postorder(ptr->lchild); postorder(ptr->rchild); printf("%d ",ptr->info);
}
}/*End of postorder()*/
void 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()*/ main()
{
int choice,num; root=NULL; while(1)
{
printf("\n"); printf("1.Insert\n"); printf("2.Delete\n"); printf("3.Inorder Traversal\n");
printf("4.Preorder Traversal\n"); printf("5.Postorder Traversal\n"); printf("6.Display\n");
printf("7.Quit\n"); printf("Enter your choice : "); scanf("%d",&choice);
switch(choice) {

48
case 1:
printf("Enter the number to be inserted : ");
scanf("%d",&num);
insert(num);
break; case 2:
printf("Enter the number to be deleted : "); scanf("%d",&num);
del(num); break;
case 3: inorder(root); break;
case 4: preorder(root); break;
case 5: postorder(root); break;
case 6: display(root,1); break;
case 7:
break; default:
printf("Wrong choice\n"); }/*End of switch */
}/*End of while */
}/*End of main()*/

OUTPUT:

1. Insert
2. Delete
3. Find
4. Find Min
5. Find Max
6. Display
7. Exit
Enter your Choice : 1
Enter an element : 10
1. Insert
2. Delete
3. Find
4. Find Min
5. Find Max
6. Display
7. Exit
Enter your Choice : 1

49
Enter an element : 20
1. Insert
2. Delete
3. Find
4. Find Min
5. Find Max
6. Display
7. Exit
Enter your Choice : 1
Enter an element : 5
1. Insert
2. Delete
3. Find
4. Find Min
5. Find Max
6. Display
7. Exit
Enter your Choice : 4
The smallest Number is 5
1. Insert
2. Delete
3. Find
4. Find Min
5. Find Max
6. Display
7. Exit
Enter your Choice : 3
Enter an element : 100
Element not Found
1. Insert
2. Delete
3. Find
4. Find Min
5. Find Max
6. Display
7. Exit
Enter your Choice : 2

50
Enter an element : 20
1. Insert
2. Delete
3. Find
4. Find Min
5. Find Max
6. Display
7. Exit
Enter your Choice : 6
20
10
1. Insert
2. Delete
3. Find
4. Find Min
5. Find Max
6. Display
7. Exit
Enter your Choice: 7

RESULT:
Thus the implementation of Binary Trees and operations of Binary Treeswritten, executed and
the output was verified successfully.

51
EX.NO:11 IMPLEMENTATION OF BINARY SEARCH TREES
DATE:

AIM:
To write a C program to Implementation of Binary Search Trees.

ALGORITHM:

Step 1: Start the Program

Step 2: Declare a Template for Key and Elements
Step 3:Insert the Key-Element Pair into the Tree, overwriting Existing pair, if any, with same key
Step 4: Find place to Insert. While P != NULL
Step 5: Examine Element pointed to by Pair. Move P to a Child
Step 6: If Pair First Element is Less Than Element of first P, assign P as Left Child.
Step 7: If Pair First Element is Greater than Element of first P, assign P as Right Child
Step 8: Else, Replace Old Value
Step 9: Retrieve a Node for the Pair and assign to Pair Pointer Element
Step 10: If Root != NULL, the tree is not Empty
Step 11: Stop

PROGRAM:
#include <iostream>
using namespace std;
struct Node {
int data;
Node *left;
Node *right;
};
Node* create(int item)
{
Node* node = new Node;
node->data = item;
node->left = node->right = NULL;
return node;
}
/*Inorder traversal of the tree formed*/
void inorder(Node *root)
{

52
 if (root == NULL)
return;
inorder(root->left); //traverse left subtree
cout<< root->data << " "; //traverse root node
inorder(root->right); //traverse right subtree
}
Node* findMinimum(Node* cur) /*To find the inorder successor*/
{
while(cur->left != NULL) {
cur = cur->left;
}
return cur;
}
Node* insertion(Node* root, int item) /*Insert a node*/
{
if (root == NULL)
return create(item); /*return new node if tree is empty*/
if (item < root->data)
root->left = insertion(root->left, item);
else
root->right = insertion(root->right, item);
return root;
}
void search(Node* &cur, int item, Node* &parent)
{
while (cur != NULL && cur->data != item)
{
parent = cur;
if (item < cur->data)
cur = cur->left;
else
cur = cur->right;
}
}
void deletion(Node*& root, int item) /*function to delete a node*/
{
Node* parent = NULL;

53
Node* cur = root;
search(cur, item, parent); /*find the node to be deleted*/
if (cur == NULL)
return;
if (cur->left == NULL && cur->right == NULL) /*When node has no children*/
{
if (cur != root)
{
if (parent->left == cur)
parent->left = NULL;
else
parent->right = NULL;
}
else
root = NULL;
free(cur);
}
else if (cur->left && cur->right)
{
Node* succ = findMinimum(cur->right);
int val = succ->data;
deletion(root, succ->data);
cur->data = val;
}
else
{
Node* child = (cur->left)? cur->left: cur->right;
if (cur != root)
{
if (cur == parent->left)
parent->left = child;
else
parent->right = child;
}
else
root = child;
free(cur);

54
 }
}
int main()
{
Node* root = NULL;
root = insertion(root, 45);
root = insertion(root, 30);
root = insertion(root, 50);
root = insertion(root, 25);
root = insertion(root, 35);
root = insertion(root, 45);
root = insertion(root, 60);
root = insertion(root, 4);
printf("The inorder traversal of the given binary tree is - \n");
inorder(root);
deletion(root, 25);
printf("\nAfter deleting node 25, the inorder traversal of the given binary tree is - \n");
inorder(root);
insertion(root, 2);
printf("\nAfter inserting node 2, the inorder traversal of the given binary tree is - \n");
inorder(root);
return 0;
}

OUTPUT:

RESULT:
Thus the Implementation of Binary Search Treeswas written, executed and the output was
verified successfully.

55
EX.NO:12
IMPLEMENTATION OF SEARCHING TECHNIQUES
DATE:

AIM:
To perform linear search of an element on the given array.

ALGORITHM:

Step 1. Start
Step2. Read number of array elements n
Step3. Read array elements Ai, i = 0,1,2,…n–1
Step4. Read search value
Step5. Assign 0 to found
Step6. Check each array element against search
Step7. If Ai = search then found = 1
Step 8. Print "Element found" Print position i , Stop
Step9. If found = 0 thenprint "Element not found"
Step 10. Stop

PROGRAM:

#include <stdio.h>
#include <conio.h>
main()
{
int a[50],i, n, val, found; clrscr();
printf("Enter number of elements : "); scanf("%d", &n);
printf("Enter Array Elements : \n"); for(i=0; i<n; i++)
scanf("%d", &a[i]);
printf("Enter element to locate : "); scanf("%d", &val);
found = 0; for(i=0; i<n; i++) {
if (a[i] == val) {
printf("Element found at position %d", i); found = 1;
break; }
}
if (found == 0)
printf("\n Element not found");
getch();
}

56
OUTPUT:

Enter number of elements : 7

Enter Array Elements :
23 6 12 5 0 32 10
Enter element to locate : 5
Element found at position 3

57
12 b: To locate an element in a sorted array using Binary search method
ALGORITHM:

Step 1. Start
Step2. Read number of array elements, say n
Step3. Create an array arr consisting n sorted elements
Step4. Get element, say key to be located
Step5. Assign 0 to lower and n to upper
Step6. While (lower < upper)
a. Determine middle element mid = (upper+lower)/2
b. If key = arr[mid] then
i. Print mid
ii. Stop
c. Else if key > arr[mid] then
i. lower = mid + 1
d. else
i. upper = mid – 1
Step7. Print "Element not found"
Step8. Stop

Program:

#include <stdio.h>
void main() {
int a[50],i, n, upper, lower, mid, val, found, att=0; printf("Enter array size : ");
scanf("%d", &n); for(i=0; i<n; i++) a[i] = 2 * i;
printf("\n Elements in Sorted Order \n"); for(i=0; i<n; i++)
printf("%4d", a[i]);
printf("\n Enter element to locate : "); scanf("%d", &val);
upper = n; lower = 0; found = -1;
while (lower <= upper) {
mid = (upper + lower)/2; att++;
if (a[mid] == val) {
printf("Found at index %d in %d attempts", mid, att); found = 1;
break; }
else if(a[mid] > val) upper = mid - 1; else
lower = mid + 1; }
if (found == -1) printf("Element not found");
}

58
OUTPUT:

Enter array size : 10

Elements in Sorted Order 0 2 4 6 8 10 12 14 16 18
Enter element to locate : 16
Found at index 8 in 2 attempts

RESULT:
Thus the Implementation of searching techniques was written, executed and the output was
verified successfully.

59
EX.NO:13 IMPLEMENTATION OF SORTING ALGORITHMS: INSERTION SORT,
DATE: QUICK SORT, MERGE SORT

AIM:

To sort an array of N numbers using Insertion sort.

ALGORITHM:

Step 1. Start
Step2. Read number of array elements n
Step3. Read array elements Ai
Step4. Outer index i varies from second element to last element
Step5. Inner index j is used to compare elements to left of outer index
Step6. Insert the element into the appropriate position.
Step7. Display the array elements after each pass
Step8. Display the sorted array elements.
Step9. Stop

PROGRAM:

#include< stdio.h>
#inclide<conio.h>
void main()
{
int i, j, k, n, temp, a[20], p=0; printf("Enter total elements: "); scanf("%d",&n);
printf("Enter array elements: "); for(i=0; i<n; i++)
scanf("%d", &a[i]); for(i=1; i<n; i++) {
temp = a[i]; j = i - 1;
while((temp<a[j]) && (j>=0)) {
a[j+1] = a[j]; j = j - 1;
}
a[j+1] = temp; p++;
printf("\n After Pass %d: ", p); for(k=0; k<n; k++)
printf(" %d", a[k]); }
printf("\n Sorted List : "); for(i=0; i<n; i++) printf(" %d", a[i]);
}

60
OUTPUT:

Enter total elements: 6

Enter array elements: 34 8 64 51 32 21
After Pass 1: 8 34 64 51 32 21
After Pass 2: 8 34 64 51 32 21
After Pass 3: 8 34 51 64 32 21
After Pass 4: 8 32 34 51 64 21
After Pass 5: 8 21 32 34 51 64
Sorted List: 8 21 32 34 51 64

61
13 b : To sort an array of N numbers using Quick sort.

ALGORITHM:

Step 1. Start
Step2. Read number of array elements n
Step3. Read array elements Ai
Step4. Select an pivot element x from Ai
Step5. Divide the array into 3 sequences: elements < x, x, elements > x
Step6. Recursively quick sort both sets (Ai < x and Ai > x)
Step7. Display the sorted array elements
Step8. Stop

PROGRAM:

#include<stdio.h>
#include<conio.h>
void qsort(int arr[20], int fst, int last); main()
{
int arr[30]; int i, size;
printf("Enter total no. of the elements : "); scanf("%d", &size);
printf("Enter total %d elements : \n", size); for(i=0; i<size; i++)
scanf("%d", &arr[i]); qsort(arr,0,size-1);
printf("\n Quick sorted elements \n");
for(i=0; i<size; i++) printf("%d\t", arr[i]); getch();
}
void qsort(int arr[20], int fst, int last) {
int i, j, pivot, tmp; if(fst < last)
{
pivot = fst; i = fst; j = last; while(i < j)
{
while(arr[i] <=arr[pivot] && i<last)
i++;
while(arr[j] > arr[pivot]) j--;
if(i <j ) {
tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
}}
tmp = arr[pivot]; arr[pivot] = arr[j]; arr[j] = tmp; qsort(arr, fst, j-1); qsort(arr, j+1, last);
}}

62
OUTPUT:

Enter total no. of the elements: 8

Enter total 8 elements:
127
-1
04
-2
3
Quick sorted elements -2 -1 0 1 2 3 4 7

63
13 c: To sort an array of N numbers using merge sort.

ALGORITHM:

Step 1. Start
Step2. Read number of array elements n
Step3. Read array elements Ai
Step4. Divide the array into sub-arrays with a set of elements
Step5. Recursively sort the sub-arrays
Step6. Display both sorted sub-arrays
Step7. Merge the sorted sub-arrays onto a single sorted array.
Step8. Display the merge sorted array elements
Step9. Stop

PROGRAM:

#include <stdio.h>
#include <conio.h>
void merge(int [],int ,int ,int );
void part(int [],int ,int ); int size;
main() {
int i, arr[30];
printf("Enter total no. of elements : "); scanf("%d", &size);
printf("Enter array elements : "); for(i=0; i<size; i++) scanf("%d", &arr[i]);
part(arr, 0, size-1);
printf("\n Merge sorted list : "); for(i=0; i<size; i++) printf("%d ",arr[i]);
getch(); }
void part(int arr[], int min, int max) {
int mid; if(min < max) {
mid = (min + max) / 2; part(arr, min, mid); part(arr, mid+1, max); merge(arr, min, mid, max);
}
if (max-min == (size/2)-1)
{
printf("\n Half sorted list : "); for(i=min; i<=max; i++) printf("%d ", arr[i]);
}}
void merge(int arr[],int min,int mid,int max) {
int tmp[30]; int i, j, k, m; j = min; m = mid + 1;
for(i=min; j<=mid && m<=max; i++) {
if(arr[j] <= arr[m]) {

64
tmp[i] = arr[j]; j++;
} else {
tmp[i] = arr[m]; m++;
}}
if(j > mid) {
for(k=m; k<=max; k++) {
tmp[i] = arr[k]; i++;
} } else {
for(k=j; k<=mid; k++) {
tmp[i] = arr[k]; i++;
}}
for(k=min; k<=max; k++) arr[k] = tmp[k];
}

OUTPUT:

Enter total no. of elements : 8

Enter array elements : 24 13 26 1 2 27 38 15 Half sorted list : 1 13 24 26
Half sorted list : 2 15 27 38
Merge sorted list : 1 2 13 15 24 26 27 38

RESULT:
Thus the Implementation of Sorting algorithms: Insertion Sort, Quick Sort, Merge Sort was
written, executed and the output was verified successfully.

65
EX.NO:14 IMPLEMENTATION OF HASHING – ANY TWO COLLISION
DATE: TECHNIQUES

AIM:

To implement hashing technique and collision resolution technique.

ALGORITHM:

Step 1. Start
Step2. A structure that represent the key, data pair is created
Step3. Key is generated by hashcode function which returns the value of key%sizewhere size is
assumed as 20
Step4. Insert function is called to insert a new key value pair into the hash table.
Step5. While inserting an element if the hashcode function returns a key that hasbeen previously
assigned to an element in the hash table then a collision occurs.
Step6. If there is a collision then the hash key is incremented to move to the nextplace and find
whether there is a key-space for inserting the current element.This is called collision resolution. This
process is repeated until a space if foundfor current element or the hash table is full
Step7. Delete function is called to delete an element from the hash table.
Step8. Stop

PROGRAM:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define SIZE 20
struct DataItem
{
int data;
int key;
};
struct DataItem* hashArray[SIZE]; struct DataItem* dummyItem; struct DataItem* item;
int hashCode(int key) {
return key % SIZE; }
struct DataItem *search(int key) {
int hashIndex = hashCode(key); //get the hash
while(hashArray[hashIndex] != NULL) //move in array until an empty {

66
if(hashArray[hashIndex]->key == key) return hashArray[hashIndex];
++hashIndex; //go to next cell
hashIndex %= SIZE; //wrap around the table
}
return NULL; }
void insert(int key,int data) {
struct DataItem *item = (struct DataItem*) malloc(sizeof(struct DataItem)); item->data = data;
item->key = key;
int hashIndex = hashCode(key);//get the hash
//move in array until an empty or deleted cell
while(hashArray[hashIndex] != NULL && hashArray[hashIndex]->key != -1) {
++hashIndex; //go to next cell
hashIndex %= SIZE; //wrap around the table
}
hashArray[hashIndex] = item; }
struct DataItem* delete(struct DataItem* item) {
int key = item->key;
int hashIndex = hashCode(key); //get the hash
while(hashArray[hashIndex] != NULL) //move in array until an empty {
if(hashArray[hashIndex]->key == key) {
struct DataItem* temp = hashArray[hashIndex];
hashArray[hashIndex] = dummyItem; //assign a dummy item at deleted //position
return temp; }
++hashIndex; //go to next cell
hashIndex %= SIZE; //wrap around the table }
return NULL; }
void display() {
int i = 0;
for(i = 0; i<SIZE; i++) {
if(hashArray[i] != NULL)
printf(" (%d,%d)",hashArray[i]->key,hashArray[i]->data); else
printf(" ~~ "); }
printf("\n"); }
int main() {
dummyItem = (struct DataItem*) malloc(sizeof(struct DataItem)); dummyItem->data = -1;
dummyItem->key = -1;

67
insert(1, 20); insert(2, 70); insert(42, 80); insert(4, 25); insert(12, 44); insert(14, 32); insert(17, 11);
insert(13, 78); insert(37, 97);
display();
item = search(37);
if(item != NULL) {
printf("Element found: %d\n", item->data); } else
{
printf("Element not found\n"); }
delete(item); item = search(37);
if(item != NULL) {
printf("Element found: %d\n", item->data); } else
{
printf("Element not found\n"); }
}

OUTPUT:
(1, 20) (2, 70) (42, 80) (4, 25) (12, 44) (13, 78) (14, 32) (17, 11) (37, 97)
Element found: 97
Element not found

RESULT:
Thus the implement hashing technique and collision resolution technique was written,
executed and the output was verified successfully.

68