Scribd
Upload
13 views22 pages

Lab Manual for Data Structures Course

The document is a lab manual for the City College of Management and Science, detailing mandatory instructions for students before entering the lab, including required materials and attendance policies. It outlines various programming tasks related to data structures such as arrays, linked lists, stacks, and queues, along with code examples for each task. The manual emphasizes the importance of following lab protocols and maintaining cleanliness in the lab environment.

Uploaded by

ccmasacademic
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
13 views22 pages

Lab Manual for Data Structures Course

The document is a lab manual for the City College of Management and Science, detailing mandatory instructions for students before entering the lab, including required materials and attendance policies. It outlines various programming tasks related to data structures such as arrays, linked lists, stacks, and queues, along with code examples for each task. The manual emphasizes the importance of following lab protocols and maintaining cleanliness in the lab environment.

Uploaded by

ccmasacademic
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

CITY COLLEGE OF MANAGEMENT AND SCIENCE

SAI PRIYA NAGAR, 3RD LANE, RAYAGADA-765001

LAB MANUAL

LAB NAME: ______________________________________________________

LAB CODE______________________________________________________
YEAR_________________________ SEMESTER______________________

Name of Faculty______________________________________________________________

INSTRUCTIONS TO STUDENTS
Before entering the lab the student should carry the following things (MANDATORY)
1. Identity card issued by the college.
2. Class notes
3. Lab observation book
4. Lab Manual
5. Lab Record
 Student must sign in and sign out in the register provided when attending the lab session without fail.
 Come to the laboratory in time. Students, who are late more than 15 min., will not be allowed to
attend the lab.
 Students need to maintain 100% attendance in lab if not a strict action will be taken.
 All students must follow a Dress Code while in the laboratory
 All bags must be left at the indicated place.
 Refer to the lab staff if you need any help in using the lab.
 Respect the laboratory and its other users.
 Workspace must be kept clean and tidy after experiment is completed.
 Read the Manual carefully before coming to the laboratory and be sure about what you are supposed
to do. Do the experiments as per the instructions given in the manual.
 Copy all the programs to observation which are taught in class before attending the lab session.
 Students are not supposed to use floppy disks, pen drives without permission of lab- in charge.
 Lab records need to be submitted on or before the date of submission.

CONTENTS
1. To insert and delete elements from appropriate position in an array.
2. To search an element and print the total time of occurrence in the array.
3. To delete all occurrence of an element in an array.
4. Array implementation of Stack.
5. Array implementation of Linear Queue.
6. Array implementation of Circular Queue.
7. To implement linear linked list and perform different operation such as node
insert and delete, search of an item, reverse the list.
8. To implement circular linked list and perform different operation such as node
insert and delete.
9. To implement double linked list and perform different operation such as node
insert and delete.
10. Linked list implementation of Stack.
11. Linked list implementation of Queue.
12. Polynomial representation using linked list.
13. To implement a Binary Search Tree.
14. To represent a Sparse Matrix.
15. To perform binary search operation.
16. To perform Bubble sort.
17. To perform Selection sort.
18. To perform Insertion sort.
19. To perform Quick sort.
20. To perform Merge sort.

1. Insert and Delete Elements in an Array


#include <stdio.h>

void insert(int arr[], int *n, int pos, int val) {


for (int i = *n; i > pos; i--)
arr[i] = arr[i - 1];
arr[pos] = val;
(*n)++;
}

void delete(int arr[], int *n, int pos) {


for (int i = pos; i < *n - 1; i++)
arr[i] = arr[i + 1];
(*n)--;
}

