Data Structure Lab

LAB MANUAL

Electrical Engineering Dept. | EEN 2nd Year | 3rd Semester | ECE

 List of the Experiments

1. Write a program that Implements bubble sort by taking series of

unordered data.
2. Write a program that Implements Quick sort by taking series of
unordered data.
3. Write a program of finding average using array
and by taking user defined values?
4. Write a program using a function to perform the following
operations on singly linked list i) Creation ii)insertion iii)
Deletion iv)Traversal
5. Write a program that implement stack using Arrays.
6. Write a program that implement stack using Link List.
7. Write a program to implement a binary search tree.
8. Write a program to implement a binary search tree.
9. Write a program to perform the operation insert an element
into a binary search tree.
10. Write a program to perform the operation Delete an
element into a binary search tree.
11. Write a program to implement B+trees.
 EXPERIMENT NO.:1

Title:
Write a program that Implements bubble sort by taking series of
unordered data?

Algorithm:
Suppose we are trying to sort the elements in ascending order.
1. First Iteration (Compare and Swap)
i) Starting from the first index, compare the first and the second elements.

ii) If the first element is greater than the second element, they are swapped.

iii) Now, compare the second and the third elements. Swap them if they are not in order.
The above process goes on until the last element.
2. Remaining Iteration
The same process goes on for the remaining iterations.

After each iteration, the largest element among the unsorted elements is placed at the end.

In each iteration, the comparison takes place up to the last unsorted element.

The array is sorted when all the unsorted elements are placed at their correct positions.
Code :
// Bubble sort in C
#include<stdio.h>
#include<conio.h>
void bubbleSort(int array[],int size)
{
for(int step = 0;step<size-1;++step)
{
for(int i = 0;i<size-step-1;++i)
{
if(array[i]>array[i+1]
{
int temp = array[i];
array[i] = array[i+1];
array[i+1] = temp;
}
}
}
}
void printArray(int array[],int size)
{
for(int i = 0;i<size;++i)
{
printf(“%d”,array[i]);
}
printf(“\n”);
}
int main()
{
int data[] ={-2,45,0,11,-9};
int size = sizeof(data)/sizeof(data[0]);
bubbleSort(data,size);
printf(“Sorted array in ascending order:\n”);
 printArray(data,size);
}
Output:
Sorted Array in Ascending Oder:
-9
-2
0
11
45
 EXPERIMENT NO.:2

Title :
Write a program that Implements Quick sort by taking series of
unordered data.

Quick Sort Algorithm:

Quick sort is a sorting algorithm based on the divide and conquer approach where
1. An array is divided into sub arrays by selecting a pivot element (element selected from
the array).
While dividing the array, the pivot element should be positioned in such a way that
elements less than pivot are kept on the left side and elements greater than pivot are on
the right side of the pivot.
2. The left and right sub arrays are also divided using the same approach. This process
continues until each sub array contains a single element.

3. At this point, elements are already sorted. Finally, elements are combined to form a
sorted array.

1. Select the Pivot Element

There are different variations of quicksort where the pivot element is selected from different
positions. Here, we will be selecting the rightmost element of the array as the pivot element.

2. Rearrange the Array

Now the elements of the array are rearranged so that elements that are smaller than
the pivot are put on the left and the elements greater than the pivot are put on the right.

i) A pointer is fixed at the pivot element. The pivot element is compared with the elements
beginning from the first index.

ii) If the element is greater than the pivot element, a second pointer is set for that element.

iii) Now, pivot is compared with other elements. If an element smaller than the pivot element
is reached, the smaller element is swapped with the greater element found earlier.
iv) Again, the process is repeated to set the next greater element as
the second pointer. And, swap it with another smaller element.
v) The process goes on until the second last element is reached.
vi) Finally, the pivot element is swapped with the second pointer.

3. Divide Sub arrays

Pivot elements are again chosen for the left and the right sub-parts separately. And, step
2 is repeated.

The sub arrays are divided until each sub array is formed of a
single element. At this point, the array is already sorted.

