Data Structure Practicals

Table Of Contents Page No. 1. Write a program to perform binary search in an array. 2. Write a program to perform binary search using recursion. 3. Write a program to perform linear search in 2D array. 4. Write a program to perform various operations on matrices. 5. Write a program to swap two nos. using calls by value and reference. 6. Write a program to implement bubble sort. 7. Write a program to implement insertion sort. 8. Write a program to implement selection sort. 9. Write a program of link list implementation of a stack. 10.Write a program of link list implementation of a queue. 11.Write a program of array implementation of a stack. 12.Write a program of array implementation of a queue. 13.Write a program to search an element in a link list. 14.Write a program to maintain a link list. 15.Write a program to implement BST using array.

2 3 4 6 9 10 11 13 14 16 18 20 22 24 28

1

Write a program to perform binary search in an array. /*Binary search in an array*/ #include<stdio.h> #include void main() { int arr[]={1,2,3,9,12,13,15,17}; /* Array declaration*/ int mid,lower=0,upper=8; int flag=1,num; printf(“Enter the number to be searched : “); scanf(”%d”,&num); for(mid=(lower+upper)/2;lower<=upper;mid=(lower+upper)/2) { if (arr[mid]==num) /*If the element is found print its location*/ { printf(“ The number is at location %d “,mid); flag=0; break; /* Exit the loop */ } if (arr[mid]
2

Write a program to perform binary search in an array using recursion. /* Binary search using recursion */ #include<stdio.h> #include int bin_search(int a[],int,int,int); void main() { clrscr(); int arr[7]={1,3,5,7,8,9,11}; /* Declare array */ int lower=0,upper=6;num,p; printf(” Enter the number to be searched : “); scanf(”%d”,&num); p=bin_search(arr,lower,upper,num); /* Function call to bin_search */ if (p==1) printf(” Element not in the list “); else printf(” Element is at a position %d “,p); /* Print location in array */ getch(); } int bin_search(int a[],int lb,int ub,int number) { int middle=(lb+ub)/2,m; if(lb>ub) return -1; if(a[middle]==number) /* If number is found */ return middle; /* Return location of no. */ if(a[middle]
3

Write a program to perform linear search in a 2D array #include<stdio.h> #include void create(int a[3][3]); /* Function Declarations */ void display(int a[3][3]); void search(int a[3][3], int n); void main() { int arr[3][3],num; clrscr(); printf(" Enter the array : "); create(arr); /* Function call to create an array */ display(arr); /* Function call to display array */ printf(" Enter the number to be searched : "); scanf("%d",&num); search(arr,num); /* Perform search */ getch(); } void create(int a[3][3]) /* Function to create an array */ { for(int i=0;i<=2;i++) { for(int j=0;j<=2;j++) { printf(" Enter the element : "); scanf("%d",&a[i][j]); } } } void display(int a[3][3]) /* Function to display the array */ { for(int i=0;i<=2;i++) { for(int j=0;j<=2;j++) printf(" %d",a[i][j]); } } void search(int a[3][3], int n) /* Function to perform linear search*/

4

{ for(int i=0;i<=2;i++) { for(int j=0;j<=2;j++) { if(a[i][j]==n) { printf(" Element found at location %d %d ",i+1,j+1); }

break;

} } }

Output : Enter the array : Enter the element : 1 Enter the element : 2 Enter the element : 3 Enter the element : 4 Enter the element : 5 Enter the element : 6 Enter the element : 7 Enter the element : 8 Enter the element : 9 1

2

3

4

5

6

7

8

9

Enter the number to be searched : 2 Element found at location 1 2

5

