CHANDIGARH UNIVERSITY Institute of Distance and Online Learning Course Development Committee Prof. (Dr.) R.S.Bawa Pro Chancellor, Chandigarh University, Gharuan, Punjab Advisors Prof. (Dr.) Bharat Bhushan, Director – IGNOU Prof. (Dr.) Majulika Srivastava, Director – CIQA, IGNOU Programme Coordinators & Editing Team Master of Business Administration (MBA) Bachelor of Business Administration (BBA) Coordinator – Dr. Rupali Arora Coordinator – Dr. Simran Jewandah Master of Computer Applications (MCA) Bachelor of Computer Applications (BCA) Coordinator – Dr. Raju Kumar Coordinator – Dr. Manisha Malhotra Master of Commerce (M.Com.) Bachelor of Commerce (B.Com.) Coordinator – Dr. Aman Jindal Coordinator – Dr. Minakshi Garg Master of Arts (Psychology) Bachelor of Science (Travel &Tourism Management) Coordinator – Dr. Samerjeet Kaur Coordinator – Dr. Shikha Sharma Master of Arts (English) Bachelor of Arts (General) Coordinator – Dr. Ashita Chadha Coordinator – Ms. Neeraj Gohlan Academic and Administrative Management Prof. (Dr.) R. M. Bhagat Prof. (Dr.) S.S. Sehgal Executive Director – Sciences Registrar Prof. (Dr.) Manaswini Acharya Prof. (Dr.) Gurpreet Singh Executive Director – Liberal Arts Director – IDOL © No part of this publication should be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording and/or otherwise without the prior written permission of the authors and the publisher. SLM SPECIALLY PREPARED FOR CU IDOL STUDENTS Printed and Published by: TeamLease Edtech Limited www.teamleaseedtech.com CONTACT NO:- 01133002345 For: CHANDIGARH UNIVERSITY 1 Institute of Distance and Online Learning
DATA STRUCTURES Credit: 1 (Practical) Course Code: BCA136 Course Objectives: • Design and implement appropriate data structures for computation • To perform various operations on different data structures. • To efficiently implement solutions for specific real-life problems. PRACTICAL 1: PROGRAM TO IMPLEMENT SEARCHING AND SORTING. 1. Linear Search Problem: Given an array arr[] of n elements, write a function to search a given element x in arr[]. Examples : Input : arr[] = {10, 20, 80, 30, 60, 50, 110, 100, 130, 170} x = 110; Output : 6 Element x is present at index 6 2
Input : arr[] = {10, 20, 80, 30, 60, 50, 110, 100, 130, 170} x = 175; Output : -1 Element x is not present in arr[]. Program: // C++ program for linear search #include<bits/stdc++.h> using namespace std; void search(vector<int> arr, int search_Element) { int left = 0; int length = arr.size(); int position = -1; int right = length - 1; // Run loop from 0 to right for(left = 0; left <= right;) { // If search_element is found with // left variable if (arr[left] == search_Element) 3
{ position = left; cout << \"Element found in Array at \" << position + 1 << \" Position with \" << left + 1 << \" Attempt\"; break; } // If search_element is found with // right variable if (arr[right] == search_Element) { position = right; cout << \"Element found in Array at \" << position + 1 << \" Position with \" << length - right << \" Attempt\"; break; } left++; right--; } 4
// If element not found if (position == -1) cout << \"Not found in Array with \" << left << \" Attempt\"; } // Driver code int main() { vector<int> arr{ 1, 2, 3, 4, 5 }; int search_element = 5; // Function call search(arr, search_element); } Output: Element found in Array at 5 Position with 1 Attempt 2 Binary Search // C++ program to implement recursive Binary Search #include <bits/stdc++.h> using namespace std; 5
// A recursive binary search function. It returns // location of x in given array arr[l..r] is present, // otherwise -1 int binarySearch(int arr[], int l, int r, int x) { if (r >= l) { int mid = l + (r - l) / 2; // If the element is present at the middle // itself if (arr[mid] == x) return mid; // If element is smaller than mid, then // it can only be present in left subarray if (arr[mid] > x) return binarySearch(arr, l, mid - 1, x); // Else the element can only be present // in right subarray return binarySearch(arr, mid + 1, r, x); } // We reach here when element is not 6
// present in array return -1; } int main(void) { int arr[] = { 2, 3, 4, 10, 40 }; int x = 10; int n = sizeof(arr) / sizeof(arr[0]); int result = binarySearch(arr, 0, n - 1, x); (result == -1) ? cout << \"Element is not present in array\" : cout << \"Element is present at index \" << result; return 0; } OUTPUT: Element is present at index 3 3. Selection Sort // C++ program for implementation of selection sort #include <bits/stdc++.h> using namespace std; void swap(int *xp, int *yp) { int temp = *xp; 7
*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) 8
{ int i; for (i=0; i < size; i++) cout << arr[i] << \" \"; cout << endl; } // 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); cout << \"Sorted array: \\n\"; printArray(arr, n); return 0; } o/p: Sorted array: 11 12 22 25 64 4. Bubble Sort // C++ program for implementation of Bubble sort #include <bits/stdc++.h> 9
using namespace std; void swap(int *xp, int *yp) { int temp = *xp; *xp = *yp; *yp = temp; } // A function to implement bubble sort void bubbleSort(int arr[], int n) { int i, j; for (i = 0; i < n-1; i++) // Last i elements are already in place for (j = 0; j < n-i-1; j++) if (arr[j] > arr[j+1]) swap(&arr[j], &arr[j+1]); } /* Function to print an array */ void printArray(int arr[], int size) { 10
int i; for (i = 0; i < size; i++) cout << arr[i] << \" \"; cout << endl; } // Driver code int main() { int arr[] = {64, 34, 25, 12, 22, 11, 90}; int n = sizeof(arr)/sizeof(arr[0]); bubbleSort(arr, n); cout<<\"Sorted array: \\n\"; printArray(arr, n); return 0; } Output: Sorted array: 11 12 22 25 34 64 90 5. Insertion Sort // C++ program for insertion sort #include <bits/stdc++.h> 11
using namespace std; /* 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 12
void printArray(int arr[], int n) { int i; for (i = 0; i < n; i++) cout << arr[i] << \" \"; cout << endl; } /* Driver code */ 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: 5 6 11 12 13 6. Merge Sort 13
// C++ program for Merge Sort #include <iostream> using namespace std; // 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 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 (int i = 0; i < n1; i++) L[i] = arr[l + i]; for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j]; // Merge the temp arrays back into arr[l..r] // Initial index of first subarray 14
int i = 0; // Initial index of second subarray int j = 0; // Initial index of merged subarray int k = l; 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]; 15
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){ return;//returns recursively } int m =l+ (r-l)/2; mergeSort(arr,l,m); mergeSort(arr,m+1,r); merge(arr,l,m,r); 16
} // UTILITY FUNCTIONS // Function to print an array void printArray(int A[], int size) { for (int i = 0; i < size; i++) cout << A[i] << \" \"; } // Driver code int main() { int arr[] = { 12, 11, 13, 5, 6, 7 }; int arr_size = sizeof(arr) / sizeof(arr[0]); cout << \"Given array is \\n\"; printArray(arr, arr_size); mergeSort(arr, 0, arr_size - 1); cout << \"\\nSorted array is \\n\"; printArray(arr, arr_size); return 0; 17
} OUTPUT Given array is 12 11 13 5 6 7 Sorted array is 5 6 7 11 12 13 18
PRACTICAL 2: PROGRAM TO IMPLEMENT STACKS AND PERFORM VARIOUS OPERATIONS ON IT 1. Program: /* C++ program to implement basic stack operations */ #include <bits/stdc++.h> using namespace std; #define MAX 1000 class Stack { int top; public: int a[MAX]; // Maximum size of Stack Stack() { top = -1; } bool push(int x); int pop(); int peek(); bool isEmpty(); }; 19
bool Stack::push(int x) { if (top >= (MAX - 1)) { cout << \"Stack Overflow\"; return false; } else { a[++top] = x; cout << x << \" pushed into stack\\n\"; return true; } } int Stack::pop() { if (top < 0) { cout << \"Stack Underflow\"; return 0; } else { int x = a[top--]; return x; } 20
} int Stack::peek() { if (top < 0) { cout << \"Stack is Empty\"; return 0; } else { int x = a[top]; return x; } } bool Stack::isEmpty() { return (top < 0); } // Driver program to test above functions int main() { class Stack s; s.push(10); s.push(20); 21
s.push(30); cout << s.pop() << \" Popped from stack\\n\"; //print all elements in stack : cout<<\"Elements present in stack : \"; while(!s.isEmpty()) { // print top element in stack cout<<s.peek()<<\" \"; // remove top element in stack s.pop(); } return 0; } OUTPUT: 10 pushed into stack 20 pushed into stack 30 pushed into stack 30 Popped from stack Top element is : 20 Elements present in stack : 20 10 2. Implementing Stack using Linked List: // C++ program for linked list implementation of stack 22
#include <bits/stdc++.h> using namespace std; // A structure to represent a stack class StackNode { public: int data; StackNode* next; }; StackNode* newNode(int data) { StackNode* stackNode = new StackNode(); stackNode->data = data; stackNode->next = NULL; return stackNode; } int isEmpty(StackNode* root) { return !root; } void push(StackNode** root, int data) 23
{ StackNode* stackNode = newNode(data); stackNode->next = *root; *root = stackNode; cout << data << \" pushed to stack\\n\"; } int pop(StackNode** root) { if (isEmpty(*root)) return INT_MIN; StackNode* temp = *root; *root = (*root)->next; int popped = temp->data; free(temp); return popped; } int peek(StackNode* root) { if (isEmpty(root)) return INT_MIN; return root->data; 24
} // Driver code int main() { StackNode* root = NULL; push(&root, 10); push(&root, 20); push(&root, 30); cout << pop(&root) << \" popped from stack\\n\"; cout << \"Top element is \" << peek(root) << endl; cout<<\"Elements present in stack : \"; //print all elements in stack : while(!isEmpty(root)) { // print top element in stack cout<<peek(root)<<\" \"; // remove top element in stack pop(&root); } 25
return 0; } OUTPUT: 10 pushed to stack 20 pushed to stack 30 pushed to stack 30 popped from stack Top element is 20 Elements present in stack : 20 10 26
PRACTICAL 3: PROGRAM TO IMPLEMENT QUEUES AND PERFORM VARIOUS OPERATIONS ON IT. 1. Program: // CPP program for array // implementation of queue #include <bits/stdc++.h> using namespace std; // A structure to represent a queue class Queue { public: int front, rear, size; unsigned capacity; int* array; }; // function to create a queue // of given capacity. // It initializes size of queue as 0 Queue* createQueue(unsigned capacity) { 27
Queue* queue = new Queue(); queue->capacity = capacity; queue->front = queue->size = 0; // This is important, see the enqueue queue->rear = capacity - 1; queue->array = new int[queue->capacity]; return queue; } // Queue is full when size // becomes equal to the capacity int isFull(Queue* queue) { return (queue->size == queue->capacity); } // Queue is empty when size is 0 int isEmpty(Queue* queue) { return (queue->size == 0); } // Function to add an item to the queue. 28
// It changes rear and size void enqueue(Queue* queue, int item) { if (isFull(queue)) return; queue->rear = (queue->rear + 1) % queue->capacity; queue->array[queue->rear] = item; queue->size = queue->size + 1; cout << item << \" enqueued to queue\\n\"; } // Function to remove an item from queue. // It changes front and size int dequeue(Queue* queue) { if (isEmpty(queue)) return INT_MIN; int item = queue->array[queue->front]; queue->front = (queue->front + 1) % queue->capacity; queue->size = queue->size - 1; return item; } 29
// Function to get front of queue int front(Queue* queue) { if (isEmpty(queue)) return INT_MIN; return queue->array[queue->front]; } // Function to get rear of queue int rear(Queue* queue) { if (isEmpty(queue)) return INT_MIN; return queue->array[queue->rear]; } // Driver code int main() { Queue* queue = createQueue(1000); enqueue(queue, 10); enqueue(queue, 20); 30
enqueue(queue, 30); enqueue(queue, 40); cout << dequeue(queue) << \" dequeued from queue\\n\"; cout << \"Front item is \" << front(queue) << endl; cout << \"Rear item is \" << rear(queue) << endl; return 0; } // OUTPUT: 10 enqueued to queue 20 enqueued to queue 30 enqueued to queue 40 enqueued to queue 10 dequeued from queue Front item is 20 Rear item is 40 31
PRACTICAL 4: WRITE A PROGRAM TO IMPLEMENT CIRCULAR QUEUE 1. Program: // C or C++ program for insertion and // deletion in Circular Queue #include<bits/stdc++.h> using namespace std; struct Queue { // Initialize front and rear int rear, front; // Circular Queue int size; int *arr; Queue(int s) { front = rear = -1; size = s; arr = new int[s]; } 32
void enQueue(int value); int deQueue(); void displayQueue(); }; /* Function to create Circular queue */ void Queue::enQueue(int value) { if ((front == 0 && rear == size-1) || (rear == (front-1)%(size-1))) { printf(\"\\nQueue is Full\"); return; } else if (front == -1) /* Insert First Element */ { front = rear = 0; arr[rear] = value; } else if (rear == size-1 && front != 0) 33
{ rear = 0; arr[rear] = value; } else { rear++; arr[rear] = value; } } // Function to delete element from Circular Queue int Queue::deQueue() { if (front == -1) { printf(\"\\nQueue is Empty\"); return INT_MIN; } int data = arr[front]; arr[front] = -1; if (front == rear) 34
{ front = -1; rear = -1; } else if (front == size-1) front = 0; else front++; return data; } // Function displaying the elements // of Circular Queue void Queue::displayQueue() { if (front == -1) { printf(\"\\nQueue is Empty\"); return; } printf(\"\\nElements in Circular Queue are: \"); if (rear >= front) { 35
for (int i = front; i <= rear; i++) printf(\"%d \",arr[i]); } else { for (int i = front; i < size; i++) printf(\"%d \", arr[i]); for (int i = 0; i <= rear; i++) printf(\"%d \", arr[i]); } } /* Driver of the program */ int main() { Queue q(5); // Inserting elements in Circular Queue q.enQueue(14); q.enQueue(22); q.enQueue(13); q.enQueue(-6); 36
// Display elements present in Circular Queue q.displayQueue(); // Deleting elements from Circular Queue printf(\"\\nDeleted value = %d\", q.deQueue()); printf(\"\\nDeleted value = %d\", q.deQueue()); q.displayQueue(); q.enQueue(9); q.enQueue(20); q.enQueue(5); q.displayQueue(); q.enQueue(20); return 0; } OUTPUT: Elements in Circular Queue are: 14 22 13 -6 Deleted value = 14 Deleted value = 22 Elements in Circular Queue are: 13 -6 Elements in Circular Queue are: 13 -6 9 20 5 37
Queue is Full 38
PRACTICAL 5:.WRITE A PROGRAM TO IMPLEMENT A LINKED LIST. 1. Program: // A simple CPP program to introduce // a linked list #include <bits/stdc++.h> using namespace std; class Node { public: int data; Node* next; }; // Program to create a simple linked // list with 3 nodes int main() { Node* head = NULL; Node* second = NULL; Node* third = NULL; // allocate 3 nodes in the heap 39
head = new Node(); second = new Node(); third = new Node(); /* Three blocks have been allocated dynamically. We have pointers to these three blocks as head, second and third head second third | || | || +---+-----+ +----+----+ +----+----+ |#|#| |#|#| |#|#| +---+-----+ +----+----+ +----+----+ # represents any random value. Data is random because we haven’t assigned anything yet */ head->data = 1; // assign data in first node head->next = second; // Link first node with // the second node /* data has been assigned to the data part of first block (block pointed by the head). And next 40
pointer of the first block points to second. So they both are linked. head second third || | | || +---+---+ +----+----+ +-----+----+ | 1 | o----->| # | # | | # | # | +---+---+ +----+----+ +-----+----+ */ // assign data to second node second->data = 2; // Link second node with the third node second->next = third; /* data has been assigned to the data part of the second block (block pointed by second). And next pointer of the second block points to the third block. So all three blocks are linked. head second third | | | 41
|| | +---+---+ +---+---+ +----+----+ | 1 | o----->| 2 | o-----> | # | # | +---+---+ +---+---+ +----+----+ */ third->data = 3; // assign data to third node third->next = NULL; /* data has been assigned to the data part of the third block (block pointed by third). And next pointer of the third block is made NULL to indicate that the linked list is terminated here. We have the linked list ready. head | | +---+---+ +---+---+ +----+------+ | 1 | o----->| 2 | o-----> | 3 | NULL | +---+---+ +---+---+ +----+------+ Note that only the head is sufficient to represent 42
the whole list. We can traverse the complete list by following the next pointers. */ return 0; } // Linked Traversal List: // A simple C++ program for traversal of a linked list #include <bits/stdc++.h> using namespace std; class Node { public: int data; Node* next; }; // This function prints contents of linked list // starting from the given node void printList(Node* n) { while (n != NULL) { cout << n->data << \" \"; 43
n = n->next; } } // Driver code int main() { Node* head = NULL; Node* second = NULL; Node* third = NULL; // allocate 3 nodes in the heap head = new Node(); second = new Node(); third = new Node(); head->data = 1; // assign data in first node head->next = second; // Link first node with second second->data = 2; // assign data to second node second->next = third; third->data = 3; // assign data to third node third->next = NULL; 44
printList(head); return 0; } // OUTPUT: 123 45
PRACTICAL 6: WRITE A PROGRAM TO IMPLEMENT A DOUBLY LINKED LIST. 1. Program: // A complete working C++ program to demonstrate all // insertion before a given node #include <stdio.h> #include <stdlib.h> // A linked list node struct Node { int data; struct Node* next; struct Node* prev; }; /* Given a reference (pointer to pointer) to the head of a list and an int, inserts a new node on the front of the list. */ void push(struct Node** head_ref, int new_data) { struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); 46
new_node->data = new_data; new_node->next = (*head_ref); new_node->prev = NULL; if ((*head_ref) != NULL) (*head_ref)->prev = new_node; (*head_ref) = new_node; } /* Given a node as next_node, insert a new node before the * given node */ void insertBefore(struct Node** head_ref, struct Node* next_node, int new_data) { /*1. check if the given next_node is NULL */ if (next_node == NULL) { printf(\"the given next node cannot be NULL\"); return; } /* 2. allocate new node */ 47
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); /* 3. put in the data */ new_node->data = new_data; /* 4. Make prev of new node as prev of next_node */ new_node->prev = next_node->prev; /* 5. Make the prev of next_node as new_node */ next_node->prev = new_node; /* 6. Make next_node as next of new_node */ new_node->next = next_node; /* 7. Change next of new_node's previous node */ if (new_node->prev != NULL) new_node->prev->next = new_node; /* 8. If the prev of new_node is NULL, it will be the new head node */ else (*head_ref) = new_node; } 48
// This function prints contents of linked list starting // from the given node void printList(struct Node* node) { struct Node* last; printf(\"\\nTraversal in forward direction \\n\"); while (node != NULL) { printf(\" %d \", node->data); last = node; node = node->next; } printf(\"\\nTraversal in reverse direction \\n\"); while (last != NULL) { printf(\" %d \", last->data); last = last->prev; } } /* Driver program to test above functions*/ int main() { /* Start with the empty list */ struct Node* head = NULL; 49
push(&head, 7); push(&head, 1); push(&head, 4); // Insert 8, before 1. So linked list becomes // 4->8->1->7->NULL insertBefore(&head, head->next, 8); printf(\"Created DLL is: \"); printList(head); getchar(); return 0; } Output: Created DLL is: Traversal in forward direction 4817 Traversal in reverse direction 7184 50
Search
