NAME:Ruchi Vengurlekar

ROLL NO: 18043

SUBJECT:DATA STRUCTURE PRATICAL

Practical no:-1
A. Write a program to store the elements in 1-D array and
perform the operations like searching, sorting, reversing the
elements.
Code:-
Searching the element:
#include<stdio.h
int main()
{
int a[100], n, element, pos=0;
int i;
printf("Enter array size : ");
scanf("%d", &n);
printf("Enter array elements: ");
for(i=0; i<n; i++)
scanf("%d", &a[i]);
printf("Enter element to search: ");
scanf("%d",&element);
for(i=0; i<n; i++)
{
if(a[i]==element)
{
printf("%d is found at position : %d", element, i+1);
return 0;
}
}
printf("%d not found.", element);
return 0;
}
output:
Sorting the element:
#include <stdio.h>
void main()
{
int i,j,n,a[100],temp,p,q,temp1;
printf("Enter the size of array : ") ;
scanf("%d",&n) ;
printf("Enter the elements : ") ;
for(i=0;i<n;i++)
{
scanf("%d",&a[i]) ;
}
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++) { if(a[i]>a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
printf("\nAscending order of an array : \n");
for(i=0;i<n;i++)
{
printf("%d ",a[i]) ;
}
for(p=0;p<n;p++)
{
for(q=p+1;q<n;q++)
{
if(a[p]<a[q])
{
temp1=a[p];
a[p]=a[q];
a[q]=temp1;
}
}
}
printf("\n \nDescending order of an array : \n ");
for(p=0;p<n;p++)
{
printf("%d ",a[p]) ;
}
}
output:
Reversing the element:
#include <stdio.h>
int main()
{
int arr[100],reverse[100];
int size, i, a, b;
printf("Enter size of the array: ");
scanf("%d", &size);
printf("Enter elements in array: ");
for(i=0; i<size; i++)
{
scanf("%d", &arr[i]);
}
b = 0;
a = size - 1;
while(a >= 0)
{
reverse[b] = arr[a];
b++;
a--;
}
printf("\nReversed array : ");
for(i=0; i<size; i++)
{
printf("%d \t", reverse[i]);
}
return 0;
}
output:
B. Read the two arrays from the user and merge them and
display the elements in sorted order.
Code:-
#include <stdio.h>
int main()
{
int n1,n2,n3; //Array Size Declaration
printf("\nEnter the size of first array: ");
scanf("%d",&n1);
printf("\nEnter the size of second array: ");
scanf("%d",&n2);
n3=n1+n2;
printf("\nEnter the sorted array elements: ");
int a[n1],b[n2],c[n3]; //Array Declaration
for(int i=0;i<n1;i++) //Array Initialized
{
scanf("%d",&a[i]);
c[i]=a[i];
}
int k=n1;
printf("\nEnter the sorted array elements: ");
for(int i=0;i<n2;i++) //Array Initialized
{
scanf("%d",&b[i]);
c[k]=b[i];
k++;
}
printf("\nThe merged array..\n");
for(int i=0;i<n3;i++)
printf("%d ",c[i]); //Print the merged array
printf("\nAfter sorting...\n");
for(int i=0;i<n3;i++) //Sorting Array
{
int temp;
for(int j=i+1; j<n3 ;j++)
{
if(c[i]<c[j])
{
temp=c[i];
c[i]=c[j];
c[j]=temp;
}
}
}
for(int i=0 ; i<n3 ; i++) //Print the sorted Array
{
printf(" %d ",c[i]);
}
return 0;
}
output:
C. Write a program to perform the Matrix addition,
Multiplication, Transpose operation.
Code:-
#include<stdio.h>
#include<conio.h>
int main()
{
int
m,n,a[20][20],b[20][20],i,j,sum[20][20],sub[20][20],opt,tr[20][2
0]
,opt1,ch,e,f;
printf("Enter the no. of rows: ");
scanf("%d",&m);
printf("Enter the no. of columns: ");
scanf("%d",&n);
printf("Enter the Data Elements of first matrices\n");
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&a[i][j]);
}
} printf("Enter the no. of rows for second matrices: ");
scanf("%d",&e);
printf("Enter the no. of columns: ");
scanf("%d",&f);
printf("Enter the Data Elements of second matrices\n");
for(i=0;i<e;i++)
{
for(j=0;j<f;j++)
{
scanf("%d",&b[i][j]);
}
}
do
{
if(m==e&&n==f)
{

if(n==e){printf("Enter 2 for multiplication of matrices\n");}

printf("Enter 3 for transpose of first matrices\n");
}
else if(m!=n&&n==e)
{
printf("Enter 2 for multiplication of matrices\n");
printf("Enter 3 for transpose of first matrices\n");
}
else
{
printf("Enter 3 for transpose of first matrices\n");
}
scanf("%d",&ch);
switch(ch)
{
case 1 :
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
sum[i][j]=a[i][j]+b[i][j];
sub[i][j]=a[i][j]-b[i][j];
}
}
printf("Enter 1 for Addition" );
scanf("%d",&opt);
switch(opt)
{
case 1 :
printf("The resultant matrices is :\n");
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
printf("%3d",sum[i][j]);
}
printf("\n");
}
break;
case 2 :
printf("The resultant matrices is :\n");
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
printf("%3d",sub[i][j]);
}
printf("\n");
}
}
break;
case 2 :
printf("The resultant matrices is : \n");
int k;
for(i=0;i<m;i++)
{
for(j=0;j<f;j++)
{ sum[i][j]=0;
for(k=0;k<m;k++)
{
sum[i][j]+=a[i][k]*b[k][j];
}
printf("%d\t",sum[i][j]);
}
printf("\n");
}
break;
case 3 :
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
tr[j][i]=a[i][j];
}
}
printf("The resultant matrices is :\n");
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
printf("%3d",tr[i][j]);
}
printf("\n");
}
break; }}
while(ch>0);
getch();
}
output:
Practical no 2(a)
2(a).Write a program to create a single linked list and
display the node elements in Reverse order
Code:-
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node *next;
}*head;