void display(int arr[], int n) {


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

int main() {
int arr[50] = {10, 20, 30, 40, 50};
int n = 5;

printf("Original Array: ");


display(arr, n);

insert(arr, &n, 2, 99);


printf("After Insertion at pos 2: ");
display(arr, n);

delete(arr, &n, 4);


printf("After Deletion at pos 4: ");
display(arr, n);

return 0;
}

2. Search an Element and Print Total Occurrences


#include <stdio.h>

int main() {
int arr[] = {5, 3, 7, 5, 2, 5, 9};
int n = 7, key, count = 0;

printf("Enter element to search: ");


scanf("%d", &key);

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


if (arr[i] == key) count++;

if (count > 0)
printf("%d found %d times\n", key, count);
else
printf("%d not found\n", key);

return 0;
}

3. Delete All Occurrences of an Element


#include <stdio.h>

int main() {
int arr[50] = {5, 2, 7, 2, 9, 2, 1};
int n = 7, key;

printf("Enter element to delete: ");


scanf("%d", &key);

int j = 0;
for (int i = 0; i < n; i++) {
if (arr[i] != key)
arr[j++] = arr[i];
}
n = j;

printf("Array after deletion: ");


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

return 0;
}

Array Implementation of Stack (4)


#include <stdio.h>
#define MAX 5

int stack[MAX], top = -1;

void push(int val) {


if (top == MAX - 1)
printf("Stack Overflow\n");
else
stack[++top] = val;
}

void pop() {
if (top == -1)
printf("Stack Underflow\n");
else
printf("Popped: %d\n", stack[top--]);
}

void display() {
if (top == -1) {
printf("Stack is Empty\n");
return;
}
printf("Stack elements: ");
for (int i = top; i >= 0; i--)
printf("%d ", stack[i]);
printf("\n");
}

int main() {
push(10);
push(20);
push(30);
display();

pop();
display();

return 0;
}

Array Implementation of Linear Queue (5)


#include <stdio.h>
#define MAX 5
int queue[MAX], front = -1, rear = -1;

void enqueue(int val) {


if (rear == MAX - 1)
printf("Queue Overflow\n");
else {
if (front == -1) front = 0;
queue[++rear] = val;
}
}

void dequeue() {
if (front == -1 || front > rear)
printf("Queue Underflow\n");
else
printf("Dequeued: %d\n", queue[front++]);
}

void display() {
if (front == -1 || front > rear) {
printf("Queue is Empty\n");
return;
}
printf("Queue elements: ");
for (int i = front; i <= rear; i++)
printf("%d ", queue[i]);
printf("\n");
}

int main() {
enqueue(10);
enqueue(20);
enqueue(30);
display();

dequeue();
display();

return 0;
}

Array Implementation of Circular Queue (6)


#include <stdio.h>
#define MAX 5
int cqueue[MAX], front = -1, rear = -1;

void enqueue(int val) {


if ((rear + 1) % MAX == front)
printf("Circular Queue Overflow\n");
else {
if (front == -1) front = 0;
rear = (rear + 1) % MAX;
cqueue[rear] = val;
}
}

void dequeue() {
if (front == -1)
printf("Circular Queue Underflow\n");
else {
printf("Dequeued: %d\n", cqueue[front]);
if (front == rear)
front = rear = -1;
else
front = (front + 1) % MAX;
}
}

void display() {
if (front == -1) {
printf("Circular Queue is Empty\n");
return;
}
printf("Circular Queue elements: ");
int i = front;
while (1) {
printf("%d ", cqueue[i]);
if (i == rear) break;
i = (i + 1) % MAX;
}
printf("\n");
}

int main() {
enqueue(10);
enqueue(20);
enqueue(30);
enqueue(40);
display();

dequeue();
display();

enqueue(50);
display();

return 0;
}
7. Linear Linked List (Insert, Delete, Search, Reverse)
#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node *next;
};

struct Node* head = NULL;


void insert(int val) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = val;
newNode->next = head;
head = newNode;
}

void delete(int key) {


struct Node *temp = head, *prev = NULL;
if (temp != NULL && temp->data == key) {
head = temp->next;
free(temp);
return;
}
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}
if (temp == NULL) return;
prev->next = temp->next;
free(temp);
}

