Data Structures & Algorithms — Exam Programs in C (Unit I – Unit X)
All programs are complete, standalone and compile with: gcc program.c -o program (add -lm only where noted)
Every program below is one that has a high chance of appearing in the final exam ("Write a program in C to ...").
Table of Contents
| Unit | Topic | Programs |
|---|---|---|
| I | Introduction to Data Structure | Array traversal with step count, Divide & Conquer Max-Min, Linear vs Binary step comparison |
| II | Recursion | Factorial, Fibonacci, TOH, GCD, Sum/Reverse of digits, Indirect recursion, Tail recursion |
| III | Stacks | Stack using array, Stack using linked list, Reverse string, Balanced parentheses, Infix→Postfix, Postfix evaluation |
| IV | Queue | Linear queue, Circular queue, Priority queue, Queue using linked list |
| V | Linked List | Singly linked list (all operations), Reverse a list, Doubly linked list, Circular linked list, Concatenation, Polynomial addition |
| VI | Trees | Binary tree + 3 traversals, Level order, Height/Count/Leaf, BST (insert/search/delete), AVL tree, Huffman coding, B-Tree |
| VII | Sorting | Bubble, Insertion, Selection, Quick, Merge, Shell, Binary insertion sort, All-in-one menu |
| VIII | Searching | Sequential, Binary (iterative + recursive), BST search, Linear probing, Quadratic probing, Double hashing, Chaining, Rehashing |
| IX | Graph | Adjacency matrix & list, BFS, DFS (recursive + stack), Prim, Kruskal, Dijkstra |
| X | Growth Functions | Growth rate comparison table, Operation counting |
UNIT I — Introduction to Data Structure
Q1. Write a program in C to store n elements in an array, display them, and count the number of basic operations (time complexity demonstration).
/* Unit I - Program 1: Array traversal with operation counting (O(n)) */
#include <stdio.h>
int main(void)
{
int a[100], n, i;
long sum = 0;
long steps = 0; /* counts basic operations */
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter %d elements: ", n);
for (i = 0; i < n; i++) {
scanf("%d", &a[i]);
steps++;
}
printf("Elements are: ");
for (i = 0; i < n; i++) {
printf("%d ", a[i]);
sum += a[i];
steps++;
}
printf("\nSum = %ld", sum);
printf("\nTotal basic operations executed = %ld", steps);
printf("\nTime complexity = O(n), Space complexity = O(n)\n");
return 0;
}
Q2. Write a program in C to find the maximum and minimum element of an array using the Divide and Conquer approach.
/* Unit I - Program 2: Divide and Conquer Max-Min T(n) = 2T(n/2) + 2 => O(n) */
#include <stdio.h>
typedef struct {
int min;
int max;
} Pair;
Pair maxMin(int a[], int low, int high)
{
Pair res, left, right;
int mid;
if (low == high) { /* only one element */
res.min = res.max = a[low];
return res;
}
if (high == low + 1) { /* exactly two elements */
if (a[low] < a[high]) { res.min = a[low]; res.max = a[high]; }
else { res.min = a[high]; res.max = a[low]; }
return res;
}
mid = (low + high) / 2; /* DIVIDE */
left = maxMin(a, low, mid); /* CONQUER */
right = maxMin(a, mid + 1, high);
res.min = (left.min < right.min) ? left.min : right.min; /* COMBINE */
res.max = (left.max > right.max) ? left.max : right.max;
return res;
}
int main(void)
{
int a[] = { 45, 12, 78, 3, 99, 56, 7, 23 };
int n = sizeof(a) / sizeof(a[0]);
Pair r = maxMin(a, 0, n - 1);
printf("Minimum = %d\n", r.min);
printf("Maximum = %d\n", r.max);
return 0;
}
Q3. Write a program in C that compares the number of comparisons made by Linear Search (incremental approach) and Binary Search (divide & conquer approach).
/* Unit I - Program 3: Incremental vs Divide-and-Conquer (O(n) vs O(log n)) */
#include <stdio.h>
int linearSearch(int a[], int n, int key, int *cmp)
{
int i;
*cmp = 0;
for (i = 0; i < n; i++) {
(*cmp)++;
if (a[i] == key) return i;
}
return -1;
}
int binarySearch(int a[], int n, int key, int *cmp)
{
int low = 0, high = n - 1, mid;
*cmp = 0;
while (low <= high) {
mid = low + (high - low) / 2;
(*cmp)++;
if (a[mid] == key) return mid;
else if (a[mid] < key) low = mid + 1;
else high = mid - 1;
}
return -1;
}
int main(void)
{
int a[] = { 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 }; /* sorted */
int n = sizeof(a) / sizeof(a[0]);
int key = 91, c1, c2, p1, p2;
p1 = linearSearch(a, n, key, &c1);
p2 = binarySearch(a, n, key, &c2);
printf("Searching for %d in %d elements\n\n", key, n);
printf("Linear Search : index = %d, comparisons = %d -> O(n)\n", p1, c1);
printf("Binary Search : index = %d, comparisons = %d -> O(log n)\n", p2, c2);
return 0;
}
UNIT II — Recursion
Q1. Write a program in C to find the factorial of a number using recursion (and iteration).
/* Unit II - Program 1: Factorial - recursive and iterative */
#include <stdio.h>
long factRecursive(int n)
{
if (n == 0 || n == 1) /* base case */
return 1;
return n * factRecursive(n - 1); /* recursive case */
}
long factIterative(int n)
{
long f = 1;
int i;
for (i = 2; i <= n; i++)
f = f * i;
return f;
}
int main(void)
{
int n;
printf("Enter a number: ");
scanf("%d", &n);
if (n < 0) {
printf("Factorial of a negative number is not defined.\n");
return 1;
}
printf("Factorial (recursive) of %d = %ld\n", n, factRecursive(n));
printf("Factorial (iterative) of %d = %ld\n", n, factIterative(n));
return 0;
}
Q2. Write a program in C to generate the Fibonacci series using recursion.
/* Unit II - Program 2: Fibonacci series using recursion (O(2^n)) and iteration (O(n)) */
#include <stdio.h>
int fib(int n)
{
if (n == 0) return 0; /* base case 1 */
if (n == 1) return 1; /* base case 2 */
return fib(n - 1) + fib(n - 2);
}
int main(void)
{
int n, i;
int a = 0, b = 1, c;
printf("How many terms? ");
scanf("%d", &n);
printf("Fibonacci series (recursive): ");
for (i = 0; i < n; i++)
printf("%d ", fib(i));
printf("\nFibonacci series (iterative): ");
for (i = 0; i < n; i++) {
printf("%d ", a);
c = a + b;
a = b;
b = c;
}
printf("\n");
return 0;
}
Q3. Write a program in C to solve the Tower of Hanoi problem using recursion.
/* Unit II - Program 3: Tower of Hanoi -> moves = 2^n - 1 */
#include <stdio.h>
int moves = 0;
void towerOfHanoi(int n, char source, char aux, char dest)
{
if (n == 1) {
printf("Move disk 1 from %c to %c\n", source, dest);
moves++;
return;
}
towerOfHanoi(n - 1, source, dest, aux); /* move n-1 to auxiliary */
printf("Move disk %d from %c to %c\n", n, source, dest);
moves++;
towerOfHanoi(n - 1, aux, source, dest); /* move n-1 to destination */
}
int main(void)
{
int n;
printf("Enter number of disks: ");
scanf("%d", &n);
towerOfHanoi(n, 'A', 'B', 'C'); /* A = source, B = auxiliary, C = destination */
printf("\nTotal moves = %d (2^%d - 1)\n", moves, n);
return 0;
}
Q4. Write a program in C to find the GCD of two numbers using recursion.
/* Unit II - Program 4: GCD using recursion (Euclid's algorithm) */
#include <stdio.h>
int gcd(int a, int b)
{
if (b == 0)
return a; /* base case */
return gcd(b, a % b); /* tail recursion */
}
int main(void)
{
int a, b;
printf("Enter two numbers: ");
scanf("%d %d", &a, &b);
printf("GCD(%d, %d) = %d\n", a, b, gcd(a, b));
printf("LCM(%d, %d) = %d\n", a, b, (a * b) / gcd(a, b));
return 0;
}
Q5. Write a program in C to find the sum of digits and reverse of a number using recursion.
/* Unit II - Program 5: Sum of digits and reverse of a number using recursion */
#include <stdio.h>
int sumOfDigits(int n)
{
if (n == 0) return 0;
return (n % 10) + sumOfDigits(n / 10);
}
int reverseNumber(int n, int rev)
{
if (n == 0) return rev;
return reverseNumber(n / 10, rev * 10 + n % 10);
}
int power(int base, int exp)
{
if (exp == 0) return 1;
return base * power(base, exp - 1);
}
int main(void)
{
int n, b, e;
printf("Enter a number: ");
scanf("%d", &n);
printf("Sum of digits = %d\n", sumOfDigits(n));
printf("Reverse = %d\n", reverseNumber(n, 0));
printf("Enter base and exponent: ");
scanf("%d %d", &b, &e);
printf("%d ^ %d = %d\n", b, e, power(b, e));
return 0;
}
Q6. Write a program in C to demonstrate Direct, Indirect, Linear and Tail recursion.
/* Unit II - Program 6: Types of recursion */
#include <stdio.h>
/* 1. DIRECT + LINEAR recursion : function calls itself once */
int sumN(int n)
{
if (n == 0) return 0;
return n + sumN(n - 1);
}
/* 2. TAIL recursion : recursive call is the LAST statement */
int sumTail(int n, int acc)
{
if (n == 0) return acc;
return sumTail(n - 1, acc + n);
}
/* 3. INDIRECT recursion : isEven -> isOdd -> isEven ... */
int isOdd(int n); /* forward declaration */
int isEven(int n)
{
if (n == 0) return 1;
return isOdd(n - 1);
}
int isOdd(int n)
{
if (n == 0) return 0;
return isEven(n - 1);
}
/* 4. TREE (non-linear) recursion : more than one recursive call */
int fibTree(int n)
{
if (n < 2) return n;
return fibTree(n - 1) + fibTree(n - 2);
}
int main(void)
{
int n = 5;
printf("Direct/Linear : sum of 1..%d = %d\n", n, sumN(n));
printf("Tail recursion : sum of 1..%d = %d\n", n, sumTail(n, 0));
printf("Indirect : %d is %s\n", n, isEven(n) ? "Even" : "Odd");
printf("Tree recursion : fib(%d) = %d\n", n, fibTree(n));
return 0;
}
UNIT III — Stacks
Q1. Write a program in C to implement a stack using an array with PUSH, POP, PEEK and DISPLAY operations.
/* Unit III - Program 1: Stack using array (menu driven) */
#include <stdio.h>
#include <stdlib.h>
#define MAX 5
int stack[MAX];
int top = -1;
void push(int item)
{
if (top == MAX - 1) { /* OVERFLOW */
printf("Stack Overflow! Cannot push %d\n", item);
return;
}
top = top + 1;
stack[top] = item;
printf("%d pushed into stack\n", item);
}
int pop(void)
{
int item;
if (top == -1) { /* UNDERFLOW */
printf("Stack Underflow!\n");
return -1;
}
item = stack[top];
top = top - 1;
return item;
}
int peek(void)
{
if (top == -1) {
printf("Stack is empty!\n");
return -1;
}
return stack[top];
}
void display(void)
{
int i;
if (top == -1) {
printf("Stack is empty!\n");
return;
}
printf("Stack (top to bottom): ");
for (i = top; i >= 0; i--)
printf("%d ", stack[i]);
printf("\n");
}
int main(void)
{
int choice, item;
while (1) {
printf("\n1.Push 2.Pop 3.Peek 4.Display 5.Exit\nEnter choice: ");
if (scanf("%d", &choice) != 1) break;
switch (choice) {
case 1:
printf("Enter item to push: ");
scanf("%d", &item);
push(item);
break;
case 2:
item = pop();
if (item != -1) printf("Popped item = %d\n", item);
break;
case 3:
item = peek();
if (item != -1) printf("Top item = %d\n", item);
break;
case 4:
display();
break;
case 5:
exit(0);
default:
printf("Invalid choice!\n");
}
}
return 0;
}
Q2. Write a program in C to implement a stack using a linked list.
/* Unit III - Program 2: Stack using linked list (dynamic stack) */
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *next;
};
struct Node *top = NULL;
void push(int item)
{
struct Node *newNode = (struct Node *) malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory not available (Overflow)\n");
return;
}
newNode->data = item;
newNode->next = top; /* new node points to old top */
top = newNode; /* new node becomes top */
printf("%d pushed\n", item);
}
int pop(void)
{
struct Node *temp;
int item;
if (top == NULL) {
printf("Stack Underflow!\n");
return -1;
}
temp = top;
item = temp->data;
top = top->next;
free(temp);
return item;
}
void display(void)
{
struct Node *temp = top;
if (temp == NULL) { printf("Stack is empty\n"); return; }
printf("Stack (top to bottom): ");
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
int main(void)
{
push(10); push(20); push(30);
display();
printf("Popped = %d\n", pop());
display();
printf("Top element = %d\n", top ? top->data : -1);
return 0;
}
Q3. Write a program in C to reverse a string using a stack.
/* Unit III - Program 3: Reverse a string using stack */
#include <stdio.h>
#include <string.h>
#define MAX 100
char stack[MAX];
int top = -1;
void push(char c) { stack[++top] = c; }
char pop(void) { return stack[top--]; }
int isEmpty(void) { return (top == -1); }
int main(void)
{
char str[MAX];
int i, len;
printf("Enter a string: ");
scanf("%99s", str);
len = strlen(str);
for (i = 0; i < len; i++) /* push all characters */
push(str[i]);
printf("Reversed string: ");
while (!isEmpty()) /* pop => reverse order (LIFO) */
printf("%c", pop());
printf("\n");
return 0;
}
Q4. Write a program in C to check whether an expression has balanced parentheses using a stack.
/* Unit III - Program 4: Balanced parentheses checking using stack */
#include <stdio.h>
#include <string.h>
#define MAX 100
char stack[MAX];
int top = -1;
void push(char c) { stack[++top] = c; }
char pop(void) { return (top == -1) ? '\0' : stack[top--]; }
int isEmpty(void) { return (top == -1); }
int isMatch(char open, char close)
{
return (open == '(' && close == ')') ||
(open == '[' && close == ']') ||
(open == '{' && close == '}');
}
int main(void)
{
char exp[MAX], ch;
int i, balanced = 1;
printf("Enter an expression: ");
scanf("%99s", exp);
for (i = 0; exp[i] != '\0'; i++) {
ch = exp[i];
if (ch == '(' || ch == '[' || ch == '{')
push(ch);
else if (ch == ')' || ch == ']' || ch == '}') {
if (isEmpty() || !isMatch(pop(), ch)) { balanced = 0; break; }
}
}
if (!isEmpty()) balanced = 0;
printf("Expression is %s\n", balanced ? "BALANCED" : "NOT BALANCED");
return 0;
}
Q5. Write a program in C to convert an infix expression into its postfix form using a stack.
/* Unit III - Program 5: Infix to Postfix conversion using stack */
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#define MAX 100
char stack[MAX];
int top = -1;
void push(char c) { stack[++top] = c; }
char pop(void) { return stack[top--]; }
char peek(void) { return stack[top]; }
int isEmpty(void) { return (top == -1); }
int precedence(char c)
{
if (c == '^') return 3;
if (c == '*' || c == '/' || c == '%') return 2;
if (c == '+' || c == '-') return 1;
return 0;
}
int main(void)
{
char infix[MAX], postfix[MAX], ch;
int i, j = 0;
printf("Enter infix expression (no spaces): ");
scanf("%99s", infix);
for (i = 0; infix[i] != '\0'; i++) {
ch = infix[i];
if (isalnum(ch)) { /* operand -> output */
postfix[j++] = ch;
}
else if (ch == '(') {
push(ch);
}
else if (ch == ')') { /* pop till '(' */
while (!isEmpty() && peek() != '(')
postfix[j++] = pop();
if (!isEmpty()) pop(); /* discard '(' */
}
else { /* operator */
while (!isEmpty() && peek() != '(' &&
(precedence(peek()) > precedence(ch) ||
(precedence(peek()) == precedence(ch) && ch != '^')))
postfix[j++] = pop();
push(ch);
}
}
while (!isEmpty()) /* pop remaining */
postfix[j++] = pop();
postfix[j] = '\0';
printf("Infix : %s\n", infix);
printf("Postfix : %s\n", postfix);
return 0;
}
/* Sample: input a+b*c-(d/e+f)*g
output abc*+de/f+g*- */
Q6. Write a program in C to evaluate a postfix expression using a stack.
/* Unit III - Program 6: Evaluation of postfix expression (single digit operands) */
#include <stdio.h>
#include <ctype.h>
#include <math.h>
#define MAX 100
int stack[MAX];
int top = -1;
void push(int x) { stack[++top] = x; }
int pop(void) { return stack[top--]; }
int main(void)
{
char postfix[MAX], ch;
int i, op1, op2, result;
printf("Enter postfix expression (single digits, e.g. 53+82-*): ");
scanf("%99s", postfix);
for (i = 0; postfix[i] != '\0'; i++) {
ch = postfix[i];
if (isdigit(ch)) {
push(ch - '0'); /* char to int */
} else {
op2 = pop(); /* second operand popped first */
op1 = pop();
switch (ch) {
case '+': push(op1 + op2); break;
case '-': push(op1 - op2); break;
case '*': push(op1 * op2); break;
case '/': push(op1 / op2); break;
case '^': push((int) pow(op1, op2)); break;
default : printf("Invalid operator %c\n", ch); return 1;
}
}
}
result = pop();
printf("Result = %d\n", result);
return 0;
}
/* compile with: gcc prog.c -o prog -lm
Sample: 53+82-* => (5+3)*(8-2) = 48 */
UNIT IV — Queue
Q1. Write a program in C to implement a linear queue using an array (insertion and deletion).
/* Unit IV - Program 1: Linear (simple) queue using array */
#include <stdio.h>
#include <stdlib.h>
#define MAX 5
int queue[MAX];
int front = -1, rear = -1;
void enqueue(int item)
{
if (rear == MAX - 1) { /* queue full */
printf("Queue Overflow! Cannot insert %d\n", item);
return;
}
if (front == -1) front = 0; /* first insertion */
queue[++rear] = item;
printf("%d inserted\n", item);
}
int dequeue(void)
{
int item;
if (front == -1 || front > rear) { /* queue empty */
printf("Queue Underflow!\n");
return -1;
}
item = queue[front++];
if (front > rear) front = rear = -1; /* reset when empty */
return item;
}
void display(void)
{
int i;
if (front == -1) { printf("Queue is empty\n"); return; }
printf("Queue (front to rear): ");
for (i = front; i <= rear; i++)
printf("%d ", queue[i]);
printf("\n");
}
int main(void)
{
int choice, item;
while (1) {
printf("\n1.Insert 2.Delete 3.Display 4.Exit\nEnter choice: ");
if (scanf("%d", &choice) != 1) break;
switch (choice) {
case 1: printf("Enter item: "); scanf("%d", &item); enqueue(item); break;
case 2: item = dequeue();
if (item != -1) printf("Deleted item = %d\n", item);
break;
case 3: display(); break;
case 4: exit(0);
default: printf("Invalid choice\n");
}
}
return 0;
}
/* Limitation of simple queue: after deletions the front slots cannot be
reused even though they are free -> solved by CIRCULAR QUEUE */
Q2. Write a program in C to implement a circular queue.
/* Unit IV - Program 2: Circular queue using array */
#include <stdio.h>
#include <stdlib.h>
#define MAX 5
int cq[MAX];
int front = -1, rear = -1;
void enqueue(int item)
{
if ((front == 0 && rear == MAX - 1) || (rear + 1) % MAX == front) {
printf("Circular Queue Overflow! Cannot insert %d\n", item);
return;
}
if (front == -1) { front = rear = 0; }
else { rear = (rear + 1) % MAX; } /* wrap around */
cq[rear] = item;
printf("%d inserted at position %d\n", item, rear);
}
int dequeue(void)
{
int item;
if (front == -1) { printf("Circular Queue Underflow!\n"); return -1; }
item = cq[front];
if (front == rear) front = rear = -1; /* last element */
else front = (front + 1) % MAX;
return item;
}
void display(void)
{
int i;
if (front == -1) { printf("Queue is empty\n"); return; }
printf("Circular Queue: ");
i = front;
while (1) {
printf("%d ", cq[i]);
if (i == rear) break;
i = (i + 1) % MAX;
}
printf("\n");
}
int main(void)
{
int choice, item;
while (1) {
printf("\n1.Insert 2.Delete 3.Display 4.Exit\nEnter choice: ");
if (scanf("%d", &choice) != 1) break;
switch (choice) {
case 1: printf("Enter item: "); scanf("%d", &item); enqueue(item); break;
case 2: item = dequeue();
if (item != -1) printf("Deleted item = %d\n", item);
break;
case 3: display(); break;
case 4: exit(0);
default: printf("Invalid choice\n");
}
}
return 0;
}
Q3. Write a program in C to implement a priority queue.
/* Unit IV - Program 3: Priority queue using array (lower number = higher priority) */
#include <stdio.h>
#include <stdlib.h>
#define MAX 20
struct Item {
int data;
int priority;
};
struct Item pq[MAX];
int size = 0;
void insert(int data, int priority)
{
int i;
if (size == MAX) { printf("Priority Queue is Full\n"); return; }
/* find correct position (sorted by priority) */
i = size - 1;
while (i >= 0 && pq[i].priority > priority) {
pq[i + 1] = pq[i];
i--;
}
pq[i + 1].data = data;
pq[i + 1].priority = priority;
size++;
printf("Inserted data=%d with priority=%d\n", data, priority);
}
void deleteHighest(void)
{
int i;
if (size == 0) { printf("Priority Queue is Empty\n"); return; }
printf("Deleted data=%d (priority=%d)\n", pq[0].data, pq[0].priority);
for (i = 0; i < size - 1; i++)
pq[i] = pq[i + 1];
size--;
}
void display(void)
{
int i;
if (size == 0) { printf("Priority Queue is Empty\n"); return; }
printf("Priority Queue (data:priority) -> ");
for (i = 0; i < size; i++)
printf("%d:%d ", pq[i].data, pq[i].priority);
printf("\n");
}
int main(void)
{
insert(100, 3);
insert(200, 1);
insert(300, 4);
insert(400, 2);
display();
deleteHighest();
deleteHighest();
display();
return 0;
}
Q4. Write a program in C to implement a queue using a linked list.
/* Unit IV - Program 4: 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 item)
{
struct Node *newNode = (struct Node *) malloc(sizeof(struct Node));
newNode->data = item;
newNode->next = NULL;
if (rear == NULL) { /* empty queue */
front = rear = newNode;
} else {
rear->next = newNode;
rear = newNode;
}
printf("%d inserted\n", item);
}
int dequeue(void)
{
struct Node *temp;
int item;
if (front == NULL) { printf("Queue Underflow\n"); return -1; }
temp = front;
item = temp->data;
front = front->next;
if (front == NULL) rear = NULL; /* queue became empty */
free(temp);
return item;
}
void display(void)
{
struct Node *temp = front;
if (temp == NULL) { printf("Queue is empty\n"); return; }
printf("Queue (front to rear): ");
while (temp != NULL) { printf("%d ", temp->data); temp = temp->next; }
printf("\n");
}
int main(void)
{
enqueue(11); enqueue(22); enqueue(33);
display();
printf("Deleted = %d\n", dequeue());
display();
return 0;
}
UNIT V — Linked List
Q1. Write a program in C to create a singly linked list and perform creation, insertion (beginning / end / specific position), deletion (beginning / end / specific position), traversing, searching and display.
/* Unit V - Program 1: Singly Linked List - ALL operations (most important) */
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *next;
};
struct Node *head = NULL;
struct Node *createNode(int data)
{
struct Node *newNode = (struct Node *) malloc(sizeof(struct Node));
if (newNode == NULL) { printf("Memory allocation failed\n"); exit(1); }
newNode->data = data;
newNode->next = NULL;
return newNode;
}
/* ---------- INSERTION ---------- */
void insertAtBeginning(int data)
{
struct Node *newNode = createNode(data);
newNode->next = head;
head = newNode;
}
void insertAtEnd(int data)
{
struct Node *newNode = createNode(data);
struct Node *temp;
if (head == NULL) { head = newNode; return; }
temp = head;
while (temp->next != NULL) temp = temp->next;
temp->next = newNode;
}
void insertAtPosition(int data, int pos) /* pos starts from 1 */
{
struct Node *newNode, *temp;
int i;
if (pos < 1) { printf("Invalid position\n"); return; }
if (pos == 1) { insertAtBeginning(data); return; }
temp = head;
for (i = 1; i < pos - 1 && temp != NULL; i++)
temp = temp->next;
if (temp == NULL) { printf("Position out of range\n"); return; }
newNode = createNode(data);
newNode->next = temp->next;
temp->next = newNode;
}
/* ---------- DELETION ---------- */
void deleteFromBeginning(void)
{
struct Node *temp;
if (head == NULL) { printf("List is empty\n"); return; }
temp = head;
head = head->next;
printf("Deleted %d\n", temp->data);
free(temp);
}
void deleteFromEnd(void)
{
struct Node *temp = head, *prev = NULL;
if (head == NULL) { printf("List is empty\n"); return; }
if (head->next == NULL) {
printf("Deleted %d\n", head->data);
free(head); head = NULL; return;
}
while (temp->next != NULL) { prev = temp; temp = temp->next; }
prev->next = NULL;
printf("Deleted %d\n", temp->data);
free(temp);
}
void deleteFromPosition(int pos)
{
struct Node *temp = head, *prev = NULL;
int i;
if (head == NULL) { printf("List is empty\n"); return; }
if (pos == 1) { deleteFromBeginning(); return; }
for (i = 1; i < pos && temp != NULL; i++) { prev = temp; temp = temp->next; }
if (temp == NULL) { printf("Position out of range\n"); return; }
prev->next = temp->next;
printf("Deleted %d\n", temp->data);
free(temp);
}
/* ---------- SEARCH / TRAVERSE / COUNT ---------- */
int search(int key)
{
struct Node *temp = head;
int pos = 1;
while (temp != NULL) {
if (temp->data == key) return pos;
temp = temp->next;
pos++;
}
return -1;
}
int countNodes(void)
{
struct Node *temp = head;
int count = 0;
while (temp != NULL) { count++; temp = temp->next; }
return count;
}
void display(void)
{
struct Node *temp = head;
if (head == NULL) { printf("List is empty\n"); return; }
printf("List: ");
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
int main(void)
{
int choice, data, pos;
while (1) {
printf("\n--- SINGLY LINKED LIST ---\n");
printf("1.Insert at beginning 2.Insert at end 3.Insert at position\n");
printf("4.Delete from beginning 5.Delete from end 6.Delete from position\n");
printf("7.Search 8.Count 9.Display 10.Exit\nEnter choice: ");
if (scanf("%d", &choice) != 1) break;
switch (choice) {
case 1: printf("Enter data: "); scanf("%d", &data);
insertAtBeginning(data); break;
case 2: printf("Enter data: "); scanf("%d", &data);
insertAtEnd(data); break;
case 3: printf("Enter data and position: "); scanf("%d %d", &data, &pos);
insertAtPosition(data, pos); break;
case 4: deleteFromBeginning(); break;
case 5: deleteFromEnd(); break;
case 6: printf("Enter position: "); scanf("%d", &pos);
deleteFromPosition(pos); break;
case 7: printf("Enter key to search: "); scanf("%d", &data);
pos = search(data);
if (pos == -1) printf("%d not found\n", data);
else printf("%d found at position %d\n", data, pos);
break;
case 8: printf("Total nodes = %d\n", countNodes()); break;
case 9: display(); break;
case 10: exit(0);
default: printf("Invalid choice\n");
}
}
return 0;
}
Q2. Write a program in C to reverse a singly linked list.
/* Unit V - Program 2: Reverse a singly linked list (iterative + recursive) */
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *next;
};
struct Node *head = NULL;
void insertAtEnd(int data)
{
struct Node *newNode = malloc(sizeof(struct Node));
struct Node *temp = head;
newNode->data = data;
newNode->next = NULL;
if (head == NULL) { head = newNode; return; }
while (temp->next != NULL) temp = temp->next;
temp->next = newNode;
}
/* Iterative reversal - O(n) time, O(1) space */
void reverseIterative(void)
{
struct Node *prev = NULL, *current = head, *nextNode = NULL;
while (current != NULL) {
nextNode = current->next; /* save next */
current->next = prev; /* reverse link */
prev = current; /* move prev */
current = nextNode; /* move current */
}
head = prev;
}
/* Recursive reversal */
struct Node *reverseRecursive(struct Node *node)
{
struct Node *rest;
if (node == NULL || node->next == NULL) return node;
rest = reverseRecursive(node->next);
node->next->next = node;
node->next = NULL;
return rest;
}
void display(void)
{
struct Node *temp = head;
while (temp != NULL) { printf("%d -> ", temp->data); temp = temp->next; }
printf("NULL\n");
}
int main(void)
{
insertAtEnd(10); insertAtEnd(20); insertAtEnd(30);
insertAtEnd(40); insertAtEnd(50);
printf("Original list : "); display();
reverseIterative();
printf("After iterative: "); display();
head = reverseRecursive(head);
printf("After recursive: "); display();
return 0;
}
Q3. Write a program in C to implement a doubly linked list with insertion, deletion and traversal (forward and backward).
/* Unit V - Program 3: Doubly Linked List */
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *prev;
struct Node *next;
};
struct Node *head = NULL;
struct Node *createNode(int data)
{
struct Node *newNode = malloc(sizeof(struct Node));
newNode->data = data;
newNode->prev = newNode->next = NULL;
return newNode;
}
void insertAtBeginning(int data)
{
struct Node *newNode = createNode(data);
if (head != NULL) { newNode->next = head; head->prev = newNode; }
head = newNode;
}
void insertAtEnd(int data)
{
struct Node *newNode = createNode(data), *temp = head;
if (head == NULL) { head = newNode; return; }
while (temp->next != NULL) temp = temp->next;
temp->next = newNode;
newNode->prev = temp;
}
void deleteNode(int key)
{
struct Node *temp = head;
while (temp != NULL && temp->data != key) temp = temp->next;
if (temp == NULL) { printf("%d not found\n", key); return; }
if (temp->prev != NULL) temp->prev->next = temp->next;
else head = temp->next; /* deleting head */
if (temp->next != NULL) temp->next->prev = temp->prev;
printf("Deleted %d\n", temp->data);
free(temp);
}
void displayForward(void)
{
struct Node *temp = head;
printf("Forward : NULL <-> ");
while (temp != NULL) { printf("%d <-> ", temp->data); temp = temp->next; }
printf("NULL\n");
}
void displayBackward(void)
{
struct Node *temp = head;
if (temp == NULL) { printf("List empty\n"); return; }
while (temp->next != NULL) temp = temp->next; /* go to last */
printf("Backward: NULL <-> ");
while (temp != NULL) { printf("%d <-> ", temp->data); temp = temp->prev; }
printf("NULL\n");
}
int main(void)
{
insertAtEnd(20); insertAtEnd(30); insertAtEnd(40);
insertAtBeginning(10);
displayForward();
displayBackward();
deleteNode(30);
displayForward();
return 0;
}
Q4. Write a program in C to implement a circular linked list (insertion, deletion, display).
/* Unit V - Program 4: Circular Linked List (last node points to first node) */
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *next;
};
struct Node *last = NULL; /* pointer to last node */
void insertAtEnd(int data)
{
struct Node *newNode = malloc(sizeof(struct Node));
newNode->data = data;
if (last == NULL) {
newNode->next = newNode; /* points to itself */
last = newNode;
return;
}
newNode->next = last->next; /* new node -> first node */
last->next = newNode;
last = newNode; /* new node becomes last */
}
void insertAtBeginning(int data)
{
struct Node *newNode = malloc(sizeof(struct Node));
newNode->data = data;
if (last == NULL) { newNode->next = newNode; last = newNode; return; }
newNode->next = last->next;
last->next = newNode;
}
void deleteNode(int key)
{
struct Node *current, *prev;
if (last == NULL) { printf("List is empty\n"); return; }
current = last->next; /* first node */
prev = last;
do {
if (current->data == key) {
if (current == last && current->next == last) { /* only node */
free(current); last = NULL;
} else {
prev->next = current->next;
if (current == last) last = prev;
free(current);
}
printf("Deleted %d\n", key);
return;
}
prev = current;
current = current->next;
} while (current != last->next);
printf("%d not found\n", key);
}
void display(void)
{
struct Node *temp;
if (last == NULL) { printf("List is empty\n"); return; }
temp = last->next;
printf("Circular List: ");
do {
printf("%d -> ", temp->data);
temp = temp->next;
} while (temp != last->next);
printf("(back to first)\n");
}
int main(void)
{
insertAtEnd(10); insertAtEnd(20); insertAtEnd(30);
insertAtBeginning(5);
display();
deleteNode(20);
display();
return 0;
}
Q5. Write a program in C to concatenate two singly linked lists.
/* Unit V - Program 5: Concatenation of two linked lists */
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *next;
};
void insertAtEnd(struct Node **head, int data)
{
struct Node *newNode = malloc(sizeof(struct Node));
struct Node *temp = *head;
newNode->data = data;
newNode->next = NULL;
if (*head == NULL) { *head = newNode; return; }
while (temp->next != NULL) temp = temp->next;
temp->next = newNode;
}
struct Node *concatenate(struct Node *first, struct Node *second)
{
struct Node *temp;
if (first == NULL) return second;
if (second == NULL) return first;
temp = first;
while (temp->next != NULL) temp = temp->next; /* last node of first */
temp->next = second; /* link to second */
return first;
}
void display(struct Node *head)
{
while (head != NULL) { printf("%d -> ", head->data); head = head->next; }
printf("NULL\n");
}
int main(void)
{
struct Node *list1 = NULL, *list2 = NULL, *result;
insertAtEnd(&list1, 1); insertAtEnd(&list1, 2); insertAtEnd(&list1, 3);
insertAtEnd(&list2, 7); insertAtEnd(&list2, 8); insertAtEnd(&list2, 9);
printf("List 1: "); display(list1);
printf("List 2: "); display(list2);
result = concatenate(list1, list2);
printf("Concatenated: "); display(result);
return 0;
}
Q6. Write a program in C to add two polynomials using a linked list.
/* Unit V - Program 6: Addition of two polynomials using linked list
(VERY IMPORTANT - application of linked list) */
#include <stdio.h>
#include <stdlib.h>
struct Node {
int coef; /* coefficient */
int exp; /* exponent */
struct Node *next;
};
/* insert term at end (terms kept in decreasing order of exponent) */
void insertTerm(struct Node **head, int coef, int exp)
{
struct Node *newNode, *temp;
if (coef == 0) return;
newNode = malloc(sizeof(struct Node));
newNode->coef = coef;
newNode->exp = exp;
newNode->next = NULL;
if (*head == NULL) { *head = newNode; return; }
temp = *head;
while (temp->next != NULL) temp = temp->next;
temp->next = newNode;
}
struct Node *addPolynomials(struct Node *p1, struct Node *p2)
{
struct Node *result = NULL;
while (p1 != NULL && p2 != NULL) {
if (p1->exp > p2->exp) {
insertTerm(&result, p1->coef, p1->exp);
p1 = p1->next;
} else if (p1->exp < p2->exp) {
insertTerm(&result, p2->coef, p2->exp);
p2 = p2->next;
} else { /* same exponent -> add */
insertTerm(&result, p1->coef + p2->coef, p1->exp);
p1 = p1->next;
p2 = p2->next;
}
}
while (p1 != NULL) { insertTerm(&result, p1->coef, p1->exp); p1 = p1->next; }
while (p2 != NULL) { insertTerm(&result, p2->coef, p2->exp); p2 = p2->next; }
return result;
}
void display(struct Node *p)
{
if (p == NULL) { printf("0\n"); return; }
while (p != NULL) {
printf("%dx^%d", p->coef, p->exp);
if (p->next != NULL) printf(" + ");
p = p->next;
}
printf("\n");
}
int main(void)
{
struct Node *poly1 = NULL, *poly2 = NULL, *sum;
/* poly1 = 5x^3 + 4x^2 + 2x^0 */
insertTerm(&poly1, 5, 3);
insertTerm(&poly1, 4, 2);
insertTerm(&poly1, 2, 0);
/* poly2 = 5x^4 + 3x^2 + 4x^1 */
insertTerm(&poly2, 5, 4);
insertTerm(&poly2, 3, 2);
insertTerm(&poly2, 4, 1);
printf("Polynomial 1 : "); display(poly1);
printf("Polynomial 2 : "); display(poly2);
sum = addPolynomials(poly1, poly2);
printf("Sum : "); display(sum);
return 0;
}
/* Output: 5x^4 + 5x^3 + 7x^2 + 4x^1 + 2x^0 */
UNIT VI — Trees
Q1. Write a program in C to create a binary tree using linked representation and display its Preorder, Inorder and Postorder traversal.
/* Unit VI - Program 1: Binary tree creation + 3 traversals (recursive) */
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *left;
struct Node *right;
};
struct Node *createNode(int data)
{
struct Node *newNode = malloc(sizeof(struct Node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
/* Root -> Left -> Right */
void preorder(struct Node *root)
{
if (root == NULL) return;
printf("%d ", root->data);
preorder(root->left);
preorder(root->right);
}
/* Left -> Root -> Right */
void inorder(struct Node *root)
{
if (root == NULL) return;
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
/* Left -> Right -> Root */
void postorder(struct Node *root)
{
if (root == NULL) return;
postorder(root->left);
postorder(root->right);
printf("%d ", root->data);
}
/* create tree by asking user (enter -1 for no child) */
struct Node *buildTree(void)
{
int data;
struct Node *root;
printf("Enter data (-1 for no node): ");
scanf("%d", &data);
if (data == -1) return NULL;
root = createNode(data);
printf("Enter left child of %d\n", data);
root->left = buildTree();
printf("Enter right child of %d\n", data);
root->right = buildTree();
return root;
}
int main(void)
{
struct Node *root = buildTree();
printf("\nPreorder : "); preorder(root);
printf("\nInorder : "); inorder(root);
printf("\nPostorder : "); postorder(root);
printf("\n");
return 0;
}
/* 1
/ \
2 3 Preorder : 1 2 4 5 3
/ \ Inorder : 4 2 5 1 3
4 5 Postorder: 4 5 2 3 1
Input sequence: 1 2 4 -1 -1 5 -1 -1 3 -1 -1 */
Q2. Write a program in C to find the height, total number of nodes, and number of leaf nodes of a binary tree, and print the level order traversal.
/* Unit VI - Program 2: Height, Depth, Level order traversal, Node counts */
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
struct Node {
int data;
struct Node *left, *right;
};
struct Node *createNode(int data)
{
struct Node *n = malloc(sizeof(struct Node));
n->data = data; n->left = n->right = NULL;
return n;
}
int height(struct Node *root) /* height of tree = max depth */
{
int lh, rh;
if (root == NULL) return -1; /* height of empty tree = -1 */
lh = height(root->left);
rh = height(root->right);
return (lh > rh ? lh : rh) + 1;
}
int countNodes(struct Node *root)
{
if (root == NULL) return 0;
return 1 + countNodes(root->left) + countNodes(root->right);
}
int countLeaves(struct Node *root)
{
if (root == NULL) return 0;
if (root->left == NULL && root->right == NULL) return 1;
return countLeaves(root->left) + countLeaves(root->right);
}
int countInternal(struct Node *root)
{
if (root == NULL || (root->left == NULL && root->right == NULL)) return 0;
return 1 + countInternal(root->left) + countInternal(root->right);
}
/* Level order traversal (BFS) using a queue */
void levelOrder(struct Node *root)
{
struct Node *queue[MAX], *current;
int front = 0, rear = 0;
if (root == NULL) return;
queue[rear++] = root;
while (front < rear) {
current = queue[front++];
printf("%d ", current->data);
if (current->left != NULL) queue[rear++] = current->left;
if (current->right != NULL) queue[rear++] = current->right;
}
}
int main(void)
{
/* 1
/ \
2 3
/ \ \
4 5 6 */
struct Node *root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
root->right->right = createNode(6);
printf("Level order traversal : "); levelOrder(root);
printf("\nHeight of tree : %d", height(root));
printf("\nTotal nodes : %d", countNodes(root));
printf("\nLeaf nodes : %d", countLeaves(root));
printf("\nInternal nodes : %d\n", countInternal(root));
return 0;
}
Q3. Write a program in C to create a Binary Search Tree and perform insertion, searching and deletion.
/* Unit VI - Program 3: Binary Search Tree - Insert, Search, Delete (MOST IMPORTANT) */
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *left, *right;
};
struct Node *createNode(int data)
{
struct Node *n = malloc(sizeof(struct Node));
n->data = data; n->left = n->right = NULL;
return n;
}
/* ---------------- INSERTION ---------------- */
struct Node *insert(struct Node *root, int data)
{
if (root == NULL) return createNode(data);
if (data < root->data)
root->left = insert(root->left, data);
else if (data > root->data)
root->right = insert(root->right, data);
else
printf("%d already exists\n", data);
return root;
}
/* ---------------- SEARCHING ---------------- */
struct Node *search(struct Node *root, int key)
{
if (root == NULL || root->data == key) return root;
if (key < root->data) return search(root->left, key);
return search(root->right, key);
}
/* smallest node of right subtree = inorder successor */
struct Node *findMin(struct Node *root)
{
while (root->left != NULL) root = root->left;
return root;
}
/* ---------------- DELETION ---------------- */
struct Node *deleteNode(struct Node *root, int key)
{
struct Node *temp;
if (root == NULL) { printf("%d not found\n", key); return NULL; }
if (key < root->data)
root->left = deleteNode(root->left, key);
else if (key > root->data)
root->right = deleteNode(root->right, key);
else {
/* CASE 1: leaf node (no child) */
if (root->left == NULL && root->right == NULL) {
free(root);
return NULL;
}
/* CASE 2: only one child */
else if (root->left == NULL) {
temp = root->right; free(root); return temp;
}
else if (root->right == NULL) {
temp = root->left; free(root); return temp;
}
/* CASE 3: two children -> replace with inorder successor */
else {
temp = findMin(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
}
return root;
}
void inorder(struct Node *root)
{
if (root == NULL) return;
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
int main(void)
{
struct Node *root = NULL;
int choice, value;
/* sample tree */
root = insert(root, 50);
insert(root, 30); insert(root, 70); insert(root, 20);
insert(root, 40); insert(root, 60); insert(root, 80);
while (1) {
printf("\n1.Insert 2.Search 3.Delete 4.Inorder(sorted) 5.Exit\nChoice: ");
if (scanf("%d", &choice) != 1) break;
switch (choice) {
case 1: printf("Enter value: "); scanf("%d", &value);
root = insert(root, value); break;
case 2: printf("Enter key: "); scanf("%d", &value);
if (search(root, value)) printf("%d FOUND\n", value);
else printf("%d NOT FOUND\n", value);
break;
case 3: printf("Enter key to delete: "); scanf("%d", &value);
root = deleteNode(root, value); break;
case 4: printf("Inorder: "); inorder(root); printf("\n"); break;
case 5: exit(0);
default: printf("Invalid choice\n");
}
}
return 0;
}
Q4. Write a program in C to implement an AVL (height balanced) tree with insertion and rotations.
/* Unit VI - Program 4: AVL Tree insertion with LL, RR, LR, RL rotations */
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *left, *right;
int height;
};
int height(struct Node *n)
{
return (n == NULL) ? 0 : n->height;
}
int max(int a, int b) { return (a > b) ? a : b; }
struct Node *createNode(int data)
{
struct Node *n = malloc(sizeof(struct Node));
n->data = data;
n->left = n->right = NULL;
n->height = 1;
return n;
}
int getBalance(struct Node *n)
{
return (n == NULL) ? 0 : height(n->left) - height(n->right);
}
/* Right rotation (for LL imbalance) */
struct Node *rightRotate(struct Node *y)
{
struct Node *x = y->left;
struct Node *T2 = x->right;
x->right = y;
y->left = T2;
y->height = max(height(y->left), height(y->right)) + 1;
x->height = max(height(x->left), height(x->right)) + 1;
return x; /* new root */
}
/* Left rotation (for RR imbalance) */
struct Node *leftRotate(struct Node *x)
{
struct Node *y = x->right;
struct Node *T2 = y->left;
y->left = x;
x->right = T2;
x->height = max(height(x->left), height(x->right)) + 1;
y->height = max(height(y->left), height(y->right)) + 1;
return y; /* new root */
}
struct Node *insert(struct Node *node, int data)
{
int balance;
/* 1. normal BST insertion */
if (node == NULL) return createNode(data);
if (data < node->data)
node->left = insert(node->left, data);
else if (data > node->data)
node->right = insert(node->right, data);
else
return node; /* duplicates not allowed */
/* 2. update height */
node->height = 1 + max(height(node->left), height(node->right));
/* 3. get balance factor */
balance = getBalance(node);
/* 4. four rotation cases */
if (balance > 1 && data < node->left->data) /* LL */
return rightRotate(node);
if (balance < -1 && data > node->right->data) /* RR */
return leftRotate(node);
if (balance > 1 && data > node->left->data) { /* LR */
node->left = leftRotate(node->left);
return rightRotate(node);
}
if (balance < -1 && data < node->right->data) { /* RL */
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
void preorder(struct Node *root)
{
if (root == NULL) return;
printf("%d(bf=%d) ", root->data, getBalance(root));
preorder(root->left);
preorder(root->right);
}
void inorder(struct Node *root)
{
if (root == NULL) return;
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
int main(void)
{
struct Node *root = NULL;
int values[] = { 10, 20, 30, 40, 50, 25 };
int i, n = sizeof(values) / sizeof(values[0]);
for (i = 0; i < n; i++)
root = insert(root, values[i]);
printf("Preorder of AVL tree : "); preorder(root);
printf("\nInorder (sorted) : "); inorder(root);
printf("\nHeight of AVL tree : %d\n", height(root));
return 0;
}
/* Preorder = 30 20 10 25 40 50 -> tree stays balanced */
Q5. Write a program in C to implement Huffman coding (Huffman algorithm).
/* Unit VI - Program 5: Huffman coding algorithm (greedy) */
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
struct Node {
char ch;
int freq;
struct Node *left, *right;
};
struct Node *heap[MAX];
int heapSize = 0;
struct Node *createNode(char ch, int freq)
{
struct Node *n = malloc(sizeof(struct Node));
n->ch = ch; n->freq = freq;
n->left = n->right = NULL;
return n;
}
void insertNode(struct Node *n)
{
heap[heapSize++] = n;
}
/* remove and return node with minimum frequency */
struct Node *extractMin(void)
{
int i, minIndex = 0;
struct Node *minNode;
for (i = 1; i < heapSize; i++)
if (heap[i]->freq < heap[minIndex]->freq)
minIndex = i;
minNode = heap[minIndex];
for (i = minIndex; i < heapSize - 1; i++)
heap[i] = heap[i + 1];
heapSize--;
return minNode;
}
struct Node *buildHuffmanTree(char chars[], int freq[], int n)
{
int i;
struct Node *left, *right, *parent;
for (i = 0; i < n; i++)
insertNode(createNode(chars[i], freq[i]));
while (heapSize > 1) {
left = extractMin();
right = extractMin();
parent = createNode('$', left->freq + right->freq); /* internal node */
parent->left = left;
parent->right = right;
insertNode(parent);
}
return extractMin();
}
void printCodes(struct Node *root, char code[], int top)
{
if (root == NULL) return;
if (root->left != NULL) {
code[top] = '0';
printCodes(root->left, code, top + 1);
}
if (root->right != NULL) {
code[top] = '1';
printCodes(root->right, code, top + 1);
}
if (root->left == NULL && root->right == NULL) { /* leaf = character */
code[top] = '\0';
printf(" %c | %-4d | %s\n", root->ch, root->freq, code);
}
}
int main(void)
{
char chars[] = { 'a', 'b', 'c', 'd', 'e', 'f' };
int freq[] = { 5, 9, 12, 13, 16, 45 };
int n = sizeof(chars) / sizeof(chars[0]);
char code[MAX];
struct Node *root;
root = buildHuffmanTree(chars, freq, n);
printf("Char | Freq | Huffman Code\n");
printf("------------------------------\n");
printCodes(root, code, 0);
return 0;
}
Q6. Write a program in C to implement a B-Tree with insertion, traversal and searching.
/* Unit VI - Program 6: B-Tree (minimum degree t = 3, i.e. max 5 keys per node) */
#include <stdio.h>
#include <stdlib.h>
#define T 3 /* minimum degree */
struct BTreeNode {
int keys[2 * T - 1]; /* max 2t-1 keys */
struct BTreeNode *child[2 * T]; /* max 2t children */
int n; /* current key count */
int leaf; /* 1 if leaf node */
};
struct BTreeNode *createNode(int leaf)
{
struct BTreeNode *node = malloc(sizeof(struct BTreeNode));
int i;
node->leaf = leaf;
node->n = 0;
for (i = 0; i < 2 * T; i++) node->child[i] = NULL;
return node;
}
/* inorder-like traversal of B-Tree -> gives sorted keys */
void traverse(struct BTreeNode *root)
{
int i;
if (root == NULL) return;
for (i = 0; i < root->n; i++) {
if (!root->leaf) traverse(root->child[i]);
printf("%d ", root->keys[i]);
}
if (!root->leaf) traverse(root->child[i]);
}
/* search a key */
struct BTreeNode *search(struct BTreeNode *root, int k)
{
int i = 0;
if (root == NULL) return NULL;
while (i < root->n && k > root->keys[i]) i++;
if (i < root->n && root->keys[i] == k) return root;
if (root->leaf) return NULL;
return search(root->child[i], k);
}
/* split the full child y = x->child[i] */
void splitChild(struct BTreeNode *x, int i, struct BTreeNode *y)
{
struct BTreeNode *z = createNode(y->leaf);
int j;
z->n = T - 1;
for (j = 0; j < T - 1; j++) /* copy last t-1 keys to z */
z->keys[j] = y->keys[j + T];
if (!y->leaf)
for (j = 0; j < T; j++) /* copy last t children */
z->child[j] = y->child[j + T];
y->n = T - 1;
for (j = x->n; j >= i + 1; j--) /* make room in x */
x->child[j + 1] = x->child[j];
x->child[i + 1] = z;
for (j = x->n - 1; j >= i; j--)
x->keys[j + 1] = x->keys[j];
x->keys[i] = y->keys[T - 1]; /* middle key moves up */
x->n = x->n + 1;
}
void insertNonFull(struct BTreeNode *x, int k)
{
int i = x->n - 1;
if (x->leaf) {
while (i >= 0 && x->keys[i] > k) {
x->keys[i + 1] = x->keys[i];
i--;
}
x->keys[i + 1] = k;
x->n = x->n + 1;
} else {
while (i >= 0 && x->keys[i] > k) i--;
i++;
if (x->child[i]->n == 2 * T - 1) { /* child is full -> split */
splitChild(x, i, x->child[i]);
if (x->keys[i] < k) i++;
}
insertNonFull(x->child[i], k);
}
}
struct BTreeNode *insert(struct BTreeNode *root, int k)
{
if (root == NULL) { /* empty tree */
root = createNode(1);
root->keys[0] = k;
root->n = 1;
return root;
}
if (root->n == 2 * T - 1) { /* root is full -> grow height */
struct BTreeNode *s = createNode(0);
int i = 0;
s->child[0] = root;
splitChild(s, 0, root);
if (s->keys[0] < k) i = 1;
insertNonFull(s->child[i], k);
return s; /* new root */
}
insertNonFull(root, k);
return root;
}
int main(void)
{
struct BTreeNode *root = NULL;
int values[] = { 10, 20, 5, 6, 12, 30, 7, 17, 3, 25, 40, 1 };
int i, n = sizeof(values) / sizeof(values[0]);
int key = 17;
for (i = 0; i < n; i++)
root = insert(root, values[i]);
printf("B-Tree traversal (sorted order): ");
traverse(root);
printf("\n");
printf("Search %d : %s\n", key, search(root, key) ? "FOUND" : "NOT FOUND");
printf("Search %d : %s\n", 99, search(root, 99) ? "FOUND" : "NOT FOUND");
printf("Keys in root node: ");
for (i = 0; i < root->n; i++) printf("%d ", root->keys[i]);
printf("\n");
return 0;
}
UNIT VII — Sorting
Q1. Write a program in C to sort an array using Bubble Sort.
/* Unit VII - Program 1: Bubble Sort Best O(n), Avg/Worst O(n^2), Space O(1), Stable */
#include <stdio.h>
void bubbleSort(int a[], int n)
{
int i, j, temp, swapped;
for (i = 0; i < n - 1; i++) { /* n-1 passes */
swapped = 0;
for (j = 0; j < n - 1 - i; j++) {
if (a[j] > a[j + 1]) { /* swap adjacent */
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
swapped = 1;
}
}
printf("Pass %d: ", i + 1);
for (j = 0; j < n; j++) printf("%d ", a[j]);
printf("\n");
if (swapped == 0) break; /* already sorted */
}
}
int main(void)
{
int a[] = { 64, 34, 25, 12, 22, 11, 90 };
int n = sizeof(a) / sizeof(a[0]), i;
printf("Original array: ");
for (i = 0; i < n; i++) printf("%d ", a[i]);
printf("\n\n");
bubbleSort(a, n);
printf("\nSorted array: ");
for (i = 0; i < n; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}
Q2. Write a program in C to sort an array using Insertion Sort.
/* Unit VII - Program 2: Insertion Sort Best O(n), Worst O(n^2), Stable */
#include <stdio.h>
void insertionSort(int a[], int n)
{
int i, j, key;
for (i = 1; i < n; i++) {
key = a[i]; /* element to be inserted */
j = i - 1;
/* shift all larger elements one position right */
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = key; /* insert at correct place */
}
}
int main(void)
{
int a[] = { 12, 11, 13, 5, 6 };
int n = sizeof(a) / sizeof(a[0]), i;
insertionSort(a, n);
printf("Sorted array: ");
for (i = 0; i < n; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}
Q3. Write a program in C to sort an array using Selection Sort.
/* Unit VII - Program 3: Selection Sort O(n^2) always, Space O(1), Not stable */
#include <stdio.h>
void selectionSort(int a[], int n)
{
int i, j, minIndex, temp;
for (i = 0; i < n - 1; i++) {
minIndex = i; /* assume i is minimum */
for (j = i + 1; j < n; j++)
if (a[j] < a[minIndex])
minIndex = j; /* find actual minimum */
if (minIndex != i) { /* swap */
temp = a[i];
a[i] = a[minIndex];
a[minIndex] = temp;
}
}
}
int main(void)
{
int a[] = { 29, 10, 14, 37, 13 };
int n = sizeof(a) / sizeof(a[0]), i;
selectionSort(a, n);
printf("Sorted array: ");
for (i = 0; i < n; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}
Q4. Write a program in C to sort an array using Quick Sort.
/* Unit VII - Program 4: Quick Sort (divide & conquer)
Best/Avg O(n log n), Worst O(n^2), Space O(log n) */
#include <stdio.h>
void swap(int *a, int *b)
{
int t = *a; *a = *b; *b = t;
}
int partition(int a[], int low, int high)
{
int pivot = a[high]; /* last element as pivot */
int i = low - 1, j;
for (j = low; j < high; j++) {
if (a[j] <= pivot) {
i++;
swap(&a[i], &a[j]);
}
}
swap(&a[i + 1], &a[high]); /* pivot to its final place */
return i + 1;
}
void quickSort(int a[], int low, int high)
{
int pi;
if (low < high) {
pi = partition(a, low, high); /* DIVIDE */
quickSort(a, low, pi - 1); /* CONQUER left */
quickSort(a, pi + 1, high); /* CONQUER right */
}
}
int main(void)
{
int a[] = { 10, 7, 8, 9, 1, 5 };
int n = sizeof(a) / sizeof(a[0]), i;
quickSort(a, 0, n - 1);
printf("Sorted array: ");
for (i = 0; i < n; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}
Q5. Write a program in C to sort an array using Merge Sort.
/* Unit VII - Program 5: Merge Sort (divide & conquer)
Time O(n log n) in all cases, Space O(n), Stable */
#include <stdio.h>
#define MAX 100
void merge(int a[], int low, int mid, int high)
{
int temp[MAX];
int i = low, j = mid + 1, k = low;
while (i <= mid && j <= high) {
if (a[i] <= a[j]) temp[k++] = a[i++];
else temp[k++] = a[j++];
}
while (i <= mid) temp[k++] = a[i++]; /* copy remaining left */
while (j <= high) temp[k++] = a[j++]; /* copy remaining right */
for (i = low; i <= high; i++)
a[i] = temp[i];
}
void mergeSort(int a[], int low, int high)
{
int mid;
if (low < high) {
mid = (low + high) / 2;
mergeSort(a, low, mid); /* sort left half */
mergeSort(a, mid + 1, high); /* sort right half */
merge(a, low, mid, high); /* merge them */
}
}
int main(void)
{
int a[] = { 38, 27, 43, 3, 9, 82, 10 };
int n = sizeof(a) / sizeof(a[0]), i;
mergeSort(a, 0, n - 1);
printf("Sorted array: ");
for (i = 0; i < n; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}
Q6. Write a program in C to sort an array using Shell Sort.
/* Unit VII - Program 6: Shell Sort (diminishing increment sort)
Time O(n log n) to O(n^2) depending on gap sequence */
#include <stdio.h>
void shellSort(int a[], int n)
{
int gap, i, j, temp;
for (gap = n / 2; gap > 0; gap /= 2) { /* reduce gap each pass */
for (i = gap; i < n; i++) {
temp = a[i];
/* gapped insertion sort */
for (j = i; j >= gap && a[j - gap] > temp; j -= gap)
a[j] = a[j - gap];
a[j] = temp;
}
printf("After gap = %d : ", gap);
for (j = 0; j < n; j++) printf("%d ", a[j]);
printf("\n");
}
}
int main(void)
{
int a[] = { 12, 34, 54, 2, 3, 45, 8, 21 };
int n = sizeof(a) / sizeof(a[0]), i;
shellSort(a, n);
printf("\nSorted array: ");
for (i = 0; i < n; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}
Q7. Write a program in C to sort an array using Binary Insertion Sort (Binary Sort).
/* Unit VII - Program 7: Binary Sort = Binary Insertion Sort
Uses binary search to find the insertion position -> fewer comparisons */
#include <stdio.h>
/* returns the position where 'key' should be inserted in a[low..high] */
int binarySearchPos(int a[], int key, int low, int high)
{
int mid;
if (high <= low)
return (key > a[low]) ? (low + 1) : low;
mid = (low + high) / 2;
if (key == a[mid]) return mid + 1;
if (key > a[mid]) return binarySearchPos(a, key, mid + 1, high);
return binarySearchPos(a, key, low, mid - 1);
}
void binaryInsertionSort(int a[], int n)
{
int i, j, pos, key;
for (i = 1; i < n; i++) {
key = a[i];
j = i - 1;
pos = binarySearchPos(a, key, 0, j); /* find position */
while (j >= pos) { /* shift right */
a[j + 1] = a[j];
j--;
}
a[pos] = key;
}
}
int main(void)
{
int a[] = { 37, 23, 0, 17, 12, 72, 31, 46 };
int n = sizeof(a) / sizeof(a[0]), i;
binaryInsertionSort(a, n);
printf("Sorted array: ");
for (i = 0; i < n; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}
Q8. Write a menu-driven program in C that sorts an array using any of the sorting techniques and compares the number of comparisons (efficiency of sorting).
/* Unit VII - Program 8: All sorting techniques in one menu-driven program
+ comparison counter (efficiency / Big-O demonstration) */
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
long comparisons;
void printArray(int a[], int n)
{
int i;
for (i = 0; i < n; i++) printf("%d ", a[i]);
printf("\n");
}
void copyArray(int src[], int dest[], int n)
{
int i;
for (i = 0; i < n; i++) dest[i] = src[i];
}
void bubbleSort(int a[], int n)
{
int i, j, t;
for (i = 0; i < n - 1; i++)
for (j = 0; j < n - 1 - i; j++) {
comparisons++;
if (a[j] > a[j + 1]) { t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; }
}
}
void insertionSort(int a[], int n)
{
int i, j, key;
for (i = 1; i < n; i++) {
key = a[i]; j = i - 1;
while (j >= 0 && (++comparisons) && a[j] > key) { a[j + 1] = a[j]; j--; }
a[j + 1] = key;
}
}
void selectionSort(int a[], int n)
{
int i, j, min, t;
for (i = 0; i < n - 1; i++) {
min = i;
for (j = i + 1; j < n; j++) { comparisons++; if (a[j] < a[min]) min = j; }
t = a[i]; a[i] = a[min]; a[min] = t;
}
}
int partition(int a[], int low, int high)
{
int pivot = a[high], i = low - 1, j, t;
for (j = low; j < high; j++) {
comparisons++;
if (a[j] <= pivot) { i++; t = a[i]; a[i] = a[j]; a[j] = t; }
}
t = a[i + 1]; a[i + 1] = a[high]; a[high] = t;
return i + 1;
}
void quickSort(int a[], int low, int high)
{
int pi;
if (low < high) {
pi = partition(a, low, high);
quickSort(a, low, pi - 1);
quickSort(a, pi + 1, high);
}
}
void merge(int a[], int low, int mid, int high)
{
int temp[MAX], i = low, j = mid + 1, k = low;
while (i <= mid && j <= high) {
comparisons++;
if (a[i] <= a[j]) temp[k++] = a[i++]; else temp[k++] = a[j++];
}
while (i <= mid) temp[k++] = a[i++];
while (j <= high) temp[k++] = a[j++];
for (i = low; i <= high; i++) a[i] = temp[i];
}
void mergeSort(int a[], int low, int high)
{
int mid;
if (low < high) {
mid = (low + high) / 2;
mergeSort(a, low, mid);
mergeSort(a, mid + 1, high);
merge(a, low, mid, high);
}
}
void shellSort(int a[], int n)
{
int gap, i, j, temp;
for (gap = n / 2; gap > 0; gap /= 2)
for (i = gap; i < n; i++) {
temp = a[i];
for (j = i; j >= gap && (++comparisons) && a[j - gap] > temp; j -= gap)
a[j] = a[j - gap];
a[j] = temp;
}
}
int main(void)
{
int original[MAX], work[MAX], n, i, choice;
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter %d elements: ", n);
for (i = 0; i < n; i++) scanf("%d", &original[i]);
while (1) {
printf("\n1.Bubble 2.Insertion 3.Selection 4.Quick 5.Merge 6.Shell 7.Exit\n");
printf("Enter choice: ");
if (scanf("%d", &choice) != 1) break;
copyArray(original, work, n);
comparisons = 0;
switch (choice) {
case 1: bubbleSort(work, n); printf("Bubble Sort O(n^2) : "); break;
case 2: insertionSort(work, n); printf("Insertion Sort O(n^2) : "); break;
case 3: selectionSort(work, n); printf("Selection Sort O(n^2) : "); break;
case 4: quickSort(work, 0, n - 1); printf("Quick Sort O(n log n) : "); break;
case 5: mergeSort(work, 0, n - 1); printf("Merge Sort O(n log n) : "); break;
case 6: shellSort(work, n); printf("Shell Sort O(n log n) : "); break;
case 7: exit(0);
default: printf("Invalid choice\n"); continue;
}
printArray(work, n);
printf("Comparisons made = %ld\n", comparisons);
}
return 0;
}
UNIT VIII — Searching & Hashing
Q1. Write a program in C to search an element using Sequential (Linear) Search.
/* Unit VIII - Program 1: Sequential / Linear search O(n) */
#include <stdio.h>
int linearSearch(int a[], int n, int key)
{
int i;
for (i = 0; i < n; i++)
if (a[i] == key)
return i; /* found -> return index */
return -1; /* not found */
}
int main(void)
{
int a[100], n, i, key, pos;
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter %d elements: ", n);
for (i = 0; i < n; i++) scanf("%d", &a[i]);
printf("Enter element to search: ");
scanf("%d", &key);
pos = linearSearch(a, n, key);
if (pos == -1) printf("%d not found in the array\n", key);
else printf("%d found at index %d (position %d)\n", key, pos, pos + 1);
return 0;
}
Q2. Write a program in C to search an element using Binary Search (iterative and recursive).
/* Unit VIII - Program 2: Binary search - iterative and recursive O(log n)
NOTE: array must be sorted */
#include <stdio.h>
int binarySearchIterative(int a[], int n, int key)
{
int low = 0, high = n - 1, mid;
while (low <= high) {
mid = low + (high - low) / 2;
if (a[mid] == key) return mid;
else if (a[mid] < key) low = mid + 1; /* search right half */
else high = mid - 1; /* search left half */
}
return -1;
}
int binarySearchRecursive(int a[], int low, int high, int key)
{
int mid;
if (low > high) return -1; /* base case */
mid = low + (high - low) / 2;
if (a[mid] == key) return mid;
if (a[mid] < key) return binarySearchRecursive(a, mid + 1, high, key);
return binarySearchRecursive(a, low, mid - 1, key);
}
int main(void)
{
int a[] = { 11, 22, 33, 44, 55, 66, 77, 88, 99 };
int n = sizeof(a) / sizeof(a[0]);
int key, p1, p2;
printf("Sorted array: ");
{ int i; for (i = 0; i < n; i++) printf("%d ", a[i]); }
printf("\nEnter element to search: ");
scanf("%d", &key);
p1 = binarySearchIterative(a, n, key);
p2 = binarySearchRecursive(a, 0, n - 1, key);
printf("Iterative: %s", p1 == -1 ? "Not found\n" : "");
if (p1 != -1) printf("found at index %d\n", p1);
printf("Recursive: %s", p2 == -1 ? "Not found\n" : "");
if (p2 != -1) printf("found at index %d\n", p2);
return 0;
}
Q3. Write a program in C to implement hashing with Linear Probing (open addressing).
/* Unit VIII - Program 3: Hashing with LINEAR PROBING
h(k) = k mod SIZE , on collision: (h(k) + i) mod SIZE */
#include <stdio.h>
#define SIZE 10
#define EMPTY -1
int hashTable[SIZE];
void initTable(void)
{
int i;
for (i = 0; i < SIZE; i++) hashTable[i] = EMPTY;
}
int hashFunction(int key)
{
return key % SIZE; /* division method */
}
void insert(int key)
{
int index = hashFunction(key);
int i = 0;
while (hashTable[(index + i) % SIZE] != EMPTY) {
i++;
if (i == SIZE) { printf("Hash table is FULL, cannot insert %d\n", key); return; }
}
hashTable[(index + i) % SIZE] = key;
printf("Inserted %d at index %d (home=%d, probes=%d)\n",
key, (index + i) % SIZE, index, i);
}
int search(int key)
{
int index = hashFunction(key);
int i = 0;
while (hashTable[(index + i) % SIZE] != EMPTY) {
if (hashTable[(index + i) % SIZE] == key)
return (index + i) % SIZE;
i++;
if (i == SIZE) break;
}
return -1;
}
void display(void)
{
int i;
printf("\nHash Table:\n");
for (i = 0; i < SIZE; i++) {
printf("[%d] -> ", i);
if (hashTable[i] == EMPTY) printf("empty\n");
else printf("%d\n", hashTable[i]);
}
}
int main(void)
{
int keys[] = { 12, 22, 32, 45, 67, 15, 25 };
int n = sizeof(keys) / sizeof(keys[0]), i, pos;
initTable();
for (i = 0; i < n; i++) insert(keys[i]);
display();
pos = search(32);
printf("\nSearch 32 : %s", pos == -1 ? "not found\n" : "");
if (pos != -1) printf("found at index %d\n", pos);
return 0;
}
Q4. Write a program in C to implement hashing with Quadratic Probing and Double Hashing.
/* Unit VIII - Program 4: Quadratic Probing and Double Hashing
Quadratic : (h(k) + i*i) mod SIZE
Double : (h1(k) + i*h2(k)) mod SIZE where h2(k) = 1 + (k mod (SIZE-1)) */
#include <stdio.h>
#define SIZE 11 /* prime size works best */
#define EMPTY -1
int qTable[SIZE], dTable[SIZE];
void initTables(void)
{
int i;
for (i = 0; i < SIZE; i++) { qTable[i] = EMPTY; dTable[i] = EMPTY; }
}
int h1(int key) { return key % SIZE; }
int h2(int key) { return 1 + (key % (SIZE - 1)); } /* must never be 0 */
void insertQuadratic(int key)
{
int home = h1(key), i, index;
for (i = 0; i < SIZE; i++) {
index = (home + i * i) % SIZE;
if (qTable[index] == EMPTY) {
qTable[index] = key;
printf("Quadratic : %3d -> index %2d (home %2d, i=%d)\n", key, index, home, i);
return;
}
}
printf("Quadratic : could not insert %d\n", key);
}
void insertDouble(int key)
{
int home = h1(key), step = h2(key), i, index;
for (i = 0; i < SIZE; i++) {
index = (home + i * step) % SIZE;
if (dTable[index] == EMPTY) {
dTable[index] = key;
printf("Double : %3d -> index %2d (h1=%2d, h2=%d, i=%d)\n",
key, index, home, step, i);
return;
}
}
printf("Double : could not insert %d\n", key);
}
void display(int t[], const char *name)
{
int i;
printf("\n%s table:\n", name);
for (i = 0; i < SIZE; i++) {
printf("[%2d] ", i);
if (t[i] == EMPTY) printf("empty\n"); else printf("%d\n", t[i]);
}
}
int main(void)
{
int keys[] = { 22, 33, 44, 11, 55, 66 };
int n = sizeof(keys) / sizeof(keys[0]), i;
initTables();
for (i = 0; i < n; i++) insertQuadratic(keys[i]);
printf("\n");
for (i = 0; i < n; i++) insertDouble(keys[i]);
display(qTable, "Quadratic probing");
display(dTable, "Double hashing");
return 0;
}
Q5. Write a program in C to implement hashing with Chaining (collision resolution by separate chaining).
/* Unit VIII - Program 5: Hashing with CHAINING (each slot holds a linked list) */
#include <stdio.h>
#include <stdlib.h>
#define SIZE 7
struct Node {
int key;
struct Node *next;
};
struct Node *hashTable[SIZE] = { NULL };
int hashFunction(int key) { return key % SIZE; }
void insert(int key)
{
int index = hashFunction(key);
struct Node *newNode = malloc(sizeof(struct Node));
newNode->key = key;
newNode->next = hashTable[index]; /* insert at front of chain */
hashTable[index] = newNode;
printf("Inserted %d into chain %d\n", key, index);
}
int search(int key)
{
int index = hashFunction(key);
struct Node *temp = hashTable[index];
int steps = 0;
while (temp != NULL) {
steps++;
if (temp->key == key) {
printf("%d found in chain %d after %d comparison(s)\n", key, index, steps);
return 1;
}
temp = temp->next;
}
printf("%d not found\n", key);
return 0;
}
void deleteKey(int key)
{
int index = hashFunction(key);
struct Node *temp = hashTable[index], *prev = NULL;
while (temp != NULL && temp->key != key) { prev = temp; temp = temp->next; }
if (temp == NULL) { printf("%d not found, cannot delete\n", key); return; }
if (prev == NULL) hashTable[index] = temp->next;
else prev->next = temp->next;
free(temp);
printf("Deleted %d\n", key);
}
void display(void)
{
int i;
struct Node *temp;
printf("\nHash table with chaining:\n");
for (i = 0; i < SIZE; i++) {
printf("[%d]", i);
temp = hashTable[i];
while (temp != NULL) { printf(" -> %d", temp->key); temp = temp->next; }
printf(" -> NULL\n");
}
}
int main(void)
{
int keys[] = { 10, 20, 15, 7, 24, 3, 17 };
int n = sizeof(keys) / sizeof(keys[0]), i;
for (i = 0; i < n; i++) insert(keys[i]);
display();
search(24);
search(99);
deleteKey(15);
display();
return 0;
}
Q6. Write a program in C to demonstrate Rehashing (when the load factor exceeds a threshold).
/* Unit VIII - Program 6: REHASHING
When load factor = n/size > 0.75, table size is doubled (next prime)
and every key is re-inserted with the new hash function. */
#include <stdio.h>
#include <stdlib.h>
#define EMPTY -1
int *table;
int tableSize = 7;
int count = 0;
int isPrime(int n)
{
int i;
if (n < 2) return 0;
for (i = 2; i * i <= n; i++)
if (n % i == 0) return 0;
return 1;
}
int nextPrime(int n)
{
while (!isPrime(n)) n++;
return n;
}
void initTable(int size)
{
int i;
table = malloc(sizeof(int) * size);
for (i = 0; i < size; i++) table[i] = EMPTY;
}
void insertKey(int key); /* forward declaration */
void rehash(void)
{
int *oldTable = table;
int oldSize = tableSize, i;
tableSize = nextPrime(oldSize * 2);
printf(">>> REHASHING: size %d -> %d\n", oldSize, tableSize);
initTable(tableSize);
count = 0;
for (i = 0; i < oldSize; i++) /* re-insert all old keys */
if (oldTable[i] != EMPTY)
insertKey(oldTable[i]);
free(oldTable);
}
void insertKey(int key)
{
int index, i = 0;
index = key % tableSize;
while (table[(index + i) % tableSize] != EMPTY) i++; /* linear probing */
table[(index + i) % tableSize] = key;
count++;
if ((double) count / tableSize > 0.75) /* load factor check */
rehash();
}
void display(void)
{
int i;
printf("Table (size=%d, keys=%d, load factor=%.2f)\n",
tableSize, count, (double) count / tableSize);
for (i = 0; i < tableSize; i++) {
printf("[%2d] ", i);
if (table[i] == EMPTY) printf("empty\n"); else printf("%d\n", table[i]);
}
printf("\n");
}
int main(void)
{
int keys[] = { 10, 20, 30, 40, 50, 60, 70, 80 };
int n = sizeof(keys) / sizeof(keys[0]), i;
initTable(tableSize);
for (i = 0; i < n; i++) {
printf("Inserting %d\n", keys[i]);
insertKey(keys[i]);
}
display();
return 0;
}
UNIT IX — Graph
Q1. Write a program in C to represent a graph using an Adjacency Matrix and an Adjacency List.
/* Unit IX - Program 1: Graph representation - adjacency matrix + adjacency list */
#include <stdio.h>
#include <stdlib.h>
#define MAX 20
int adj[MAX][MAX]; /* adjacency matrix */
int n; /* number of vertices */
struct Node { /* node of adjacency list */
int vertex;
struct Node *next;
};
struct Node *list[MAX];
void addEdgeList(int u, int v)
{
struct Node *newNode = malloc(sizeof(struct Node));
newNode->vertex = v;
newNode->next = list[u];
list[u] = newNode;
newNode = malloc(sizeof(struct Node)); /* undirected -> both ways */
newNode->vertex = u;
newNode->next = list[v];
list[v] = newNode;
}
void displayMatrix(void)
{
int i, j;
printf("\nAdjacency Matrix:\n ");
for (i = 0; i < n; i++) printf("%3d", i);
printf("\n");
for (i = 0; i < n; i++) {
printf("%3d ", i);
for (j = 0; j < n; j++) printf("%3d", adj[i][j]);
printf("\n");
}
}
void displayList(void)
{
int i;
struct Node *temp;
printf("\nAdjacency List:\n");
for (i = 0; i < n; i++) {
printf("%d", i);
temp = list[i];
while (temp != NULL) { printf(" -> %d", temp->vertex); temp = temp->next; }
printf("\n");
}
}
int main(void)
{
int e, i, u, v;
printf("Enter number of vertices and edges: ");
scanf("%d %d", &n, &e);
for (i = 0; i < n; i++) list[i] = NULL;
printf("Enter %d edges (u v):\n", e);
for (i = 0; i < e; i++) {
scanf("%d %d", &u, &v);
adj[u][v] = 1;
adj[v][u] = 1; /* remove this line for directed graph */
addEdgeList(u, v);
}
displayMatrix();
displayList();
return 0;
}
Q2. Write a program in C to traverse a graph using Breadth First Search (BFS).
/* Unit IX - Program 2: BFS traversal using a queue O(V^2) with matrix */
#include <stdio.h>
#define MAX 20
int adj[MAX][MAX], visited[MAX], n;
int queue[MAX], front = 0, rear = 0;
void bfs(int start)
{
int current, i;
visited[start] = 1;
queue[rear++] = start;
printf("BFS traversal: ");
while (front < rear) {
current = queue[front++]; /* dequeue */
printf("%d ", current);
for (i = 0; i < n; i++) {
if (adj[current][i] == 1 && visited[i] == 0) {
visited[i] = 1;
queue[rear++] = i; /* enqueue unvisited neighbour */
}
}
}
printf("\n");
}
int main(void)
{
int i, j, start;
printf("Enter number of vertices: ");
scanf("%d", &n);
printf("Enter adjacency matrix (%dx%d):\n", n, n);
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
scanf("%d", &adj[i][j]);
for (i = 0; i < n; i++) visited[i] = 0;
printf("Enter starting vertex: ");
scanf("%d", &start);
bfs(start);
return 0;
}
/* Sample input:
4
0 1 1 0
1 0 0 1
1 0 0 1
0 1 1 0
0 -> BFS: 0 1 2 3 */
Q3. Write a program in C to traverse a graph using Depth First Search (DFS) — recursive and using a stack.
/* Unit IX - Program 3: DFS traversal - recursive and iterative (stack) */
#include <stdio.h>
#define MAX 20
int adj[MAX][MAX], visited[MAX], n;
void dfsRecursive(int v)
{
int i;
visited[v] = 1;
printf("%d ", v);
for (i = 0; i < n; i++)
if (adj[v][i] == 1 && !visited[i])
dfsRecursive(i);
}
void dfsIterative(int start)
{
int stack[MAX], top = -1, current, i;
stack[++top] = start;
while (top != -1) {
current = stack[top--]; /* pop */
if (!visited[current]) {
visited[current] = 1;
printf("%d ", current);
}
/* push neighbours in reverse so smallest is processed first */
for (i = n - 1; i >= 0; i--)
if (adj[current][i] == 1 && !visited[i])
stack[++top] = i;
}
}
int main(void)
{
int i, j, start;
printf("Enter number of vertices: ");
scanf("%d", &n);
printf("Enter adjacency matrix:\n");
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
scanf("%d", &adj[i][j]);
printf("Enter starting vertex: ");
scanf("%d", &start);
for (i = 0; i < n; i++) visited[i] = 0;
printf("DFS (recursive): ");
dfsRecursive(start);
for (i = 0; i < n; i++) visited[i] = 0;
printf("\nDFS (iterative): ");
dfsIterative(start);
printf("\n");
return 0;
}
Q4. Write a program in C to find the Minimum Spanning Tree using Prim's Algorithm.
/* Unit IX - Program 4: Prim's algorithm for Minimum Spanning Tree O(V^2) */
#include <stdio.h>
#define MAX 20
#define INF 9999
int cost[MAX][MAX], n;
void prim(void)
{
int visited[MAX], i, j, u = 0, v = 0, edgeCount = 0, minCost = 0, min;
for (i = 0; i < n; i++) visited[i] = 0;
visited[0] = 1; /* start from vertex 0 */
printf("Edges of Minimum Spanning Tree:\n");
while (edgeCount < n - 1) {
min = INF;
/* find minimum cost edge from visited set to unvisited set */
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
if (visited[i] == 1 && visited[j] == 0 && cost[i][j] < min) {
min = cost[i][j];
u = i;
v = j;
}
printf(" %d - %d weight = %d\n", u, v, min);
visited[v] = 1;
minCost += min;
edgeCount++;
}
printf("Total minimum cost = %d\n", minCost);
}
int main(void)
{
int i, j;
printf("Enter number of vertices: ");
scanf("%d", &n);
printf("Enter cost matrix (0 or 9999 for no edge):\n");
for (i = 0; i < n; i++)
for (j = 0; j < n; j++) {
scanf("%d", &cost[i][j]);
if (cost[i][j] == 0) cost[i][j] = INF; /* no edge */
}
prim();
return 0;
}
/* Sample input (4 vertices):
4
0 10 6 5
10 0 0 15
6 0 0 4
5 15 4 0 */
Q5. Write a program in C to find the Minimum Spanning Tree using Kruskal's Algorithm.
/* Unit IX - Program 5: Kruskal's algorithm using Union-Find O(E log E) */
#include <stdio.h>
#include <stdlib.h>
#define MAX 50
struct Edge {
int u, v, weight;
};
struct Edge edges[MAX];
int parent[MAX];
int n, e;
int find(int i) /* find set of element i */
{
while (parent[i] != i)
i = parent[i];
return i;
}
void unionSet(int a, int b)
{
parent[find(a)] = find(b);
}
/* sort edges in ascending order of weight (simple bubble sort) */
void sortEdges(void)
{
int i, j;
struct Edge temp;
for (i = 0; i < e - 1; i++)
for (j = 0; j < e - 1 - i; j++)
if (edges[j].weight > edges[j + 1].weight) {
temp = edges[j];
edges[j] = edges[j + 1];
edges[j + 1] = temp;
}
}
void kruskal(void)
{
int i, count = 0, totalCost = 0, setU, setV;
for (i = 0; i < n; i++) parent[i] = i; /* each vertex is its own set */
sortEdges();
printf("Edges of Minimum Spanning Tree:\n");
for (i = 0; i < e && count < n - 1; i++) {
setU = find(edges[i].u);
setV = find(edges[i].v);
if (setU != setV) { /* no cycle formed */
printf(" %d - %d weight = %d\n", edges[i].u, edges[i].v, edges[i].weight);
unionSet(setU, setV);
totalCost += edges[i].weight;
count++;
}
}
printf("Total minimum cost = %d\n", totalCost);
}
int main(void)
{
int i;
printf("Enter number of vertices and edges: ");
scanf("%d %d", &n, &e);
printf("Enter each edge as: u v weight\n");
for (i = 0; i < e; i++)
scanf("%d %d %d", &edges[i].u, &edges[i].v, &edges[i].weight);
kruskal();
return 0;
}
/* Sample input:
4 5
0 1 10
0 2 6
0 3 5
1 3 15
2 3 4 */
Q6. Write a program in C to find the shortest path from a source vertex using Dijkstra's Algorithm.
/* Unit IX - Program 6: Dijkstra's shortest path algorithm O(V^2) */
#include <stdio.h>
#define MAX 20
#define INF 9999
int cost[MAX][MAX], n;
void dijkstra(int source)
{
int distance[MAX], visited[MAX], parent[MAX];
int i, j, u = 0, min, count;
for (i = 0; i < n; i++) {
distance[i] = cost[source][i];
visited[i] = 0;
parent[i] = source;
}
distance[source] = 0;
visited[source] = 1;
count = 1;
while (count < n) {
min = INF;
for (i = 0; i < n; i++) /* pick nearest unvisited */
if (!visited[i] && distance[i] < min) { min = distance[i]; u = i; }
visited[u] = 1;
count++;
for (j = 0; j < n; j++) /* relax edges */
if (!visited[j] && distance[u] + cost[u][j] < distance[j]) {
distance[j] = distance[u] + cost[u][j];
parent[j] = u;
}
}
printf("\nShortest distances from vertex %d:\n", source);
for (i = 0; i < n; i++) {
if (i == source) continue;
printf(" To %d : distance = %d, path = %d", i, distance[i], i);
j = i;
while (j != source) { j = parent[j]; printf(" <- %d", j); }
printf("\n");
}
}
int main(void)
{
int i, j, source;
printf("Enter number of vertices: ");
scanf("%d", &n);
printf("Enter cost matrix (0 for no edge):\n");
for (i = 0; i < n; i++)
for (j = 0; j < n; j++) {
scanf("%d", &cost[i][j]);
if (cost[i][j] == 0 && i != j) cost[i][j] = INF;
}
printf("Enter source vertex: ");
scanf("%d", &source);
dijkstra(source);
return 0;
}
/* Sample input (5 vertices):
5
0 10 0 30 100
10 0 50 0 0
0 50 0 20 10
30 0 20 0 60
100 0 10 60 0
0 */
UNIT X — Growth Functions
Q1. Write a program in C to compare the growth rates of common complexity functions (Big O demonstration).
/* Unit X - Program 1: Growth rate comparison table
compile with: gcc prog.c -o prog -lm */
#include <stdio.h>
#include <math.h>
int main(void)
{
int nValues[] = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 1024 };
int count = sizeof(nValues) / sizeof(nValues[0]);
int i, n;
printf("%6s %8s %10s %12s %12s %16s\n",
"n", "log n", "n", "n log n", "n^2", "2^n");
printf("--------------------------------------------------------------------\n");
for (i = 0; i < count; i++) {
n = nValues[i];
printf("%6d %8.2f %10d %12.2f %12.0f ", n, log2((double) n), n,
n * log2((double) n), pow((double) n, 2));
if (n <= 40) printf("%16.0f\n", pow(2.0, (double) n));
else printf("%16s\n", "too large");
}
printf("\nGrowth order (slowest to fastest):\n");
printf("O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)\n");
return 0;
}
Q2. Write a program in C that counts the basic operations of different algorithms to verify their Big O, Omega and Theta complexity.
/* Unit X - Program 2: Verifying Big O (worst), Omega (best) and Theta (average)
using operation counting on Linear Search and Bubble Sort */
#include <stdio.h>
long steps;
/* Linear search: Omega(1) best, O(n) worst, Theta(n) average */
int linearSearch(int a[], int n, int key)
{
int i;
steps = 0;
for (i = 0; i < n; i++) {
steps++;
if (a[i] == key) return i;
}
return -1;
}
/* Bubble sort: Omega(n) best (sorted), O(n^2) worst (reverse sorted) */
void bubbleSort(int a[], int n)
{
int i, j, t, swapped;
steps = 0;
for (i = 0; i < n - 1; i++) {
swapped = 0;
for (j = 0; j < n - 1 - i; j++) {
steps++;
if (a[j] > a[j + 1]) {
t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
swapped = 1;
}
}
if (!swapped) break;
}
}
int main(void)
{
int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; /* already sorted */
int b[] = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 }; /* reverse sorted */
int n = 10;
printf("=== LINEAR SEARCH (n = %d) ===\n", n);
linearSearch(a, n, 1);
printf("Best case (first element) : steps = %ld -> Omega(1)\n", steps);
linearSearch(a, n, 10);
printf("Worst case (last element) : steps = %ld -> O(n)\n", steps);
linearSearch(a, n, 99);
printf("Not found : steps = %ld -> O(n)\n", steps);
printf("\n=== BUBBLE SORT (n = %d) ===\n", n);
bubbleSort(a, n);
printf("Best case (sorted input) : steps = %ld -> Omega(n)\n", steps);
bubbleSort(b, n);
printf("Worst case (reverse input) : steps = %ld -> O(n^2)\n", steps);
printf("\nLimitation of Big O: it gives only an upper bound, it hides\n");
printf("constants and lower order terms, and it says nothing about the\n");
printf("best or average case (Omega and Theta are needed for those).\n");
return 0;
}
Quick Revision — Complexity Table
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Shell Sort | O(n log n) | O(n^1.25) | O(n²) | O(1) | No |
| Linear Search | O(1) | O(n) | O(n) | O(1) | — |
| Binary Search | O(1) | O(log n) | O(log n) | O(1) | — |
| BST operations | O(log n) | O(log n) | O(n) | O(n) | — |
| AVL operations | O(log n) | O(log n) | O(log n) | O(n) | — |
| Hashing | O(1) | O(1) | O(n) | O(n) | — |
| BFS / DFS | — | O(V+E) | O(V²) matrix | O(V) | — |
| Prim's | — | O(V²) | O(V²) | O(V) | — |
| Kruskal's | — | O(E log E) | O(E log E) | O(V) | — |
| Dijkstra's | — | O(V²) | O(V²) | O(V) | — |
Compile & run any program:
gcc program.c -o program
./program
Add -lm for the programs that use math.h (postfix evaluation, growth functions).