Data Structures & Algorithm(21CSC201J)

B. TECH, Second Year, III Semester

Name-

Registration number-

FACULTY OF ENGINEERING & TECHNOLOGY

SRM INSTITUTE OF SCIENCE AND TECHNOLOGY DELHI

NCR CAMPUS, MODINAGAR

SIKRI KALAN, DELHI MEERUT ROAD, DIST. - GHAZIABAD - 201204

 ODD SEMESTER (2024-2025)

Odd Semester 2024-25

BONAFIDE CERTIFICATE

Registration no.

Certified to be the Bonafide record of work done by _________ of 3th semester 2nd year
B. TECH degree course in SRM INSTITUTE OF SCIENCE AND TECHNOLOGY, NCR Campus
of Department of Computer Science & Engineering, in Data Structure & Algorithm, during
the academic year 2023-24.

Mrs. Rupam kumari Dr.Avneesh vashishtha (Assistant

Professor) Head of Department (CSE)
Submitted for university examination held on___/ /___at SRM IST, NCR
Campus.

Internal Examiner-I Internal Examiner-II

 INDEX

Exp.
Title of Experiments Date of
No. Signature
submission
1 Implementation of Structure.

2 Implementation of using Pointers.

Implementation of matrix Multiplication –

3 Dynamic Memory Allocation.

4 Array Implementation of list.

5 Implementation of linked list.

6 Implementation of Doubly linked list.

7 Implementation of Stack using Array.

8 Implementation of Queue using Array.

9 Implementation of Stack Application –Infix to Postfix

10 Implementation of Tree Using Array

11 Implementation of Binary Search Tree using linked list

12

13 Implementation of Graph Using Array.

14 Implementation of Shortest Path Algorithm

 EXPERIMENT: 1

AIM:

To write a C Program for the implementation of structures.

ALGORITHM:

• Define the structure using the struct keyword, specifying its fields (data members) within
curly braces.

• Declare variables of the structure type to hold data.

• Assign values to the fields of the structure variables.

• Access and manipulate the fields of the structure variables using the dot (.) operator.

PROGRAM:

#include <stdio.h> #include <string.h> struct

Person