void search(int key) {


struct Node* temp = head;
while (temp != NULL) {
if (temp->data == key) {
printf("%d Found!\n", key);
return;
}
temp = temp->next;
}
printf("%d Not Found\n", key);
}

void reverse() {
struct Node *prev = NULL, *curr = head, *next = NULL;
while (curr != NULL) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
head = prev;
}

void display() {
struct Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}

int main() {
insert(10);
insert(20);
insert(30);
display();

search(20);
delete(20);
display();
reverse();
printf("Reversed List: ");
display();

return 0;
}
8. Circular Linked List (Insert, Delete)
#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node *next;
};
struct Node *last = NULL;
void insert(int val) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = val;
if (last == NULL) {
last = newNode;
last->next = last;
} else {
newNode->next = last->next;
last->next = newNode;
last = newNode;
}
}

void delete(int key) {


if (last == NULL) return;

struct Node *temp = last->next, *prev = last;


do {
if (temp->data == key) {
if (temp == last && temp->next == last) {
free(temp);
last = NULL;
return;
}
if (temp == last->next) last->next = temp->next;
if (temp == last) last = prev;
prev->next = temp->next;
free(temp);
return;
}
prev = temp;
temp = temp->next;
} while (temp != last->next);
}

void display() {
if (last == NULL) {
printf("List is Empty\n");
return;
}
struct Node *temp = last->next;
do {
printf("%d -> ", temp->data);
temp = temp->next;
} while (temp != last->next);
printf("(back to start)\n");
}
int main() {
insert(10);
insert(20);
insert(30);
display();
delete(20);
display();
return 0;
}

9. Doubly Linked List (Insert, Delete)


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

struct Node {
int data;
struct Node *prev, *next;
};

struct Node *head = NULL;

void insert(int val) {


struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = val;
newNode->prev = NULL;
newNode->next = head;
if (head != NULL) head->prev = newNode;
head = newNode;
}

void delete(int key) {


struct Node* temp = head;
while (temp != NULL && temp->data != key)
temp = temp->next;
if (temp == NULL) return;
if (temp->prev != NULL) temp->prev->next = temp->next;
else head = temp->next;
if (temp->next != NULL) temp->next->prev = temp->prev;
free(temp);
}

void display() {
struct Node* temp = head;
while (temp != NULL) {
printf("%d <-> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}

int main() {
insert(10);
insert(20);
insert(30);
display();

delete(20);
display();

return 0;
}
10. Stack using Linked List
#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node* next;
};

struct Node* top = NULL;

void push(int val) {


struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = val;
newNode->next = top;
top = newNode;
}

void pop() {
if (top == NULL) {
printf("Stack Underflow\n");
return;
}
struct Node* temp = top;
printf("Popped: %d\n", top->data);
top = top->next;
free(temp);
}

void display() {
struct Node* temp = top;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}

int main() {
push(10);
push(20);
push(30);
display();

pop();
display();

return 0;
}
11. Queue using Linked List
#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node* next;
};

struct Node *front = NULL, *rear = NULL;

void enqueue(int val) {


struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = val;
newNode->next = NULL;
if (rear == NULL) {
front = rear = newNode;
return;
}
rear->next = newNode;
rear = newNode;
}

void dequeue() {
if (front == NULL) {
printf("Queue Underflow\n");
return;
}
struct Node* temp = front;
printf("Dequeued: %d\n", front->data);
front = front->next;
if (front == NULL) rear = NULL;
free(temp);
}

void display() {
struct Node* temp = front;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}

int main() {
enqueue(10);
enqueue(20);
enqueue(30);
display();

dequeue();
display();

return 0;
}
12. Polynomial Representation using Linked List
#include <stdio.h>
#include <stdlib.h>

struct Node {
int coeff, pow;
struct Node* next;
};

struct Node* head = NULL;

void insert(int c, int p) {


struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->coeff = c;
newNode->pow = p;
newNode->next = head;
head = newNode;
}

void display() {
struct Node* temp = head;
while (temp != NULL) {
printf("%dx^%d", temp->coeff, temp->pow);
temp = temp->next;
if (temp != NULL) printf(" + ");
}
printf("\n");
}

int main() {
insert(3, 2);
insert(4, 1);
insert(5, 0);

printf("Polynomial: ");
display();

return 0;
}
13. Binary Search Tree (Insert, Traversals)
#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node *left, *right;
};