Code:
// Quick sort in C
#include <stdio.h>
// function to swap elements
void swap(int *a, int *b)
{
int t = *a;
*a = *b;
*b = t;
}
// function to find the partition position
int partition(int array[], int low, int high)
{
// select the rightmost element as pivot
int pivot = array[high];
// pointer for greater element
int i = (low - 1);
// traverse each element of the array
// compare them with the pivot
for (int j = low; j < high; j++)
{
if (array[j] <= pivot)
{
 // if element smaller than pivot is found
// swap it with the greater element pointed by i
i++;
// swap element at i with element at j
swap(&array[i], &array[j]);
}
}
// swap the pivot element with the greater element at i
swap(&array[i + 1], &array[high]);
// return the partition point
return (i + 1);
}
void quickSort(int array[], int low, int high)
{
if (low < high)
{
// find the pivot element such that
// elements smaller than pivot are on left of pivot
// elements greater than pivot are on right of pivot
int pi = partition(array, low, high);
// recursive call on the left of pivot
quickSort(array, low, pi - 1);
// recursive call on the right of pivot
quickSort(array, pi + 1, high);
}
}
// function to print array elements
void printArray(int array[], int size)
{
for (int i = 0; i < size; ++i)
{
printf("%d ", array[i]);
}
printf("\n");
}
// main function
int main()
{
int data[] = {8, 7, 2, 1, 0, 9, 6};
int n = sizeof(data) / sizeof(data[0]);
printf("Unsorted Array\n");
printArray(data, n);
// perform quicksort on data
quickSort(data, 0, n - 1);
printf("Sorted array in ascending order: \n");
printArray(data, n);
}

Output:
Unsorted Array:
8721096
Sorted array in ascending order:
0126789
 EXPERIMENT NO.:3

Title:
1. Write a program of finding average using array
and by taking user defined values?
Algorithm:
A simple algorithm to understand the usability of array.
1. An array of size 10 is defined initially.
2. User will be asked to get the values from the keyboard.
3. After the value has been received AND average gets calculated on the
basis of given value.
4. Average get s printed on the screen.

Code :
#include <stdio.h>
int main()
{
int marks[10], i, n, sum = 0;
double average;
printf("Enter number of elements: ");
scanf("%d", &n);
for(i=0; i < n; ++i)
{
printf("Enter number%d: ",i+1);
scanf("%d", &marks[i]);
// adding integers entered by the user to the sum variable
sum += marks[i];
}
// explicitly convert sum to double
// then calculate average
average = (double) sum / n;
 printf("Average = %.2lf", average);
return 0;
}
Output:
Enter no Of Elements :
Enter Number1:
Enter Number 2:
.
.
 EXPERIMENT NO.:4

Title :
1. Write a program that implement stack using Arrays?
Algorithm:

Code :
#include<stdio.h>
int stack[100],choice,n,top,x,i;
void push(void);
void pop(void);
void display(void);
int main()
{
top=-1;
printf("\n Enter the size of STACK[MAX=100]:");
scanf("%d",&n);
printf("\n\t STACK OPERATIONS USING ARRAY");
printf("\n\t ");
printf("\n\t 1.PUSH\n\t 2.POP\n\t 3.DISPLAY\n\t 4.EXIT");
do
{
printf("\n Enter the Choice:");
scanf("%d",&choice);
switch(choice)
{
case 1:
{
push();
break;
}
case 2:
{
pop();
 break;
}
case 3:
{
display();
break;
}
case 4:
{
printf("\n\t EXIT POINT ");
break;
}
default:
{
printf ("\n\t Please Enter a Valid Choice(1/2/3/4)");
}
}
}
while(choice!=4);
return 0;
}
void push()
{
if(top>=n-1)
{
printf("\n\tSTACK is over flow");

}
else
{
printf(" Enter a value to be pushed:");
scanf("%d",&x);
top++;
stack[top]=x;
}
}
void pop()
{
if(top<=-1)
{
printf("\n\t Stack is under flow");
}
else
{
printf("\n\t The popped elements is %d",stack[top]);
top--;
}
}
void display()
{
if(top>=0)
{
printf("\n The elements in STACK \n");
for(i=top; i>=0; i--)
printf("\n%d",stack[i]);
printf("\n Press Next Choice");
}
else
{
printf("\n The STACK is empty");
}
}
Output
Enter the size of STACK [MAX=100]:10
STACK OPERATIONS USING ARRAY

1. PUSH
2. POP
3. DISPLAY
4. EXIT
Enter the Choice:1
Enter a value to be pushed:12

Enter the Choice:1

Enter a value to be pushed:24

Enter the Choice:1

Enter a value to be pushed:98

Enter the Choice:3

The elements in STACK
98
24
12

Press Next Choice

Enter the Choice:2
The popped elements is 98

Enter the Choice:3

The elements in STACK
24
12

Press Next Choice

Enter the Choice:4
EXIT POINT
 EXPERIMENT NO.:5

Title : Write a program that implements Linked List?Also define the

following functions and implement using switch case?
void create();
void display();
void insert_begin();
void insert_end();
void insert_pos();
void delete_begin();
void delete_end();
void delete_pos();

Algorithm:
Manually from
yourself.
Code :
#include<stdlib.h>
#include <stdio.h>

void create();
void display();
void insert_begin();
void insert_end();
void insert_pos();
void delete_begin();
void delete_end();
void delete_pos();

