Scribd
Upload
20 views13 pages

DSA Lab

The document contains a series of C programming examples covering various data structures and algorithms, including array manipulations, stack and queue operations, linked lists, sorting algorithms, and recursion. Each section provides code snippets along with expected output, demonstrating practical implementations of these concepts. Topics include 2D and 3D arrays, polynomial addition, infix to postfix conversion, and different types of linked lists.

Uploaded by

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

DSA Lab

The document contains a series of C programming examples covering various data structures and algorithms, including array manipulations, stack and queue operations, linked lists, sorting algorithms, and recursion. Each section provides code snippets along with expected output, demonstrating practical implementations of these concepts. Topics include 2D and 3D arrays, polynomial addition, infix to postfix conversion, and different types of linked lists.

Uploaded by

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

DSA Lab Copy

1. 2D and 3D Arrays Creation


#include <stdio.h>
int main() {
int arr2D[2][2] = {{1, 2}, {3, 4}};
int arr3D[2][2][2] = {{{1, 2}, {3, 4}}, {{5, 6}, {7, 8}}};

printf("2D Array:\n%d %d\n%d %d\n", arr2D[0][0], arr2D[0][1], arr2D[1][0], arr2D[1][1]);


printf("3D Array First Layer:\n%d %d\n%d %d\n", arr3D[0][0][0], arr3D[0][0][1],
arr3D[0][1][0], arr3D[0][1][1]);

return 0;
}
Output:

EN
2D Array:
12
34
3D Array First Layer:

K
12
34
IC
2. Merge Two 3D Arrays
H
#include <stdio.h>
int main() {
C

int a[1][1][1] = {{{1}}}, b[1][1][1] = {{{2}}}, c[2][1][1];


G

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


for (int j = 0; j < 1; j++)
N

for (int k = 0; k < 1; k++)


c[i][j][k] = a[i][j][k];
YI

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


FL

for (int j = 0; j < 1; j++)


for (int k = 0; k < 1; k++)
c[i + 1][j][k] = b[i][j][k];

printf("Merged 3D Array: %d %d\n", c[0][0][0], c[1][0][0]);

return 0;
}
Output:
Merged 3D Array: 1 2
3. Create 3D Array Using Nested Loops
#include <stdio.h>
int main() {
int arr[2][2][2];
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
for (int k = 0; k < 2; k++)
arr[i][j][k] = i + j + k;

printf("3D Array Element: %d\n", arr[1][1][1]);

return 0;
}
Output:
3D Array Element: 3
4. Polynomial Addition
#include <stdio.h>
void addPolynomials(int a[], int b[], int sum[], int n) {
for (int i = 0; i < n; i++)

EN
sum[i] = a[i] + b[i];
}

int main() {

K
int a[] = {1, 2, 3}, b[] = {4, 5, 6}, sum[3];
addPolynomials(a, b, sum, 3);
IC
printf("Sum of polynomials: %d %d %d\n", sum[0], sum[1], sum[2]);
H

return 0;
C

}
Output:
G

Sum of polynomials: 5 7 9
5. Stack Push and Pop Operations
N

#include <stdio.h>
#define MAX_SIZE 10
YI

int stack[MAX_SIZE], top = -1;


FL

void push(int val) {


if (top == MAX_SIZE - 1) {
printf("Stack Overflow!\n");
return;
}
stack[++top] = val;
}

void pop() {
if (top == -1) {
printf("Stack Underflow!\n");
return;
}
top--;
}

int main() {
push(10);
push(20);
pop();
printf("Stack top after operations: %d\n", stack[top]);

return 0;
}
Output:
Stack top after operations: 10
6. Queue Implementation (Array)
#include <stdio.h>
#define MAX_SIZE 10

EN
int queue[MAX_SIZE], front = -1, rear = -1;

void enqueue(int val) {

K
if (rear == MAX_SIZE - 1) {
printf("Queue Overflow!\n");
IC
return;
}
H
if (front == -1) front = 0;
queue[++rear] = val;
C

}
G

void dequeue() {
if (front == -1 || front > rear) {
N

printf("Queue Underflow!\n");
return;
YI

}
front++;
FL

int main() {
enqueue(10);
enqueue(20);
dequeue();
printf("Front element after operations: %d\n", queue[front]);

return 0;
}
Output:
Front element after operations: 20
7. Queue Using Key Module
// Not applicable in C; use array or linked list implementations.
8. Array Operations (Sum, Max)
#include <stdio.h>
int main() {
int n, sum = 0, max;

printf("Enter number of elements: ");


scanf("%d", &n);

int arr[n];
printf("Enter elements: ");
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
sum += arr[i];
}

max = arr[0];

EN
for (int i = 1; i < n; i++)
if (arr[i] > max) max = arr[i];

printf("Sum: %d, Max: %d\n", sum, max);

K
return 0;
IC
}
Output:
H
Enter number of elements: 2
Enter elements: 1 2
C

Sum: 3, Max: 2
9. Infix to Postfix Conversion
G

#include <stdio.h>
#include <ctype.h>
N

#include <string.h>
#define MAX_SIZE 100
YI

char stack[MAX_SIZE];
FL

int top = -1;

void push(char c) {
if (top == MAX_SIZE - 1) {
printf("Stack Overflow!\n");
return;
}
stack[++top] = c;
}

char pop() {
if (top == -1) {
printf("Stack Underflow!\n");
return '\0';
}
return stack[top--];
}

int precedence(char c) {
if (c == '^') return 3;
if (c == '*' || c == '/') return 2;
if (c == '+' || c == '-') return 1;
return 0;
}

void infixToPostfix(char *infix, char *postfix) {


int i = 0, j = 0;
while (infix[i] != '\0') {
if (isalnum(infix[i])) postfix[j++] = infix[i];
else if (infix[i] == '(') push(infix[i]);

EN
else if (infix[i] == ')') {
while (stack[top] != '(') postfix[j++] = pop();
pop();
} else {

K
while (top != -1 && precedence(stack[top]) >= precedence(infix[i]))
postfix[j++] = pop();
IC
push(infix[i]);
}
H
i++;
C

}
while (top != -1) postfix[j++] = pop();
postfix[j] = '\0';
G

}
N

int main() {
char infix[MAX_SIZE], postfix[MAX_SIZE];
YI

printf("Enter infix expression: ");


scanf("%s", infix);
FL

infixToPostfix(infix, postfix);
printf("Postfix expression: %s\n", postfix);

return 0;
}
Output:
Enter infix expression: a+b*(c^d-e)^(f+g*h)-i
Postfix expression: abcd^e-fgh*+^*+i-
10. Queue Implementation (Array)
#include <stdio.h>
#define MAX_SIZE 10

int queue[MAX_SIZE], front = 0, rear = -1;


void enqueue(int val) {
if (rear == MAX_SIZE - 1) {
printf("Queue Overflow!\n");
return;
}
queue[++rear] = val;
}

void dequeue() {
if (front > rear) {
printf("Queue Underflow!\n");
return;
}
front++;
}

EN
int main() {
enqueue(5);
enqueue(10);

K
dequeue();
IC
printf("Queue Front: %d\n", queue[front]);

return 0;
H
}
Output:​
C

Queue Front: 10
11. Circular Queue Implementation
G

#include <stdio.h>
#define MAX_SIZE 5
N

int cq[MAX_SIZE], front = -1, rear = -1;


YI

void enqueue(int val) {


FL

if ((rear + 1) % MAX_SIZE == front) {


printf("Queue Overflow!\n");
return;
}
if (front == -1) front = 0;
rear = (rear + 1) % MAX_SIZE;
cq[rear] = val;
}

void dequeue() {
if (front == -1) {
printf("Queue Underflow!\n");
return;
}
if (front == rear) front = rear = -1;
else front = (front + 1) % MAX_SIZE;
}

int main() {
enqueue(10);
enqueue(20);
dequeue();
printf("Circular Queue Front: %d\n", cq[front]);

return 0;
}
Output:
Circular Queue Front: 20
12. Singly Linked List
#include <stdio.h>

EN
#include <stdlib.h>

struct Node {
int data;

K
struct Node *next;
};
IC
void insert(struct Node **head, int data) {
H
struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
newNode->data = data;
C

newNode->next = *head;
*head = newNode;
G

}
N

void printList(struct Node *head) {


while (head != NULL) {
YI

printf("%d -> ", head->data);


head = head->next;
FL

}
printf("NULL\n");
}

int main() {
struct Node *head = NULL;
insert(&head, 10);
insert(&head, 20);
printList(head);

return 0;
}
Output:​
20 -> 10 -> NULL
13. Doubly Linked List
#include <stdio.h>
#include <stdlib.h>

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

void insert(struct Node **head, int data) {


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

EN
}

void printList(struct Node *head) {


while (head != NULL) {

K
printf("%d <-> ", head->data);
head = head->next;
IC
}
printf("NULL\n");
H
}
C

int main() {
struct Node *head = NULL;
G

insert(&head, 10);
insert(&head, 20);
N

printList(head);
YI

return 0;
}
FL

Output:
20 <-> 10 <-> NULL
14. Factorial (Recursion)
#include <stdio.h>
int fact(int n) {
return (n <= 1) ? 1 : n * fact(n - 1);
}

int main() {
printf("Factorial(5): %d\n", fact(5));
return 0;
}
Output:​
Factorial(5): 120
15. Singly Circular Linked List
#include <stdio.h>
#include <stdlib.h>

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