void createList(int n);

void reverseList();
void displayList();

int main()
{
int n, choice;
printf("Enter the total number of nodes: ");
scanf("%d", &n);
createList(n);

printf("\nData in the list \n");

displayList();

printf("\nPress 1 to reverse the order of singly linked

list\n");
scanf("%d", &choice);
if(choice == 1)
{
reverseList();
}

printf("\nData in the list\n");

displayList();
return 0;
}
void createList(int n)
{
struct node *newNode, *temp;
int data, i;

if(n <= 0)
{
printf("List size must be greater than zero.\n");
return;
}

head = (struct node *)malloc(sizeof(struct node));

if(head == NULL)
{
printf("Unable to allocate memory.");
}
else
{
printf("Enter the data of node 1: ");
scanf("%d", &data);

head->data = data;
head->next = NULL;

temp = head;
for(i=2; i<=n; i++)
{
newNode = (struct node *)malloc(sizeof(struct node));

if(newNode == NULL)
{
printf("Unable to allocate memory.");
break;
}
else
{
printf("Enter the data of node %d: ", i);
scanf("%d", &data);

newNode->data = data;
newNode->next = NULL;

temp->next = newNode;
temp = temp->next;
}
}

printf("SINGLY LINKED LIST CREATED SUCCESSFULLY\n");

}
}
void reverseList()
{
struct node *prevNode, *curNode;

if(head != NULL)
{
prevNode = head;
curNode = head->next;
head = head->next;

prevNode->next = NULL;

while(head != NULL)
{
head = head->next;
curNode->next = prevNode;

prevNode = curNode;
curNode = head;
}

head = prevNode;

printf("SUCCESSFULLY REVERSED LIST\n");

}
}

void displayList()
{
struct node *temp;
if(head == NULL)
{
printf("List is empty.");
}
else
{
temp = head;
while(temp != NULL)
{
printf("Data = %d\n", temp->data);
temp = temp->next;
}
}
}

Output :
2(b).Write a program to search the elements in the
linked list and display the same
Code:-
#include <stdio.h>
#include <stdlib.h>
*, int);
void release(struct node **);
void display(struct node *);

int main()
{
struct node *p = NULL;
int key, result;

printf("Enter data into the list\n");

create(&p);
printf("Displaying the nodes in the list:\n");
display(p);
printf("Enter key to search in the list: ");
scanf("%d", &key);
result = search(p, key);
if (result)
{
printf("%d found in the list.\n", key);
}
else
{
printf("%d not found in the list.\n", key);
}
release(&p);

return 0;
}

int search(struct node *head, int key)

{
while (head != NULL)
{
if (head->num == key)
{
return 1;
}
head = head->next;
}

return 0;
}

void create(struct node **head)

{
int c, ch;
struct node *temp, *rear;

do
{
printf("Enter number: ");
scanf("%d", &c);
temp = (struct node *)malloc(sizeof(struct node));
temp->num = c;
temp->next = NULL;
if (*head == NULL)
{
*head = temp;
}
else
{
rear->next = temp;
}
rear = temp;
printf("Do you wish to continue [1/0]: ");
scanf("%d", &ch);
} while (ch != 0);
printf("\n");
}

void display(struct node *p)

{
while (p != NULL)
{
printf("%d\t", p->num);
p = p->next;
}
printf("\n");
}

void release(struct node **head)

{
struct node *temp = *head;
*head = (*head)->next;
while ((*head) != NULL)
{
free(temp);
temp = *head;
(*head) = (*head)->next;
}
}

Output:-
2(c).Write a program to create double linked
list and sort the elements in the linked list.
Code:-

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

struct node {
int num;
struct node * preptr;
struct node * nextptr;
}*stnode, *ennode;

void DlListcreation(int n);

void displayDlList();

