C program Linked List

write c program to implement a linked list just give me the program i don't any explanation or
definition

#include <stdio.h>
#include <stdlib.h>

// Define the structure for a node

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

// Function to create a new node

struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}

// Function to insert a node at the beginning

struct Node* insertAtBeginning(struct Node* head, int data) {
struct Node* newNode = createNode(data);
newNode->next = head;
return newNode;
}

// Function to insert a node at the end

struct Node* insertAtEnd(struct Node* head, int data) {
struct Node* newNode = createNode(data);
if (head == NULL) {
return newNode;
}
struct Node* temp = head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
return head;
}

// Function to delete a node by value

struct Node* deleteNode(struct Node* head, int key) {
struct Node* temp = head;
struct Node* prev = NULL;

if (temp != NULL && temp->data == key) {

head = temp->next;
free(temp);
return head;
}

while (temp != NULL && temp->data != key) {

prev = temp;
temp = temp->next;
}

Printed using Save ChatGPT as PDF, powered by PDFCrowd HTML to PDF API. 1/21
 if (temp == NULL) return head;

prev->next = temp->next;
free(temp);
return head;
}

// Function to display the linked list

void displayList(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}

// Main function
int main() {
struct Node* head = NULL;

head = insertAtEnd(head, 10);

head = insertAtEnd(head, 20);
head = insertAtEnd(head, 30);
displayList(head);

head = insertAtBeginning(head, 5);

displayList(head);

head = deleteNode(head, 20);

displayList(head);

return 0;
}

write a c program to implement queue using linked list give me the program i don't want any
explanation or definition

#include <stdio.h>
#include <stdlib.h>

// Define the structure for a node

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

// Define the structure for the queue

struct Queue {
struct Node* front;
struct Node* rear;
};

// Function to create a new node

struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;

Printed using Save ChatGPT as PDF, powered by PDFCrowd HTML to PDF API. 2/21
 }

// Function to create a new queue

struct Queue* createQueue() {
struct Queue* q = (struct Queue*)malloc(sizeof(struct Queue));
q->front = NULL;
q->rear = NULL;
return q;
}

// Function to enqueue an element

void enqueue(struct Queue* q, int data) {
struct Node* newNode = createNode(data);
if (q->rear == NULL) {
q->front = q->rear = newNode;
return;
}
q->rear->next = newNode;
q->rear = newNode;
}

// Function to dequeue an element

int dequeue(struct Queue* q) {
if (q->front == NULL) {
printf("Queue is empty.\n");
return -1;
}
struct Node* temp = q->front;
int data = temp->data;
q->front = q->front->next;
if (q->front == NULL) {
q->rear = NULL;
}
free(temp);
return data;
}

// Function to display the queue

void displayQueue(struct Queue* q) {
struct Node* temp = q->front;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}

// Main function
int main() {
struct Queue* q = createQueue();

enqueue(q, 10);
enqueue(q, 20);
enqueue(q, 30);
displayQueue(q);

printf("Dequeued: %d\n", dequeue(q));

displayQueue(q);

printf("Dequeued: %d\n", dequeue(q));

displayQueue(q);

return 0;
}

write a c program to implement a stack using linked list give me only the program i dont want any
explanation or definition

Printed using Save ChatGPT as PDF, powered by PDFCrowd HTML to PDF API. 3/21
 c

#include <stdio.h>
#include <stdlib.h>

// Define the structure for a node

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

// Function to create a new node

struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}

// Function to push an element onto the stack

struct Node* push(struct Node* top, int data) {
struct Node* newNode = createNode(data);
newNode->next = top;
return newNode;
}

// Function to pop an element from the stack

struct Node* pop(struct Node* top, int* poppedData) {
if (top == NULL) {
printf("Stack is empty.\n");
*poppedData = -1;
return NULL;
}
struct Node* temp = top;
*poppedData = temp->data;
top = top->next;
free(temp);
return top;
}

// Function to display the stack

void displayStack(struct Node* top) {
struct Node* temp = top;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}

// Main function
int main() {
struct Node* top = NULL;
int poppedData;

top = push(top, 10);

top = push(top, 20);
top = push(top, 30);
displayStack(top);

top = pop(top, &poppedData);

printf("Popped: %d\n", poppedData);
displayStack(top);

top = pop(top, &poppedData);

printf("Popped: %d\n", poppedData);
displayStack(top);

Printed using Save ChatGPT as PDF, powered by PDFCrowd HTML to PDF API. 4/21
 return 0;
}