Write a program to perform addition , subtraction , multiplication , transpose on matrices. #include<stdio.h> #include void create(int[3][3]); void display(int[3][3]); void add(int[3][3],int[3][3],int[3][3]); void sub(int[3][3],int[3][3],int[3][3]); void mul(int[3][3],int[3][3],int[3][3]); void transpose(int[3][3],int[3][3]); void main() { int matrix1[3][3],matrix2[3][3],matrix3[3][3]; clrscr(); printf(" Enter first matrix \n"); /* Enter the matrices */ create(matrix1); printf(" Enter second matrix \n"); create(matrix2); printf(" First array "); display(matrix1); printf(" Second array "); display(matrix2); add(matrix1,matrix2,matrix3); /* Call to function add */ printf(" Addition "); display(matrix3); sub(matrix1,matrix2,matrix3); /* Call to function sub */ printf(" Subtraction "); display(matrix3); mul(matrix1,matrix2,matrix3); printf(" Multipication "); display(matrix3); printf(" Transpose "); transpose(matrix1,matrix3);

/* Call to function mul */ /* Call to function transpose */

display(matrix3); getch(); } /*creates a matrix*/ void create(int mat[3][3]) 6

{ int i,j; for(i=0;i<=2;i++) { for(j=0;j<=2;j++) { printf(" Enter the element "); scanf("%d",&mat[i][j]); } } }

/* Display matrix*/ void display(int mat[3][3]) { int i,j; for(i=0;i<=2;i++) { for(j=0;j<=2;j++) { printf(" %d",mat[i][j]); printf(" \n"); } } } /*Add matrices*/ void add(int mat1[3][3],int mat2[3][3],int mat3[3][3]) { int i,j; for(i=0;i<=2;i++) { for(j=0;j<=2;j++) { mat3[i][j]=mat1[i][j]+mat2[i][j]; } } } /* Subtract matrices */ void sub(int mat1[3][3],int mat2[3][3],int mat3[3][3]) { int i,j; for(i=0;i<=2;i++) { for(j=0;j<=2;j++)

7

{ mat3[i][j]=mat1[i][j]-mat2[i][j]; } } } /*Multiply matrices */ void mul(int m1[3][3],int m2[3][3],int m3[3][3]) { int i,j,k; for(k=0;k<=2;k++) { for(i=0;i<=2;i++) { m3[k][i]=0; for(j=0;j<=2;j++) m3[k][i]+=m1[k][j]*m2[j][i]; } } } /* Transpose of a matrix */ void transpose(int m1[3][3],int m2[3][3]) { int i,j; for(i=0;i<=2;i++) { for(j=0;j<=2;j++) { m2[i][j]=m1[j][i]; } } }

8

Write a program swap two numbers using call by value and call by reference. #include<stdio.h> #include void swapvalue(int,int); void swapref(int *,int *); void main() { int a=5, b=6; printf(" Before swap "); printf(" a=%d b=%d ",a,b); /* Values before swapping*/ swapvalue(a,b); printf(" Call by value : a=%d b=%d",a,b); swapref(&a,&b); printf(" Call by reference : a=%d b=%d",a,b); getch(); } void swapvalue( int m, int n) /* Function to swap values using values*/ { int temp; temp=n; n=m; m=temp; printf(" m=%d n=%d ",m,n); } void swapref(int *n,int *m) /* Function to swap values using */ { /* reference */ int temp; temp=*n; *n=*m; *m=temp; } Output : Before swap a=5 b=6 Call by value : a=5 b=6

m=6 n=5

9

Call by reference : a=6 b=5

Write a program to implement bubble sort. /*Program to implement bubble sort*/ #include<stdio.h> #include void bsort(int *arr,int n); void main() { int array[7]={5,3,9,6,2,11,1}; /* Initialize array */ int i; clrscr(); printf(" Array before sorting : \n "); for(i=0;i<=6;i++) /* Display array before applying sort */ { printf(" %d ",array[i]); } printf(" \n Array after sorting : \n "); bsort(array,7); /* Call bubble sort function */ getch(); } void bsort(int *arr,int n) { int temp; for(int i=0;iarr[j+1]) { temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; } } } for(i=0;i<=n-1;i++) printf(" %d ",arr[i]); } Output : Array before sorting : Array after sorting :

5 1

/*

3 2

9 3

Interchange consecutive elements */

6 5

2 6

11 1 9 11

10

