C Language Data Structures and Algorithms Implementations
C Language Data Structures and Algorithms
This document presents fundamental data structures and algorithms implemented in C. Each section provides a complete code example, demonstrating core concepts like stack operations, sorting, searching, and mathematical functions.
Stack Data Structure: Interactive Operations
A stack is a Last-In, First-Out (LIFO) data structure. This C program demonstrates a basic array-based stack implementation with interactive functions for pushing, popping, peeking, and displaying elements.
C Code: Stack Implementation with Menu
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
int stack[MAX];
int top = -1;
void push() {
int val;
if (top == MAX - 1) {
printf("Stack Overflow! Cannot push more elements.\n");
} else {
printf("Enter the value to push: ");
scanf("%d", &val);
stack[++top] = val;
printf("%d pushed to the stack.\n", val);
}
}
void pop() {
if (top == -1) {
printf("Stack Underflow! No element to pop.\n");
} else {
printf("Popped element: %d\n", stack[top--]);
}
}
void peek() {
if (top == -1) {
printf("Stack is empty.\n");
} else {
printf("Top element: %d\n", stack[top]);
}
}
void display() {
if (top == -1) {
printf("Stack is empty.\n");
} else {
printf("Stack elements: ");
for (int i = top; i >= 0; i--) {
printf("%d ", stack[i]);
}
printf("\n");
}
}
int main() {
int choice;
while (1) {
printf("\n--- Stack Operations Menu ---\n");
printf("1. Push\n");
printf("2. Pop\n");
printf("3. Peek\n");
printf("4. Display\n");
printf("5. Exit\n");
printf("Enter your choice (1-5): ");
scanf("%d", &choice);
switch (choice) {
case 1: push(); break;
case 2: pop(); break;
case 3: peek(); break;
case 4: display(); break;
case 5: exit(0);
default: printf("Invalid choice! Please enter 1-5.\n");
}
}
return 0;
}
Greatest Common Divisor (GCD) Calculation
The Greatest Common Divisor (GCD) of two or more integers is the largest positive integer that divides each of the integers without leaving a remainder. This C program calculates the GCD of three numbers using a recursive Euclidean algorithm.
C Code: Recursive GCD Function
#include <stdio.h>
int GCD(int m, int n) {
if (n == 0)
return m;
else if (n > m)
return GCD(n, m);
else
return GCD(n, m % n);
}
int main() {
int k, m, n;
printf("\nEnter any three numbers: ");
scanf("%d%d%d", &k, &m, &n);
printf("GCD for %d, %d, %d is %d\n", k, m, n, GCD(k, GCD(m, n)));
return 0;
}
Bubble Sort Algorithm
Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until no swaps are needed, indicating the list is sorted.
C Code: Bubble Sort Implementation
#include <stdio.h>
void bubbleSort(int A[], int n) {
int pass, j, temp;
for (pass = 0; pass < n - 1; pass++) {
for (j = 0; j < n - 1 - pass; j++) {
if (A[j] > A[j+1]) {
temp = A[j];
A[j] = A[j+1];
A[j+1] = temp;
}
}
}
}
int main() {
int A[50], i, n;
printf("Enter the size of the array: ");
scanf("%d", &n);
for (i = 0; i < n; i++) {
printf("Enter element %d: ", i + 1);
scanf("%d", &A[i]);
}
printf("Before sorting: \n");
for (i = 0; i < n; i++)
printf("%5d", A[i]);
bubbleSort(A, n);
printf("\nAfter sorting: \n");
for (i = 0; i < n; i++)
printf("%5d", A[i]);
printf("\n");
return 0;
}
Binary Search Algorithm
Binary Search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you’ve narrowed down the possible locations to just one.
C Code: Binary Search Implementation
#include <stdio.h>
int binarySearch(int arr[], int size, int key) {
int low = 0, high = size - 1;
while (low <= high) {
int mid = low + (high - low) / 2; // Prevents potential integer overflow
if (arr[mid] == key)
return mid;
if (arr[mid] < key)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
int main() {
int arr[100], n, key, i;
printf("Enter number of elements in the array (sorted): ");
scanf("%d", &n);
printf("Enter %d sorted elements:\n", n);
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
printf("Enter the element to search: ");
scanf("%d", &key);
int result = binarySearch(arr, n, key);
if (result != -1)
printf("Element found at index %d.\n", result);
else
printf("Element not found in the array.\n");
return 0;
}
Stack Operations: Push, Pop, and Display
This section provides another C implementation of a stack, focusing on the fundamental push, pop, and display operations. It serves as a concise example of how to manage a LIFO data structure with a function that accepts the value to push as an argument.
C Code: Basic Stack Operations
#include <stdio.h>
#define MAX 100
int stack[MAX];
int top = -1;
void push(int value) {
if (top == MAX - 1) {
printf("Stack Overflow! Cannot push %d\n", value);
} else {
top++;
stack[top] = value;
printf("%d pushed to stack.\n", value);
}
}
void pop() {
if (top == -1) {
printf("Stack Underflow! Cannot pop from empty stack.\n");
} else {
printf("%d popped from stack.\n", stack[top]);
top--;
}
}
void display() {
if (top == -1) {
printf("Stack is empty.\n");
} else {
printf("Stack contents: ");
for (int i = top; i >= 0; i--) {
printf("%d ", stack[i]);
}
printf("\n");
}
}
int main() {
int choice, value;
while (1) {
printf("\n*** Stack Menu ***\n");
printf("1. Push\n2. Pop\n3. Display\n4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch(choice) {
case 1:
printf("Enter value to push: ");
scanf("%d", &value);
push(value);
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
printf("Exiting program.\n");
return 0;
default:
printf("Invalid choice! Please enter 1-4.\n");
}
}
return 0;
}