give me a c program to implement binary search tree

#include <stdio.h>
#include <stdlib.h>

// Define the structure for a tree node

struct Node {
int data;
struct Node* left;
struct Node* right;
};

// Function to create a new node

struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}

// Function to insert a node into the binary search tree

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);
}
return root;
}

// Function to perform an inorder traversal of the tree

void inorderTraversal(struct Node* root) {
if (root != NULL) {
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
}

// Function to search for a value in the tree

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);
}

// Main function
int main() {
struct Node* root = NULL;

Printed using Save ChatGPT as PDF, powered by PDFCrowd HTML to PDF API. 5/21
 root = insert(root, 50);
root = insert(root, 30);
root = insert(root, 70);
root = insert(root, 20);
root = insert(root, 40);
root = insert(root, 60);
root = insert(root, 80);

printf("Inorder traversal: ");

inorderTraversal(root);
printf("\n");

int key = 40;

struct Node* result = search(root, key);
if (result != NULL) {
printf("Found %d in the tree.\n", key);
} else {
printf("%d not found in the tree.\n", key);
}

return 0;
}

c program for avl tree

#include <stdio.h>
#include <stdlib.h>

// Define the structure for a node in the AVL tree

struct Node {
int data;
struct Node* left;
struct Node* right;
int height;
};

// Function to get the height of a node

int height(struct Node* node) {
if (node == NULL) {
return 0;
}
return node->height;
}

// Function to get the maximum of two integers

int max(int a, int b) {
return (a > b) ? a : b;
}

// Function to create a new node

struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
newNode->height = 1;
return newNode;
}

// Function to perform a right rotation

Printed using Save ChatGPT as PDF, powered by PDFCrowd HTML to PDF API. 6/21
 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;
}

// Function to perform a left rotation

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;
}

// Function to get the balance factor of a node

int getBalance(struct Node* node) {
if (node == NULL) {
return 0;
}
return height(node->left) - height(node->right);
}

// Function to insert a node into the AVL tree

struct Node* insert(struct Node* node, int data) {
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;
}

node->height = max(height(node->left), height(node->right)) + 1;

int balance = getBalance(node);

if (balance > 1 && data < node->left->data) {

return rightRotate(node);
}
if (balance < -1 && data > node->right->data) {
return leftRotate(node);
}
if (balance > 1 && data > node->left->data) {
node->left = leftRotate(node->left);
return rightRotate(node);
}
if (balance < -1 && data < node->right->data) {
node->right = rightRotate(node->right);
return leftRotate(node);
}

return node;
}

// Function to perform an inorder traversal of the AVL tree

void inorderTraversal(struct Node* root) {
if (root != NULL) {
inorderTraversal(root->left);
printf("%d ", root->data);
Printed using Save ChatGPT as PDF, powered by PDFCrowd HTML to PDF API. 7/21
 inorderTraversal(root->right);
}
}

// Main function
int main() {
struct Node* root = NULL;

root = insert(root, 10);

root = insert(root, 20);
root = insert(root, 30);
root = insert(root, 40);
root = insert(root, 50);
root = insert(root, 25);

printf("Inorder traversal of the AVL tree: ");

inorderTraversal(root);
printf("\n");

return 0;
}

binary heap

Here is a C program to implement a binary heap (min-heap):

#include <stdio.h>

#define MAX_SIZE 100

int heap[MAX_SIZE];
int heapSize = 0;

// Function to swap two elements

void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}

// Function to insert an element into the heap

void insert(int value) {
if (heapSize >= MAX_SIZE) {
printf("Heap overflow.\n");
return;
}

heap[heapSize] = value;
int current = heapSize;
heapSize++;

while (current > 0 && heap[current] < heap[(current - 1) / 2]) {

swap(&heap[current], &heap[(current - 1) / 2]);
current = (current - 1) / 2;
}
}

// Function to heapify the tree at a given index

void heapify(int index) {
int smallest = index;

Printed using Save ChatGPT as PDF, powered by PDFCrowd HTML to PDF API. 8/21
 int left = 2 * index + 1;
int right = 2 * index + 2;

if (left < heapSize && heap[left] < heap[smallest]) {

smallest = left;
}
if (right < heapSize && heap[right] < heap[smallest]) {
smallest = right;
}
if (smallest != index) {
swap(&heap[index], &heap[smallest]);
heapify(smallest);
}
}