int main()
{
int n;
stnode = NULL;
ennode = NULL;
printf("\n\n Doubly Linked List : Create and display a
doubly linked list :\n");
printf("--------------------------------------------------------------
-----\n");

printf(" Input the number of nodes : ");

scanf("%d", &n);

DlListcreation(n);
displayDlList();
return 0;
}

void DlListcreation(int n)
{
int i, num;
struct node *fnNode;

if(n >= 1)
{
stnode = (struct node *)malloc(sizeof(struct node));

if(stnode != NULL)
{
printf(" Input data for node 1 : ");
scanf("%d", &num);

stnode->num = num;
stnode->preptr = NULL;
stnode->nextptr = NULL;
ennode = stnode;
for(i=2; i<=n; i++)
{
fnNode = (struct node *)malloc(sizeof(struct
node));
if(fnNode != NULL)
{
printf(" Input data for node %d : ", i);
scanf("%d", &num);
fnNode->num = num;
fnNode->preptr = ennode;
fnNode->nextptr = NULL;

ennode->nextptr = fnNode;
ennode = fnNode;
}
else
{
printf(" Memory can not be allocated.");
break;
}
}
}
else
{
printf(" Memory can not be allocated.");
}
}
}
void displayDlList()
{
struct node * tmp;
int n = 1;
if(stnode == NULL)
{
printf(" No data found in the List yet.");
}
else
{
tmp = stnode;
printf("\n\n Data entered on the list are :\n");

while(tmp != NULL)
{
printf(" node %d : %d\n", n, tmp->num);
n++;
tmp = tmp->nextptr; // current pointer moves to
the next node
}
}
}
Output:

3. Implement the following for

Stack:-
A.Write a program to implement the concept of
Stack with Push, Pop, Display and Exit operations.
Input:-
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 5
struct stack
{
int stk[MAXSIZE];
int top;
};
typedef struct stack ST;
ST s;

void push ()
{
int num;
if (s.top == (MAXSIZE - 1))
{
printf ("Stack is Full\n");
return;
}
else
{
printf ("\nEnter element to be pushed : ");
scanf ("%d", &num);
s.top = s.top + 1;
s.stk[s.top] = num;
}
return;
}

int pop ()
{
int num;
if (s.top == - 1)
{
printf ("Stack is Empty\n");
return (s.top);
}
else
{
num = s.stk[s.top];
printf ("poped element is = %d\n", s.stk[s.top]);
s.top = s.top - 1;
}
return(num);
}

void display ()
{
int i;
if (s.top == -1)
{
printf ("Stack is empty\n");
return;
}
else
{
printf ("\nStatus of elements in stack : \n");
for (i = s.top; i >= 0; i--)
{
printf ("%d\n", s.stk[i]);
}
}
}
int main ()
{
int ch;
s.top = -1;

printf ("\tSTACK OPERATIONS\n");

printf("----------------------------\n");
printf(" 1. PUSH\n");
printf(" 2. POP\n");
printf(" 3. DISPLAY\n");
printf(" 4. EXIT\n");
//printf("----------------------------\n");
while(1)
{
printf("\nChoose operation : ");
scanf("%d", &ch);
switch (ch)
{
case 1:
push();
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
exit(0);
default:
printf("Invalid operation \n");
}
}
return 0;
}

Output:-
B. Write a program to convert an infix
expression to postfix and prefix conversion.
Input:-
#include<stdio.h>
#include<ctype.h>

Char stack[100];
Int top = -1;

Void push(char x)
{
Stack[++top] = x;
}

Char pop()
{
If(top == -1)
Return -1;
Else
Return stack[top--];
}

Int priority(char x)
{
If(x == ‘(‘)
Return 0;
If(x == ‘+’ || x == ‘-‘)
Return 1;
If(x == ‘*’ || x == ‘/’)
Return 2;
Return 0;
}
#include<stdio.h>
#include<ctype.h>

Char stack[100];
Int top = -1;

Void push(char x)
{
Stack[++top] = x;
}

Char pop()
{
If(top == -1)
Return -1;
Else
Return stack[top--];
}

Int priority(char x)
{
If(x == ‘(‘)
Return 0;
If(x == ‘+’ || x == ‘-‘)
Return 1;
If(x == ‘*’ || x == ‘/’)
Return 2;
Return 0;
}

Int main()
{
Char exp[100];
Char *e, x;
Printf(“Enter the expression : “);
Scanf(“%s”,exp);
Printf(“\n”);
E = exp;

While(*e != ‘\0’)
{
If(isalnum(*e))
Printf(“%c “,*e);
Else if(*e == ‘(‘)
Push(*e);
Else if(*e == ‘)’)
{
While((x = pop()) != ‘(‘)
Printf(“%c “, x);
}
Else
{
While(priority(stack[top]) >= priority(*e))
Printf(“%c “,pop());
Push(*e);
}
E++;
}

While(top != -1)
{
Printf(“%c “,pop());
}return 0;
}

Output:-
C. Write a program to implement Tower of
Hanoi problem.
Input:-
#include<stdio.h>
void TOH(int n,char x,char y,char z)
{
if(n>0)
{
TOH(n-1,x,z,y);
printf("\n%c to %c",x,y);
TOH(n-1,z,y,x);
}
}
int main()
{
int n=3;
TOH(n,'A','B','C');
}

Output:-

Practical no:-4
(a). Write a program to implement the concept of Queue
with Insert, Delete, Display
and Exit operations.
Code:-
#include <stdio.h>
#define MAX 50
void insert();
void delete();
void display();
int queue_array[MAX];
int rear = - 1;
int front = - 1;
main()
{
int choice;
while (1)
{
printf("1.Insert element to queue \n");
printf("2.Delete element from queue \n");
printf("3.Display all elements of queue \n");
printf("4.Quit \n");
printf("Enter your choice : ");
scanf("%d", &choice);
switch (choice)
{
case 1:
insert();
break;
case 2:
delete();
break;
case 3:
display();
break;
case 4:
exit(1);
default:
printf("Wrong choice \n");
}
}
}
void insert()
{
int add_item;
if (rear == MAX - 1)
printf("Queue Overflow \n");
else
{
if (front == - 1)
/*If queue is initially empty */
front = 0;
printf("Inset the element in queue : ");
scanf("%d", &add_item);
rear = rear + 1;
queue_array[rear] = add_item;
}
}
void delete()
{
if (front == - 1 || front > rear)
{
printf("Queue Underflow \n");
return ;
}
else
{
printf("Element deleted from queue is : %d\n",
queue_array[front]);
front = front + 1;
}
}

void display()

int i;

if (front == - 1)

printf("Queue is empty \n");

else

printf("Queue is : \n");

for (i = front; i <= rear; i++)

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

printf("\n");

Output:-

(b). Write a program to implement the concept of

Circular Queue
Code:-
// Circular Queue implementation in C

#include <stdio.h>

#define SIZE 5
int items[SIZE];
int front = -1, rear = -1;

// Check if the queue is full

int isFull() {
if ((front == rear + 1) || (front == 0 && rear == SIZE -
1)) return 1;
return 0;
}

// Check if the queue is empty

int isEmpty() {
if (front == -1) return 1;
return 0;
}
// Adding an element
void enQueue(int element) {
if (isFull())
printf("\n Queue is full!! \n");
else {
if (front == -1) front = 0;
rear = (rear + 1) % SIZE;
items[rear] = element;
printf("\n Inserted -> %d", element);
}
}

// Removing an element
int deQueue() {
int element;
if (isEmpty()) {
printf("\n Queue is empty !! \n");
return (-1);
} else {
element = items[front];
if (front == rear) {
front = -1;
rear = -1;
}
// Q has only one element, so we reset the
// queue after dequeing it. ?
else {
front = (front + 1) % SIZE;
}
printf("\n Deleted element -> %d \n", element);
return (element);
}
}
// Display the queue
void display() {
int i;
if (isEmpty())
printf(" \n Empty Queue\n");
else {
printf("\n Front -> %d ", front);
printf("\n Items -> ");
for (i = front; i != rear; i = (i + 1) % SIZE) {
printf("%d ", items[i]);
}
printf("%d ", items[i]);
printf("\n Rear -> %d \n", rear);
}
}

int main() {
// Fails because front = -1
deQueue();

enQueue(1);
enQueue(2);
enQueue(3);
enQueue(4);
enQueue(5);

// Fails to enqueue because front == 0 && rear ==

SIZE - 1
enQueue(6);

display();
deQueue();

display();
enQueue(7);
display();

// Fails to enqueue because front == rear + 1

enQueue(8);

return 0;
}
Output:-
(c). Write a program to implement the concept
of Deque.
Code:-

#include <stdio.h>
#define MAX 10
void addFront(int *, int, int *, int *);
void addRear(int *, int, int *, int *);
int delFront(int *, int *, int *);
int delRear(int *, int *, int *);
void display(int *);
int count(int *);
int main() {
int arr[MAX];
int front, rear, i, n;

front = rear = -1;

for (i = 0; i < MAX; i++)
arr[i] = 0;

addRear(arr, 5, &front, &rear);

addFront(arr, 12, &front, &rear);
addRear(arr, 11, &front, &rear);
addFront(arr, 5, &front, &rear);
addRear(arr, 6, &front, &rear);
addFront(arr, 8, &front, &rear);

printf("\nElements in a deque: ");

display(arr);
i = delFront(arr, &front, &rear);
printf("\nremoved item: %d", i);

printf("\nElements in a deque after deletion: ");

display(arr);
addRear(arr, 16, &front, &rear);
addRear(arr, 7, &front, &rear);

printf("\nElements in a deque after addition: ");

display(arr);

i = delRear(arr, &front, &rear);

printf("\nremoved item: %d", i);

printf("\nElements in a deque after deletion: ");

display(arr);
n = count(arr);
printf("\nTotal number of elements in deque: %d", n);
}
void addFront(int *arr, int item, int *pfront, int *prear) {
int i, k, c;
if (*pfront == 0 && *prear == MAX - 1) {
printf("\nDeque is full.\n");
return;
}

if (*pfront == -1) {
*pfront = *prear = 0;
arr[*pfront] = item;
return;
}

if (*prear != MAX - 1) {
c = count(arr);
k = *prear + 1;
for (i = 1; i <= c; i++) {
arr[k] = arr[k - 1];
k--;
}
arr[k] = item;
*pfront = k;
(*prear)++;
} else {
(*pfront)--;
arr[*pfront] = item;
}
}

void addRear(int *arr, int item, int *pfront, int *prear) {

int i, k;

if (*pfront == 0 && *prear == MAX - 1) {

printf("\nDeque is full.\n");
return;
}

if (*pfront == -1) {
*prear = *pfront = 0;
arr[*prear] = item;
return;
}

if (*prear == MAX - 1) {
k = *pfront - 1;
for (i = *pfront - 1; i < *prear; i++) {
k = i;
if (k == MAX - 1)
arr[k] = 0;
else
arr[k] = arr[i + 1];
}
(*prear)--;
(*pfront)--;
}
(*prear)++;
arr[*prear] = item;
}

int delFront(int *arr, int *pfront, int *prear) {

int item;

if (*pfront == -1) {
printf("\nDeque is empty.\n");
return 0;
}

item = arr[*pfront];
arr[*pfront] = 0;
if (*pfront == *prear)
*pfront = *prear = -1;
else
(*pfront)++;

return item;
}

int delRear(int *arr, int *pfront, int *prear) {

int item;

if (*pfront == -1) {
printf("\nDeque is empty.\n");
return 0;
}
item = arr[*prear];
arr[*prear] = 0;
(*prear)--;
if (*prear == -1)
*pfront = -1;
return item;
}

void display(int *arr) {

int i;

printf("\n front: ");

for (i = 0; i < MAX; i++)
printf(" %d", arr[i]);
printf(" :rear");
}
int count(int *arr) {
int c = 0, i;

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

if (arr[i] != 0)
c++;
}
return c;
}

Output:-
Practical no:- 5. Implement the following sorting techniques:

5a)

Aim:- Write a program to implement bubble sort.

Code:-
#include <stdio.h> void
bubblesort(int arr[], int size)
{ int
i, j;

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

for (j = 0; j < size - i; j++)

if (arr[j] > arr[j+1])

swap(&arr[j], &arr[j+1]);
}

void swap(int *a, int *b)

{
int temp;
temp = *a;
*a = *b;
*b = temp;

int main()

int array[100], i, size;

printf("How many numbers you want to sort: ");

scanf("%d", &size); printf("\nEnter %d numbers : ",
size);

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

scanf("%d", &array[i]);
bubblesort(array, size);
printf("\nSorted array is ");
for (i = 0; i < size; i++)
printf(" %d ", array[i]); return
0;
}

Output:

5b)
Aim:- Write a program to implement selection sort.
Code:- #include
<stdio.h>

void swap(int *xp, int *yp)

int temp = *xp;

*xp = *yp;
*yp = temp;

void selectionSort(int arr[], int n)

int i, j, min_idx;

// One by one move boundary of unsorted subarray

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

// Find the minimum element in unsorted array

min_idx = i; for (j =
i+1; j < n; j++) if (arr[j] <
arr[min_idx]) min_idx
= j;

// Swap the found minimum element with the first element swap(&arr[min_idx],

&arr[i]);
}

}
/* Function to print an array */ void
printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]); printf("\n");
}