struct node
{
int info;
struct node *next;
};
struct node *start=NULL;
int main()
{
int choice;
while(1){

printf("n MENU n");

printf("n 1.Create n");
printf("n 2.Display n");
printf("n 3.Insert at the beginning n");
 printf("n 4.Insert at the end n");
printf("n 5.Insert at specified position n");
printf("n 6.Delete from beginning n");
printf("n 7.Delete from the end n");
printf("n 8.Delete from specified position n");
printf("n 9.Exit n");
printf("n--------------------------------------n");
printf("Enter your choice:t");
scanf("%d",&choice);
switch(choice)
{
case 1:
create();
break;
case 2:
display();
break;
case 3:
insert_begin();
break;
case 4:
insert_end();
break;
case 5:
insert_pos();
break;
case 6:
delete_begin();
break;
case 7:
delete_end();
break;
case 8:
delete_pos();
break;

case 9:
exit(0);
break;

default:
printf("n Wrong Choice:n");
break;
}
}
return 0;
}
void create()
{
struct node *temp,*ptr;
temp=(struct node *)malloc(sizeof(struct node));
if(temp==NULL)
{
printf("nOut of Memory Space:n");
exit(0);
}
 printf("nEnter the data value for the node:t");
scanf("%d",&temp->info);
temp->next=NULL;
if(start==NULL)
{
start=temp;
}
else
{
ptr=start;
while(ptr->next!=NULL)
{
ptr=ptr->next;
}
ptr->next=temp;
}
}
void display()
{
struct node *ptr;
if(start==NULL)
{
printf("nList is empty:n");
return;
}
else
{
ptr=start;
printf("nThe List elements are:n");
while(ptr!=NULL)
{
printf("%dt",ptr->info );
ptr=ptr->next ;
}
}
}
void insert_begin()
{
struct node *temp;
temp=(struct node *)malloc(sizeof(struct node));
if(temp==NULL)
{
printf("nOut of Memory Space:n");
return;
}
printf("nEnter the data value for the node:t" );
scanf("%d",&temp->info);
temp->next =NULL;
if(start==NULL)
{
start=temp;
}
else
{
temp->next=start;
start=temp;
}
}
void insert_end()
{
struct node *temp,*ptr;
temp=(struct node *)malloc(sizeof(struct node));
if(temp==NULL)
{
printf("nOut of Memory Space:n");
return;
}
printf("nEnter the data value for the node:t" );
scanf("%d",&temp->info );
temp->next =NULL;
if(start==NULL)
{
start=temp;
}
else
{
ptr=start;
while(ptr->next !=NULL)
{
ptr=ptr->next ;
}
ptr->next =temp;
}
}
void insert_pos()
{
struct node *ptr,*temp;
int i,pos;
temp=(struct node *)malloc(sizeof(struct node));
if(temp==NULL)
{
printf("nOut of Memory Space:n");
return;
}
printf("nEnter the position for the new node to be inserted:t");
scanf("%d",&pos);
printf("nEnter the data value of the node:t");
scanf("%d",&temp->info) ;

temp->next=NULL;
if(pos==0)
{
temp->next=start;
start=temp;
}
else
{
for(i=0,ptr=start;i<pos-1;i++) { ptr=ptr->next;
if(ptr==NULL)
{
printf("nPosition not found:[Handle with care]n");
return;
}
}
 temp->next =ptr->next ;
ptr->next=temp;
}
}
void delete_begin()
{
struct node *ptr;
if(ptr==NULL)
{
printf("nList is Empty:n");
return;
}
else
{
ptr=start;
start=start->next ;
printf("nThe deleted element is :%dt",ptr->info);
free(ptr);
}
}
void delete_end()
{
struct node *temp,*ptr;
if(start==NULL)
{
printf("nList is Empty:");
exit(0);
}
else if(start->next ==NULL)
{
ptr=start;
start=NULL;
printf("nThe deleted element is:%dt",ptr->info);
free(ptr);
}
else
{
ptr=start;
while(ptr->next!=NULL)
{
temp=ptr;
ptr=ptr->next;
}
temp->next=NULL;
printf("nThe deleted element is:%dt",ptr->info);
free(ptr);
}
}
void delete_pos()
{
int i,pos;
struct node *temp,*ptr;
if(start==NULL)
{
printf("nThe List is Empty:n");
exit(0);
}
 else
{
printf("nEnter the position of the node to be deleted:t");
scanf("%d",&pos);
if(pos==0)
{
ptr=start;
start=start->next ;
printf("nThe deleted element is:%dt",ptr->info );
free(ptr);
}
else
{
ptr=start;
for(i=0;i<pos;i++) { temp=ptr; ptr=ptr->next ;
if(ptr==NULL)
{
printf("nPosition not Found:n");
return;
}
}
temp->next =ptr->next ;
printf("nThe deleted element is:%dt",ptr->info );
free(ptr);
}
}
}

Output: