Data Structures and Algorithms in C
This document contains simple, complete, and runnable C programs for various data structures and
algorithms. Each sub-topic is provided as a standalone program.
1. Matrix Operations
1.1 Matrix Addition
#include <stdio.h>
int main() {
int r = 2, c = 2, i, j;
int a[2][2] = {{1, 2}, {3, 4}};
int b[2][2] = {{5, 6}, {7, 8}};
int sum[2][2];
for(i = 0; i < r; i++) {
for(j = 0; j < c; j++) {
sum[i][j] = a[i][j] + b[i][j];
}
}
printf("Matrix Addition:\n");
for(i=0; i<r; i++) {
for(j=0; j<c; j++) printf("%d ", sum[i][j]);
printf("\n");
}
return 0;
}
Output:
Matrix Addition:
6 8
10 12
1.2 Matrix Subtraction
#include <stdio.h>
int main() {
int r = 2, c = 2, i, j;
int a[2][2] = {{5, 6}, {7, 8}};
int b[2][2] = {{1, 2}, {3, 4}};
int sub[2][2];
for(i = 0; i < r; i++) {
for(j = 0; j < c; j++) {
sub[i][j] = a[i][j] - b[i][j];
}
}
printf("Matrix Subtraction:\n");
for(i=0; i<r; i++) {
for(j=0; j<c; j++) printf("%d ", sub[i][j]);
printf("\n");
}
return 0;
}
Output:
Matrix Subtraction:
4 4
4 4
1.3 Matrix Multiplication
#include <stdio.h>
int main() {
int r = 2, c = 2, i, j, k;
int a[2][2] = {{1, 2}, {3, 4}};
int b[2][2] = {{5, 6}, {7, 8}};
int mul[2][2] = {0};
for(i = 0; i < r; i++) {
for(j = 0; j < c; j++) {
for(k = 0; k < c; k++) {
mul[i][j] += a[i][k] * b[k][j];
}
}
}
printf("Matrix Multiplication:\n");
for(i=0; i<r; i++) {
for(j=0; j<c; j++) printf("%d ", mul[i][j]);
printf("\n");
}
return 0;
}
Output:
Matrix Multiplication:
19 22
43 50
2. Searching Algorithms
2.1 Linear Search
#include <stdio.h>
int main() {
int arr[] = {10, 50, 30, 70, 80, 20};
int n = 6, key = 30, found = 0, i;
for (i = 0; i < n; i++) {
if (arr[i] == key) {
printf("Linear Search: %d found at index %d\n", key, i);
found = 1;
break;
}
}
if (!found) printf("Element not found\n");
return 0;
}
Output:
Linear Search: 30 found at index 2
2.2 Binary Search
#include <stdio.h>
int main() {
int arr[] = {10, 20, 30, 40, 50}; // Must be sorted
int n = 5, key = 40;
int low = 0, high = n - 1, mid;
while (low <= high) {
mid = (low + high) / 2;
if (arr[mid] == key) {
printf("Binary Search: %d found at index %d\n", key, mid);
return 0;
}
else if (arr[mid] < key) low = mid + 1;
else high = mid - 1;
}
printf("Element not found\n");
return 0;
}
Output:
Binary Search: 40 found at index 3
3. Sorting Algorithms
3.1 Insertion Sort
#include <stdio.h>
int main() {
int arr[] = {12, 11, 13, 5, 6};
int n = 5, i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
printf("Insertion Sort: ");
for (i = 0; i < n; i++) printf("%d ", arr[i]);
return 0;
}
Output:
Insertion Sort: 5 6 11 12 13
3.2 Bubble Sort
#include <stdio.h>
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = 7, i, j, temp;
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;
}
}
}
printf("Bubble Sort: ");
for (i = 0; i < n; i++) printf("%d ", arr[i]);
return 0;
}
Output:
Bubble Sort: 11 12 22 25 34 64 90
3.3 Selection Sort
#include <stdio.h>
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = 5, i, j, min_idx, temp;
for (i = 0; i < n-1; i++) {
min_idx = i;
for (j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
printf("Selection Sort: ");
for (i = 0; i < n; i++) printf("%d ", arr[i]);
return 0;
}
Output:
Selection Sort: 11 12 22 25 64
3.4 Merge Sort
#include <stdio.h>
void merge(int arr[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (i = 0; i < n1; i++) L[i] = arr[l + i];
for (j = 0; j < n2; j++) R[j] = arr[m + 1 + j];
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 - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
int main() {
int arr[] = {38, 27, 43, 3, 9, 82, 10};
int n = 7;
mergeSort(arr, 0, n - 1);
printf("Merge Sort: ");
for (int i = 0; i < n; i++) printf("%d ", arr[i]);
return 0;
}
Output:
Merge Sort: 3 9 10 27 38 43 82
4. Stack Operations
4.1 Stack Traversing
#include <stdio.h>
int stack[] = {10, 20, 30}; // Pre-filled stack
int top = 2; // Top index
int main() {
printf("Traversing Stack: ");
if(top == -1) printf("Empty");
else {
for(int i = top; i >= 0; i--) printf("%d ", stack[i]);
}
printf("\n");
return 0;
}
Output:
Traversing Stack: 30 20 10
4.2 Stack Push
#include <stdio.h>
#define MAX 5
int stack[MAX], top = -1;
void push(int val) {
if(top == MAX - 1) printf("Overflow\n");
else {
stack[++top] = val;
printf("Pushed %d\n", val);
}
}
int main() {
push(10);
push(20);
return 0;
}
Output:
Pushed 10
Pushed 20
4.3 Stack Pop
#include <stdio.h>
int stack[] = {10, 20, 30};
int top = 2;
void pop() {
if(top == -1) printf("Underflow\n");
else printf("Popped %d\n", stack[top--]);
}
int main() {
pop();
pop();
return 0;
}
Output:
Popped 30
Popped 20
5. Recursion
5.1 Fibonacci Series
#include <stdio.h>
int fib(int n) {
if (n <= 1) return n;
return fib(n-1) + fib(n-2);
}
int main() {
int n = 5;
printf("Fibonacci term %d is %d\n", n, fib(n));
return 0;
}
Output:
Fibonacci term 5 is 5
5.2 Factorial
#include <stdio.h>
int fact(int n) {
if (n == 0) return 1;
return n * fact(n-1);
}
int main() {
int n = 5;
printf("Factorial of %d is %d\n", n, fact(n));
return 0;
}
Output:
Factorial of 5 is 120
5.3 Tower of Hanoi
#include <stdio.h>
void hanoi(int n, char from, char to, char aux) {
if (n == 1) {
printf("Move disk 1 from %c to %c\n", from, to);
return;
}
hanoi(n-1, from, aux, to);
printf("Move disk %d from %c to %c\n", n, from, to);
hanoi(n-1, aux, to, from);
}
int main() {
int disks = 3;
printf("Tower of Hanoi for %d disks:\n", disks);
hanoi(disks, 'A', 'C', 'B');
return 0;
}
Output:
Tower of Hanoi for 3 disks:
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C
6. Queue Operations
6.1 Queue Insertion
#include <stdio.h>
#define MAX 5
int queue[MAX], front = -1, rear = -1;
void insert(int val) {
if (rear == MAX - 1) printf("Overflow\n");
else {
if (front == -1) front = 0;
queue[++rear] = val;
printf("Inserted %d\n", val);
}
}
int main() {
insert(100);
insert(200);
return 0;
}
Output:
Inserted 100
Inserted 200
6.2 Queue Deletion
#include <stdio.h>
int queue[] = {100, 200, 300};
int front = 0, rear = 2;
void delete() {
if (front == -1 || front > rear) printf("Underflow\n");
else printf("Deleted %d\n", queue[front++]);
}
int main() {
delete();
return 0;
}
Output:
Deleted 100
6.3 Queue Traversing
#include <stdio.h>
int queue[] = {10, 20, 30, 40};
int front = 0, rear = 3;
int main() {
printf("Traversing Queue: ");
for (int i = front; i <= rear; i++) printf("%d ", queue[i]);
printf("\n");
return 0;
}
Output:
Traversing Queue: 10 20 30 40
7. Evaluations
7.1 Postfix Evaluation
#include <stdio.h>
#include <ctype.h>
int stack[20], top = -1;
void push(int x) { stack[++top] = x; }
int pop() { return stack[top--]; }
int main() {
char exp[] = "23*5+"; // (2*3)+5
for (int i = 0; exp[i]; ++i) {
if (isdigit(exp[i])) push(exp[i] - '0');
else {
int val1 = pop(), val2 = pop();
switch (exp[i]) {
case '+': push(val2 + val1); break;
case '*': push(val2 * val1); break;
}
}
}
printf("Postfix '23*5+' Result: %d\n", pop());
return 0;
}
Output:
Postfix '23*5+' Result: 11
7.2 Prefix Evaluation
#include <stdio.h>
#include <ctype.h>
#include <string.h>
int stack[20], top = -1;
void push(int x) { stack[++top] = x; }
int pop() { return stack[top--]; }
int main() {
char exp[] = "+*235"; // (2*3)+5
int len = strlen(exp);
for (int i = len - 1; i >= 0; i--) {
if (isdigit(exp[i])) push(exp[i] - '0');
else {
int val1 = pop(), val2 = pop();
switch (exp[i]) {
case '+': push(val1 + val2); break;
case '*': push(val1 * val2); break;
}
}
}
printf("Prefix '+*235' Result: %d\n", pop());
return 0;
}
Output:
Prefix '+*235' Result: 11
8. Infix to Postfix Conversion
#include <stdio.h>
#include <ctype.h>
char stack[20];
int top = -1;
void push(char x) { stack[++top] = x; }
char pop() { return (top == -1) ? -1 : stack[top--]; }
int priority(char x) {
if(x == '(') return 0;
if(x == '+' || x == '-') return 1;
if(x == '*' || x == '/') return 2;
return 0;
}
int main() {
char exp[] = "a+b*c";
char *e = exp, x;
printf("Infix: %s\nPostfix: ", exp);
while(*e != '\0') {
if(isalnum(*e)) printf("%c", *e);
else if(*e == '(') push(*e);
else if(*e == ')') {
while((x = pop()) != '(') printf("%c", x);
} else {
while(top != -1 && priority(stack[top]) >= priority(*e))
printf("%c", pop());
push(*e);
}
e++;
}
while(top != -1) printf("%c", pop());
printf("\n");
return 0;
}
Output:
Infix: a+b*c
Postfix: abc*+
9. Singly Linked List: Insertion
9.1 Insertion at Beginning
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node* next; };
int main() {
struct Node* head = NULL;
// Insert 10 at Beg
struct Node* ptr = (struct Node*)malloc(sizeof(struct Node));
ptr->data = 10; ptr->next = head; head = ptr;
printf("List after Inserting 10 at Beg: %d -> NULL\n", head->data);
return 0;
}
Output:
List after Inserting 10 at Beg: 10 -> NULL
9.2 Insertion at End
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node* next; };
int main() {
struct Node* head = (struct Node*)malloc(sizeof(struct Node)); // Dummy node 10
head->data = 10; head->next = NULL;
// Insert 20 at End
struct Node* temp = head;
while(temp->next != NULL) temp = temp->next;
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = 20; newNode->next = NULL;
temp->next = newNode;
printf("List: %d -> %d -> NULL\n", head->data, head->next->data);
return 0;
}
Output:
List: 10 -> 20 -> NULL
9.3 Insertion at Any Location
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node* next; };
int main() {
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->data = 10; head->next = NULL; // List: 10
// Insert 15 after 10
int target = 10, val = 15;
struct Node* temp = head;
while(temp != NULL && temp->data != target) temp = temp->next;
if(temp != NULL) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = val;
newNode->next = temp->next;
temp->next = newNode;
}
printf("List: %d -> %d -> NULL\n", head->data, head->next->data);
return 0;
}
Output:
List: 10 -> 15 -> NULL
10. Singly Linked List: Deletion
10.1 Deletion at Beginning
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node* next; };
int main() {
// Setup 10->20
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->data = 10;
head->next = (struct Node*)malloc(sizeof(struct Node));
head->next->data = 20; head->next->next = NULL;
// Delete Beg
if(head != NULL) {
struct Node* temp = head;
head = head->next;
free(temp);
}
printf("After Delete Beg: %d -> NULL\n", head->data);
return 0;
}
Output:
After Delete Beg: 20 -> NULL
10.2 Deletion at End
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node* next; };
int main() {
// Setup 10->20
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->data = 10;
head->next = (struct Node*)malloc(sizeof(struct Node));
head->next->data = 20; head->next->next = NULL;
// Delete End
struct Node* temp = head;
while(temp->next->next != NULL) temp = temp->next;
free(temp->next);
temp->next = NULL;
printf("After Delete End: %d -> NULL\n", head->data);
return 0;
}
Output:
After Delete End: 10 -> NULL
10.3 Deletion at Any Location
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node* next; };
int main() {
// Setup 10->20->30
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->data = 10;
struct Node* second = (struct Node*)malloc(sizeof(struct Node));
second->data = 20; head->next = second;
struct Node* third = (struct Node*)malloc(sizeof(struct Node));
third->data = 30; second->next = third; third->next = NULL;
// Delete 20
int val = 20;
struct Node *temp = head, *prev = NULL;
while(temp != NULL && temp->data != val) {
prev = temp;
temp = temp->next;
}
if(temp != NULL) {
prev->next = temp->next;
free(temp);
}
printf("After Delete 20: %d -> %d -> NULL\n", head->data, head->next->data);
return 0;
}
Output:
After Delete 20: 10 -> 30 -> NULL
11. Doubly Linked List: Insertion
11.1 Insertion at Beginning
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *prev, *next; };
int main() {
struct Node* head = NULL;
// Insert 10 at Beg
struct Node* n = (struct Node*)malloc(sizeof(struct Node));
n->data = 10; n->prev = NULL; n->next = head;
if(head != NULL) head->prev = n;
head = n;
printf("DLL: %d -> NULL\n", head->data);
return 0;
}
Output:
DLL: 10 -> NULL
11.2 Insertion at End
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *prev, *next; };
int main() {
// Setup List: 10
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->data = 10; head->prev = NULL; head->next = NULL;
// Insert 20 at End
struct Node* n = (struct Node*)malloc(sizeof(struct Node));
n->data = 20; n->next = NULL;
struct Node* temp = head;
while(temp->next != NULL) temp = temp->next;
temp->next = n;
n->prev = temp;
printf("DLL: %d <-> %d -> NULL\n", head->data, head->next->data);
return 0;
}
Output:
DLL: 10 <-> 20 -> NULL
11.3 Insertion at Any Location
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *prev, *next; };
int main() {
// Setup List: 10
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->data = 10; head->prev = NULL; head->next = NULL;
// Insert 20 After 10
struct Node* temp = head;
if(temp != NULL) {
struct Node* n = (struct Node*)malloc(sizeof(struct Node));
n->data = 20; n->next = temp->next; n->prev = temp;
if(temp->next) temp->next->prev = n;
temp->next = n;
}
printf("DLL: %d <-> %d -> NULL\n", head->data, head->next->data);
return 0;
}
Output:
DLL: 10 <-> 20 -> NULL
12. Doubly Linked List: Deletion
12.1 Deletion at Beginning
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *prev, *next; };
int main() {
// Setup 10->20
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->data = 10;
struct Node* node2 = (struct Node*)malloc(sizeof(struct Node));
node2->data = 20; node2->next = NULL; node2->prev = head; head->next = node2;
// Delete Beg
struct Node* temp = head;
head = head->next;
if(head) head->prev = NULL;
free(temp);
printf("After Del Beg: %d -> NULL\n", head->data);
return 0;
}
Output:
After Del Beg: 20 -> NULL
12.2 Deletion at End
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *prev, *next; };
int main() {
// Setup 10->20
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->data = 10;
struct Node* node2 = (struct Node*)malloc(sizeof(struct Node));
node2->data = 20; node2->next = NULL; node2->prev = head; head->next = node2;
// Delete End
struct Node* temp = head;
while(temp->next != NULL) temp = temp->next;
if(temp->prev) temp->prev->next = NULL;
free(temp);
printf("After Del End: %d -> NULL\n", head->data);
return 0;
}
Output:
After Del End: 10 -> NULL
12.3 Deletion at Any Location
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *prev, *next; };
int main() {
// Setup 10->20->30
struct Node* head = (struct Node*)malloc(sizeof(struct Node)); head->data = 10;
struct Node* n2 = (struct Node*)malloc(sizeof(struct Node)); n2->data = 20;
struct Node* n3 = (struct Node*)malloc(sizeof(struct Node)); n3->data = 30;
head->next = n2; n2->prev = head; n2->next = n3; n3->prev = n2; n3->next = NULL;
// Delete 20
struct Node* temp = head;
while(temp != NULL && temp->data != 20) temp = temp->next;
if(temp != NULL) {
if(temp->prev) temp->prev->next = temp->next;
if(temp->next) temp->next->prev = temp->prev;
free(temp);
}
printf("After Del 20: %d <-> %d -> NULL\n", head->data, head->next->data);
return 0;
}
Output:
After Del 20: 10 <-> 30 -> NULL
13. Graph Implementations
13.1 DFS (Depth First Search)
#include <stdio.h>
int G[5][5] = { {0,1,1,0,0}, {1,0,0,1,0}, {1,0,0,1,0}, {0,1,1,0,1}, {0,0,0,1,0} };
int visited[5] = {0}, n = 5;
void DFS(int i) {
printf("%d ", i);
visited[i] = 1;
for(int j=0; j<n; j++)
if(G[i][j]==1 && !visited[j]) DFS(j);
}
int main() {
printf("DFS: ");
DFS(0);
return 0;
}
Output:
DFS: 0 1 3 2 4
13.2 BFS (Breadth First Search)
#include <stdio.h>
int G[5][5] = { {0,1,1,0,0}, {1,0,0,1,0}, {1,0,0,1,0}, {0,1,1,0,1}, {0,0,0,1,0} };
int n = 5;
void BFS(int start) {
int queue[10], front=0, rear=0;
int visited[5] = {0};
printf("%d ", start);
visited[start] = 1;
queue[rear++] = start;
while(front < rear) {
int i = queue[front++];
for(int j=0; j<n; j++) {
if(G[i][j]==1 && !visited[j]) {
printf("%d ", j);
visited[j] = 1;
queue[rear++] = j;
}
}
}
}
int main() {
printf("BFS: ");
BFS(0);
return 0;
}