// Driver program to test above functions int

main()
{

int arr[] = {64, 25, 12, 22, 11};

int n = sizeof(arr)/sizeof(arr[0]);
selectionSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n); return 0;
}

Output:
5c)

Aim:- Write a program to implement insertion sort.

Code:- #include
<math.h>

#include <stdio.h>

/* Function to sort an array using insertion sort*/ void

insertionSort(int arr[], int n)
{ int i, key, j; for (i
= 1; i < n; i++) {
key = arr[i];
j = i - 1;

/* Move elements of arr[0..i-1], that are

greater than key, to one position ahead
of their current position */ while (j >= 0
&& arr[j] > key) {
arr[j + 1] = arr[j];

j = j - 1;

arr[j + 1] = key;

// A utility function to print an array of size n void

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

/* Driver program to test insertion sort */ int

main()
{

int arr[] = { 12, 11, 13, 5, 6 }; int

n = sizeof(arr) / sizeof(arr[0]);

insertionSort(arr, n);
printArray(arr, n);

return 0;

Output:

Practical no:- 6 Implement the following data structure techniques:

6a)
Aim:- Write a program to implement merge sort.

Code:-
#include <stdio.h>

#include <stdlib.h>

// Merges two subarrays of arr[].

// First subarray is arr[l..m] // Second

subarray is arr[m+1..r] void merge(int
arr[], int l, int m, int r)
{ int i, j,
k;
int n1 = m - l + 1;
int n2 = r - m;

/* create temp arrays */

int L[n1], R[n2];

/* Copy data to temp arrays L[] and R[] */

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

L[i] = arr[l + i]; for (j
= 0; j < n2; j++)
R[j] = arr[m + 1 + j];

/* Merge the temp arrays back into arr[l..r]*/

i = 0; // Initial index of first subarray j=

0; // Initial index of second subarray k = l;
// Initial index of merged subarray while (i
< n1 && j < n2) {
if (L[i] <= R[j])
{ arr[k] =
L[i]; i++;
}
else {
arr[k] = R[j];
j++;
}

k++;

/* Copy the remaining elements of L[], if there

are any */ while (i < n1) { arr[k] = L[i];
i++; k++;
}

/* Copy the remaining elements of R[], if there

are any */ while (j < n2) { arr[k] = R[j];
j++; k++;
}

/* l is for left index and r is right index of the sub-array of

arr to be sorted */

void mergeSort(int arr[], int l, int r)

{ if (l <
r) {
// Same as (l+r)/2, but avoids overflow for
// large l and h
int m = l + (r - l) / 2;

// Sort first and second halves

mergeSort(arr, l, m); mergeSort(arr,
m + 1, r);

merge(arr, l, m, r);

/* UTILITY FUNCTIONS */ /*
Function to print an array */
void printArray(int A[], int size)
{
int i;
for (i = 0; i < size; i++)
printf("%d ", A[i]); printf("\n");
}

/* Driver code */
int main()
{

int arr[] = { 12, 11, 13, 5, 6, 7 }; int

arr_size = sizeof(arr) / sizeof(arr[0]);
printf("Given array is \n");
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);

printf("\nSorted array is \n");

printArray(arr, arr_size);
return 0;
}

Output:

6b)

Aim:- Write a program to search the element using sequential search.

Code:-

#include <stdio.h>

#define MAX 5

/** function : linearSearch()

to search an element.
**/ int linearSearch(int
*a,int n)
{

int i,pos=-1;

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

{

if(a[i]==n)

pos=i;
break;

return pos;

int main()

int i,n,arr[MAX]; int num; /*

element to search*/ int position;

printf("\nEnter array elements:\n");

for(i=0;i< MAX;i++)
scanf("%d",&arr[i]);

printf("\nNow enter element to search :"); scanf("%d",&num);

/* calling linearSearch function*/

position=linearSearch(arr,num);

if(num==-1) printf("Element
not found.\n");
else

printf("Element found @ %d position.\n",position);

return 0;

Output:

6c)

Aim:- Write a program to search the element using binary search

Code:-
#include <stdio.h> void
binary_search();

int a[50], n, item, loc, beg, mid, end, i; void

main()
{
printf("\nEnter size of an array: "); scanf("%d", &n);
printf("\nEnter elements of an array in sorted form:\n");
for(i=0; i<n; i++) scanf("%d", &a[i]);
printf("\nEnter ITEM to be searched: ");
scanf("%d", &item); binary_search();
getch();

void binary_search()

beg = 0;

end = n-1; mid = (beg + end) / 2;

while ((beg<=end) && (a[mid]!=item))
{

if (item < a[mid])

end = mid - 1;
else

beg = mid + 1;
mid = (beg + end) / 2;
}

if (a[mid] == item) printf("\n\nITEM found at

location %d", mid+1);
else

printf("\n\nITEM doesn't exist");

Output:

Enter number of elements

6
Enter 6 integers
10
30
20
15
56
100
Enter value to find
33
Not found! 33 is not present in the list.
Practical no:- 7 Implement the following data
structure techniques:
7a) Aim:- Write a program to create the tree and
display the elements.
Code:-
#include <stdio.h>
#include <malloc.h>
#include <stdio.h>
#include <conio.h>
typedef struct TREE {
int data;
struct TREE *left;
struct TREE *right;
}
TREE;
int main() {
int data,depth;
TREE *tree =NULL;
TREE *InsertTree(int data,TREE *p);
TREE *PrintTreeTriangle(TREE *tree, int level);
int TreeDepth(TREE *tree,int *depth,int level);
while(1) {
printf("\nKey to insert|");
scanf("%d", &data);
if (data==0)
break;
tree =InsertTree(data,tree);
printf("\n Tree Display;\n");
PrintTreeTriangle(tree,1);
depth=0;

75 | P a g e
TreeDepth(tree,&depth,0);
printf("\nTree Depth =%d\n",depth);
}
return(0);
}
TREE *InsertTree(int data,TREE *p) {
if(!p) {
p=(TREE*)malloc(sizeof(TREE));
p->data=data;
p->left=NULL;
p->right=NULL;
return(p);
}
if(data < p->data)
p->left=InsertTree(data,p->left); else
if(data > p->data)
p->right=InsertTree(data,p->right);
return(p);
}
TREE *PrintTreeTriangle(TREE *tree, int level) {
int i;
if(tree) {
PrintTreeTriangle(tree->right,level+1);
printf("\n\n");
for (i=0;i<level;i++)
printf(" ");
printf("%d",tree->data);
PrintTreeTriangle(tree->left,level+1);
}
return(NULL);

76 | P a g e
}
int TreeDepth(TREE *tree,int *depth,int level) {
if(tree) {
if (level>*depth)
*depth=level;
TreeDepth(tree->left,depth,level+1);
TreeDepth(tree->right,depth,level+1);
}
return(0);
}
Output:

Practical 7b)

Aim:- Write a program to construct the binary tree

Code:-
#include<stdio.h>
#include<stdlib.h>

struct treenode
{
int info;
struct treenode *lchild;
struct treenode *rchild;
}*root=NULL;

struct listnode
{
struct listnode *prev;
int info;
struct listnode *next;
}*pre=NULL, *in=NULL;

void display(struct treenode *ptr,int level);

struct listnode *addtoempty(struct listnode *start,int data);
struct listnode *addatend(struct listnode *start,int data);
struct listnode *create_list(struct listnode *start, int n);
struct treenode *construct(struct listnode *inptr,struct listnode
*preptr, int num);
void inorder(struct treenode *ptr);
void postorder(struct treenode *ptr);
void preorder(struct treenode *ptr);

int main( )
{
int n;

printf("Enter the number of nodes : ");

scanf("%d",&n);

printf("\nEnter inorder\n");
in = create_list(in, n);

printf("\nEnter preorder\n");
pre=create_list(pre, n);

root = construct(in,pre,n);
printf("\nInorder : "); inorder(root);
printf("\n\nPostorder : "); postorder(root);
printf("\n\nPreorder : "); preorder(root);
printf("\n\n\nTree is : \n");
display(root,0);
printf("\n");

return 0;
}

struct treenode *construct(struct listnode *inptr,struct listnode

*preptr, int num )
{
struct treenode *temp;
struct listnode *q;

int i,j;
if(num==0)
return NULL;

temp=(struct treenode *)malloc(sizeof(struct treenode));

temp->info=preptr->info;
temp->lchild = NULL;
temp->rchild = NULL;

if(num==1)/*if only one node in tree */

return temp;

q = inptr;
for(i=0; q->info != preptr->info; i++)
q = q->next;

/*Now q points to root node in inorder list and

and number of nodes in its left subtree is i*/

/*For left subtree*/

temp->lchild = construct(inptr, preptr->next, i);

/*For right subtree*/

for(j=1;j<=i+1;j++)
preptr=preptr->next;
temp->rchild = construct(q->next, preptr, num-i-1);

return temp;
}/*End of construct()*/

void display(struct treenode *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 display()*/

struct listnode *create_list(struct listnode *start, int n)

{
int i, data;
start=NULL;
for(i=1;i<=n;i++)
{
printf("Enter the element to be inserted : ");
scanf("%d",&data);
if(start==NULL)
start=addtoempty(start,data);
else
start=addatend(start,data);
}
return start;
}/*End of create_list()*/

struct listnode *addtoempty(struct listnode *start,int data)

{
struct listnode *tmp;
tmp=(struct listnode*)malloc(sizeof(struct listnode));
tmp->info=data;
tmp->prev=NULL;
tmp->next=NULL;
start=tmp;
return start;
}/*End of addtoempty( )*/
struct listnode *addatend(struct listnode *start,int data)
{
struct listnode *tmp,*p;
tmp=(struct listnode*)malloc(sizeof(struct listnode));
tmp->info=data;
p=start;
while(p->next!=NULL)
p=p->next;
p->next=tmp;
tmp->next=NULL;
tmp->prev=p;
return start;
}/*End of addatend( )*/

void inorder(struct treenode *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 treenode *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 preorder(struct treenode *ptr)

{
if(root==NULL)
{
printf("Tree is empty");
return;
}
if(ptr!=NULL)
{
printf("%d ",ptr->info);
preorder(ptr->lchild);
preorder(ptr->rchild);
}
}/*End of preorder( )*/
Output:
Practical7c)
Aim:- Write a program for inorder, postorder and
preorder traversal of tree
Code:-
// C++ program for different tree traversals

#include <iostream>

using namespace std;

/* A binary tree node has data, pointer to left child

and a pointer to right child */

struct Node {

int data;
struct Node *left, *right;

Node(int data)

this->data = data;

left = right = NULL;

};

/* Given a binary tree, print its nodes according to the

"bottom-up" postorder traversal. */

void printPostorder(struct Node* node)

if (node == NULL)

return;

// first recur on left subtree

printPostorder(node->left);

// then recur on right subtree

printPostorder(node->right);

// now deal with the node

cout << node->data << " ";

/* Given a binary tree, print its nodes in inorder*/

void printInorder(struct Node* node)

if (node == NULL)

return;

/* first recur on left child */

printInorder(node->left);

/* then print the data of node */

cout << node->data << " ";

/* now recur on right child */

printInorder(node->right);

/* Given a binary tree, print its nodes in preorder*/

void printPreorder(struct Node* node)

{
if (node == NULL)

return;

/* first print data of node */

cout << node->data << " ";

/* then recur on left subtree */

printPreorder(node->left);

/* now recur on right subtree */

printPreorder(node->right);

/* Driver program to test above functions*/

int main()

struct Node* root = new Node(1);

root->left = new Node(2);

root->right = new Node(3);

root->left->left = new Node(4);

root->left->right = new Node(5);

cout << "\nPreorder traversal of binary tree is \n";

printPreorder(root);

cout << "\nInorder traversal of binary tree is \n";

printInorder(root);

cout << "\nPostorder traversal of binary tree is \n";

printPostorder(root);

return 0;

Output:
Practical no 8
Aim:- Write a program to insert the element into minimum heap.

Code:
#include <iostream>

#include <conio.h>

using namespace std;

void min_heap(int *a, int m, int n){

int j, t;

t= a[m];

j = 2 * m;

while (j <= n) {

if (j < n && a[j+1] < a[j])

j = j + 1;

if (t < a[j])

break;

else if (t >= a[j]) {

a[j/2] = a[j];

j = 2 * j;

a[j/2] = t;

return;

}
void build_minheap(int *a, int n) {

int k;

for(k = n/2; k >= 1; k--) {

min_heap(a,k,n);

int main() {

int n, i;

cout<<"enter no of elements of array\n";

cin>>n;

int a[30];

for (i = 1; i <= n; i++) {

cout<<"enter element"<<" "<<(i)<<endl;

cin>>a[i];

build_minheap(a, n);

cout<<"Min Heap\n";

for (i = 1; i <= n; i++) {

cout<<a[i]<<endl;

getch();

Output
enter no of elements of array
5
enter element 1
7
enter element 2
6
enter element 3
2
enter element 4
1
enter element 5
4
Min Heap
1
4
2
6
7

Practical no.8(b)

Aim:- Write a program to insert the element into minimum heap.

Code:
#include <iostream>

#include <conio.h>

using namespace std;

void min_heap(int *a, int m, int n){

int j, t;

t= a[m];

j = 2 * m;

while (j <= n) {

if (j < n && a[j+1] < a[j])

j = j + 1;

if (t < a[j])

break;

else if (t >= a[j]) {

a[j/2] = a[j];

j = 2 * j;

a[j/2] = t;

return;

void build_minheap(int *a, int n) {

int k;

for(k = n/2; k >= 1; k--) {

min_heap(a,k,n);

int main() {

int n, i;

cout<<"enter no of elements of array\n";

cin>>n;

int a[30];

for (i = 1; i <= n; i++) {

cout<<"enter element"<<" "<<(i)<<endl;

cin>>a[i];
}

build_minheap(a, n);

cout<<"Min Heap\n";

for (i = 1; i <= n; i++) {

cout<<a[i]<<endl;

getch();

Output
enter no of elements of array
5
enter element 1
7
enter element 2
6
enter element 3
2
enter element 4
1
enter element 5
4
Min Heap
1
4
2
6
7
Practical no.9(a)
Aim: Write a program to implement the collision technique.
Code:

#include<bits/stdc++.h>

using namespace std;

class Hash

int BUCKET; // No. of buckets

// Pointer to an array containing buckets

list<int> *table;

public:

Hash(int V); // Constructor

// inserts a key into hash table

void insertItem(int x);

// deletes a key from hash table

void deleteItem(int key);

// hash function to map values to key

int hashFunction(int x) {

return (x % BUCKET);

}
void displayHash();

};

Hash::Hash(int b)

this->BUCKET = b;

table = new list<int>[BUCKET];

void Hash::insertItem(int key)

int index = hashFunction(key);

table[index].push_back(key);

void Hash::deleteItem(int key)

// get the hash index of key

int index = hashFunction(key);

// find the key in (index)th list

list <int> :: iterator i;

for (i = table[index].begin();

i != table[index].end(); i++) {

if (*i == key)
break;

// if key is found in hash table, remove it

if (i != table[index].end())

table[index].erase(i);

// function to display hash table

void Hash::displayHash() {

for (int i = 0; i < BUCKET; i++) {

cout << i;

for (auto x : table[i])

cout << " --> " << x;

cout << endl;

// Driver program

int main()

// array that contains keys to be mapped

int a[] = {15, 11, 27, 8, 12};

int n = sizeof(a)/sizeof(a[0]);
// insert the keys into the hash table

Hash h(7); // 7 is count of buckets in

// hash table

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

h.insertItem(a[i]);

// delete 12 from hash table

h.deleteItem(12);

// display the Hash table

h.displayHash();

return 0;

Output:

0
1 --> 15 --> 8

4 --> 11

6 --> 27

1 --> 15 --> 8
Practical no.9(b)

Aim: Write a program to implement the concept of linear probing.

Code:

#include <stdio.h>
#include<stdlib.h>
#define TABLE_SIZE 10

int h[TABLE_SIZE]={NULL};

void insert()
{

int key,index,i,flag=0,hkey;
printf("\nenter a value to insert into hash table\n");
scanf("%d",&key);
hkey=key%TABLE_SIZE;
for(i=0;i<TABLE_SIZE;i++)
{

index=(hkey+i)%TABLE_SIZE;

if(h[index] == NULL)
{
h[index]=key;
break;
}

if(i == TABLE_SIZE)

printf("\nelement cannot be inserted\n");

}
void search()
{

int key,index,i,flag=0,hkey;
printf("\nenter search element\n");
scanf("%d",&key);
hkey=key%TABLE_SIZE;
for(i=0;i<TABLE_SIZE; i++)
{
index=(hkey+i)%TABLE_SIZE;
if(h[index]==key)
{
printf("value is found at index %d",index);
break;
}
}
if(i == TABLE_SIZE)
printf("\n value is not found\n");
}
void display()
{

int i;

printf("\nelements in the hash table are \n");

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

printf("\nat index %d \t value = %d",i,h[i]);

}
main()
{
int opt,i;
while(1)
{
printf("\nPress 1. Insert\t 2. Display \t3. Search \t4.Exit \n");
scanf("%d",&opt);
switch(opt)
{
case 1:
insert();
break;
case 2:
display();
break;
case 3:
search();
break;
case 4:exit(0);
}
}
}

Output

Press 1. Insert 2. Display 3. Search 4.Exit

1

enter a value to insert into hash table

12

Press 1. Insert 2. Display 3. Search 4.Exit

1

enter a value to insert into hash table

13

Press 1. Insert 2. Display 3. Search 4.Exit

1

enter a value to insert into hash table

22

Press 1. Insert 2. Display 3. Search 4.Exit

2

elements in the hash table are

at index 0 value = 0
at index 1 value = 0
at index 2 value = 12
at index 3 value = 13
at index 4 value = 22
at index 5 value = 0
at index 6 value = 0
at index 7 value = 0
at index 8 value = 0
at index 9 value = 0
Press 1. Insert 2. Display 3. Search 4.Exit
3
enter search element
12
value is found at index 2
Press 1. Insert 2. Display 3. Search 4.Exit
23

enter search element

23

value is not found

Press 1. Insert 2. Display 3. Search 4.Exit

4

Practical no.10(a)

Aim: Implement the following data structure techniques: a. Write a program to generate the adjacency
matrix.

Code:

/* C Program for creation of adjacency matrix */

#include<stdio.h>

#define MAX 100

int adj[MAX][MAX]; /*Adjacency matrix*/

int n; /*Number of vertices in the graph*/

int main()

int max_edges,i,j,origin,destin;
int graph_type;

printf("\nEnter 1 for Undirected graph\nEnter 2 for Directed graph\n");

printf("\nEnter your choice :: ");

scanf("%d",&graph_type);

printf("\nEnter number of vertices :: ");

scanf("%d",&n);

if(graph_type==1)

max_edges = n*(n-1)/2;

else

max_edges = n*(n-1);

for(i=1; i<=max_edges; i++)

printf("\nEnter edge [ %d ] ( -1 -1 to quit ) : ",i);

scanf("%d %d",&origin,&destin);

if( (origin == -1) && (destin == -1) )

break;

if( origin>=n || destin>=n || origin<0 || destin<0 )

printf("\nInvalid vertex!\n");

i--;

}
else

adj[origin][destin] = 1;

if( graph_type == 1) /*if undirected graph*/

adj[destin][origin] = 1;

}/*End of for*/

printf("\nThe adjacency matrix is :: \n");

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

for(j=0; j<=n-1; j++)

printf("%4d",adj[i][j]);

printf("\n");

}/*End of main()*/

OUTPUT : :

/* C Program for Creation of Adjacency matrix */

Enter 1 for Undirected graph

Enter 2 for Directed graph

Enter your choice :: 2

Enter number of vertices :: 5

Enter edge [ 1 ] ( -1 -1 to quit ) : 0 1

Enter edge [ 2 ] ( -1 -1 to quit ) : 0 2

Enter edge [ 3 ] ( -1 -1 to quit ) : 0 3

Enter edge [ 4 ] ( -1 -1 to quit ) : 1 3

Enter edge [ 5 ] ( -1 -1 to quit ) : 2 3

Enter edge [ 6 ] ( -1 -1 to quit ) : 3 4

Enter edge [ 7 ] ( -1 -1 to quit ) : 4 2

Enter edge [ 8 ] ( -1 -1 to quit ) : -1 -1

The adjacency matrix is ::

0 1 1 1 0

0 0 0 1 0

0 0 0 1 0

0 0 0 0 1

0 0 1 0 0
Process returned 0

Practical no.10(b)

Aim:. Write a program for shortest path diagram.

Code:

#include <limits.h>

#include <stdio.h>

#define V 9

int minDistance(int dist[], bool sptSet[]) {

int min = INT_MAX, min_index;

for (int v = 0; v < V; v++)

if (sptSet[v] == false && dist[v] <= min)

min = dist[v], min_index = v;

return min_index;

int printSolution(int dist[], int n) {

printf("Vertex Distance from Source\n");

for (int i = 0; i < V; i++)

printf("%d \t %d\n", i, dist[i]);

void dijkstra(int graph[V][V], int src) {

int dist[V];
bool sptSet[V];

for (int i = 0; i < V; i++)

dist[i] = INT_MAX, sptSet[i] = false;

dist[src] = 0;

for (int count = 0; count < V - 1; count++) {

int u = minDistance(dist, sptSet);

sptSet[u] = true;

for (int v = 0; v < V; v++)

if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) dist[v] =
dist[u] + graph[u][v];

printSolution(dist, V);

int main() {

int graph[V][V] = { { 0, 6, 0, 0, 0, 0, 0, 8, 0 },

{ 6, 0, 8, 0, 0, 0, 0, 13, 0 },

{ 0, 8, 0, 7, 0, 6, 0, 0, 2 },

{ 0, 0, 7, 0, 9, 14, 0, 0, 0 },

{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },

{ 0, 0, 6, 14, 10, 0, 2, 0, 0 },

{ 0, 0, 0, 0, 0, 2, 0, 1, 6 },

{ 8, 13, 0, 0, 0, 0, 1, 0, 7 },

{ 0, 0, 2, 0, 0, 0, 6, 7, 0 }

};

dijkstra(graph, 0);

return 0;
}

Output
Vertex Distance from Source
0 0
1 6
2 14
3 21
4 21
5 11
6 9
7 8
8 15

Rollno:18043
3
4 --> 11
5
6 --> 27