Write a program to implement insertion sort algorithm. #include<stdio.h> #include void insertion_sort(int *arr,int n) */ { int temp,k; for(int i=1;i<=n-1;i++) { for(int j=0;jarr[i]) { temp=arr[j]; arr[j]=arr[i]; for(k=i;k>j;k--) arr[k]=arr[k-1]; arr[k+1]=temp; } } } for(i=0;i<=4;i++) { printf( "%d ",arr[i]); } }

/* Function to perform insertion sort

/* Shift the elements */

/* Display sorted array */

void main() { int array[5]; clrscr(); for(int i=0;i<=4;i++) { printf(" Enter the element %d ",i); scanf("%d",&array[i]); } printf(" Unsorted array is : " ); for(i=0;i<=4;i++) { printf( "%d ",array[i]); }

11

printf(" Sorted array is : " ); insertion_sort(array,5);

/* Call insertion_sort */

getch(); }

Output : Enter the element 0 : 8 Enter the element 1 : 4 Enter the element 2 : 5 Enter the element 3 : 3 Enter the element 4 : 9 Unsorted array is : 8 4 5 3 9 Sorted array is : 3 4 5 8 9

12

Write a program to implement selection sort. #include<stdio.h> #include void main() { int arr[5]={25,17,31,13,2}; int i,j,temp; clrscr(); printf(“ Selection sort\n”); printf(“\nArray before sorting :\n”); for(i=0;i<=4;i++) printf(“ %d ”,arr[i]); for(i=0;i<=3;i++) { for(j=i+1;j<=4;j++) { if(arr[i]>arr[j]) { temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; } } } printf(“\n Array after sorting :\n”); for(i=0;i<=4;i++) printf(“ %d ” ,arr[i]); getch(); }

/* Display array before sorting*/

/* Interchange the elements */

/* Display array after sorting */

Output : Selection sort Array before sorting : 25 17 31 13 2 Array after sorting : 2

13 17 25 31

13

Write a program to implement a stack using link list #include<stdio.h> #include # include "malloc.h" struct node { int data; struct node *link; }; struct node *top; void main() { void push(int); void display(); int wish, num,will,a; wish = 1; top = NULL; clrscr(); printf("Program for Stack as Linked List demo.."); while(wish == 1) {printf(" Main Menu 1.Enter data in stack 2.Delete from stack "); scanf("%d",&will); switch(will) { case 1: printf("Enter the data"); scanf("%d",&num); push(num); display(); break; case 2: a=pop(); printf("Value returned from top of the stack is %d",a); 14

break; default: printf("Invalid choice"); }