// Function to remove the minimum element (root) from the heap

int removeMin() {
if (heapSize <= 0) {
printf("Heap underflow.\n");
return -1;
}

int root = heap[0];

heap[0] = heap[heapSize - 1];
heapSize--;
heapify(0);

return root;
}

// Function to display the elements of the heap

void displayHeap() {
for (int i = 0; i < heapSize; i++) {
printf("%d ", heap[i]);
}
printf("\n");
}

// Main function
int main() {
insert(10);
insert(20);
insert(15);
insert(30);
insert(5);

printf("Heap elements: ");

displayHeap();

printf("Removed min: %d\n", removeMin());

printf("Heap after removing min: ");
displayHeap();

return 0;
}

Features:

1. Insert: Adds an element while maintaining the heap property.

2. RemoveMin: Removes the smallest element (root of the min-heap).
3. DisplayHeap: Prints the elements in the heap array.

MAX and MIN Binary Heap

Printed using Save ChatGPT as PDF, powered by PDFCrowd HTML to PDF API. 9/21
Below is a C program implementing both Min-Heap and Max-Heap operations:

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

int minHeap[MAX_SIZE], maxHeap[MAX_SIZE];

int minHeapSize = 0, maxHeapSize = 0;

// Utility function to swap two elements

void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}

/*-------------------- MIN HEAP FUNCTIONS --------------------*/

// Insert into Min-Heap

void insertMinHeap(int value) {
if (minHeapSize >= MAX_SIZE) {
printf("Min-Heap overflow.\n");
return;
}
minHeap[minHeapSize] = value;
int current = minHeapSize;
minHeapSize++;

while (current > 0 && minHeap[current] < minHeap[(current - 1) / 2]) {

swap(&minHeap[current], &minHeap[(current - 1) / 2]);
current = (current - 1) / 2;
}
}

// Heapify Min-Heap
void minHeapify(int index) {
int smallest = index;
int left = 2 * index + 1;
int right = 2 * index + 2;

if (left < minHeapSize && minHeap[left] < minHeap[smallest]) {

smallest = left;
}
if (right < minHeapSize && minHeap[right] < minHeap[smallest]) {
smallest = right;
}
if (smallest != index) {
swap(&minHeap[index], &minHeap[smallest]);
minHeapify(smallest);
}
}

// Remove minimum element from Min-Heap

int removeMin() {
if (minHeapSize <= 0) {
printf("Min-Heap underflow.\n");
return -1;
}

int root = minHeap[0];

minHeap[0] = minHeap[minHeapSize - 1];
minHeapSize--;
minHeapify(0);

return root;
}

Printed using Save ChatGPT as PDF, powered by PDFCrowd HTML to PDF API. 10/21
 /*-------------------- MAX HEAP FUNCTIONS --------------------*/

// Insert into Max-Heap

void insertMaxHeap(int value) {
if (maxHeapSize >= MAX_SIZE) {
printf("Max-Heap overflow.\n");
return;
}
maxHeap[maxHeapSize] = value;
int current = maxHeapSize;
maxHeapSize++;

while (current > 0 && maxHeap[current] > maxHeap[(current - 1) / 2]) {

swap(&maxHeap[current], &maxHeap[(current - 1) / 2]);
current = (current - 1) / 2;
}
}

// Heapify Max-Heap
void maxHeapify(int index) {
int largest = index;
int left = 2 * index + 1;
int right = 2 * index + 2;

if (left < maxHeapSize && maxHeap[left] > maxHeap[largest]) {

largest = left;
}
if (right < maxHeapSize && maxHeap[right] > maxHeap[largest]) {
largest = right;
}
if (largest != index) {
swap(&maxHeap[index], &maxHeap[largest]);
maxHeapify(largest);
}
}

// Remove maximum element from Max-Heap

int removeMax() {
if (maxHeapSize <= 0) {
printf("Max-Heap underflow.\n");
return -1;
}

int root = maxHeap[0];

maxHeap[0] = maxHeap[maxHeapSize - 1];
maxHeapSize--;
maxHeapify(0);

return root;
}

/*-------------------- DISPLAY FUNCTIONS --------------------*/