void insert(struct Node **head, int data) {


struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
newNode->data = data;
if (*head == NULL) {
*head = newNode;
newNode->next = *head;
} else {

EN
struct Node *temp = *head;
while (temp->next != *head) temp = temp->next;
temp->next = newNode;
newNode->next = *head;

K
}
}
IC
void printList(struct Node *head) {
H
if (head == NULL) return;
C

struct Node *temp = head;


do {
printf("%d -> ", temp->data);
G

temp = temp->next;
} while (temp != head);
N

printf("HEAD\n");
}
YI

int main() {
FL

struct Node *head = NULL;


insert(&head, 10);
insert(&head, 20);
printList(head);

return 0;
}
Output:
10 -> 20 -> HEAD
16. Fibonacci (Recursion)
#include <stdio.h>
int fib(int n) {
return (n <= 1) ? n : fib(n - 1) + fib(n - 2);
}
int main() {
printf("Fibonacci(5): %d\n", fib(5));
return 0;
}
Output:
Fibonacci(5): 5
17. Binary Search
#include <stdio.h>
int bs(int arr[], int n, int x) {
int l = 0, r = n - 1;
while (l <= r) {
int m = (l + r) / 2;
if (arr[m] == x) return m;
else if (arr[m] < x) l = m + 1;
else r = m - 1;

EN
}
return -1;
}

K
int main() {
int arr[] = {1, 2, 3};
IC
printf("Index: %d\n", bs(arr, 3, 2));
return 0;
H
}
Output:
C

Index: 1
18. Selection Sort
G

#include <stdio.h>
void selectionSort(int arr[], int n) {
N

for (int i = 0; i < n - 1; i++) {


int minIdx = i;
YI

for (int j = i + 1; j < n; j++)


if (arr[j] < arr[minIdx]) minIdx = j;
FL

int temp = arr[i];


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

int main() {
int arr[] = {3, 1, 2};
selectionSort(arr, 3);
printf("Selection Sorted: %d %d %d\n", arr[0], arr[1], arr[2]);
return 0;
}​
Output:
Selection Sorted: 1 2 3
9. 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[] = {3, 1, 2};
insertionSort(arr, 3);

EN
printf("Insertion Sorted: %d %d %d\n", arr[0], arr[1], arr[2]);
return 0;
}
Output:

K
Insertion Sorted: 1 2 3
20. Merge Sort
IC
#include <stdio.h>
void merge(int arr[], int l, int m, int r) {
H
int n1 = m - l + 1, n2 = r - m;
int L[n1], R[n2];
C

for (int i = 0; i < n1; i++) L[i] = arr[l + i];


G

for (int i = 0; i < n2; i++) R[i] = arr[m + 1 + i];


N

int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
YI

if (L[i] <= R[j]) arr[k++] = L[i++];


else arr[k++] = R[j++];
FL

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 - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
int main() {
int arr[] = {3, 1, 2};
mergeSort(arr, 0, 2);
printf("Merge Sorted: %d %d %d\n", arr[0], arr[1], arr[2]);
return 0;
}
Outside:
Merge Sorted: 1 2 3
21. Quicksort
#include <stdio.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}

EN
int partition(int arr[], int low, int high) {
int pivot = arr[high], i = low - 1;
for (int j = low; j < high; j++) {

K
if (arr[j] < pivot) swap(&arr[++i], &arr[j]);
}
IC
swap(&arr[i + 1], &arr[high]);
return i + 1;
H
}
C

void quicksort(int arr[], int low, int high) {


if (low < high) {
G

int pi = partition(arr, low, high);


quicksort(arr, low, pi - 1);
N

quicksort(arr, pi + 1, high);
}
YI

}
FL

int main() {
int arr[] = {3, 1, 2};
quicksort(arr, 0, 2);
printf("Quicksort Result: %d %d %d\n", arr[0], arr[1], arr[2]);
return 0;
}
Outside:
Quicksort Result: 1 2 3
22. BFS Algorithm
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100

int adj[MAX_SIZE][MAX_SIZE], visited[MAX_SIZE], queue[MAX_SIZE], front = -1, rear = -1;


void enqueue(int val) {
if (rear == MAX_SIZE - 1) return;
if (front == -1) front = 0;
queue[++rear] = val;
}

int dequeue() {
if (front == -1 || front > rear) return -1;
return queue[front++];
}

void bfs(int start, int n) {


enqueue(start);
visited[start] = 1;

EN
while (front != -1 && front <= rear) {
int current = dequeue();
printf("%d ", current);

K
for (int i = 0; i < n; i++) {
if (adj[current][i] && !visited[i]) {
IC
enqueue(i);
visited[i] = 1;
H
}
C

}
}
}
G

int main() {
N

int n = 4; // Number of vertices


adj[0][1] = adj[1][0] = 1;
YI

adj[0][2] = adj[2][0] = 1;
adj[1][3] = adj[3][1] = 1;
FL

printf("BFS Traversal: ");


bfs(0, n);

return 0;
}
Output:
BFS Traversal: 0 1 2 3

You might also like