printf("Do you want to continue, press 1"); scanf("%d",&wish); } } void push(int y) { struct node *x; x=malloc(sizeof(struct node)); printf("Address of newly created node x is %d",x); x->data = y; x->link = top; top = x; } void display() { int i =0; struct node * temp; temp = top; while(temp!=NULL) { printf("Item No. %d : Data %d >link); temp=temp->link; } }

Link %d ",i++,temp->data,temp-

/*THIS FUNCTION REMOVES TOP NODE FROM THE STACK AND RETURNS ITS VALUE*/ int pop() { int a; if(top==NULL) {printf("STACK EMPTY..."); return 0;} else { a=top->data; printf("The value returned is %d ",a);

15

free(top); top=top->link;

return (a);

} }

Write a program for Queue implementation through Linked List #include<stdio.h> #include struct node { int data; struct node *link; }; struct node *front, *rear; void main() { int wish,will,a,num; void add(int); wish=1; clrscr(); front=rear=NULL; printf("Program for Queue as Linked List demo.."); while(wish == 1) { printf(" Main Menu 1.Enter data in queue 2.Delete from queue "); scanf("%d",&will); switch(will) { case 1: printf("Enter the data"); scanf("%d",&num); add(num); //display(); break; case 2: a=del(); printf("Value returned from front of the queue is %d",a); break; default:

16

printf("Invalid choice"); }

printf("Do you want to continue, press 1"); scanf("%d",&wish); } getch(); } void add(int y) { struct node *ptr; ptr=malloc(sizeof(struct node)); ptr->data=y; ptr->link=NULL; if(front ==NULL) { front = rear= ptr; } else { rear->link=ptr; rear=ptr; } } int del() { int num; if(front==NULL) { printf(“QUEUE EMPTY"); return(0); } else { num=front->data; front = front->link; printf("Value returned by delete function is %d ",num); return(num); } }

17

Write a program for array implementation of stack. #include <stdio.h> #include # define MAXSIZE 200 int stack[MAXSIZE]; int top; //index pointing to the top of stack void main() { void push(int); int pop(); int will=1,i,num; clrscr(); while(will ==1) { printf(" MAIN MENU: 1.Add element to stack 2.Delete element from the stack "); scanf("%d",&will); switch(will) { case 1: printf("Enter the data... "); scanf("%d",&num); push(num); break; case 2: i=pop(); printf("Value returned from pop function is %d ",i); break; default: printf("Invalid Choice . "); } printf(" Do you want to do more operations on Stack ( 1 for yes, any other key to exit) ");

18

scanf("%d" , &will); }

//end of outer while //end of main

} void push(int y) { if(top>MAXSIZE) { printf("STACK FULL"); return; } else { top++; stack[top]=y; } } int pop() { int a; if(top<=0) { printf("STACK EMPTY"); return 0; } else { a=stack[top]; top--; } return(a); }

19

Write a program of queue implementation using array #include <stdio.h> #include # define MAXSIZE 200 int q[MAXSIZE]; int front, rear; void main() { void add(int); int del(); int will=1,i,num; front =0;rear = 0; clrscr(); printf("Program for queue demonstration through array"); while(will ==1) { printf(" MAIN MENU: 1.Add element to queue 2.Delete element from the queue "); scanf("%d",&will);

other

switch(will) { case 1: printf("Enter the data... "); scanf("%d",&num); add(num); break; case 2: i=del(); printf("Value returned from delete function is %d ",i); break; default: printf("Invalid Choice ... "); } printf(" Do you want to do more operations on Queue ( 1 for yes, any key to exit) "); scanf("%d" , &will); } //end of outer while } //end of main void add(int a)

20

{ if(rear>MAXSIZE) { printf("QUEUE FULL"); return; } else { q[rear]=a; rear++; printf("Value of rear = %d and the value of front is %d",rear,front); } } int del() { int a; if(front == rear) { printf("QUEUE EMPTY"); return(0); } else { a=q[front]; front++; } return(a); }

21

Write a program to search an element in a link list. #include<stdio.h> #include #include<malloc.h> struct linlst { int info; struct link *next; }start, *node; int search(int); void main() { int no,i,item,pos; clrscr(); start.next=NULL; node=&start; printf("How many nodes, you want in linked list? "); scanf("%d",&no); printf(" "); for(i=0;i<no;i++) { node->next=(struct linlst *)malloc(sizeof(struct linlst)); printf("Enter element in node %d: ",i+1); scanf("%d",&node->info); node=node->next; } node->next=NULL; printf("Linked list(only with info field) is:"); node=&start; while(node->next!=NULL) { printf("%d ",node->info); node=node->next; } printf("Enter item to be searched : "); scanf("%d",&item); pos=search(item); if(pos<=no) printf("Your item is at node %d",pos); else printf("Sorry! item is no in linked list.a"); getch();

22

} int search(int item) { int n=1; node=&start; while(node->next!=NULL) { if(node->info==item) break; else n++; node=node->next; } return n; }

23

Write a program to maintain a link list. #include <stdio.h> #include #include /* structure containing a data part and link part */ struct node { int data ; struct node * link ; }; void append ( struct node **, int ) ; void addatbeg ( struct node **, int ) ; void addafter ( struct node *, int, int ) ; void display ( struct node * ) ; int count ( struct node * ) ; void delete ( struct node **, int ) ; void main( ) { struct node *p ; p = NULL ; /* empty linked list */ printf ( "\nNo. of elements in the Linked List = %d", count ( p ) ) ; append ( &p, 14 ) ; append ( &p, 30 ) ; append ( &p, 25 ) ; append ( &p, 42 ) ; append ( &p, 17 ) ; display ( p ) ; addatbeg ( &p, 999 ) ; addatbeg ( &p, 888 ) ; addatbeg ( &p, 777 ) ; display ( p ) ; addafter ( p, 7, 0 ) ; addafter ( p, 2, 1 ) ; addafter ( p, 5, 99 ) ; display ( p ) ; printf ( "\nNo. of elements in the Linked List = %d", count ( p ) ) ;