void displayMinHeap() {
for (int i = 0; i < minHeapSize; i++) {
printf("%d ", minHeap[i]);
}
printf("\n");
}

void displayMaxHeap() {
for (int i = 0; i < maxHeapSize; i++) {
printf("%d ", maxHeap[i]);
}
printf("\n");
}

/*-------------------- MAIN FUNCTION --------------------*/

int main() {
// Min-Heap Operations
printf("Min-Heap:\n");
insertMinHeap(10);
insertMinHeap(20);
insertMinHeap(5);
Printed using Save ChatGPT as PDF, powered by PDFCrowd HTML to PDF API. 11/21
 insertMinHeap(15);
printf("Heap elements: ");
displayMinHeap();
printf("Removed Min: %d\n", removeMin());
printf("Heap after removal: ");
displayMinHeap();

// Max-Heap Operations
printf("\nMax-Heap:\n");
insertMaxHeap(10);
insertMaxHeap(20);
insertMaxHeap(5);
insertMaxHeap(15);
printf("Heap elements: ");
displayMaxHeap();
printf("Removed Max: %d\n", removeMax());
printf("Heap after removal: ");
displayMaxHeap();

return 0;
}

Features:

1. Min-Heap Functions:
`insertMinHeap`:
Insert an element into the Min-Heap.
`removeMin`: Remove the minimum (root) element from the Min-Heap.
`displayMinHeap`: Display elements in the Min-Heap.
2. Max-Heap Functions:
`insertMaxHeap`:Insert an element into the Max-Heap.
`removeMax`:Remove the maximum (root) element from the Max-Heap.
`displayMaxHeap`: Display elements in the Max-Heap.

for every program i ask here afterward dont give any explanation and definiton

Understood.

Polynomial Addition, Subtraction and Multiplication using linked list

#include <stdio.h>
#include <stdlib.h>

// Define the structure for a node in the linked list

struct Node {
int coeff;

Printed using Save ChatGPT as PDF, powered by PDFCrowd HTML to PDF API. 12/21
 int exp;
struct Node* next;
};

// Function to create a new node

struct Node* createNode(int coeff, int exp) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->coeff = coeff;
newNode->exp = exp;
newNode->next = NULL;
return newNode;
}

// Function to insert a node in the polynomial list

void insert(struct Node** poly, int coeff, int exp) {
struct Node* newNode = createNode(coeff, exp);
if (*poly == NULL || (*poly)->exp < exp) {
newNode->next = *poly;
*poly = newNode;
} else {
struct Node* temp = *poly;
while (temp->next != NULL && temp->next->exp > exp) {
temp = temp->next;
}
if (temp->exp == exp) {
temp->coeff += coeff;
} else {
newNode->next = temp->next;
temp->next = newNode;
}
}
}

// Function to display the polynomial

void display(struct Node* poly) {
while (poly != NULL) {
printf("%dx^%d", poly->coeff, poly->exp);
if (poly->next != NULL) {
printf(" + ");
}
poly = poly->next;
}
printf("\n");
}

// Function to add two polynomials

struct Node* add(struct Node* poly1, struct Node* poly2) {
struct Node* result = NULL;
while (poly1 != NULL && poly2 != NULL) {
if (poly1->exp > poly2->exp) {
insert(&result, poly1->coeff, poly1->exp);
poly1 = poly1->next;
} else if (poly1->exp < poly2->exp) {
insert(&result, poly2->coeff, poly2->exp);
poly2 = poly2->next;
} else {
int coeff = poly1->coeff + poly2->coeff;
if (coeff != 0) {
insert(&result, coeff, poly1->exp);
}
poly1 = poly1->next;
poly2 = poly2->next;
}
}
while (poly1 != NULL) {
insert(&result, poly1->coeff, poly1->exp);
poly1 = poly1->next;
}
while (poly2 != NULL) {
insert(&result, poly2->coeff, poly2->exp);
poly2 = poly2->next;
}
return result;
}

Printed using Save ChatGPT as PDF, powered by PDFCrowd HTML to PDF API. 13/21
 // Function to subtract two polynomials
