Data Structures C Programs
Unit 3 - Stack using Linked List
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
} Node;
Node* top = NULL;
void push(int value) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (!newNode) {
printf("Heap Overflow\n");
return;
}
newNode->data = value;
newNode->next = top;
top = newNode;
printf("%d pushed to stack\n", value);
}
void pop() {
if (top == NULL) {
printf("Stack Underflow\n");
return;
}
Node* temp = top;
top = top->next;
printf("Popped: %d\n", temp->data);
free(temp);
}
void display() {
if (top == NULL) {
printf("Stack is empty\n");
return;
}
Node* temp = top;
printf("Stack: ");
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
int main() {
push(10);
push(20);
push(30);
display();
pop();
display();
return 0;
}
Unit 3 - Infix to Postfix Conversion
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#define SIZE 100
char stack[SIZE];
int top = -1;
void push(char c) {
stack[++top] = c;
}
char pop() {
return stack[top--];
}
int precedence(char op) {
if (op == '^') return 3;
if (op == '*' || op == '/') return 2;
if (op == '+' || op == '-') return 1;
return 0;
}
int isOperator(char ch) {
return (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch ==
'^');
}
void infixToPostfix(char* infix, char* postfix) {
int i, j = 0;
char ch;
for (i = 0; infix[i]; i++) {
ch = infix[i];
if (isalnum(ch)) {
postfix[j++] = ch;
} else if (ch == '(') {
push(ch);
} else if (ch == ')') {
while (stack[top] != '(')
postfix[j++] = pop();
pop();
} else if (isOperator(ch)) {
while (top != -1 && precedence(stack[top]) >=
precedence(ch))
postfix[j++] = pop();
push(ch);
}
}
while (top != -1)
postfix[j++] = pop();
postfix[j] = '\0';
}
int main() {
char infix[SIZE], postfix[SIZE];
printf("Enter infix expression: ");
scanf("%s", infix);
infixToPostfix(infix, postfix);
printf("Postfix: %s\n", postfix);
return 0;
}
Unit 3 - Postfix Evaluation
#include <stdio.h>
#include <ctype.h>
#define SIZE 100
int stack[SIZE];
int top = -1;
void push(int val) {
stack[++top] = val;
}
int pop() {
return stack[top--];
}
int evaluatePostfix(char* exp) {
int i, a, b;
for (i = 0; exp[i]; i++) {
if (isdigit(exp[i])) {
push(exp[i] - '0');
} else {
b = pop();
a = pop();
switch (exp[i]) {
case '+': push(a + b); break;
case '-': push(a - b); break;
case '*': push(a * b); break;
case '/': push(a / b); break;
}
}
}
return pop();
}
int main() {
char exp[SIZE];
printf("Enter postfix expression: ");
scanf("%s", exp);
printf("Result: %d\n", evaluatePostfix(exp));
return 0;
}
Unit 3 - Circular Queue
#include <stdio.h>
#define SIZE 5
int queue[SIZE];
int front = -1, rear = -1;
int isFull() {
return (front == (rear + 1) % SIZE);
}
int isEmpty() {
return (front == -1);
}
void enqueue(int val) {
if (isFull()) {
printf("Queue is full\n");
return;
}
if (isEmpty()) front = 0;
rear = (rear + 1) % SIZE;
queue[rear] = val;
}
void dequeue() {
if (isEmpty()) {
printf("Queue is empty\n");
return;
}
printf("Deleted: %d\n", queue[front]);
if (front == rear)
front = rear = -1;
else
front = (front + 1) % SIZE;
}
void display() {
if (isEmpty()) {
printf("Queue is empty\n");
return;
}
int i = front;
printf("Queue: ");
while (1) {
printf("%d ", queue[i]);
if (i == rear) break;
i = (i + 1) % SIZE;
}
printf("\n");
}
int main() {
enqueue(10);
enqueue(20);
enqueue(30);
display();
dequeue();
display();
return 0;
}
Unit 4 - Binary Search Tree (BST) Operations
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *left, *right;
} Node;
Node* createNode(int data) {
Node* newNode = malloc(sizeof(Node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
Node* insert(Node* root, int data) {
if (root == NULL) return createNode(data);
if (data < root->data) root->left = insert(root->left, data);
else root->right = insert(root->right, data);
return root;
}
Node* search(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);
}
void inorder(Node* root) {
if (root) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
void preorder(Node* root) {
if (root) {
printf("%d ", root->data);
preorder(root->left);
preorder(root->right);
}
}
void postorder(Node* root) {
if (root) {
postorder(root->left);
postorder(root->right);
printf("%d ", root->data);
}
}
int main() {
Node* root = NULL;
int vals[] = {50, 30, 70, 20, 40, 60, 80};
for (int i = 0; i < 7; i++)
root = insert(root, vals[i]);
printf("In-order: "); inorder(root); printf("\n");
printf("Pre-order: "); preorder(root); printf("\n");
printf("Post-order: "); postorder(root); printf("\n");
int key = 40;
printf("Searching for %d: %s\n", key, search(root, key) ? "Found" :
"Not Found");
return 0;
}
Unit 5 - Graph using Adjacency List
#include <stdio.h>
#include <stdlib.h>
#define MAX 10
typedef struct Node {
int dest;
struct Node* next;
} Node;
typedef struct {
Node* head[MAX];
} Graph;
Graph* createGraph(int v) {
Graph* g = malloc(sizeof(Graph));
for (int i = 0; i < v; i++)
g->head[i] = NULL;
return g;
}
void addEdge(Graph* g, int src, int dest) {
Node* n = malloc(sizeof(Node));
n->dest = dest;
n->next = g->head[src];
g->head[src] = n;
}
void printGraph(Graph* g, int v) {
for (int i = 0; i < v; i++) {
printf("Adj[%d]:", i);
Node* temp = g->head[i];
while (temp) {
printf(" -> %d", temp->dest);
temp = temp->next;
}
printf("\n");
}
}
int main() {
int v = 5;
Graph* g = createGraph(v);
addEdge(g, 0, 1);
addEdge(g, 0, 2);
addEdge(g, 1, 3);
addEdge(g, 2, 4);
printGraph(g, v);
return 0;
}
Unit 5 - Breadth First Search (BFS)
#include <stdio.h>
#include <stdlib.h>
#define SIZE 100
int adj[SIZE][SIZE], visited[SIZE], queue[SIZE];
int front = 0, rear = -1;
void bfs(int start, int n) {
visited[start] = 1;
queue[++rear] = start;
while (front <= rear) {
int node = queue[front++];
printf("%d ", node);
for (int i = 0; i < n; i++) {
if (adj[node][i] && !visited[i]) {
visited[i] = 1;
queue[++rear] = i;
}
}
}
}
int main() {
int n = 5;
adj[0][1] = adj[1][0] = 1;
adj[0][2] = adj[2][0] = 1;
adj[1][3] = adj[3][1] = 1;
adj[2][4] = adj[4][2] = 1;
printf("BFS: ");
bfs(0, n);
return 0;
}
Unit 5 - Depth First Search (DFS)
#include <stdio.h>
int adj[10][10], visited[10];
void dfs(int node, int n) {
printf("%d ", node);
visited[node] = 1;
for (int i = 0; i < n; i++) {
if (adj[node][i] && !visited[i]) {
dfs(i, n);
}
}
}
int main() {
int n = 5;
adj[0][1] = adj[1][0] = 1;
adj[0][2] = adj[2][0] = 1;
adj[1][3] = adj[3][1] = 1;
adj[2][4] = adj[4][2] = 1;
printf("DFS: ");
dfs(0, n);
return 0;
}