struct Node* newNode(int val) {


struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->data = val;
node->left = node->right = NULL;
return node;
}

struct Node* insert(struct Node* root, int val) {


if (root == NULL) return newNode(val);
if (val < root->data) root->left = insert(root->left, val);
else if (val > root->data) root->right = insert(root->right, val);
return root;
}

void inorder(struct Node* root) {


if (root != NULL) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}

int main() {
struct Node* root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 70);
insert(root, 20);
insert(root, 40);

printf("Inorder Traversal: ");


inorder(root);
return 0;
}
14. Sparse Matrix Representation
#include <stdio.h>

int main() {
int rows, cols;
printf("Enter rows and columns: ");
scanf("%d %d", &rows, &cols);

int mat[rows][cols];
printf("Enter matrix:\n");
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++)
scanf("%d", &mat[i][j]);

printf("\nSparse Matrix Representation (row, col, value):\n");


for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (mat[i][j] != 0)
printf("%d %d %d\n", i, j, mat[i][j]);
}
}
return 0;
}
15. Binary Search
#include <stdio.h>

int binarySearch(int arr[], int n, int key) {


int low = 0, high = n - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == key) return mid;
else if (arr[mid] < key) low = mid + 1;
else high = mid - 1;
}
return -1;
}

int main() {
int arr[] = {10, 20, 30, 40, 50};
int n = 5, key;
printf("Enter element to search: ");
scanf("%d", &key);

int pos = binarySearch(arr, n, key);


if (pos != -1) printf("Element found at index %d\n", pos);
else printf("Element not found\n");

return 0;
}
16. Bubble Sort
#include <stdio.h>

void bubbleSort(int arr[], int n) {


for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}

int main() {
int arr[] = {64, 34, 25, 12, 22};
int n = 5;
bubbleSort(arr, n);

printf("Sorted array: ");


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

17. Selection Sort


#include <stdio.h>

void selectionSort(int arr[], int n) {


for (int i = 0; i < n - 1; i++) {
int min = i;
for (int j = i + 1; j < n; j++)
if (arr[j] < arr[min]) min = j;

int temp = arr[min];


arr[min] = arr[i];
arr[i] = temp;
}
}

int main() {
int arr[] = {29, 10, 14, 37, 13};
int n = 5;
selectionSort(arr, n);

printf("Sorted array: ");


for (int i = 0; i < n; i++) printf("%d ", arr[i]);
return 0;
}
18. Insertion Sort
#include <stdio.h>

void insertionSort(int arr[], int n) {


for (int i = 1; i < n; i++) {
int key = arr[i], j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}

int main() {
int arr[] = {12, 11, 13, 5, 6};
int n = 5;
insertionSort(arr, n);

printf("Sorted array: ");


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

19. Quick Sort


#include <stdio.h>

void swap(int* a, int* b) {


int t = *a;
*a = *b;
*b = t;
}

int partition(int arr[], int low, int high) {


int pivot = arr[high], i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return i + 1;
}
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);
}
}
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = 6;
quickSort(arr, 0, n - 1);

printf("Sorted array: ");


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

20. Merge Sort


#include <stdio.h>

void merge(int arr[], int l, int m, int r) {


int n1 = m - l + 1, n2 = r - m;
int L[n1], R[n2];

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];

int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) arr[k++] = L[i++];
else arr[k++] = R[j++];
}
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}

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


if (l < r) {
int m = (l + r) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}

int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = 6;
mergeSort(arr, 0, n - 1);

printf("Sorted array: ");


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

You might also like