struct Node* subtract(struct Node* poly1, struct Node* poly2) {
struct Node* result = NULL;
while (poly1 != NULL && poly2 != NULL) {
if (poly1->exp > poly2->exp) {
insert(&result, poly1->coeff, poly1->exp);
poly1 = poly1->next;
} else if (poly1->exp < poly2->exp) {
insert(&result, -poly2->coeff, poly2->exp);
poly2 = poly2->next;
} else {
int coeff = poly1->coeff - poly2->coeff;
if (coeff != 0) {
insert(&result, coeff, poly1->exp);
}
poly1 = poly1->next;
poly2 = poly2->next;
}
}
while (poly1 != NULL) {
insert(&result, poly1->coeff, poly1->exp);
poly1 = poly1->next;
}
while (poly2 != NULL) {
insert(&result, -poly2->coeff, poly2->exp);
poly2 = poly2->next;
}
return result;
}

// Function to multiply two polynomials

struct Node* multiply(struct Node* poly1, struct Node* poly2) {
struct Node* result = NULL;
for (struct Node* p1 = poly1; p1 != NULL; p1 = p1->next) {
for (struct Node* p2 = poly2; p2 != NULL; p2 = p2->next) {
int coeff = p1->coeff * p2->coeff;
int exp = p1->exp + p2->exp;
insert(&result, coeff, exp);
}
}
return result;
}

// Main function
int main() {
struct Node* poly1 = NULL;
struct Node* poly2 = NULL;

insert(&poly1, 5, 2);
insert(&poly1, 4, 1);
insert(&poly1, 2, 0);

insert(&poly2, 3, 2);
insert(&poly2, 1, 1);
insert(&poly2, 4, 0);

printf("Polynomial 1: ");
display(poly1);

printf("Polynomial 2: ");
display(poly2);

struct Node* sum = add(poly1, poly2);

printf("Sum: ");
display(sum);

struct Node* diff = subtract(poly1, poly2);

printf("Difference: ");
display(diff);

struct Node* prod = multiply(poly1, poly2);

printf("Product: ");
display(prod);

Printed using Save ChatGPT as PDF, powered by PDFCrowd HTML to PDF API. 14/21
 return 0;
}

Infix to Postfix conversion

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

#define MAX_SIZE 100

// Stack structure
struct Stack {
int top;
char arr[MAX_SIZE];
};

// Function to initialize the stack

void initStack(struct Stack* stack) {
stack->top = -1;
}

// Function to check if the stack is empty

int isEmpty(struct Stack* stack) {
return stack->top == -1;
}

// Function to push an element onto the stack

void push(struct Stack* stack, char value) {
if (stack->top < MAX_SIZE - 1) {
stack->arr[++stack->top] = value;
}
}

// Function to pop an element from the stack

char pop(struct Stack* stack) {
if (!isEmpty(stack)) {
return stack->arr[stack->top--];
}
return -1;
}

// Function to get the top element of the stack

char peek(struct Stack* stack) {
if (!isEmpty(stack)) {
return stack->arr[stack->top];
}
return -1;
}

// Function to check precedence of operators

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

Printed using Save ChatGPT as PDF, powered by PDFCrowd HTML to PDF API. 15/21
 }

// Function to check if a character is an operator

int isOperator(char ch) {
return ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '^';
}

// Function to convert infix to postfix

void infixToPostfix(char* infix, char* postfix) {
struct Stack stack;
initStack(&stack);
int j = 0;

for (int i = 0; infix[i] != '\0'; i++) {

char current = infix[i];

// If current character is an operand, add it to the postfix expression

if (isalnum(current)) {
postfix[j++] = current;
}
// If current character is '(', push it to the stack
else if (current == '(') {
push(&stack, current);
}
// If current character is ')', pop until '('
else if (current == ')') {
while (!isEmpty(&stack) && peek(&stack) != '(') {
postfix[j++] = pop(&stack);
}
pop(&stack); // Pop '(' from the stack
}
// If current character is an operator
else if (isOperator(current)) {
while (!isEmpty(&stack) && precedence(peek(&stack)) >= precedence(current)) {
postfix[j++] = pop(&stack);
}
push(&stack, current);
}
}

// Pop any remaining operators from the stack

while (!isEmpty(&stack)) {
postfix[j++] = pop(&stack);
}

postfix[j] = '\0'; // Null-terminate the postfix string

}

// Main function
int main() {
char infix[MAX_SIZE], postfix[MAX_SIZE];

printf("Enter infix expression: ");

gets(infix);

infixToPostfix(infix, postfix);

printf("Postfix expression: ");

puts(postfix);

return 0;
}

Dijkstra's Algorithm

