S.S. & S.

S’s Vidhyadhan Commerce Collage Wade Road Dhule

Class SYBCA Sem: - IV
Subject: - 402 lab on Data Structure
Student
Name:___________________________________________________
Roll Number: -______________________
Practical 1. Write a program to implement Bubble sort
************************************************************************************************
**

#include<iostream>
using namespace std;
int main()
{
int n, i, arr[50], j, temp;
cout<<"Enter the Size (max. 50): ";
cin>>n;
cout<<"Enter "<<n<<" Numbers: ";
for(i=0; i<n; i++)
cin>>arr[i];
cout<<"\nSorting the Array using Bubble Sort Technique..\n";
for(i=0; i<(n-1); i++)
{
for(j=0; j<(n-i-1); j++)
{
if(arr[j]>arr[j+1])
{
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
cout<<"\nArray Sorted Successfully!\n";
cout<<"\nThe New Array is: \n";
for(i=0; i<n; i++)
cout<<arr[i]<<" ";
cout<<endl;
return 0;
}
 Output

#include<iostream>
using namespace std;
int main()
{
int i, arr[10], j, temp;
cout<<"Enter 10 Elements: ";
for(i=0; i<10; i++)
cin>>arr[i];
cout<<endl;
for(i=0; i<9; i++)
{
for(j=0; j<(10-i-1); j++)
{
if(arr[j]>arr[j+1])
{
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
cout<<"Step "<<i+1<<": ";
for(j=0; j<10; j++)
cout<<arr[j]<<" ";
cout<<endl;
}
cout<<endl;
 return 0;
}
 S.S. & S. S’s Vidhyadhan Commerce Collage Wade Road Dhule
Class SYBCA Sem: - IV
Subject: - 402 lab on Data Structure
Student Name:___________________________________________________
Roll Number: -______________________
Practical 2. Write a program to implement Quick sort
**********************************************************************************************
#include<iostream>
using namespace std;
int partition(int arr[], int low, int high)
{
int pivot = arr[high]; // pivot
int i = (low - 1); // Index of smaller element
for (int j = low; j <= high - 1; j++) {
// If current element is smaller than or equal to pivot
if (arr[j] <= pivot) {
i++; // increment index of smaller element
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return (i + 1);
}
// Main function that sorts arr[low..high] using quickSort
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// Utility function to print the array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
// Driver code
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
 cout << "Original array is: \n";
printArray(arr, n);

quickSort(arr, 0, n - 1);

cout << "Sorted array in ascending order is: \n";

printArray(arr, n);
return 0;
}
 S.S. & S. S’s Vidhyadhan Commerce Collage Wade Road Dhule
Class SYBCA Sem: - IV
Subject: - 402 lab on Data Structure
Student Name:___________________________________________________
Roll Number: -______________________
Practical 3. Write a program to implement Selection sort.
*********************************************************************

#include<iostream>
using namespace std;
int main()
{
int tot, arr[50], i, j, temp, small, chk, index;
cout<<"Enter the Size of Array: ";
cin>>tot;
cout<<"Enter "<<tot<<" Array Elements: ";
for(i=0; i<tot; i++)
cin>>arr[i];
for(i=0; i<(tot-1); i++)
{
chk=0;
small = arr[i];
for(j=(i+1); j<tot; j++)
{
if(small>arr[j])
{
small = arr[j];
chk++;
index = j;
}
}
if(chk!=0)
{
temp = arr[i];
arr[i] = small;
arr[index] = temp;
}
}
cout<<"\nSorted Array is:\n";
for(i=0; i<tot; i++)
cout<<arr[i]<<" ";
 cout<<endl;
return 0;
}
 S.S. & S. S’s Vidhyadhan Commerce Collage Wade Road Dhule
Class SYBCA Sem: - IV
Subject: - 402 lab on Data Structure
Student Name:___________________________________________________
Roll Number: -______________________
Practical 4. Write a program to implement Insertion sort.

#include<iostream>
using namespace std;
int main()
{
int arr[50], tot, i, j, k, elem, index;
cout<<"Enter the Size for Array: ";
cin>>tot;
cout<<"Enter "<<tot<<" Array Elements: ";
for(i=0; i<tot; i++)
cin>>arr[i];
for(i=1; i<tot; i++)
{
elem = arr[i];
if(elem<arr[i-1])
{
for(j=0; j<=i; j++)
{
if(elem<arr[j])
{
index = j;
for(k=i; k>j; k--)
arr[k] = arr[k-1];
break;
}
}
}
else
continue;
arr[index] = elem;
cout<<"\nStep "<<i<<": ";
for(j=0; j<tot; j++)
cout<<arr[j]<<" ";
}
cout<<"\n\nThe New Array (Sorted Array):\n";
for(i=0; i<tot; i++)
cout<<arr[i]<<" ";
cout<<endl;
 return 0;
}
 S.S. & S. S’s Vidhyadhan Commerce Collage Wade Road Dhule
Class SYBCA Sem: - IV
Subject: - 402 lab on Data Structure
Student Name:___________________________________________________
Roll Number: -______________________
Practical 5. Write a program to implement linear search.
*********************************************************************
#include <stdio.h>
int main()
{
int a[10], i, item,n;
printf("\nEnter number of elements of an array:\n");
scanf("%d",&n);
printf("\nEnter elements: \n");
for (i=0; i<n; i++)
scanf("%d", &a[i]);
printf("\nEnter item to search: ");
scanf("%d", &item);
for (i=0; i<=9; i++)
if (item == a[i])
{
printf("\nItem found at location %d", i+1);
break;
}
if (i > 9)
printf("\nItem does not exist.");
return 0;
}

Output
 S.S. & S. S’s Vidhyadhan Commerce Collage Wade Road Dhule
Class SYBCA Sem: - IV
Subject: - 402 lab on Data Structure
Student Name:___________________________________________________
Roll Number: -______________________
Practical 6. Write a program to implement Binary search.
*********************************************************************

#include<iostream>
using namespace std;
int main()
{
int i, arr[10], num, first, last, middle;
cout<<"Enter 10 Elements (in ascending order): ";
for(i=0; i<10; i++)
cin>>arr[i];
cout<<"\nEnter Element to be Search: ";
cin>>num;
first = 0;
last = 9;
middle = (first+last)/2;
while(first <= last)
{
if(arr[middle]<num)
first = middle+1;
else if(arr[middle]==num)
{
cout<<"\nThe number, "<<num<<" found at Position "<<middle+1;
break;
}
else
last = middle-1;
middle = (first+last)/2;
}
if(first>last)
cout<<"\nThe number, "<<num<<" is not found in given Array";
cout<<endl;
return 0;
}
 S.S. & S. S’s Vidhyadhan Commerce Collage Wade Road Dhule
Class SYBCA Sem: - IV
Subject: - 402 lab on Data Structure
Student Name:___________________________________________________
Roll Number: -______________________
Practical 7. Write a program to implement Stack operations: push, pop, display
*********************************************************************
#include <iostream>
#define SIZE 5
using namespace std;
class STACK {
private:
int num[SIZE];
int top;

public:
STACK(); //defualt constructor
int push(int);
int pop();
int isEmpty();
int isFull();
void displayItems();
};
STACK::STACK()
{
top = -1;
}
int STACK::isEmpty()
{
if (top == -1)
return 1;
else
return 0;
}
int STACK::isFull()
{
if (top == (SIZE - 1))
return 1;
else
return 0;
int STACK::push(int n)
{
//check stack is full or not
if (isFull()) {
return 0;
}
++top;
num[top] = n;
return n;
}
int STACK::pop()
{
//to store and print which number
//is deleted
int temp;
//check for empty
if (isEmpty())
return 0;
temp = num[top];
--top;
return temp;
}
void STACK::displayItems()
{
int i; //for loop
cout << "STACK is: ";
for (i = (top); i >= 0; i--)
cout << num[i] << " ";
cout << endl;
}
// Main code
int main()
{
//declare object
STACK stk;
int choice, n, temp;

do {
cout << endl;
cout << "0 - Exit." << endl;
cout << "1 - Push Item." << endl;
cout << "2 - Pop Item." << endl;
cout << "3 - Display Items (Print STACK)." << endl;
 cout << "Enter your choice: ";
cin >> choice;

switch (choice) {
case 0:
break;
case 1:
cout << "Enter item to insert: ";
cin >> n;
temp = stk.push(n);
if (temp == 0)
cout << "STACK is FULL." << endl;
else
cout << temp << " inserted." << endl;
break;

case 2:
temp = stk.pop();
if (temp == 0)
cout << "STACK IS EMPTY." << endl;
else
cout << temp << " is removed (popped)." << endl;
break;
case 3:
stk.displayItems();
break;
default:
cout << "An Invalid choice." << endl;
}
} while (choice != 0);
return 0;
}
 S.S. & S. S’s Vidhyadhan Commerce Collage Wade Road Dhule
Class SYBCA Sem: - IV
Subject: - 402 lab on Data Structure
Student Name:___________________________________________________
Roll Number: -______________________
Practical 8. Write a program to implement Linear Queue operations: Insert, Delete,
Display
*********************************************************************
// C++ Program to implement a queue using array
#include <iostream>
using namespace std;
// defining the max size of the queue
#define MAX_SIZE 100
// Implement the queue data structure
class Queue {
public:
int front;
int rear;
int arr[MAX_SIZE];
// initializing pointers in the constructor
Queue(): front(-1), rear(-1) {}
// Function to check if the queue is empty or not
bool isEmpty() { return front == -1 || front > rear; }
// Function to check if the queue is full or not
bool isFull() { return rear == MAX_SIZE - 1; }
// Function to get the front element of the queue
int getFront()
{
if (isEmpty()) {
cout << "Queue is empty" << endl;
return -1;
}
return arr[front];
}

// Function to get the rear element of the queue

int getRear()
{
if (isEmpty()) {
cout << "Queue is empty" << endl;
 return -1;
}
return arr[rear];

// Function to enqueue elements from the queue

void enqueue(int val)
{
// Check overflow condition
if (isFull()) {
cout << "Queue is full" << endl;
return;
}
// if queue is empty, set front to 0
if (isEmpty())
front = 0;
rear++;
arr[rear] = val;
}

// Function to dequeue elements from the queue

int dequeue()
{
// Check underflow condition
if (isEmpty()) {
cout << "Queue is empty" << endl;
return -1;
}
int ans = arr[front];
front++;
// if queue becomes empty, reset both pointers
if (isEmpty())
front = rear = -1;
return ans;
}
// Display function to print the queue
void display()
{
if (isEmpty()) {
cout << "Queue is empty" << endl;
return;
}
cout << "Queue: ";
for (int i = front; i <= rear; i++) {
 cout << arr[i] << " ";
}
cout << endl;
}
};
int main()
{
// Created Queue of size 5
Queue q;
// Enqueueing elements
q.enqueue(1);
q.enqueue(2);
q.enqueue(3);
// Displaying status of the queue after enqueuing
cout << "\nAfter Enqueueing:" << endl;
cout << "Front element: " << q.getFront() << endl;
cout << "Rear element: " << q.getRear() << endl;
q.display();
// Enqueueing more elements
q.enqueue(4);
q.enqueue(5);
// Displaying the updated queue
q.display();
// Enqueueing one more element to demonstrate overflow
// condition
q.enqueue(6);
// Dequeueing elements
cout << "\nDequeueing elements:" << endl;
cout << "Dequeued element: " << q.dequeue() << endl;
cout << "Dequeued element: " << q.dequeue() << endl;
// Displaying status of the queue after dequeueing
cout << "\nAfter Dequeueing:" << endl;
cout << "Front element: " << q.getFront() << endl;
cout << "Rear element: " << q.getRear() << endl;
q.display();
return 0;
}
 S.S. & S. S’s Vidhyadhan Commerce Collage Wade Road Dhule
Class SYBCA Sem: - IV
Subject: - 402 lab on Data Structure
Student Name:___________________________________________________
Roll Number: -______________________
Practical 8. Write a program to implement Linear Queue operations: Insert, Delete,
Display
*********************************************************************

// Linked list operations in C++

#include <stdlib.h>

#include <iostream>
using namespace std;

// Create a node
struct Node {
int data;
struct Node* next;
};

void insertAtBeginning(struct Node** head_ref, int new_data) {

// Allocate memory to a node
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

// insert the data

new_node->data = new_data;
new_node->next = (*head_ref);

// Move head to new node

(*head_ref) = new_node;
}

// Insert a node after a node

void insertAfter(struct Node* prev_node, int new_data) {
if (prev_node == NULL) {
cout << "the given previous node cannot be NULL";
return;
}
 struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = prev_node->next;
prev_node->next = new_node;
}

// Insert at the end

void insertAtEnd(struct Node** head_ref, int new_data) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
struct Node* last = *head_ref; /* used in step 5*/

new_node->data = new_data;
new_node->next = NULL;

if (*head_ref == NULL) {
*head_ref = new_node;
return;
}

while (last->next != NULL) last = last->next;

last->next = new_node;
return;
}

// Delete a node
void deleteNode(struct Node** head_ref, int key) {
struct Node *temp = *head_ref, *prev;

if (temp != NULL && temp->data == key) {

*head_ref = temp->next;
free(temp);
return;
}
// Find the key to be deleted
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}

// If the key is not present

if (temp == NULL) return;
 // Remove the node
prev->next = temp->next;

free(temp);
}

// Search a node
bool searchNode(struct Node** head_ref, int key) {
struct Node* current = *head_ref;

while (current != NULL) {

if (current->data == key) return true;
current = current->next;
}
return false;
}

// Sort the linked list

void sortLinkedList(struct Node** head_ref) {
struct Node *current = *head_ref, *index = NULL;
int temp;

if (head_ref == NULL) {
return;
} else {
while (current != NULL) {
// index points to the node next to current
index = current->next;

while (index != NULL) {

if (current->data > index->data) {
temp = current->data;
current->data = index->data;
index->data = temp;
}
index = index->next;
}
current = current->next;
}
}
}
// Print the linked list
void printList(struct Node* node) {
while (node != NULL) {
cout << node->data << " ";
node = node->next;
}
}

// Driver program
int main() {
struct Node* head = NULL;

insertAtEnd(&head, 1);
insertAtBeginning(&head, 2);
insertAtBeginning(&head, 3);
insertAtEnd(&head, 4);
insertAfter(head->next, 5);

cout << "Linked list: ";

printList(head);

cout << "\nAfter deleting an element: ";

deleteNode(&head, 3);
printList(head);

int item_to_find = 3;
if (searchNode(&head, item_to_find)) {
cout << endl << item_to_find << " is found";
} else {
cout << endl << item_to_find << " is not found";
}

sortLinkedList(&head);
cout << "\nSorted List: ";
printList(head);
}