{ char name[50];
int stu_id; float
cgpa; } person1;
int main()
{

strcpy(person1.name, "George"); person1.stu_id = 2211;

person1.cgpa = 9.68; printf("Name: %s\n", person1.name);
printf("student id
:%d\n",person1.stu_id ); printf("student cgpa : %.2f", person1.cgpa); return
0;

}
OUTPUT :

Name:George
student id :2211
student cgpa : 9.68
 EXPERIMENT: 2

AIM:

To write a C Program for Structures using Pointers.

ALGORITHM:

STEP 1: Enter the input for creating a structure of student database. STEP 2: Create a structure
pointer using normal structure variable and pointer variable

STEP 3:Dot (.) operator is used to access the data using normal structure variable and arrow (->) is
used to access data using pointer variable. STEP 4: Student details are printed using normal and
pointer structure variable.

PROGRAM:

#include <stdio.h> #include <string.h> int main()

struct student

{ int roll_no; char name[30];

int
phone_number;

};

struct student p1 = {1,"Brown",123443}; struct student p2,* p3;

p3=&p1;

p2.roll_no = 2; strcpy(p2.name,"Sam"); p2.phone_number =

1234567822; p3->roll_no = 3; strcpy(p3.name,"Addy"); p3-
>phone_number = 1234567844;

printf("First Student\n"); printf("roll_no : %d\n",

p1.roll_no); printf("name : %s\n", p1.name); printf("phone_number
: %d\n", p1.phone_number);

printf("Second Student\n"); printf("roll_no : %d\n",

p2.roll_no); printf("name : %s\n", p2.name); printf("phone_number :
%d\n", p2.phone_number);

printf("Third Student\n"); printf("roll_no :

%d\n", p3->roll_no); printf("name : %s\n", p3-

>name); printf("phone_number : %d\n", p3->phone_number); return

0; }
INPUT & OUTPUT

First Student roll_no : 1

name : Brown

phone_number : : 123443

Second Student

roll_no : 2

name : Sam

phone_number : 1234567822

Third Student

roll_no : 3

name : Addy

phone_number : 1234567844
 EXPERIMENT: 3

AIM:

To write a C Program to implement matrix Multiplication using Dynamic Memory Allocation

ALGORITHM:

• Read the dimensions of the two matrices (rows and columns).

• Allocate memory dynamically for the matrices using the malloc function.

• Read the elements of the matrices.

• Perform matrix multiplication using nested loops.

• Allocate memory for the result matrix.

• Store the result of multiplication in the result matrix.

• Display the result matrix.

• Free the dynamically allocated memory.

PROGRAM

#include <stdio.h> #include

<stdlib.h> struct Matrix
{
int rows; int columns;
int
**data;

};

struct Matrix* createMatrix(int rows, int columns) {

struct Matrix* matrix = (struct Matrix*)malloc(sizeof(struct Matrix)); matrix->rows = rows;

matrix->columns = columns; matrix-

>data = (int*)malloc(rows * sizeof(int)); for (int i =

0; i < rows; i++) { matrix->data[i] =

(int*)malloc(columns * sizeof(int));

return matrix;

}
 void freeMatrix(struct Matrix* matrix) { for (int i = 0; i < matrix-
>rows; i++) { free(matrix->data[i]);

free(matrix->data); free(matrix);

void readMatrix(struct Matrix* matrix) { for (int i = 0; i <

matrix->rows; i++) { for (int j = 0; j < matrix->columns; j++) { scanf("%d", &matrix-
>data[i][j]);

struct Matrix* multiplyMatrices(struct Matrix* matrix1, struct Matrix* matrix2) { if

(matrix1->columns != matrix2->rows) { printf("Matrix multiplication not possible. Invalid
dimensions!\n"); return NULL;

struct Matrix* result = createMatrix(matrix1->rows, matrix2-

>columns);

for (int i = 0; i < matrix1->rows; i++) { for (int j = 0; j <

matrix2->columns; j++) { int sum = 0; for (int k = 0; k
< matrix1->columns; k++) {

sum += matrix1->data[i][k] * matrix2->data[k][j];

result->data[i][j] = sum;

} }

return result;

void displayMatrix(struct Matrix* matrix) { for (int i = 0; i <

matrix->rows; i++) { for (int j = 0; j < matrix- >columns; j++) {
printf("%d\t", matrix-

>data[i][j]);

printf("\n");
 }

int main() { int rows1, columns1, rows2, columns2; printf("Enter the number of rows and
columns of the first matrix: "); scanf("%d %d", &rows1, &columns1); printf("Enter the
number of rows and columns of the second matrix: "); scanf("%d %d", &rows2,
&columns2); if (columns1 != rows2) { printf("Matrix multiplication is not possible. Invalid
dimensions!\n"); return 1;

struct Matrix* matrix1 = createMatrix(rows1, columns1); struct

Matrix* matrix2 = createMatrix(rows2, columns2); printf("Enter elements for

the first matrix:\n"); readMatrix(matrix1); printf("Enter elements for the
second matrix:\n"); readMatrix(matrix2);

struct Matrix* resultMatrix = multiplyMatrices(matrix1, matrix2);

printf("Resultant matrix:\n"); displayMatrix(resultMatrix); freeMatrix(matrix1);
freeMatrix(matrix2); freeMatrix(resultMatrix); return 0;

}
OUTPUT:

Enter the number of rows and columns of the first matrix: 2 2 Enter the number of rows
and columns of the second matrix: 2 2

Enter elements for the first matrix: 2 3 3 3

Enter elements for the second matrix: 2 3 4 5

Resultant matrix:

16 21

18 24
 EXPERIMENT: 4

AIM:

To create a list using array in c program.

ALGORITHM:

• Define the maximum size of the list (array size) and initialize variables for tracking the
number of elements in the list.

• Declare an array to hold the list elements.

• Implement functions for common list operations (e.g., insertion, deletion, searching, and
displaying).

• In each function, handle edge cases (e.g., checking for empty or full list, handling invalid
indices).

• Test the implemented functions in the main program.

PROGRAM
#include <stdio.h> #define MAX_SIZE

100

struct List { int arr[MAX_SIZE];

int size;
};
// Function to initialize the list void initList(struct
List* list) { list- >size
= 0; }

// Function to insert an element at the end of the list

void insert(struct List* list, int element) { if (list->size
< MAX_SIZE) { list>arr[list>size] = element; list-
>size++; }
else { printf("List is full.
Cannot insert.\n");
}
}
 // Function to delete an element at a given index from the list
void deleteAtIndex(struct List* list, int index) { if (index < 0 ||
index >= list->size) {
printf("Invalid index.\n"); return; } for (int i =
index; i < list->size - 1; i++) { list->arr[i]
= list->arr[i + 1];

} list->size--
;}

// Function to display the list elements void

display(struct List* list) { printf("List: "); for (int
i = 0; i
< list->size; i++) { printf("%d

", list->arr[i]); } printf("\n");

}

int main() { struct List

myList; initList(&myList);

// Insert elements into the list insert(&myList,

5); insert(&myList,
10); insert(&myList, 15);

// Display the list display(&myList);

// Delete an element at index 1

deleteAtIndex(&myList, 1);

// Display the updated list display(&myList);

return
0;
}
OUTPUT:

List: 5 10 15
List: 5 15
 EXPERIMENT: 5

AIM:

To write a c program to implement linked List and it’s operations.

ALGORITHM:

1. Start

2. Define single linked list node as self referential structure

3. Create Head node with label = -1 and next = NULL using

4. Display menu on list operation

5. Accept user choice

6. If choice = 1 then

7. Locate node after which insertion is to be done

8. Create a new node and get data part

9. Insert the new node at appropriate position by manipulating address

10. Else if choice = 2

11. Get node's data to be deleted.

12. Locate the node and delink the node

13. Rearrange the links

14. Else

15. Traverse the list from Head node to node which points to null

16. Stop

PROGRAM

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

int data; struct node *next;

}; struct node *head; void

beginsert (); void lastinsert ();
void randominsert(); void
begin_delete(); void
last_delete(); void
random_delete(); void display();
void search(); void main ()
{

int choice =0; while(choice

!= 7)

printf("\n*********Main Menu*********\n");

printf("\nChoose one option from the following list ...\n");

printf("\n=====================================

==========\n"); printf("\n1.Insert in begining\n2.Insert at

last\n3.Delete from

Beginning\n4.Delete from last\n5.Search for

an element\n6.Show\n7.Exit\n"); printf("\nEnter your choice?\n");
scanf("\n%d",&choice); switch(choice) {

case 1:
beginsert(); break; case
2:

lastinsert(); break; case 3: begin_delete(); break; case 4:

last_delete(); break; case 5: search(); break; case 6:
display(); break; case 7: exit(0); break; default:
printf("Please enter valid choice..");

void beginsert()

struct node *ptr,*temp; int item; ptr = (struct node

*)malloc(sizeof(struct node)); if(ptr == NULL) {
printf("\nOVERFLOW");

else

printf("\nEnter the node data?");

scanf("%d",&item); ptr -> data = item;
if(head == NULL) { head = ptr; ptr -> next
= head; } else
{ temp = head; while(temp->next

!= head) temp = temp->next; ptr>next

= head; temp -> next = ptr; head = ptr;

printf("\nnode inserted\n");

void lastinsert()

struct node *ptr,*temp; int item; ptr = (struct node

*)malloc(sizeof(struct node)); if(ptr == NULL) { printf("\nOVERFLOW\n");

else

printf("\nEnter Data?");
scanf("%d",&item); ptr>data = item;
if(head == NULL) { head = ptr; ptr ->
next = head; } else { temp = head;
while(temp -> next != head) { temp =
temp -> next; } temp -> next = ptr; ptr
-> next = head;

printf("\nnode inserted\n");

void begin_delete()

struct node *ptr; if(head == NULL) {

printf("\nUNDERFLOW"); } else if(head>next
== head) { head = NULL; free(head);
printf("\nnode deleted\n");

else { ptr = head; while(ptr -> next

!= head) ptr = ptr -> next; ptr-
>next = head->next; free(head);
head = ptr->next; printf("\nnode
deleted\n");

void last_delete()

struct node *ptr, *preptr; if(head==NULL) {

printf("\nUNDERFLOW"); }

else if (head ->next == head) { head = NULL; free(head);

printf("\nnode deleted\n");

else

ptr = head; while(ptr ->next != head)

preptr=ptr; ptr = ptr->next;

preptr->next = ptr -> next; free(ptr); printf("\nnode deleted\n");

void search()

struct node *ptr; int item,i=0,flag=1;

ptr =
head; if(ptr == NULL)
{

printf("\nEmpty List\n");

else

printf("\nEnter item which you want to search?\n"); scanf("%d",&item); if(head ->data ==

item)

{
 printf("item found at location %d",i+1); flag=0;

} else

while (ptr->next != head)

if(ptr->data == item)

printf("item found at location %d ",i+1); flag=0; break;

} else

{ flag=1; } i++; ptr = ptr

-> next; }

if(flag != 0)

printf("Item not found\n");

}}}

void display()

struct node *ptr; ptr=head; if(head

== NULL)

printf("\nnothing to print");

else

printf("\n printing values ... \n"); while(ptr

-> next != head)

printf("%d\n", ptr -> data); ptr = ptr -> next;

printf("%d\n", ptr -> data);

}
OUTPUT:

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in beginning

2.Insert at last

3.Delete from Beginning

4.Delete from last

5.Search for an element

6.Show

7.Exit

Enter your choice?

Enter the node data?10 node

inserted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in beginning

2.Insert at last

3.Delete from Beginning

4.Delete from last

5.Search for an element

6.Show

7.Exit Enter your

choice?

2 Enter Data?

20 node
inserted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in beginning

2.Insert at last

3.Delete from Beginning

4.Delete from last

5.Search for an element

6.Show

7.Exit

Enter your choice?

6 printing values

...

20

10

*********Main Menu*********

Choose one option from the following list ...

1.Insert in beginning

2.Insert at last

3.Delete from Beginning

4.Delete from last

5.Search for an element

6.Show

7.Exit

Enter your choice?

Enter item which you want to search?

10 items found at location 2

 EXPERIMENT: 6

AIM:

To write a c program to implement doubly linked List

ALGORITHM:

i. Insert at Beginning Start

Input the DATA to be inserted Create a new node.

NewNode → Data = DATA NewNode →Lpoint =NULL

IF START IS NULL NewNode→ Rpoint = NULL

Else NewNode → Rpoint = START START→Lpoint = NewNode START

=NewNode Stop

ii. Insertion at location:

Start

Input the DATA and POS

Initialize TEMP = START; i = 0

Repeat the step 4 if (i less than POS) and (TEMP is not equal to NULL)

TEMP = TEMP → RPoint; i = i +1

If (TEMP not equal to NULL) and (i equal to POS)

(a) Create a New Node

(b) NewNode → DATA = DATA

(c) NewNode → RPoint = TEMP → RPoint

(d) NewNode → LPoint = TEMP

(e) (TEMP → RPoint) → LPoint = NewNode

(f) ) TEMP → RPoint = New Node Else

(a) Display “Position NOT found” Stop

iii. Insert at End

Start

Input DATA to be inserted

Create a NewNode
NewNode → DATA = DATA

NewNode → RPoint = NULL If

(SATRT equal to NULL) a. START =
NewNode

b. NewNode → LPoint=NULL

Else

a. TEMP = START

b. While (TEMP → Next not equal to NULL)

i. TEMP = TEMP → Next

c. TEMP → RPoint = NewNode

d. NewNode → LPoint = TEMP Stop iv. Forward Traversal Start

If (START is equal to NULL)

a) Display “The list is Empty”

b) StopInitialize TEMP = START

Repeat the step 5 and 6 until (TEMP == NULL ) Display “TEMP → DATA”

TEMP = TEMP → Next

Stop

v. Backward Traversal

Start

If (START is equal to NULL) Display

“The list is Empty” Stop

Initialize TEMP = TAIL

Repeat the step 5 and 6 until (TEMP == NULL ) Display “TEMP → DATA”

TEMP = TEMP → Prev Stop

PROGRAM

#include <stdio.h>

#include <stdlib.h> struct node { int

num; struct node * preptr; struct node *
nextptr; }*stnode, *ennode; void
DlListcreation(int n); void
displayDlList(); int main()
 { int n;

stnod

e = NULL; en node = NULL; printf("\n\n Doubly Linked List : Create and display a

doubly linked

list :\n");

printf(" \n"); printf(" Input the

number of nodes : ");

scanf("%d", &n);

DlListcreation(n); displayDlList();

return 0;

void DlListcreation(int n)

int i, num; struct node *fnNode; if(n >= 1)

{

stnode = (struct node *)malloc(sizeof(struct node)); if(stnode != NULL)

printf(" Input data for node 1 : "); // assigning data in the first node scanf("%d",
&num); stnode->num = num; stnode->preptr = NULL; stnode->nextptr = NULL; ennode = stnode;

// putting data for rest of the nodes for(i=2; i<=n; i++)

{

fnNode = (struct node *)malloc(sizeof(struct node)); if(fnNode != NULL)

printf(" Input data for node %d : ", i);

scanf("%d", &num); fnNode->num = num; fnNode->preptr = ennode; // new node is linking with
the previous node fnNode->nextptr = NULL;

ennode->nextptr = fnNode; // previous node is linking with the new node ennode = fnNode; //
assign new node as last node

else

printf(" Memory can not be allocated."); break;

}
}

else

printf(" Memory can not be allocated.");

void displayDlList()

struct node * tmp; int n = 1; if(stnode ==

NULL)

printf(" No data found in the List yet.");

else

{ tmp = stnode; printf("\n\n Data entered on the list are

:\n"); while(tmp != NULL)

printf(" node %d : %d\n", n, tmp->num); n++; tmp = tmp-

>nextptr; // current pointer moves to the next node

}}}
OUTPUT:

Main Menu

1. Insert at beginning

2. Insert at end

3. Delete from beginning

4. Delete from end

5. Search for an element

6. Display list

7. Exit

Enter your choice?

Enter the node data?10 Node

inserted at beginning.

Enter your choice?

Enter the node data?20 Node

inserted at end.

Enter your choice?

List: 10 <-> 20

Enter your choice?

Node deleted from beginning.

Enter your choice?

List: 20

Enter your choice?

Enter item to search?20

Item found in the list.

Enter your choice?

7
 EXPERIMENT: 7 A

AIM:

To write a c program to implement stack using array

ALGORITHM:

Step 1 - Include all the header files which are used in the program and define a constant 'SIZE' with
specific value.

Step 2 - Declare all the functions used in stack implementation.

Step 3 - Create a one dimensional array with fixed size (int stack[SIZE])

Step 4 - Define a integer variable 'top' and initialize with '-1'. (int top = -1)

Step 5 - In main method, display menu with list of operations and make suitable function calls to
perform operation selected by the user on the stack.

push(value) - Inserting value into the stack Step 1 - Check whether stack is FULL.
(top == SIZE-1)

Step 2 - If it is FULL, then display "Stack is FULL!!! Insertion is not possible!!!" and terminate the
function.

Step 3 - If it is NOT FULL, then increment top value by one (top++) and set stack[top] to value
(stack[top] = value). pop() - Delete a value from the Stack

In a stack, pop() is a function used to delete an element from the stack.

Step 1 - Check whether stack is EMPTY. (top == -1)

Step 2 - If it is EMPTY, then display "Stack is EMPTY!!! Deletion is not possible!!!" and terminate the
function.

Step 3 - If it is NOT EMPTY, then delete stack[top] and decrement top value by one (top--).

display() - Displays the elements of a Stack Step 1 - Check whether stack is EMPTY. (top
== -1)

Step 2 - If it is EMPTY, then display "Stack is EMPTY!!!" and terminate the function. Step 3 -
If it is NOT EMPTY, then define a variable 'i' and initialize with top.

Display stack[i] value and decrement i value by one (i--). Step 3 - Repeat above step until i value
becomes '0'.
 PROGRAM

#include<stdio.h> #include<conio.h>

int stack[10],choice,n,top,x,i; // Declaration of variables void push(); void pop(); void display();
int main()

top = -1; // Initially there is no element in stack printf("\n Enter the size of STACK : ");
scanf("%d",&n); printf("\nSTACK IMPLEMENTATION USING ARRAYS\n");

do {

printf("\n1.PUSH\n2.POP\n3.DISPLAY\n4.EXIT\n");

printf("\nEnter the choice : ");

scanf("%d",&choice); switch(choice) { case
1: { push(); break; } case 2: { pop(); break; }
case 3: { display(); break; } case 4:
{ break; } default:
{

printf ("\nInvalid Choice\n");

}}}

while(choice!=4); return 0;

void push()

{ if(top >= n - 1)

printf("\nSTACK OVERFLOW\n");

}
else
{

printf(" Enter
a value to be
pushed
: ");

scanf("%d",&x);

top++; // TOP is incremented after an element is pushed stack[top] = x; // The pushed

element is made as TOP

}}

void pop()

{
 if(top <= -1)

printf("\nSTACK UNDERFLOW\n");

} else
{

printf("\nThe popped element is %d",stack[top]); top--; // Decrement TOP after a pop }} void
display()

If (top >= 0)

// Print the stack

printf("\nELEMENTS IN THE STACK\n\n"); for(i = top ; i >= 0 ; i--) printf("%d\t",stack[i]);

}
else
{

printf("\nEMPTY STACK\n");
OUTPUT :

*********Main Menu*********

1. Push

2. Pop

3. Display

4. Exit

Enter your choice?

1 Enter value to push:

10 10 pushed to stack.

Enter your choice?

1 Enter value to push:

20

20 pushed to stack.

Enter your choice?

Stack elements: 10 20

Enter your choice?

Popped value: 20

Enter your choice?

3 Stack elements:

10

Enter your choice?

4
 EXPERIMENT: 7 B

AIM:

To write a c program to implement stack using Linked List

ALGORITHM:

Step 1 - Include all the header files which are used in the program. And declare all the user defined
functions.

Step 2 - Define a 'Node' structure with two members data and next.

Step 3 - Define a Node pointer 'top' and set it to NULL.

Step 4 - Implement the main method by displaying Menu with list of operations and make suitable
function calls in the main method.

push(value) - Inserting an element into the Stack Step 1 - Create a newNode with given value.

Step 2 - Check whether stack is Empty (top == NULL) Step 3 - If it is Empty, then set newNode →
next = NULL.

Step 4 - If it is Not Empty, then set newNode → next = top. Step 5 - Finally, set top = newNode.

pop() - Deleting an Element from a Stack

Step 1 - Check whether stack is Empty (top == NULL).

Step 2 - If it is Empty, then display "Stack is Empty!!! Deletion is not possible!!!" and terminate the
function

Step 3 - If it is Not Empty, then define a Node pointer 'temp' and set it to 'top'.

Step 4 - Then set 'top = top → next'. Step 5 - Finally, delete 'temp'. (free(temp)).

display() - Displaying stack of elements

Step 1 - Check whether stack is Empty (top == NULL).

Step 2 - If it is Empty, then display 'Stack is Empty!!!' and terminate the function.

Step 3 - If it is Not Empty, then define a Node pointer 'temp' and initialize with top.

Step 4 - Display 'temp → data --->' and move it to the next node. Repeat the same until temp
reaches to the first node in the stack. (temp → next != NULL).

Step 5 - Finally! Display 'temp → data ---> NULL'.

PROGRAM

#include<stdio.h> #include<conio.h> struct

Node
{

int data; struct Node *next;

}*top = NULL; void push(int);
void pop(); void
display(); void
main()

int choice, value; clrscr(); printf("\n:: Stack using Linked List

::\n"); while(1){
printf("\n****** MENU ******\n"); printf("1. Push\n2.
Pop\n3. Display\n4. Exit\n"); printf("Enter your choice: ");
scanf("%d",&choice); switch(choice){ case 1: printf("Enter
the value to be insert: ");

scanf("%d", &value); push(value); break; case 2: pop();

break; case 3: display(); break; case 4: exit(0); default:
printf("\nWrong selection!!! Please try again!!!\n");

void push(int value) { struct Node *newNode; newNode = (struct Node*)malloc(sizeof(struct

Node));

newNode->data = value; if(top == NULL)

newNode->next = NULL; else newNode-
>next = top; top =
newNode; printf("\nInsertion is
Success!!!\n");

void pop() { if(top == NULL) printf("\nStack is

Empty!!!\n"); else{ struct Node *temp = top;
printf("\nDeleted element: %d", temp->data);
top = temp->next; free(temp);

void display()

if(top == NULL) printf("\nStack is Empty!!!\n");

else{ struct Node *temp = top;
while(temp->next != NULL){ printf("%d---
>",temp->data); temp = temp
-> next;

printf("%d--->NULL",temp->data);

}
OUTPUT :

*********Main Menu*********
1.
Push
2. Pop
3. Display
4. Exit

Enter your choice?

1

Enter value to push: 30 30 pushed

to stack.

Enter your choice?

1

Enter value to push: 40 40 pushed

to stack.

Enter your choice?

3
Stack elements: 40 30

Enter your choice? 2

Popped value: 40

Enter your choice?

3
Stack elements: 30

Enter your choice?

4
 EXPERIMENT: 8 A

AIM:

To write a c program to implement queue using array

ALGORITHM:

Step 1 - Include all the header files which are used in the program and define a constant 'SIZE' with
specific value.

Step 2 - Declare all the user defined functions which are used in queue implementation.

Step 3 - Create a one dimensional array with above defined SIZE (int queue[SIZE])

Step 4 - Define two integer variables 'front' and 'rear' and initialize both with '-1'. (int front = -1,
rear = -1)

Step 5 - Then implement main method by displaying menu of operations list and make suitable
function calls to perform operation selected by the user on queue.

enQueue(value) - Inserting value into the queue Step 1 - Check whether queue is FULL. (rear
== SIZE-1)

Step 2 - If it is FULL, then display "Queue is FULL!!! Insertion is not possible!!!" and terminate the
function.

Step 3 - If it is NOT FULL, then increment rear value by one (rear++) and set queue[rear] = value.

deQueue() - Deleting a value from the Queue Step 1 - Check whether queue is EMPTY. (front
== rear)

Step 2 - If it is EMPTY, then display "Queue is EMPTY!!! Deletion is not possible!!!" and terminate
the function.

Step 3 - If it is NOT EMPTY, then increment the front value by one (front ++). Then display
queue[front] as deleted element. Then check whether both front and rear are equal (front == rear),
if it TRUE, then set both front and rear to '1' (front = rear = -1).

display() - Displays the elements of a Queue

Step 1 - Check whether queue is EMPTY. (front == rear)

Step 2 - If it is EMPTY, then display "Queue is EMPTY!!!" and terminate the function.

Step 3 - If it is NOT EMPTY, then define an integer variable 'i' and set 'i = front+1'.

Step 4 - Display 'queue[i]' value and increment 'i' value by one (i++). Repeat the same until 'i' value
reaches to rear (i <= rear)
 PROGRAM

#include<stdio.h>

#include<conio.h> #define SIZE 10

void enQueue(int); void deQueue();
void display(); int queue[SIZE], front
= -1, rear = -1; void main()

int value, choice; clrscr(); while(1){

printf("\n\n***** MENU *****\n");

printf("1. Insertion\n2. Deletion\n3. Display\n4. Exit");

printf("\nEnter your choice: "); scanf("%d",&choice);
switch(choice){ case 1: printf("Enter the value to be
insert: ");

scanf("%d",&value); enQueue(value); break; case

2: deQueue(); break; case 3: display(); break; case
4: exit(0); default: printf("\nWrong selection!!! Try
again!!!"); }

}}

void enQueue(int value){ if(rear == SIZE-1) printf("\nQueue is Full!!! Insertion

is not possible!!!");

else{ if(front == -1) front = 0; rear++;

queue[rear] = value;
printf("\nInsertion success!!!");

} } void deQueue(){ if(front == rear) printf("\nQueue is

Empty!!! Deletion is not possible!!!"); else{ printf("\nDeleted
: %d", queue[front]);
front++; if(front ==
rear) front = rear =
-1;

void display(){ if(rear == -1) printf("\nQueue is Empty!!!"); else{

int i;

printf("\nQueue elements are:\n"); for(i=front; i<=rear; i++) printf("%d\t",queue[i]);

}
OUTPUT :

*********Main Menu*********

1. Enqueue

2. Dequeue

3. Display

4. Exit

Enter your choice?

Enter value to enqueue: 10

10 enqueued.

Enter your choice?

Enter value to enqueue: 20

20 enqueued.

Enter your choice?

Queue elements: 10 20

Enter your choice?

Dequeued value: 10

Enter your choice?

Queue elements: 20

Enter your choice?

4
 EXPERIMENT: 8 B

AIM:

To write a c program for to implement Queue using Linked List

ALGORITHM:

Step 1 - Include all the header files which are used in the program. And declare all the user defined
functions.

Step 2 - Define a 'Node' structure with two members data and next.

Step 3 - Define two Node pointers 'front' and 'rear' and set both to NULL.

Step 4 - Implement the main method by displaying Menu of list of operations and make suitable
function calls in the main method to perform user selected operation.

enQueue(value) - Inserting an element into the Queue

Step 1 - Create a newNode with given value and set 'newNode → next' to NULL.

Step 2 - Check whether queue is Empty (rear == NULL)

Step 3 - If it is Empty then, set front = newNode and rear = newNode. Step 4 - If it is Not Empty
then, set rear → next = newNode and rear = newNode.

deQueue() - Deleting an Element from Queue

Step 1 - Check whether queue is Empty (front == NULL).

Step 2 - If it is Empty, then display "Queue is Empty!!! Deletion is not possible!!!" and terminate
from the function

Step 3 - If it is Not Empty then, define a Node pointer 'temp' and set it to

'front'.

Step 4 - Then set 'front = front → next' and delete 'temp' (free(temp)). display() - Displaying the
elements of Queue

Step 1 - Check whether queue is Empty (front == NULL).

Step 2 - If it is Empty then, display 'Queue is Empty!!!' and terminate the function.

Step 3 - If it is Not Empty then, define a Node pointer 'temp' and initialize with front.

Step 4 - Display 'temp → data --->' and move it to the next node. Repeat the same until 'temp'
reaches to 'rear' (temp → next != NULL). Step 5 - Finally! Display 'temp → data ---> NULL'.
Program:
#include <stdio.h>
#include <stdlib.h>

struct Node { int

data; struct Node
*next;
} *front = NULL, *rear = NULL;

void insert(int value); void

delete();
void display();

int main() {
int choice, value;

printf("\n:: Queue Implementation

using Linked List ::\n");
while (1) {
printf("\n****** MENU ******\n");
printf("1. Insert\n"); printf("2.
Delete\n"); printf("3. Display\n");
printf("4. Exit\n"); printf("Enter your
choice: ");
scanf("%d", &choice);

switch (choice) {
case 1:
printf("Enter the value to be
inserted: "); scanf("%d", &value);
insert(value); break; case 2:
delete(); break; case 3:
display();
break; case 4:
exit(0); default:
printf("\nWrong selection!!!
Please try again!!!\n");
}
 }

return 0; // Added return statement for

main
}

void insert(int value) {

struct Node *newNode = (struct
Node*)malloc(sizeof(struct Node)); newNode-
>data = value;
newNode->next = NULL;

if (front == NULL) {
front = rear = newNode;
} else {
rear->next = newNode;
rear = newNode;
}

printf("\nInsertion is successful!!!\n");
}

void delete() { if (front == NULL) {

printf("\nQueue is empty!!!\n");
} else { struct Node
*temp = front;
front = front->next;
printf("\nDeleted element: %d\n",
temp->data);
free(temp);
}
}

void display() { if (front == NULL) {

printf("\nQueue is empty!!!\n");
} else { struct Node *temp =
front; while (temp != NULL) {
printf("%d ---> ", temp->data);
temp = temp->next;
 }
printf("NULL\n");
}}
OUTPUT:

*********Main Menu*********

1. Enqueue
2. Dequeue
3. Display
4. Exit

Enter your choice?

1

Enter value to enqueue: 10 10 enqueued.

Enter your choice?

1

Enter value to enqueue: 20 20 enqueued.

Enter your choice?

3
Queue elements: 10 20

Enter your choice?

2
Dequeued value: 10

Enter your choice?

3
Queue elements: 20

Enter your choice?

4
 EXPERIMENT 9 A

AIM:

To write a c program to implement Application of Stack (Infix to Post Fix)

ALGORITHM:

To convert Infix Expression into Postfix Expression using a stack data structure, We can use the
following steps...

• Read all the symbols one by one from left to right in the given Infix Expression.

• If the reading symbol is operand, then directly print it to the result (Output).

• If the reading symbol is left parenthesis '(', then Push it on to the Stack.

• If the reading symbol is right parenthesis ')', then Pop all the contents of stack until
respective left parenthesis is poped and print each poped symbol to the result.

• If the reading symbol is operator (+ , - , * , / etc.,), then Push it on to the Stack.first pop the
operators which are already on the stack that have higher or equal precedence than
current operator and print them to the result.

PROGRAM :

#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 infix expression: A + B * C - D

Postfix expression: A B C * + D -

Enter infix expression: ( A + B ) * C

Postfix expression: A B + C *

Enter infix expression: A * ( B + C )

Postfix expression: A B C + *
 EXPERIMENT: 9B

AIM:

To write a c program to implement Application of Stack (Tower of Hanoi)

ALGORITHM:

START

Procedure Hanoi (disk, source, dest, aux)

IF disk == 1, THEN move disk from source to dest

ELSE

Hanoi(disk - 1, source, aux, dest) // Step 1 move disk from source to dest // Step
2

Hanoi(disk - 1, aux, dest, source) // Step 3 END IF

END Procedure STOP

PROGRAM :

#include <stdio.h>

#define MAX_DISK 10

int stkn[MAX_DISK], stksndl[MAX_DISK], stkindl[MAX_DISK], stkdndl[MAX_DISK], stkadd[MAX_DISK]; int

top = -1;

void hanoiNonRecursion(int num, char src, char dest, char aux) {

if (num < 1) return;

int to = 0;
char sndl, indl, dndl;

stkn[++top] = num;
stksndl[top] = src;
stkindl[top] = dest;
stkdndl[top] = aux;
stkadd[top] = 3;
 while (top != -1) { int
add = stkadd[top];
num = stkn[top]; sndl
= stksndl[top]; indl =
stkindl[top];
dndl = stkdndl[top];
top--;

if (add == 3) {
if (num == 1) {
printf("\nMove top disk from needle %c to needle %c.", sndl, indl);
continue;
}
stkn[++top] = num - 1;
stksndl[top] = sndl;
stkindl[top] = dndl;
stkadd[top] = 3;
stkdndl[top] = indl;
stksndl[++top] = indl;
stkindl[top] = dndl;
OUTPUT:

Enter the no. of disks to be transferred: 3

Non-Recursive

Move top disk from needle A to needle C Move top disk from needle
A to needle B Move top disk from needle C to needle B Move top
disk from needle A to needle C Move top disk from needle B to
needle A

Move top disk from needle B to needle C

Move top disk from needle A to needle C Recursive

Move top disk from needle A to needle B. Move top disk from needle A to needle
C.

Move top disk from needle B to needle C. Move top disk from needle
A to needle B. Move top disk from needle C to needle A. Move top disk
from needle C to needle B.

Move top disk from needle A to needle B.

 EXPERIMENT : 10A

AIM:

To write a c program to implement of Tree using array

ALGORITHM:

(A)CREATION AND INSERTION

STEP 1: If root is NULL then create root node return

STEP 2: If root exists then compare the data with node.data while until insertion position is located

If

data is greater than node.data goto right subtree

else

goto left subtree endwhile insert data end If

(B) SEARCH

If root.data is equal to search.data return root else while data not found

If data is greater than node.data goto right subtree else goto left subtree

If data found return node endwhile return data not found

end if

PROGRAM

#include <stdio.h> #include

<stdlib.h> typedef struct

node {

int data; struct

node *left; struct

node *right;

} node;

node *create() {

node *p;

int x;

printf("Enter data (-1 for no data): ");

 scanf("%d", &x);

if (x == -1) return NULL; p=

(node*)malloc(sizeof(node)); p->data

= x; printf("Enter left child of %d:\n",

x); p->left = create(); printf("Enter

right child of %d:\n", x); p->right =

create(); return p;

void preorder(node *t) { // address of root node is passed in t

if (t != NULL) { printf("\n%d", t->data); // visit the root

preorder(t->left); // preorder traversal on left subtree

preorder(t->right); // preorder traversal on right subtree

int main() { node *root; root = create();

printf("\nThe preorder traversal of the tree is:\n");

preorder(root);

return 0;

}
OUTPUT:

Enter data (-1 for no data): 5

Enter left child of 5: Enter

data (-1 for no data): 7 Enter

left child of 7: Enter data (-1

for no data): 8 Enter left

child of 8: Enter data (-1 for

no data): 3 Enter left child of

3: Enter data (-1 for no data):

-1 Enter right child of 3:

Enter data (-1 for no data): -1

Enter right child of 8: Enter

data (-1 for no data): -1 Enter

right child of 7: Enter data (-

1 for no data): -1 Enter right

child of 5:
Enter data (-1 for no data): -1

The preorder traversal of the tree is:

RESULT:
Thus the C Program for Implementation of Tree has been executed successfully.
 EXPERIMENT: 10B

AIM:

To write a c program to implement ofBinary Tree using array

ALGORITHM:

structure BTREE

declare

CREATE() --> btree

ISMTBT(btree, item, btree) --> boolean

MAKEBT(btree, item, btree) --> btree

LCHILD(btree) --> btree

DATA(btree) --> item

RCHILD(btree) --> btree

for all p, r in btree, d in item let

ISMTBT(CREATE) ::= true

ISMTBT(MAKEBT(p, d, r)) ::= false

LCHILD(MAKEBT(p, d, r)) ::= p

LCHILD(CREATE) ::= error

DATA(MAKEBT(p, d, r)) ::= d

DATA(CREATE) ::= error

RCHILD(MAKEBT(p, d, r)) ::= r

RCHILD(CREATE) ::= error

end

end BTREE
PROGRAM:

#include <stdio.h>

#include <stdlib.h> // Include stdlib.h for malloc

#include <conio.h>

struct Node {

int data; struct

Node *left; struct

Node *right;

};

struct Node *root = NULL; int

count = 0;

// Function prototypes struct Node*

insert(struct Node*, int); void

display(struct Node*);

int main() { int choice, value; clrscr(); // Clear screen (platform-specific, might

not be available in all compilers)

printf("\n----- Binary Tree -----\n");

while (1) {
printf("\n***** MENU *****\n");

printf("1. Insert\n2. Display\n3. Exit\n");

printf("Enter your choice: "); scanf("%d",

&choice);

switch (choice) {

case 1:

printf("\nEnter the value to be inserted: ");

 scanf("%d", &value);
root = insert(root, value);

break;
case 2:

display(root);

break; case 3:

exit(0); default:

printf("\nPlease select a correct operation!!!\n");

struct Node* insert(struct Node *root, int value) { struct Node *newNode =

(struct Node*)malloc(sizeof(struct Node)); newNode->data = value;

newNode->left = newNode->right = NULL; // Initialize left and right pointers

if (root == NULL) {

count++;

return newNode; // Return the new node as the root if the tree is empty

} else { if (count % 2 != 0) { root-

>left = insert(root->left, value);

} else {

root->right = insert(root->right, value);

count++; // Increment count after inserting

return root;

// Display is performed using Inorder Traversal void

display(struct Node *root) {

 if (root != NULL) { display(root-
>left); printf("%d\t", root->data);

display(root->right);

}
OUTPUT:
----- Binary Tree -----

***** MENU *****

1. Insert

2. Display

3. Exit

Enter your choice: 1

Enter the value to be inserted: 10

***** MENU *****

1. Insert

2. Display

3. Exit

Enter your choice: 1

Enter the value to be inserted: 20

***** MENU *****

1. Insert

2. Display

3. Exit

Enter your choice: 1

Enter the value to be inserted: 30

***** MENU *****

1. Insert

2. Display

3. Exit

Enter your choice: 2

10 20 30

***** MENU *****

1. Insert

2. Display

3. Exit

Enter your choice: 3

RESULT: Thus the C Program for Implementation of Binary Tree has been executed successfully.
 EXPERIMENT: 11

AIM:

To write a c program to implement BST using linked list

ALGORITHM:

FUNCTION search(data):

SET current = root

PRINT "Visiting elements: "

WHILE current is NOT NULL:

PRINT current.data

IF current.data == data THEN:

RETURN current

IF current.data > data THEN:

SET current = current.left

ELSE:

SET current = current.right

RETURN NULL // Data not found

PROGRAM :

#include <stdio.h>

#include <stdlib.h>

struct node {

int data; struct

node *left; struct

node *right;

};
// Function for inorder traversal void

inorder(struct node *root) {

if (root) { inorder(root-

>left); printf("%d ", root-

>data); inorder(root-

>right);

int main() {

int n, i;

struct node *p, *q, *root = NULL;

printf("Enter the number of nodes to insert: ");

scanf("%d", &n);

printf("Please enter the numbers to insert:\n");

for (i = 0; i < n; i++) { // Corrected loop condition

p = (struct node*)malloc(sizeof(struct node));

scanf("%d", &p->data); p->left = NULL; p-

>right = NULL;

if (i == 0) {

root = p; // First node becomes the root

} else {

q = root; // Start from the root to find the correct position

while (1) { if (p-

>data > q->data) { if

(q->right == NULL) {

q->right = p;

break;
 } else {

q = q->right; // Move to the right child

} else {

if (q->left == NULL) {
q->left = p; break;

} else {

q = q->left; // Move to the left child

printf("\nBinary Search Tree nodes in Inorder Traversal: ");

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

return 0;

}
OUTPUT:
Binary Search Tree nodes in Inorder Traversal: 8 10 12 15 20

RESULT:

Thus the C Program for Implementation of Binary SearchTree using Linked List has been executed successfully.
 EXPERIMENT: 12

AIM:

To write a c program to implement B – Tree

B-Tree Algorithm

B-TREE-CREATE

1. Function: B-TREE-CREATE(T) o

Allocate a new node x.

o Set leaf[x] = TRUE.

o Set n[x] = 0. o Write x to disk.

o Set root[T] = x.

B-TREE-INSERT

1. Function: B-TREE-INSERT(T, k) o

Let r = root[T].

o If n[r] = 2t - 1:

▪ Allocate a new node s.

▪ Set root[T] = s.

▪ Set leaf[s] = FALSE, n[s] = 0, c1[s] = r.

▪ Split child r using B-TREE-SPLIT-CHILD(s, 1, r).

▪ Insert k into s using B-TREE-INSERT-NONFULL(s, k). o Else:

▪ Insert k into r using B-TREE-INSERT-NONFULL(r, k).

B-TREE-SEARCH

1. Function: B-TREE-SEARCH(x, k) o

Set i = 1.

o While i ≤ n[x] and k > key[i][x]:

▪ Increment i.

o If i ≤ n[x] and k = key[i][x], return (x, i).

o If leaf[x], return NIL.

 o Else, read c[i][x] from disk and return B-TREE-SEARCH(c[i][x], k).

B-TREE-DELETION

1. If k is in leaf node x: o Delete k from x.

2. If k is in internal node x:

o If predecessor y of k has at least t keys:

▪ Find predecessor k' and delete it, replacing k with k'. o Else if

successor z of k has at least t keys:

▪ Find successor k' and delete it, replacing k with k'.

o Otherwise:

▪ Merge k with child y and z, freeing z and recursively deleting k

from y.

3. If k is not present in internal node x:

o Determine child c[i][x] for the subtree that may contain k.

o If c[i][x] has t - 1 keys:

▪ Execute steps to ensure c[i][x] has at least t keys.

o Recursively delete k from the appropriate child.

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

#define M 3 // Order of B-tree

typedef struct _node { int n; // Number of

keys in node int keys[M - 1]; struct
_node *p[M]; // Pointers to children
} node;

node *root = NULL;

typedef enum KeyStatus {

Duplicate, SearchFailure, Success, InsertIt, LessKeys,
} KeyStatus;
void insert(int key); void
display(node *root, int blanks);
void DelNode(int key); void
search(int key);
KeyStatus ins(node *ptr, int key, int *upKey, node **newnode);
int searchPos(int key, int *key_arr, int n); KeyStatus del(node
*ptr, int key); void eatline(void);

int main() { int

key, choice;
printf("Creation of B-tree for M=%d\n", M);

while (1) { printf("1.

Insert\n2. Delete\n3.
OUTPUT:
Creation of B-tree for M=3

1. Insert

2. Delete

3. Search

4. Display

5. Quit

Enter your choice: 1

Enter the key: 10

1. Insert

2. Delete

3. Search

4. Display

5. Quit

Enter your choice: 1

Enter the key: 20

1. Insert

2. Delete

3. Search

4. Display

5. Quit

Enter your choice: 1

Enter the key: 5

B-tree is:

10 20

RESULT:

Thus the C Program for Implementation of B- Tree using Linked List has been executed successfully.
 EXPERIMENT: 13

AIM:

To write a c program to implement Graph using Array to print the adjacent Matrix.

ALGORITHM

Creation of a graph

STEP 1:Get the number of nodes to be inserted for undirected graph

STEP 2:Assign max_edges=n*(n-1)

STEP 3:Read the origin,destination value and weight value from the user

STEP 4:If(origin==0)&&(dest==0) then terminate the process

STEP 5:Otherwise read the weight value of the edge from the user

STEP 6:If(origin>n||origin<=0) then print “Invalid edge”

STEP 7:Otherwise assign adj[origin][destin]=wt; STEP 8: adi[destin][origin]=wt;

PROGRAM :

#include <stdio.h>

#include <stdlib.h>

int main() { int

**adj_matrix;

char d; int r,

c, nodes;

printf("== Adjacency Matrix Demo ==\n");

printf("Number of Nodes: "); scanf("%d",

&nodes);

// Dynamic allocation of matrix array

adj_matrix = (int **)malloc(sizeof(int *) * nodes);

if (!adj_matrix) { printf("Fatal error in memory

allocation!"); return -1;

 }

for (r = 0; r < nodes; r++) { adj_matrix[r] = (int

*)malloc(sizeof(int) * nodes);

if (!adj_matrix[r]) { printf("Fatal error

in memory allocation!");

return -1;

// Initialize the adjacency matrix

for (r = 0; r < nodes; r++) { for

(c = 0; c < nodes; c++) {

adj_matrix[r][c] = 0;

printf("Node pair format <U/D><V1><V2>\n");

do { printf("Enter Node Pair: "); fflush(stdin); // Use fflush(stdin)

cautiously; it's undefined in some compilers. scanf(" %c %d %d", &d, &r, &c);

// Space before %c to ignore whitespace

if (r > 0 && r <= nodes && c > 0 && c <= nodes) { adj_matrix[r

- 1][c - 1] = 1; // Set the edge in the adjacency matrix

if (d == 'U' || d == 'u') { adj_matrix[c - 1][r - 1] = 1; //

Undirected edge printf("Undirected connection between

%d and %d\n", r, c);

} else {

printf("Directed connection from %d to %d\n", r, c);

} else {
 printf("Invalid node pair. Please enter valid nodes between 1 and %d.\n", nodes);

} while (r > 0 && c > 0); // Print

the adjacency matrix

printf("\nAdjacency Matrix\n");

printf(" "); for (c = 0; c <

nodes; c++) { printf("%d

", c + 1);

printf("\n");

for (c = 0; c < nodes; c++) {

printf("---");

printf("\n"); for (r = 0; r < nodes;

r++) { printf("%d| ", r + 1);

for (c = 0; c < nodes; c++) {

printf("%d ", adj_matrix[r][c]);

printf("\n");

// Free allocated memory

for (r = 0; r < nodes; r++) {

free(adj_matrix[r]);
}

free(adj_matrix);

return 0;

}
OUTPUT:

== Adjacency Matrix Demo ==

Number of Nodes: 4

Node pair format <U/D><V1><V2>

Enter Node Pair: U 1 2

Undirected connection between 1 and 2

Enter Node Pair: D 2 3

Directed connection from 2 to 3

Enter Node Pair: U 3 4

Undirected connection between 3 and 4

Enter Node Pair: 0 0 0

Adjacency Matrix

1234

------------- 1|

0100

2| 0 0 1 0

3| 0 1 0 1

4| 0 0 0 0

RESULT:

Thus the C Program for Implementation of Graph has been executed successfully.
 EXPERIMENT:14

AIM:

To write a c program to implement shortest path Algorithm

ALGORITHM

STEP 1:Assign to every node a distance value. Set it to zero for our initial node and to infinity for all other nodes.

STEP 2:Mark all nodes as unvisited. Set initial node as current.

STEP 3:For current node, consider all its unvisited neighbors and calculate their distance (from the initial node).
For example, if current node (A) has distance of 6, and an edge connecting it with another node (B) is 2, the
distance to B through A will be 6+2=8. If this distance is less than the previously recorded distance (infinity in the
beginning, zero for the initial node), overwrite the distance.

STEP 4:When we are done considering all neighbors of the current node, mark it as visited. A visited node will not
be checked ever again; its distance recorded now is final and minimal.

STEP 5:Set the unvisited node with the smallest distance (from the initial node) as the next "current node" and
continue from step 3 .

(i)function Dijkstra(Graph, source):

(ii)for each vertex v in Graph: // Initializations

(iii)dist[v] := infinity // Unknown distance function from source to v

(iv)previous[v] := undefined // Previous node in optimal path from source

(v)dist[source] := 0 // Distance from source to source

(vi)Q := the set of all nodes in Graph

// All nodes in the graph are unoptimized - thus are in Q

(vii)while Q is not empty: // The main loop (viii)u := vertex in Q with smallest dist[]

(ix)if dist[u] = infinity:

(x) break // all remaining vertices are inaccessible

(xi)remove u from Q

(xii)for each neighbor v of u: // where v has not yet been removed from alt := dist[u] + dist_between(u, v)

(xiii)if alt < dist[v]: // Relax (u,v,a) dist[v] := alt

(xiiii)previous[v] := u

(xv)return previous []
PROGRAM:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define IN INT_MAX
#define N 6

int dijkstra(int cost[][N], int source, int target);

int main() { int

cost[N][N], i, j, w; int
source, target, x, y;

printf("\t The Shortest Path Algorithm (DIJKSTRA'S ALGORITHM in C)\n\n");

// Initialize cost matrix

for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
cost[i][j] = IN;

}
}

// Input edge weights

for (x = 0; x < N; x++) {
for (y = x + 1; y < N; y++) {
printf("Enter the weight of the path between nodes %d and %d (0 if no path): ", x +
1, y + 1);
scanf("%d", &w); if
(w > 0) {

cost[x][y] = cost[y][x] = w; // Assuming undirected graph

}
}
printf("\n");
}

printf("\nEnter the source (1 to %d): ", N);

scanf("%d", &source); printf("Enter the
target (1 to %d): ", N); scanf("%d",
&target);

int distance = dijkstra(cost, source - 1, target - 1); // Adjusting for zero-based indexing
printf("\nThe Shortest Path Distance: %d\n", distance);

return 0;
}

int dijkstra(int cost[][N], int source, int target) {

int dist[N], prev[N], selected[N] = {0}; int i,
m, min, start, d, j; char path[N];

// Initialize distances and previous nodes

for (i = 0; i < N; i++) {
dist[i] = IN; prev[i]
= -1;
}
 start = source;
selected[start] = 1;
dist[start] = 0;

while (selected[target] == 0) {
min = IN;
m = -1; // Reset m to an invalid value for comparison

for (i = 0; i < N; i++) { d=

dist[start] + cost[start][i]; if (d <
dist[i] && selected[i] == 0) {
dist[i] = d; prev[i] = start;
}
if (min > dist[i] && selected[i] == 0) {
min = dist[i]; m = i;
}
}
start = m;
if (start == -1) break; // Break if no next node is found
selected[start] = 1;

// Construct path
start = target;

j = 0;
while (start != -1) { path[j++] = start + 65; // Convert
to ASCII (A, B, C...) start = prev[start];

}
path[j] = '\0'; // Null terminate the string

// Reverse the path

 for (int k = 0; k < j / 2; k++) {
char temp = path[k]; path[k]
= path[j - k - 1]; path[j - k -
1] = temp;

printf("The path is: %s\n", path);

return dist[target];

}
Output :

The Shortest Path Algorithm (DIJKSTRA'S ALGORITHM in C)

Enter the weight of the path between nodes 1 and 2 (0 if no path): 5

Enter the weight of the path between nodes 1 and 3 (0 if no path): 10
Enter the weight of the path between nodes 1 and 4 (0 if no path): 0
Enter the weight of the path between nodes 1 and 5 (0 if no path): 0
Enter the weight of the path between nodes 1 and 6 (0 if no path): 0

Enter the weight of the path between nodes 2 and 3 (0 if no path): 2

Enter the weight of the path between nodes 2 and 4 (0 if no path): 0
Enter the weight of the path between nodes 2 and 5 (0 if no path): 0
Enter the weight of the path between nodes 2 and 6 (0 if no path): 0

Enter the weight of the path between nodes 3 and 4 (0 if no path): 1

Enter the weight of the path between nodes 3 and 5 (0 if no path): 5
Enter the weight of the path between nodes 3 and 6 (0 if no path): 0

Enter the weight of the path between nodes 4 and 5 (0 if no path): 0

Enter the weight of the path between nodes 4 and 6 (0 if no path): 0

Enter the weight of the path between nodes 5 and 6 (0 if no path): 3

Enter the source (1 to 6): 1

Enter the target (1 to 6): 6

The Shortest Path Distance: 10

The path is: ABCDEF