Printed using Save ChatGPT as PDF, powered by PDFCrowd HTML to PDF API. 16/21
 c

#include <stdio.h>
#include <limits.h>

#define V 9

// Find the vertex with the minimum distance value

int minDistance(int dist[], int sptSet[]) {
int min = INT_MAX, min_index;

for (int v = 0; v < V; v++) {

if (sptSet[v] == 0 && dist[v] <= min) {
min = dist[v];
min_index = v;
}
}
return min_index;
}

// Dijkstra's Algorithm to find the shortest path from a source vertex

void dijkstra(int graph[V][V], int src) {
int dist[V]; // Array to store the shortest distance from source
int sptSet[V]; // Set of vertices not yet processed

// Initialize all distances to INFINITY and sptSet[] to false

for (int i = 0; i < V; i++) {
dist[i] = INT_MAX;
sptSet[i] = 0;
}
dist[src] = 0; // Distance to the source is 0

// Find the shortest path for all vertices

for (int count = 0; count < V - 1; count++) {
int u = minDistance(dist, sptSet); // Get the vertex with the minimum distance
sptSet[u] = 1; // Mark the picked vertex as processed

// Update dist[] for the adjacent vertices of the picked vertex

for (int v = 0; v < V; v++) {
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < d
ist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}

// Print the shortest distance from source to all vertices

printf("Vertex\tDistance from Source\n");
for (int i = 0; i < V; i++) {
printf("%d\t%d\n", i, dist[i]);
}
}

// Main function
int main() {
// Example graph represented as an adjacency matrix
int graph[V][V] = {
{0, 4, 0, 0, 0, 0, 0, 8, 0},
{4, 0, 8, 0, 0, 0, 0, 11, 0},
{0, 8, 0, 7, 0, 4, 0, 0, 2},
{0, 0, 7, 0, 9, 14, 0, 0, 0},
{0, 0, 0, 9, 0, 10, 0, 0, 0},
{0, 0, 4, 14, 10, 0, 2, 0, 0},
{0, 0, 0, 0, 0, 2, 0, 1, 6},
{8, 11, 0, 0, 0, 0, 1, 0, 7},
{0, 0, 2, 0, 0, 0, 6, 7, 0}
};

int src = 0; // Source vertex

dijkstra(graph, src);

Printed using Save ChatGPT as PDF, powered by PDFCrowd HTML to PDF API. 17/21
 return 0;
}

Dijkstra's Algorithm to find shortest path in a graph

#include <stdio.h>
#include <limits.h>

#define V 9

// Function to find the vertex with the minimum distance value

int minDistance(int dist[], int sptSet[]) {
int min = INT_MAX, min_index;

for (int v = 0; v < V; v++) {

if (sptSet[v] == 0 && dist[v] <= min) {
min = dist[v];
min_index = v;
}
}
return min_index;
}

// Function to implement Dijkstra's algorithm to find the shortest path

void dijkstra(int graph[V][V], int src) {
int dist[V]; // Array to store the shortest distance from source
int sptSet[V]; // Set of vertices not yet processed

// Initialize all distances as INFINITE and sptSet[] as false

for (int i = 0; i < V; i++) {
dist[i] = INT_MAX;
sptSet[i] = 0;
}
dist[src] = 0; // Distance from source to source is 0

// Find the shortest path for all vertices

for (int count = 0; count < V - 1; count++) {
int u = minDistance(dist, sptSet); // Get the vertex with the minimum distance
sptSet[u] = 1; // Mark the picked vertex as processed

// Update dist[] for the adjacent vertices of the picked vertex

for (int v = 0; v < V; v++) {
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < d
ist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}

// Print the shortest distance from the source to all other vertices
printf("Vertex\tDistance from Source\n");
for (int i = 0; i < V; i++) {
printf("%d\t%d\n", i, dist[i]);
}
}

// Main function
int main() {
// Example graph represented as an adjacency matrix
int graph[V][V] = {

Printed using Save ChatGPT as PDF, powered by PDFCrowd HTML to PDF API. 18/21
 {0, 4, 0, 0, 0, 0, 0, 8, 0},
{4, 0, 8, 0, 0, 0, 0, 11, 0},
{0, 8, 0, 7, 0, 4, 0, 0, 2},
{0, 0, 7, 0, 9, 14, 0, 0, 0},
{0, 0, 0, 9, 0, 10, 0, 0, 0},
{0, 0, 4, 14, 10, 0, 2, 0, 0},
{0, 0, 0, 0, 0, 2, 0, 1, 6},
{8, 11, 0, 0, 0, 0, 1, 0, 7},
{0, 0, 2, 0, 0, 0, 6, 7, 0}
};

int src = 0; // Source vertex

dijkstra(graph, src);

return 0;
}

Prim's Algorithm

#include <stdio.h>
#include <limits.h>

#define V 5

// Function to find the vertex with the minimum key value

int minKey(int key[], int mstSet[]) {
int min = INT_MAX, min_index;

for (int v = 0; v < V; v++) {

if (mstSet[v] == 0 && key[v] < min) {
min = key[v];
min_index = v;
}
}
return min_index;
}

// Function to implement Prim's algorithm for minimum spanning tree (MST)

void primMST(int graph[V][V]) {
int parent[V]; // Array to store constructed MST
int key[V]; // Key values to pick minimum weight edge
int mstSet[V]; // To represent the vertices that are included in MST

// Initialize all keys as INFINITE and mstSet[] as false

for (int i = 0; i < V; i++) {
key[i] = INT_MAX;
mstSet[i] = 0;
}

key[0] = 0; // Start with the first vertex

parent[0] = -1; // First node is always root of MST

// Find the minimum spanning tree

for (int count = 0; count < V - 1; count++) {
int u = minKey(key, mstSet); // Pick the minimum key vertex
mstSet[u] = 1; // Add the picked vertex to MST

// Update the key values and parent index of adjacent vertices

for (int v = 0; v < V; v++) {
if (graph[u][v] && mstSet[v] == 0 && graph[u][v] < key[v]) {

Printed using Save ChatGPT as PDF, powered by PDFCrowd HTML to PDF API. 19/21
 parent[v] = u;
key[v] = graph[u][v];
}
}
}

// Print the constructed MST

printf("Edge \tWeight\n");
for (int i = 1; i < V; i++) {
printf("%d - %d \t%d\n", parent[i], i, graph[i][parent[i]]);
}
}

// Main function
int main() {
// Example graph represented as an adjacency matrix
int graph[V][V] = {
{0, 2, 0, 6, 0},
{2, 0, 3, 8, 5},
{0, 3, 0, 0, 7},
{6, 8, 0, 0, 9},
{0, 5, 7, 9, 0}
};

primMST(graph);

return 0;
}

evaluate Postfix

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <math.h>

#define MAX_SIZE 100

// Stack structure
struct Stack {
int top;
int arr[MAX_SIZE];
};

// Function to initialize the stack

void initStack(struct Stack* stack) {
stack->top = -1;
}

// Function to check if the stack is empty

int isEmpty(struct Stack* stack) {
return stack->top == -1;
}

// Function to push an element onto the stack

void push(struct Stack* stack, int value) {
if (stack->top < MAX_SIZE - 1) {
stack->arr[++stack->top] = value;
}
}

Printed using Save ChatGPT as PDF, powered by PDFCrowd HTML to PDF API. 20/21
 // Function to pop an element from the stack
int pop(struct Stack* stack) {
if (!isEmpty(stack)) {
return stack->arr[stack->top--];
}
return -1;
}

// Function to evaluate the postfix expression

int evaluatePostfix(char* expr) {
struct Stack stack;
initStack(&stack);

for (int i = 0; expr[i] != '\0'; i++) {

char current = expr[i];

// If the current character is a digit, push it onto the stack

if (isdigit(current)) {
push(&stack, current - '0');
}
// If the current character is an operator
else if (current == '+' || current == '-' || current == '*' || current == '/') {
int operand2 = pop(&stack);
int operand1 = pop(&stack);

switch (current) {
case '+':
push(&stack, operand1 + operand2);
break;
case '-':
push(&stack, operand1 - operand2);
break;
case '*':
push(&stack, operand1 * operand2);
break;
case '/':
push(&stack, operand1 / operand2);
break;
}
}
}

// The result is the only element left in the stack

return pop(&stack);
}

// Main function
int main() {
char expr[MAX_SIZE];

printf("Enter postfix expression: ");

scanf("%s", expr);

int result = evaluatePostfix(expr);

printf("Result: %d\n", result);

return 0;
}

Printed using Save ChatGPT as PDF, powered by PDFCrowd HTML to PDF API. 21/21