24

delete ( &p, 99 ) ; delete ( &p, 1 ) ; delete ( &p, 10 ) ; display ( p ) ; printf ( "\nNo. of elements in the Linked List = %d", count ( p ) ) ; } /* adds a node at the end of a linked list */ void append ( struct node **q, int num ) { struct node *temp, *r ; if ( *q == NULL ) /* if the list is empty, create first node */ { temp = malloc ( sizeof ( struct node ) ) ; temp -> data = num ; temp -> link = NULL ; *q = temp ; } else { temp = *q ; /* go to last node */ while ( temp -> link != NULL ) temp = temp -> link ; /* add node at the end */ r = malloc ( sizeof ( struct node ) ) ; r -> data = num ; r -> link = NULL ; temp -> link = r ; } } /* adds a new node at the beginning of the linked list */ void addatbeg ( struct node **q, int num ) { struct node *temp ; /* add new node */ temp = malloc ( sizeof ( struct node ) ) ; temp -> data = num ;

25

temp -> link = *q ; *q = temp ; } /* adds a new node after the specified number of nodes */ void addafter ( struct node *q, int loc, int num ) { struct node *temp, *r ; int i ; temp = q ; /* skip to desired portion */ for ( i = 0 ; i < loc ; i++ ) { temp = temp -> link ; /* if end of linked list is encountered */ if ( temp == NULL ) { printf ( "\nThere are less than %d elements in list", loc ) ; return ; } } /* insert new node */ r = malloc ( sizeof ( struct node ) ) ; r -> data = num ; r -> link = temp -> link ; temp -> link = r ; } /* displays the contents of the linked list */ void display ( struct node *q ) { printf ( "\n" ) ; /* traverse the entire linked list */ while ( q != NULL ) { printf ( "%d ", q -> data ) ; q = q -> link ; } } /* counts the number of nodes present in the linked list */ int count ( struct node * q )

26

{ int c = 0 ; /* traverse the entire linked list */ while ( q != NULL ) { q = q -> link ; c++ ; } return c ; } /* deletes the specified node from the linked list */ void delete ( struct node **q, int num ) { struct node *old, *temp ; temp = *q ; while ( temp != NULL ) { if ( temp -> data == num ) { /* if node to be deleted is the first node in the linked list */ if ( temp == *q ) *q = temp -> link ; /* deletes the intermediate nodes in the linked list */ else old -> link = temp -> link ; /* free the memory occupied by the node */ free ( temp ) ; return ; } else

/* traverse the linked list till the last node is reached */

{ old = temp ; /* old points to the previous node */ temp = temp -> link ; /* go to the next node */ } } printf ( "\nElement %d not found", num ) ; }

27

Write a program to build binary search tree from array. #include <stdio.h> #include #include struct node { struct node *left ; char data ; struct node *right ; }; struct node * buildtree ( int ) ; void inorder ( struct node * ) ; char arr[ ] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', '\0', '\0', 'H' } ; int lc[ ] = { 1, 3, 5, -1, 9, -1, -1, -1, -1, -1 } ; int rc[ ] = { 2, 4, 6, -1, -1, -1, -1, -1, -1, -1 } ; void main( ) { struct node *root ; clrscr( ) ; root = buildtree ( 0 ) ; printf ( “In-order Traversal:\n” ) ; inorder ( root ) ; getch( ) ; } struct node * buildtree ( int index ) { struct node *temp = NULL ; if ( index != -1 ) { temp = ( struct node * ) malloc ( sizeof ( struct node ) ) ; temp -> left = buildtree ( lc[index] ) ; temp -> data = arr[index] ; temp -> right = buildtree ( rc[index] ) ; } return temp ; } void inorder ( struct node *root ) /* In order traversal of tree*/ { if ( root != NULL ) { inorder ( root -> left ) ; printf ( "%c\t", root -> data ) ; inorder ( root -> right );

28

} }

29