ds programs
1)Write a program to sort a list using bubble sort and then apply binary search.
#include <stdio.h>
void main()
{
int array[10];
int i, j, num, temp, keynum;
int low, mid, high;
printf("Enter the size of the array \n");
scanf("%d", &num);
printf("Enter the elements one by one \n");
for (i = 0; i < num; i++)
{
scanf("%d", &array[i]);
}
printf("Input array elements \n");
for (i = 0; i < num; i++)
{
printf("%d\n", array[i]);
}
/* Bubble sorting begins */
for (i = 0; i < num; i++)
{
for (j = 0; j < (num - i - 1); j++)
{
if (array[j] > array[j + 1])
{
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
printf("Sorted array is...\n");
for (i = 0; i < num; i++)
{
printf("%d\n", array[i]);
}
printf("Enter the element to be searched \n");
scanf("%d", &keynum);
/* Binary searching begins */
low = 1;
high = num;
do
{
mid = (low + high) / 2;
if (keynum < array[mid])
high = mid - 1;
else if (keynum > array[mid])
low = mid + 1;
} while (keynum != array[mid] && low <= high);
if (keynum == array[mid])
{
printf("SEARCH SUCCESSFUL found at %d position\n",mid+1);
}
else
{
printf("SEARCH FAILED \n");
}
}
OUTPUT:
Enter the size of the array
5
Enter the elements one by one
4 7 2 9 1
Input array elements
4
7
2
9
1
Sorted array is...
1
2
4
7
9
Enter the element to be searched
4
SEARCH SUCCESSFUL found at 3 position
2) write a program to implement operations on a stack.
#include <stdio.h>
#include <stdlib.h>
#define LIMIT 100 // Specifying the maximum limit of the stack
/* Global declaration of variables */
int stack[LIMIT]; // Array implementation of stack
int top; // To insert and delete the data elements in the stack
int i; // To traverse the loop to while displaying the stack
int choice; // To choose either of the 3 stack operations
void push(); // Function used to insert the element into the stack
void pop(); // Function used to delete the element from the stack
void display(); // Function used to display all the elements in the stack according to LIFO rule
int main()
{
printf ("ARRAY IMPLEMENTATION USING STACKS\n\n");
top = -1; // Initializing top to -1 indicates that it is empty
do
{
printf("1. Insert\n2. Delete\n3. Display\n4. Exit\n\n");
printf("Enter your choice:");
scanf("%d",&choice);
switch(choice)
{
case 1:
push();
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
exit(0);
break;
default:
printf("Sorry, invalid choice!\n");
break;
}
} while(choice!=4);
return 0;
}
void push()
{
int element;
if(top == LIMIT- 1)
{
printf("Stack underflow\n");
}
else
{
printf("Enter the element to be inserted:");
scanf("%d", &element);
top++;
stack[top]=element;
}
}
void pop()
{
int element;
if(top == -1)
{
printf("Stack underflow\n");
}
else
{
element=stack[top];
printf("The deleted item is %d\n",stack[top]);
top--; // The element below the topmost element is deleted
}
}
void display()
{
if(top == -1)
{
printf("Stack underflow\n"); // Stack is empty
}
else if(top > 0)
{
printf("The elements of the stack are:\n");
for(i = top; i >= 0; i--) // top to bottom traversal
{
printf("%d\n",stack[i]);
}
}
}
OUTPUT:
ARRAY IMPLEMENTATION USING STACKS
1. Insert
2. Delete
3. Display
4. Exit
Enter your choice:1
Enter the element to be inserted:5
1. Insert
2. Delete
3. Display
4. Exit
Enter your choice:1
Enter the element to be inserted:2
1. Insert
2. Delete
3. Display
4. Exit
Enter your choice:1
Enter the element to be inserted:6
1. Insert
2. Delete
3. Display
4. Exit
Enter your choice:3
The elements of the stack are:
6
2
5
1. Insert
2. Delete
3. Display
4. Exit
Enter your choice:2
The deleted item is 6
1. Insert
2. Delete
3. Display
4. Exit
Enter your choice:3
The elements of the stack are:
2
5
1. Insert
2. Delete
3. Display
4. Exit
Enter your choice:4
3) write a program to implement operations on circular queues.
#include <stdio.h>
#define SIZE 5
int items[SIZE];
int front = -1, rear = -1;
// Check if the queue is full
int isFull() {
if ((front == rear + 1) || (front == 0 && rear == SIZE - 1))
return 1;
return 0;
}
// Check if the queue is empty
int isEmpty() {
if (front == -1) return 1;
return 0;
}
// Adding an element
void enQueue(int element) {
if (isFull())
printf("\n Queue is full!! \n");
else {
if (front == -1) front = 0;
rear = (rear + 1) % SIZE;
items[rear] = element;
printf("\n Inserted -> %d", element);
}
}
// Removing an element
int deQueue() {
int element;
if (isEmpty()) {
printf("\n Queue is empty !! \n");
return (-1);
} else {
element = items[front];
if (front == rear) {
front = -1;
rear = -1;
}
// Q has only one element, so we reset the
// queue after dequeing it. ?
else {
front = (front + 1) % SIZE;
}
printf("\n Deleted element -> %d \n", element);
return (element);
}
}
// Display the queue
void display() {
int i;
if (isEmpty())
printf(" \n Empty Queue\n");
else {
printf("\n Front -> %d ", front);
printf("\n Items -> ");
for (i = front; i != rear; i = (i + 1) % SIZE) {
printf("%d ", items[i]);
}
printf("%d ", items[i]);
printf("\n Rear -> %d \n", rear);
}
}
int main() {
// Fails because front = -1
deQueue();
enQueue(1);
enQueue(2);
enQueue(3);
enQueue(4);
enQueue(5);
// Fails to enqueue because front == 0 && rear == SIZE - 1
enQueue(6);
display();
deQueue();
display();
enQueue(7);
display();
// Fails to enqueue because front == rear + 1
enQueue(8);
return 0;
}
OUTPUT:
Queue is empty !!
Inserted -> 1
Inserted -> 2
Inserted -> 3
Inserted -> 4
Inserted -> 5
Queue is full!!
Front -> 0
Items -> 1 2 3 4 5
Rear -> 4
Deleted element -> 1
Front -> 1
Items -> 2 3 4 5
Rear -> 4
Inserted -> 7
Front -> 1
Items -> 2 3 4 5 7
Rear -> 0
Queue is full!!
4)write a program for evaluating a given postfix expression using stack.
#include<stdio.h>int stack[20];int top = -1; void push(int x){ stack[++top] = x;} int pop(){ return stack[top--];} int main(){ char exp[20]; char *e; int n1,n2,n3,num; printf("Enter the expression :: "); scanf("%s",exp); e = exp; while(*e != '\0') { if(isdigit(*e)) { num = *e - 48; push(num); } else { n1 = pop(); n2 = pop(); switch(*e) { case '+': { n3 = n1 + n2; break; } case '-': { n3 = n2 - n1; break; } case '*': { n3 = n1 * n2; break; } case '/': { n3 = n2 / n1; break; } } push(n3); } e++; } printf("\nThe result of expression %s = %d\n\n",exp,pop()); return 0;} OUTPUT:Enter the expression :: 365+*
The result of expression 365+* = 33
5) Write a program for converting a given infix expression to postfix form using stack.
#include<stdio.h>
#include<ctype.h>
char
stack[100];
int
top = -1;
void
push(char x)
{
stack[++top] = x;
}
char
pop()
{
if(top == -1)
return -1;
else
return stack[top--];
}
int
priority(char x)
{
if(x == '(')
return 0;
if(x == '+' || x == '-')
return 1;
if(x == '*' || x == '/')
return 2;
return 0;
}
int
main()
{
char exp[100];
char *e, x;
printf("Enter the expression :
");
scanf("%s",exp);
printf("\n");
e = exp;
while(*e != '\0')
{
if(isalnum(*e))
printf("%c ",*e);
else if(*e == '(')
push(*e);
else if(*e == ')')
{
while((x = pop()) != '(')
printf("%c ", x);
}
else
{
while(priority(stack[top]) >=
priority(*e))
printf("%c ",pop());
push(*e);
}
e++;
}
while(top != -1)
{
printf("%c ",pop());
}return 0;
} OUTPUT:
Enter
the expression : a+b*c
a
b c * +
6)write a program for implementing the operations of a priority queue using dynamic allocation.
|
// C code to implement Priority Queue // using Linked List #include <stdio.h> #include <stdlib.h>
// Node typedef struct node { int data;
// Lower values indicate higher priority int priority;
struct node* next;
} Node;
// Function to Create A New Node Node* newNode(int d, int p) { Node* temp = (Node*)malloc(sizeof(Node)); temp->data = d; temp->priority = p; temp->next = NULL;
return temp; }
// Return the value at head int peek(Node** head) { return (*head)->data; }
// Removes the element with the // highest priority from the list void pop(Node** head) { Node* temp = *head; (*head) = (*head)->next; free(temp); }
// Function to push according to priority void push(Node** head, int d, int p) { Node* start = (*head);
// Create new Node Node* temp = newNode(d, p);
// Special Case: The head of list has lesser // priority than new node. So insert new // node before head node and change head node. if ((*head)->priority > p) {
// Insert New Node before head temp->next = *head; (*head) = temp; } else {
// Traverse the list and find a // position to insert new node while (start->next != NULL && start->next->priority < p) { start = start->next; }
// Either at the ends of the list // or at required position temp->next = start->next; start->next = temp; } }
// Function to check is list is empty int isEmpty(Node** head) { return (*head) == NULL; }
// Driver code int main() { // Create a Priority Queue // 7->4->5->6 Node* pq = newNode(4, 1); push(&pq, 5, 2); push(&pq, 6, 3); push(&pq, 7, 0);
while (!isEmpty(&pq)) { printf("%d ", peek(&pq)); pop(&pq); }
return 0; } |
OUTPUT:
7 4 5 6
7)Write a program for the representation of polynomials using circular linked list and for the addition of two such polynomials.
#include<stdio.h>
#include<stdlib.h>
struct node
{
int coeff;
int expon;
struct node *link;
};
typedef struct node *NODE;
NODE getnode()
{
NODE x;
x = (NODE) malloc(sizeof(struct node));
return x;
}
NODE attach(int coeff, int expon, NODE head)
{
NODE temp, cur;
temp = getnode();
temp->coeff = coeff;
temp->expon = expon;
cur = head->link;
while(cur->link != head)
{
cur = cur->link;
}
cur->link = temp;
temp->link = head;
return head;
}
NODE read_poly(NODE head)
{
int i = 1, coeff, expon;
printf("\nEnter the coefficient as -999 to end the polynomial ");
while(1)
{
printf("\nEnter the %d term:\n",i++);
printf("\n\tCoeff = ");
scanf("%d", &coeff);
if(coeff == -999)
break;
printf("\n\tPow x = ");
scanf("%d", &expon);
head = attach(coeff, expon, head);
}
return head;
}
NODE poly_add(NODE head1, NODE head2, NODE head3)
{
NODE a,b;
int coeff;
a = head1->link;
b = head2->link;
while(a != head1 && b != head2)
{
if(a->expon == b->expon)
{
coeff = a->coeff + b->coeff;
if(coeff != 0)
head3 = attach(coeff, a->expon, head3);
a = a->link;
b = b->link;
}
else if(a->expon > b->expon)
{
head3 = attach(a->coeff, a->expon, head3);
a = a->link;
}
else
{
head3 = attach(b->coeff, b->expon, head3);
b = b->link;
}
}
while(a != head1)
{
head3 = attach(a->coeff, a->expon, head3);
a = a->link;
}
while(b != head2)
{
head3 = attach(b->coeff, b->expon, head3);
b = b->link;
}
return head3;
}
void display(NODE head)
{
NODE temp;
if(head->link == head)
{
printf("\nPolynomial does not exist");
return;
}
temp = head->link;
while(temp != head)
{
printf("%dx^%d",temp->coeff, temp->expon);
temp = temp->link;
if(temp != head)
printf(" + ");
}
}
void main()
{
NODE head1, head2, head3;
head1 = getnode();
head2 = getnode();
head3 = getnode();
head1->link=head1;
head2->link=head2;
head3->link=head3;
printf("\nEnter the first polynomial \n");
head1 = read_poly(head1);
printf("\nEnter the second polynomial \n");
head2 = read_poly(head2);
head3 = poly_add(head1, head2, head3);
printf("\nPolynomial 1:\t");
display(head1);
printf("\nPolynomial 2:\t");
display(head2);
printf("\nPolynomial Result:\t");
display(head3);
}
OUTPUT:
Enter the first
polynomial
Enter the coefficient as -999 to end the polynomial
Enter the 1 term:
Coeff = 1
Pow x = 3
Enter the 2 term:
Coeff = 1
Pow x = 2
Enter the 3 term:
Coeff = 1
Pow x = 1
Enter the 4 term:
Coeff = 1
Pow x = 0
Enter the 5 term:
Coeff = -999
Enter the second polynomial
Enter the coefficient as -999 to end the polynomial
Enter the 1 term:
Coeff = 7
Pow x = 2
Enter the 2 term:
Coeff = 5
Pow x = 1
Enter the 3 term:
Coeff = -999
Polynomial 1: 1x^3 + 1x^2 + 1x^1 + 1x^0
Polynomial 2: 7x^2 + 5x^1
Polynomial Result: 1x^3 + 8x^2 + 6x^1 + 1x^0
9)Write a program for Merge Sort.
#include <stdio.h>
#include <stdlib.h>
void merge(int arr[], int l,
int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[],
int l, int r)
{
if (l < r)
{
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
void printArray(int A[], int size)
{
int i;
for (i = 0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
}
int main()
{
int arr[] = {12, 11, 13, 5, 6, 7};
int arr_size = sizeof(arr) / sizeof(arr[0]);
printf("Given array is \n");
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
printf("\nSorted array is \n");
printArray(arr, arr_size);
return 0;
}
OUTPUT:
Given array is
12 11 13 5 6 7
Sorted array is
5 6 7 11 12 13
8)Write a program for quick sort.
// Quick sort in C
#include <stdio.h>
// function to swap elements
void swap(int *a, int *b) {
int t = *a;
*a = *b;
*b = t;
}
// function to find the partition position
int partition(int array[], int low, int high) {
// select the rightmost element as pivot
int pivot = array[high];
// pointer for greater element
int i = (low - 1);
// traverse each element of the array
// compare them with the pivot
for (int j = low; j < high; j++) {
if (array[j] <= pivot) {
// if element smaller than pivot is found
// swap it with the greater element pointed by i
i++;
// swap element at i with element at j
swap(&array[i], &array[j]);
}
}
// swap the pivot element with the greater element at i
swap(&array[i + 1], &array[high]);
// return the partition point
return (i + 1);
}
void quickSort(int array[], int low, int high) {
if (low < high) {
// find the pivot element such that
// elements smaller than pivot are on left of pivot
// elements greater than pivot are on right of pivot
int pi = partition(array, low, high);
// recursive call on the left of pivot
quickSort(array, low, pi - 1);
// recursive call on the right of pivot
quickSort(array, pi + 1, high);
}
}
// function to print array elements
void printArray(int array[], int size) {
for (int i = 0; i < size; ++i) {
printf("%d ", array[i]);
}
printf("\n");
}
// main function
int main() {
int data[] = {8, 7, 2, 1, 0, 9, 6};
int n = sizeof(data) / sizeof(data[0]);
printf("Unsorted Array\n");
printArray(data, n);
// perform quicksort on data
quickSort(data, 0, n - 1);
printf("Sorted array in ascending order: \n");
printArray(data, n); }
OUTPUT:
Unsorted Array
8 7 2 1 0 9 6
Sorted array in ascending order:
0 1 2 6 7 8 9
9)Write a program for Merge Sort.
// Merge sort in C
#include <stdio.h>
// Merge two subarrays L and M into arr
void merge(int arr[], int p, int q, int r) {
// Create L ← A[p..q] and M ← A[q+1..r]
int n1 = q - p + 1;
int n2 = r - q;
int L[n1], M[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[p + i];
for (int j = 0; j < n2; j++)
M[j] = arr[q + 1 + j];
// Maintain current index of sub-arrays and main array
int i, j, k;
i = 0;
j = 0;
k = p;
// Until we reach either end of either L or M, pick larger among
// elements L and M and place them in the correct position at A[p..r]
while (i < n1 && j < n2) {
if (L[i] <= M[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = M[j];
j++;
}
k++;
}
// When we run out of elements in either L or M,
// pick up the remaining elements and put in A[p..r]
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = M[j];
j++;
k++;
}
}
// Divide the array into two subarrays, sort them and merge them
void mergeSort(int arr[], int l, int r) {
if (l < r) {
// m is the point where the array is divided into two subarrays
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
// Merge the sorted subarrays
merge(arr, l, m, r);
}
}
// Print the array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
// Driver program
int main() {
int arr[] = {6, 5, 12, 10, 9, 1};
int size = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, size - 1);
printf("Sorted array: \n");
printArray(arr, size);
}
OUTPUT:
Sorted array:
1 5 6 9 10 12
10)Write a program for Heap Sort.
// Heap Sort in C
#include <stdio.h>
// Function to swap the the position of two elements
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void heapify(int arr[], int n, int i) {
// Find largest among root, left child and right child
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
// Swap and continue heapifying if root is not largest
if (largest != i) {
swap(&arr[i], &arr[largest]);
heapify(arr, n, largest);
}
}
// Main function to do heap sort
void heapSort(int arr[], int n) {
// Build max heap
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// Heap sort
for (int i = n - 1; i >= 0; i--) {
swap(&arr[0], &arr[i]);
// Heapify root element to get highest element at root again
heapify(arr, i, 0);
}
}
// Print an array
void printArray(int arr[], int n) {
for (int i = 0; i < n; ++i)
printf("%d ", arr[i]);
printf("\n");
}
// Driver code
int main() {
int arr[] = {1, 12, 9, 5, 6, 10};
int n = sizeof(arr) / sizeof(arr[0]);
heapSort(arr, n);
printf("Sorted array is \n");
printArray(arr, n);
}
OUTPUT:
Sorted array is
1 5 6 9 10 12
11)Write a program to create a binary search tree and for implementing the inorder,preorder,postorder traversal using recursion.
#include <stdio.h>
#include <stdlib.h>
// structure of a node
struct node
{
int data;
struct node *left;
struct node *right;
};
// globally initialized root pointer
struct node *root = NULL;
// function prototyping
struct node *create_node(int);
void insert(int);
void inorder(struct node *);
void postorder();
void preorder();
int get_data();
int main()
{
int userChoice;
int userActive = 'Y';
int data;
struct node* result = NULL;
while (userActive == 'Y' || userActive == 'y')
{
printf("\n\n------- Binary Search Tree ------\n");
printf("\n1. Insert");
printf("\n\n-- Traversals --");
printf("\n\n2. Inorder ");
printf("\n3. Post Order ");
printf("\n4. Pre Oder ");
printf("\n5. Exit");
printf("\n\nEnter Your Choice: ");
scanf("%d", &userChoice);
printf("\n");
switch(userChoice)
{
case 1:
data = get_data();
insert(data);
break;
case 2:
inorder(root);
break;
case 3:
postorder(root);
break;
case 4:
preorder(root);
break;
case 5:
printf("\n\nProgram was terminated\n");
break;
default:
printf("\n\tInvalid Choice\n");
break;
}
printf("\n__________\nDo you want to continue? ");
fflush(stdin);
scanf(" %c", &userActive);
}
return 0;
}
// creates a new node
struct node *create_node(int data)
{
struct node *new_node = (struct node *)malloc(sizeof(struct node));
if (new_node == NULL)
{
printf("\nMemory for new node can't be allocated");
return NULL;
}
new_node->data = data;
new_node->left = NULL;
new_node->right = NULL;
return new_node;
}
// inserts the data in the BST
void insert(int data)
{
struct node *new_node = create_node(data);
if (new_node != NULL)
{
// if the root is empty then make a new node as the root node
if (root == NULL)
{
root = new_node;
printf("\n* node having data %d was inserted\n", data);
return;
}
struct node *temp = root;
struct node *prev = NULL;
// traverse through the BST to get the correct position for insertion
while (temp != NULL)
{
prev = temp;
if (data > temp->data)
{
temp = temp->right;
}
else
{
temp = temp->left;
}
}
// found the last node where the new node should insert
if (data > prev->data)
{
prev->right = new_node;
}
else
{
prev->left = new_node;
}
printf("\n* node having data %d was inserted\n", data);
}
}
// inorder traversal of the BST
void inorder(struct node *root)
{
if (root == NULL)
{
return;
}
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
// preorder traversal of the BST
void preorder(struct node *root)
{
if (root == NULL)
{
return;
}
printf("%d ", root->data);
preorder(root->left);
preorder(root->right);
}
// postorder travsersal of the BST
void postorder(struct node *root)
{
if (root == NULL)
{
return;
}
postorder(root->left);
postorder(root->right);
printf("%d ", root->data);
}
// getting data from the user
int get_data()
{
int data;
printf("\nEnter Data: ");
scanf("%d", &data);
return data;
}
OUTPUT:
------- Binary Search Tree ------
1. Insert
-- Traversals --
2. Inorder
3. Post Order
4. Pre Oder
5. Exit
Enter Your Choice: 1
Enter Data: 2
* node having data 2 was inserted
__________
Do you want to continue? y
------- Binary Search Tree ------
1. Insert
-- Traversals --
2. Inorder
3. Post Order
4. Pre Oder
5. Exit
Enter Your Choice: 1
Enter Data: 5
* node having data 5 was inserted
__________
Do you want to continue? y
------- Binary Search Tree ------
1. Insert
-- Traversals --
2. Inorder
3. Post Order
4. Pre Oder
5. Exit
Enter Your Choice: 1
Enter Data: 1
* node having data 1 was inserted
__________
Do you want to continue? y
------- Binary Search Tree ------
1. Insert
-- Traversals --
2. Inorder
3. Post Order
4. Pre Oder
5. Exit
Enter Your Choice: 1
Enter Data: 0
* node having data 0 was inserted
__________
Do you want to continue? y
------- Binary Search Tree ------
1. Insert
-- Traversals --
2. Inorder
3. Post Order
4. Pre Oder
5. Exit
Enter Your Choice: 1
Enter Data: 3
* node having data 3 was inserted
__________
Do you want to continue? y
------- Binary Search Tree ------
1. Insert
-- Traversals --
2. Inorder
3. Post Order
4. Pre Oder
5. Exit
Enter Your Choice: 2
0 1 2 3 5
__________
Do you want to continue? y
------- Binary Search Tree ------
1. Insert
-- Traversals --
2. Inorder
3. Post Order
4. Pre Oder
5. Exit
Enter Your Choice: 3
0 1 3 5 2
__________
Do you want to continue? y
------- Binary Search Tree ------
1. Insert
-- Traversals --
2. Inorder
3. Post Order
4. Pre Oder
5. Exit
Enter Your Choice: 4
2 1 0 5 3
__________
Do you want to continue? y
------- Binary Search Tree ------
1. Insert
-- Traversals --
2. Inorder
3. Post Order
4. Pre Oder
5. Exit
Enter Your Choice: 5
12 a) Write a program for finding the transitive closure of a digraph.
# include <stdio.h>
int n,a[10][10],p[10][10];
void path()
{
int i,j,k;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
p[i][j]=a[i][j];
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(p[i][k]==1&&p[k][j]==1) p[i][j]=1;
}
void main()
{
int i,j;
printf("Enter the number of nodes:");
scanf("%d",&n);
printf("\nEnter the adjacency matrix:\n");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&a[i][j]);
path();
printf("\nThe path matrix is shown below\n");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++){
printf("%d ",p[i][j]);
}
printf("\n");
}
}
OUTPUT:
Enter the number of nodes:4
Enter the adjacency matrix:
0 1 0 0
0 0 0 1
0 0 0 0
1 0 1 0
The path matrix is shown below
1 1 1 1
1 1 1 1
0 0 0 0
1 1 1 1
12 B)Write a program for finding the shortest path from a given source to any vertex in a digraph using Dijkstra’s algorithm.
#include<stdio.h>
#define INFINITY 9999
#define MAX 10
void dijkstra(int G[MAX][MAX],int n,int startnode);
int main()
{
int G[MAX][MAX],i,j,n,u;
printf("Enter no. of vertices:");
scanf("%d",&n);
printf("\nEnter the adjacency matrix:\n");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&G[i][j]);
printf("\nEnter the starting node:");
scanf("%d",&u);
dijkstra(G,n,u);
return 0;
}
void dijkstra(int G[MAX][MAX],int n,int startnode)
{
int cost[MAX][MAX],distance[MAX],pred[MAX];
int visited[MAX],count,mindistance,nextnode,i,j;
//pred[] stores the predecessor of each node
//count gives the number of nodes seen so far
//create the cost matrix
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(G[i][j]==0)
cost[i][j]=INFINITY;
else
cost[i][j]=G[i][j];
//initialize pred[],distance[] and visited[]
for(i=0;i<n;i++)
{
distance[i]=cost[startnode][i];
pred[i]=startnode;
visited[i]=0;
}
distance[startnode]=0;
visited[startnode]=1;
count=1;
while(count<n-1)
{
mindistance=INFINITY;
//nextnode gives the node at minimum distance
for(i=0;i<n;i++)
if(distance[i]<mindistance&&!visited[i])
{
mindistance=distance[i];
nextnode=i;
}
//check if a better path exists through nextnode
visited[nextnode]=1;
for(i=0;i<n;i++)
if(!visited[i])
if(mindistance+cost[nextnode][i]<distance[i])
{
distance[i]=mindistance+cost[nextnode][i];
pred[i]=nextnode;
}
count++;
}
//print the path and distance of each node
for(i=0;i<n;i++)
if(i!=startnode)
{
printf("\nDistance of node%d=%d",i,distance[i]);
printf("\nPath=%d",i);
j=i;
do
{
j=pred[j];
printf("<-%d",j);
}while(j!=startnode);
}
}
OUTPUT:
Enter no. of vertices:5
Enter the adjacency matrix:
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
Enter the starting node:0
Distance of node1=10
Path=1<-0
Distance of node2=50
Path=2<-3<-0
Distance of node3=30
Path=3<-0
Distance of node4=60
Path=4<-2<-3<-0
Comments
Post a Comment