SRM INSTITUTE OF SCIENCE AND TECHNOLOGY

Ramapuram Campus, Bharathi Salai, Ramapuram, Chennai - 600089

FACULTY OF ENGINEERING AND TECHNOLOGY

DEPARTMENT OF COMPUTER SCIENCE AND

ENGINEERING

LAB MANUAL
DEGREE / BRANCH: B.TECH/CSE

III SEMESTER

18CSC201J – DATASTRUCTURES AND ALGORITHMS

Regulation – 2018
Academic Year 2022-2023(ODD SEM)

LIST OF EXPERIMENTS:
 S.NO EXPERIMENT NAME

1. Implementation of Searching - Linear and Binary Search Techniques

2. Implementation of sorting Techniques – Insertion sort and Bubble Sort Techniques

3. Implement Structures using Pointers

4. Implementation of Array – Insertion, Deletion.

5. Implementation of Linked List - Cursor Based Implementation

6. Implementation of Doubly linked List

7. Implementation of Doubly linked List

8. Implementation of Queue using Array and linked list

9. Applications of Stack, Queue

10. Implementation of Tree using array

11. Implementation of BST using linked list

12. Implementation of B-Trees

Implementation of Graph using Array

13.

14. Implementation of Shortest path Algorithm

15. Implementation of Minimal Spanning Tree

LAB 1:
IMPLEMENTATION OF SEARCHING - LINEAR AND BINARY SEARCH
TECHNIQUES
AIM :
To code a program using the implementation of different searching techniques like linear and
binary search technique.

ALGORITHM :
LINEAR SEARCH ( Array A, Value x)
1. Start the program.
2. Set i to 0 and n be the number of elements.
3. if i > =n then go to step 7
4. if A[i] == x then go to step 6
5. Set i to i + 1
6. Go to Step 2
7. Print Element x Found at index i and go to step 8
8. Print element not found
9. Stop the program

BINARY SEARCH

1. Start the program

2. Compare the element to be searched with the element in the middle of the list/array.
3. If we get a match, we return the index of the middle element and stop goto step 7.
4. If we do not get a match, we check whether the element to be searched is less or
greater than in value than the middle element.
5. If the element/number to be searched is greater in value than the middle element, then
we pick the elements on the right side of the middle element(as the list/array is sorted,
hence on the right, we will have all the numbers greater than the middle number), and
start again from the step 1.
6. If the element/number to be searched is lesser in value than the middle number, then
we pick the elements on the left side of the middle element, and start again from the
step 1.
7. When the entire array is eliminated and the element is not found display element not
found.
8. Stop the program
Program for Linear search :
#include <stdio.h>
int main()
{
int elementsArray[100], searchValue, c, totalElements;

printf("Enter the total number of elements you are going to store n");
scanf("%d", &totalElements);

printf("Enter %d integer values one by one", totalElements);

for(c = 0 ;c < totalElements; c++)
{
scanf("%d", &elementsArray[c]);
}

printf("Enter a value to search in the array ");

scanf("%d", &searchValue);

for(c = 0; c < totalElements; c++)

 {
if(elementsArray[c] == searchValue)
{
printf("%d is present at location %d.", searchValue, c+1);
break;
}
}

if(c == totalElements)
{
printf("%d is not available in the entered numbers", searchValue);
}

return 0;
}

Output :-

Enter the total number of elements you are going to store

3

Enter 3 integer values one by one

1
2
3

Enter a value to search in the array

3

3 is present at location 3.

Program for Binary Search

#include <stdio.h>

int main()
{
int c, first, last, middle, n, search, array[100];

printf("Enter number of elements");

scanf("%d", &n);

printf("Enter %d integers", n);

for(c = 0; c < n; c++)

{
scanf("%d", &array[c]);
}

printf("Enter value to find");

scanf("%d", &search);

first = 0;
last = n - 1;
middle = (first+last) / 2;
 while(first <= last)
{
if(array[middle] < search)
first = middle + 1;
else if(array[middle] == search)
{
printf("%d found at location %d", search, middle+1);
break;
}
else
last = middle - 1;

middle = (first + last) / 2;

}

if(first > last)

printf("Not found! %d isn't present in the list", search);

return 0;
}

Output :-

Enter number of elements

3
Enter 3 integers
10
11
12
Enter value to find
11
11 found at location 2

RESULT :
The program for implementation of searching techniques is successfully coded and executed
with the required input and output.

LAB 2:
IMPLEMENTATION OF SORTING TECHNIQUES – INSERTION SORT AND
BUBBLE SORT TECHNIQUES
AIM : To code a program using the implementation of sorting techniques like insertion and
bubble sort technique.

ALGORITHM :

INSERTION SORT
1.Start the program.
2.If it is the first element, it is already sorted. return 1;
3.Pick next element
4.Compare with all elements in the sorted sub-list
5.Shift all the elements in the sorted sub-list that is greater than the value to be sorted
6.Insert the value
7.Repeat until list is sorted and we get the desired output
8.Stop the program.

BUBBLE SORT
1. Start the program.
2. algorithm Bubble_Sort(list)
3. Pre: list != fi
4. Post: list is sorted in ascending order for all values
5. for i <- 0 to list:Count - 1
6. for j <- 0 to list:Count - 1
7. if list[i] < list[j]
8. Swap(list[i]; list[j])
9. end if
10. end for
11. end for
12. return list
13. end Bubble_Sort
14. Stop the program.

Program for Insertion sort:

#include <stdio.h>

int main()
{
int count, temp, i, j, number[30];

printf("How many numbers are you going to enter?: ");

scanf("%d",&count);

printf("Enter %d numbers: ",count);

for(i=0;i<count;i++)
scanf("%d",&number[i]);

for(i=1;i<count;i++)
{
temp=number[i];
j=i-1;

while(temp<number[j] && j>=0){

 number[j+1]=number[j];
j=j-1;
}

number[j+1]=temp;
}

printf("Sorted elements: ");

for(i=0;i<count;i++)
printf(" %d",number[i]);

return 0;
}

Output :-

How many numbers are you going to enter?:

5

Enter 5 numbers:
20
15
35
2
12
Sorted elements: 2 12 15 20 35

Program for Bubble sort:

#include <stdio.h>

int main()
{
int count, temp, i, j, number[30], swapped;

printf("How many numbers are you going to enter?: ");

scanf("%d",&count);

printf("Enter %d numbers: ",count);

for(i=0;i<count;i++)
scanf("%d",&number[i]);

do
{
for(i=0, swapped = 0; i < count-1; i++)
{
if(number[i] > number[i+1])
{
temp=number[i];
number[i]=number[i+1];
number[i+1]=temp;
swapped = 1;
}
}
 }
while(swapped != 0);

printf("Sorted elements: ");

for(i=0;i<count;i++)
printf(" %d",number[i]);

return 0;
}

Output:-

How many numbers are you going to enter?:

5
Enter 5 numbers:
12
2
15
1
5
Sorted elements: 1 2 5 12 15

RESULT :
The program for implementation of sorting techniques is successfully coded and executed
with the required input and output.

LAB 3: IMPLEMENT STRUCTURES USING POINTERS

AIM : To code a program for implementing structures using pointers.

ALGORITHM :
 1. Start the program
2. Define a pointer using syntax <datatype> *variable name
3. This syntax points to the address of the memory block that stores a structure.
4. This is known as the structure pointer.
5. Passing structure data type as a reference to a function , as if we pass the pointer the
function using the pointer can actually use that and modify the contents of the
Structure that is being pointed by the pointer .
6. To declare and create dynamic data structures , usually the structures are using
dynamic memory allocation .When the structure is declared dynamically a pointer is
returned having the address location where the node has been formed. Now this
pointers has to be assigned to some variable to access that memory location and do all
kinds of operations.
7. To access the members of the structure referenced using the pointer we use the
operator “->”.This operator is called as arrow operator. Using this we can access all
the members of the structure and we can further do all operations on them.
8. If we don’t use the “->” we can first deference the pointer then we can access the
member variables using the “.” Operator. We do this until we get the desired output.
9. Stop the program

Program :-
#include <stdio.h>

struct student
{
char id[10];
char studentname[30];
char subjectname[30];
float mark;
};

int main()
{
struct student student1 = {"STU0001", "Anand", "Data structure", 80.5f};
struct student *ptrstudent1;

ptrstudent1 = &student1;

printf("Student Id: %s", ptrstudent1->id);

printf("Student Name: %s", ptrstudent1->studentname);
printf("Subject Name: %s", ptrstudent1->subjectname);
printf("Subject Mark: %f", ptrstudent1->mark);

return 0;
}

Output:-

Student Id: STU0001

Student Name: Anand
Subject Name: Data structure
Subject Mark: 80.500000
RESULT :
The program for implementation of structures using pointers is successfully coded and
executed with the required input and output.

LAB 4 : IMPLEMENTATION OF ARRAY – INSERTION, DELETION

AIM : To code a program for implementation of array like insertion and deletion.

ALGORITHM :
INSERTION OF AN ELEMENT IN AN ARRAY
1. Start the Program
2. Get the element value which needs to be inserted.
3. Get the position value.
4. Check whether the position value is valid or not.
5. If it is valid,
6. Shift all the elements from the last index to position index by 1 position to the right.
7. insert the new element in arr[position]
8. Otherwise, Invalid Position
9. Stop the program

DELETION OF AN ELEMENT FROM AN ARRAY

10. Start the Program
1. Find the given element in the given array and note the index.
2. If the element found, Shift all the elements from index + 1 by 1 position to the left.
3. Reduce the array size by 1.
4. Otherwise, print "Element Not Found"
5. Stop the program

Program for Insertion in array :-

#include <stdio.h>

int main()
{
int array[100], position, c, n, value;
printf("Enter number of elements in array");
scanf("%d", &n);

printf("Enter %d elements", n);

for (c = 0; c < n; c++)

scanf("%d", &array[c]);

printf("Enter the location to insert an element");

scanf("%d", &position);

printf("Enter the number to insert");

scanf("%d", &value);

for (c = n - 1; c >= position - 1; c--)

array[c+1] = array[c];

array[position-1] = value;

printf("After Insertion the array output is");

for (c = 0; c <= n; c++)

printf("%d", array[c]);

return 0;
}

Output:-

Enter number of elements in array

5
Enter 5 elements
1
2
3
4
5
Enter the location to insert an element
3
Enter the number to insert
10
After Insertion the array output is
1
2
10
3
4
5

Program for deletion in Array:

#include <stdio.h>
int main()
{
int array[100], position, c, n, value;
printf("Enter number of elements in array");
scanf("%d", &n);

printf("Enter %d elements", n);

for (c = 0; c < n; c++)

scanf("%d", &array[c]);

printf("Enter the location to delete an element");

scanf("%d", &position);

for (c = position; c < n; c++)

array[c-1] = array[c];

printf("After Deletion the array output is");

for (c = 0; c <= n - 2; c++)

printf("%d", array[c]);

return 0;
}

Output:-

Enter number of elements in array

5
Enter 5 elements
1
2
3
4
5
Enter the location to delete an element
4
After Deletion the array output is
1
2
3
5

RESULT :
The program for implementation of array insertion and deletion is successfully coded and
executed with the required input and output.

LAB 5:
IMPLEMENTATION OF LINKED LIST – CURSOR BASED IMPLEMENTATION
AIM:
To execute program based on implementation of linked list – cursor based.

ALGORITHM:
Inserting At Beginning of the list:
Step 1 - Create a new Node with given value.
Step 2 - Check whether list is Empty (head == NULL)
Step 3 - If it is Empty then, set new Node →next = NULL and head = new Node.
Step 4 - If it is Not Empty then, set new Node →next = head and head = new Node.
Inserting At End of the list:
Step 1 - Create a new Node with given value and new Node → next as NULL.
Step 2 - Check whether list is Empty (head == NULL).
Step 3 - If it is Empty then, set head = new Node.
Step 4 - If it is Not Empty then, define a node pointer temp and initialize with head.
Step 5 - Keep moving the temp to its next node until it reaches to the last node in the list
(until temp → next is equal to NULL).
Step 6 - Set temp → next = new Node.
Deleting from Beginning of the list:
Step 1 - Check whether list is Empty (head == NULL)
Step 2 - If it is Empty then, display 'List is Empty!!! Deletion is not possible' and terminate
the function.
Step 3 - If it is Not Empty then, define a Node pointer 'temp' and initialize with head.
Step 4 - Check whether list is having only one node (temp → next == NULL)
Step 5 - If it is TRUE then set head = NULL and delete temp (Setting Empty list
conditions)
Step 6 - If it is FALSE then set head = temp → next, and delete temp.
Deleting from End of the list:
Step 1 - Check whether list is Empty (head == NULL)
Step 2 - If it is Empty then, display 'List is Empty!!! Deletion is not possible' and terminate
the function.
Step 3 - If it is Not Empty then, define two Node pointers 'temp1' and 'temp2' and initialize
'temp1' with head.
Step 4 - Check whether list has only one Node (temp1 → next == NULL)
Step 5 - If it is TRUE. Then, set head = NULL and delete temp1. And terminate the
function. (Setting Empty list condition)
Step 6 - If it is FALSE. Then, set 'temp2 = temp1 ' and move temp1 to its next node. Repeat
the same until it reaches to the last node in the list. (until temp1 → next == NULL)
Step 7 - Finally, Set temp2 → next = NULL and delete temp1.
Program :-

#include <stdio.h>
#define SIZE 10
struct Node
{
int data;
int next;
};
typedef int PtrNode;
typedef PtrNode POS;
typedef PtrNode LIST;
struct Node cursor[SIZE];

void InitCursor();
POS CursorAllocation();
void FreeCursor(int);
void Insert(int,int);
int IsLast(int);
POS Find(int, LIST);
POS FindPrevious(int, LIST);
void Delete(int, LIST);
void MakeEmpty(LIST);
void Display();

int main()
{
LIST LI=-1;
POS PO;
int choice,position,dat,ch;
printf("Enter 1 to continue");
scanf("%d", &ch);

while(ch==1)
{
printf("1.Create2.Insert3.Delete4.MakeEmpty5.Display6.Find7.Exit");
printf("Enter your choice:");
scanf("%d", &choice);

switch(choice)
{
case 1:
if(LI == -1)
{
InitCursor();
LI = CursorAllocation();
printf("List created successfully");
}
else
{
printf("List is already created");
}
break;
case 2:
if(LI == -1)
{
printf("List is not Initialized");
}
else
{
printf("Enter the position you want to insert?");
scanf("%d", &position);
printf("Enter the data to insert");
scanf("%d", &dat);
Insert(dat, position);
}
 break;
case 3:
if(LI == -1)
{
printf("List is not Initialized");
}
else
{
printf("Which data you want to delete?");
scanf("%d", &dat);
Delete(dat, LI);
}
break;
case 4:
if(LI == -1)
{
printf("List is not Initialized");
}
else
{
MakeEmpty(LI);
}
break;
case 5:
if(LI == -1)
{
printf("List is not Initialized");
}
else
{
Display();
}
break;
case 6:
if(LI == -1)
{
printf("List is not Initialized");
}
else
{
printf("Which data you want to search?");
scanf("%d", &dat);
PO = Find(dat, LI);
printf("The data is at %d", PO);
}
break;
default:
printf("***************ENTERED WRONG CHIOCE******************");
break;
 }

printf("Enter 1 to continue");
scanf("%d", &ch);
}

return 0;
}

void InitCursor()
{
int i;
for(i = 0; i <= SIZE; i++)
{
cursor[i].next = i+1;
cursor[i].data = 0;
}

cursor[SIZE-1].next = -1;
}

POS CursorAllocation()
{
POS PO;
PO = cursor[0].next;
cursor[0].next = cursor[PO].next;
cursor[PO].data = -1;
cursor[PO].next = -1;
return PO;
}

void FreeCursor(POS PO)

{
cursor[PO].next = cursor[0].next;
cursor[0].next = PO;
cursor[PO].data = 0;
}

void Insert(int dat, POS PO)

{
POS temp;
temp = CursorAllocation();
if(temp == -1)
{
printf("List is Full");
}
else if(cursor[PO].data == 0)
{
printf("Given Position is not in the list");
}
 else
{
cursor[temp].data = dat;
cursor[temp].next = cursor[PO].next;
cursor[PO].next = temp;
}
}

int IsLast(POS PO)

{
return cursor[PO].next == -1;
}

int IsEmpty(LIST LI)

{
return cursor[LI].next == -1;
}

POS Find(int dat, LIST LI)

{
POS temp;
temp = cursor[LI].next;
while(temp != -1 && cursor[temp].data != dat)
{
temp = cursor[temp].next;
}

return temp;
}

POS FindPrevious(int dat, LIST LI)

{
POS temp;
temp = LI;
while(temp != -1 && cursor[cursor[temp].next].data != dat)
{
temp = cursor[temp].next;
}

return temp;
}

void Delete(int dat, LIST LI)

{
POS PO, temp;
PO = FindPrevious(dat, LI);

if(!IsLast(PO))
{
temp = cursor[PO].next;
 cursor[PO].next = cursor[temp].next;
FreeCursor(temp);
}
}

void MakeEmpty(LIST LI)

{
while(!IsEmpty(LI))
{
Delete(cursor[cursor[LI].next].data,LI);
}
}

void Display()
{
int i;
for(i = 0; i <= SIZE; i++)
{
printf("%d%d%d", i, cursor[i].data, cursor[i].next);
}
}

Output :-

Enter 1 to continue
1

1.Create
2.Insert
3.Delete
4.MakeEmpty
5.Display
6.Find
7.Exit
Enter your choice:
1

List created successfully

Enter 1 to continue
1

1.Create
2.Insert
3.Delete
4.MakeEmpty
5.Display
6.Find
7.Exit
Enter your choice:
2

Enter the position you want to insert?

1

Enter the data to insert

101

Enter 1 to continue
1

1.Create
2.Insert
3.Delete
4.MakeEmpty
5.Display
6.Find
7.Exit
Enter your choice:
5

0 0 3
1 -1 2
2 101 -1
3 0 4
4 0 5
5 0 6
6 0 7
7 0 8
8 0 9
9 0 -1
10 0 11
Enter 1 to continue
1

1.Create
2.Insert
3.Delete
4.MakeEmpty
5.Display
6.Find
7.Exit
Enter your choice:
2

Enter the position you want to insert?

23
Enter the data to insert
103

Enter 1 to continue
1

1.Create
2.Insert
3.Delete
4.MakeEmpty
5.Display
6.Find
7.Exit
Enter your choice:
5

0 0 4
1 -1 2
2 101 -1
3 103 3
4 0 5
5 0 6
6 0 7
7 0 8
8 0 9
9 0 -1
10 0 11
Enter 1 to continue

RESULT:
Thus the program and code for implementation of linked list – cursor based is successfully
written and executed.
LAB 6:
IMPLEMENTATION OF DOUBLY LINKED – LIST

AIM:
To execute program based on implementation of doubly linked list.
ALGORITHM:
1.Add a node at the front of DLL: The new node is always added before the head of the given
Linked List. And the newly added node becomes the new head of DLL & maintaining a
global variable for counting the total number of nodes at that time.
2.Traversal of a Doubly linked list
3.Insertion of a node: This can be done in three ways:
At the beginning: The new created node is insert in before the head node and head points to
the new node.
At the end: The new created node is insert at the end of the list and tail points to the new
node.
At a given position: Traverse the given DLL to that position(let the node be X) then do the
following:
1.Change the next pointer of new Node to the next pointer of Node X.
2.Change the prev pointer of next Node of Node X to the new Node.
3.Change the next pointer of node X to new Node.
4.Change the prev pointer of new Node to the Node X.
4.Deletion of a node: This can be done in three ways:
At the beginning: Move head to the next node to delete the node at the beginning and make
previous pointer of current head to NULL.
At the last: Move tail to the previous node to delete the node at the end and make next
pointer of tail node to NULL.
At a given position: Let the prev node of Node at position pos be Node X and next node be
Node Y, then do the following:
1.Change the next pointer of Node X to Node Y.
2.Change the previous pointer of Node Y to Node X.

Program :-

#include <stdio.h>
#include <stdlib.h>
struct node
{
struct node *prev;
struct node *next;
int data;
};
struct node *head;
void insertion_beginning();
void insertion_last();
void insertion_specified();
void deletion_beginning();
void deletion_last();
void deletion_specified();
void display();
void search();

void main()
{
int choice = 0;
while(choice != 9)
 {
printf("\n**********Main Menu**********\n");
printf("\nChoose one option in following list\n");
printf("\n======================================\n");
printf("\n1.Insert in beginning\n2.Insert at last\n3.Insert at any random location\
n4.Delete from Beginning\n5.Delete from last\n6.Delete the node after the given data\
n7.Search\n8.Show\n9.Exit");
printf("\nEnter your choice?\n");
scanf("\n%d",&choice);
switch(choice)
{
case 1:
insertion_beginning();
break;
case 2:
insertion_last();
break;
case 3:
insertion_specified();
break;
case 4:
deletion_beginning();
break;
case 5:
deletion_last();
break;
case 6:
deletion_specified();
break;
case 7:
search();
break;
case 8:
display();
break;
case 9:
exit(0);
break;
default:
printf("Please enter the valid choice..");
}
}
}

void insertion_beginning()
{
struct node *ptr;
int item;
ptr = (struct node*)malloc(sizeof(struct node));
printf("\nEnter Item value : ");
 scanf("%d",&item);

if(head == NULL)
{
ptr->next = NULL;
ptr->prev = NULL;
ptr->data = item;
head=ptr;
}
else
{
ptr->data = item;
ptr->prev = NULL;
ptr->next = head;
head=ptr;
}
printf("\nNode inserted\n");
}

void insertion_last()
{
struct node *ptr, *temp;
int item;
ptr = (struct node *)malloc(sizeof(struct node));
printf("\nEnter Item value : ");
scanf("%d",&item);
ptr->data = item;
if(head==NULL)
{
ptr->next = NULL;
ptr->prev = NULL;
head = ptr;
}
else
{
temp = head;
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=ptr;
ptr->prev = temp;
ptr->next = NULL;
}
printf("\nNode inserted\n");
}

void insertion_specified()
{
struct node *ptr, *temp;
 int item,loc,i;
ptr = (struct node *)malloc(sizeof(struct node));
temp = head;
printf("Enter the location : ");
scanf("%d", &loc);
for(i = 0; i < loc; i++)
{
temp = temp->next;
if(temp == NULL)
{
printf("\n There are less then %d elements", loc);
return;
}
}
printf("Enter value");
scanf("%d", &item);
ptr->data = item;
ptr->next = temp->next;
ptr->prev = temp;
temp->next = ptr;
temp->next->prev = ptr;
printf("\nNode inserted\n");
}

void deletion_beginning()
{
struct node *ptr;
if(head == NULL)
{
printf("\nUNDERFLOW");
}
else if(head -> next == NULL)
{
head = NULL;
free(head);
printf("\nNode deleted\n");
}
else
{
ptr = head;
head = head->next;
head->prev = NULL;
free(ptr);
printf("\nNode deleted\n");
}
}

void deletion_last()
{
struct node *ptr;
 if(head == NULL)
{
printf("\nUNDERFLOW");
}
else if(head -> next == NULL)
{
head = NULL;
free(head);
printf("\nNode deleted\n");
}
else
{
ptr = head;
if(ptr -> next != NULL)
{
ptr = ptr -> next;
}
ptr -> prev -> next = NULL;
free(ptr);
printf("\nNode deleted\n");
}
}

void deletion_specified()
{
struct node *ptr, *temp;
int val;
printf("\n Enter the data after which the node is to be deleted : ");
scanf("%d", &val);
ptr = head;
while(ptr -> data != val)
ptr = ptr -> next;
if(ptr -> next == NULL)
{
printf("\nCan't delete\n");
}
else if(ptr -> next -> next == NULL)
{
ptr ->next = NULL;
}
else
{
temp = ptr -> next;
ptr -> next = temp -> next;
temp -> next -> prev = ptr;
free(temp);
printf("\nnode deleted\n");
}
}
void display()
{
struct node *ptr;
printf("\nPrinting the values..\n");
ptr = head;
while(ptr != NULL)
{
printf("%d\n", ptr -> data);
ptr=ptr->next;
}
}

void search()
{
struct node *ptr;
int item,i=0,flag;
ptr = head;
if(ptr == NULL)
{
printf("\nEmpty List\n");
}
else
{
printf("\nEnter item which you want to search?\n");
scanf("%d",&item);
while (ptr!=NULL)
{
if(ptr->data == item)
{
printf("\nitem found at location %d ",i+1);
flag=0;
break;
}
else
{
flag=1;
}
i++;
ptr = ptr -> next;
}
if(flag==1)
{
printf("\nItem not found\n");
}
}
}

Output :-
*********Main Menu*********

Choose one option from the following list ...

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

1.Insert in beginning
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?

8

printing values...

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

Choose one option from the following list ...

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

1.Insert in beginning
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?

1

Enter Item value12

Node inserted

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

Choose one option from the following list ...

===============================================
1.Insert in beginning
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?

1

Enter Item value123

Node inserted

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

Choose one option from the following list ...

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

1.Insert in beginning
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?

1

Enter Item value1234

Node inserted

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

Choose one option from the following list ...

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

1.Insert in beginning
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?

8

printing values...
1234
123
12

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

Choose one option from the following list ...

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

1.Insert in beginning
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?

2

Enter value89

node inserted

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

Choose one option from the following list ...

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

1.Insert in beginning
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?

3
Enter the location1
Enter value12345

node inserted

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

Choose one option from the following list ...

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

1.Insert in beginning
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?

8

printing values...
1234
123
12345
12
89

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

Choose one option from the following list ...

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

1.Insert in beginning
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?

4

node deleted

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

Choose one option from the following list ...

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

1.Insert in beginning
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?

5

node deleted

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

Choose one option from the following list ...

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

1.Insert in beginning
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?

8

printing values...
123
12345
*********Main Menu*********

Choose one option from the following list ...

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

1.Insert in beginning
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?

6

Enter the data after which the node is to be deleted : 123

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

Choose one option from the following list ...

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

1.Insert in beginning
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?

8

printing values...
123

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

Choose one option from the following list ...

===============================================
1.Insert in beginning
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?

7

Enter item which you want to search?

123

item found at location 1

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

Choose one option from the following list ...

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

1.Insert in beginning
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?

6

Enter the data after which the node is to be deleted : 123

Can't delete

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

Choose one option from the following list ...

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

1.Insert in beginning
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?

9

Exited..

RESULT:
Thus the program and code for implementation of doubly linked list is successfully written
and executed.
LAB 7:
IMPLEMENTATION OF STACK USING ARRAY AND LINKED LIST

AIM:
To execute program based on implementation of Stack using array and linked list.
ALGORITHM:
Stack Operations using Linked List:
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 new Node with given value.
Step 2 - Check whether stack is Empty (top == NULL)
Step 3 - If it is Empty, then set new Node → next = NULL.
Step 4 - If it is Not Empty, then set new Node → next = top.
Step 5 - Finally, set top = new Node.
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'.
Stack Operations using Array:
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:
In a stack, push() is a function used to insert an element into the stack. In a stack, the new
element is always inserted at top position. Push function takes one integer value as parameter
and inserts that value into the stack. We can use the following steps to push an element on to
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. In a stack, the element
is always deleted from top position. Pop function does not take any value as parameter. We
can use the following steps to pop 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 :-Stack Implementation Using Linked List

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

struct node
{
int info;
struct node *ptr;
}*top,*top1,*temp;

int topelement();
void push(int data);
void pop();
void empty();
void display();
void destroy();
void stack_count();
void create();

int count = 0;

void main()
{
int no, ch, e;

create();

while (1)
{
printf("\n 1 - Push");
printf("\n 2 - Pop");
printf("\n 3 - Top");
printf("\n 4 - Empty");
printf("\n 5 - Exit");
printf("\n 6 - Display");
printf("\n 7 - Stack Count");
printf("\n 8 - Destroy stack");
 printf("\n Enter choice : ");
scanf("%d", &ch);

switch (ch)
{
case 1:
printf("Enter data : ");
scanf("%d", &no);
push(no);
break;
case 2:
pop();
break;
case 3:
if (top == NULL)
printf("No elements in stack");
else
{
e = topelement();
printf("\n Top element : %d", e);
}
break;
case 4:
empty();
break;
case 5:
exit(0);
case 6:
display();
break;
case 7:
stack_count();
break;
case 8:
destroy();
break;
default :
printf(" Wrong choice, Please enter correct choice ");
break;
}
}
}

/* Create empty stack */

void create()
{
top = NULL;
}
/* Count stack elements */
void stack_count()
{
printf("\n No. of elements in stack : %d", count);
}

/* Push data into stack */

void push(int data)
{
if (top == NULL)
{
top =(struct node *)malloc(1*sizeof(struct node));
top->ptr = NULL;
top->info = data;
}
else
{
temp =(struct node *)malloc(1*sizeof(struct node));
temp->ptr = top;
temp->info = data;
top = temp;
}
count++;
}

/* Display stack elements */

void display()
{
top1 = top;

if (top1 == NULL)
{
printf("Stack is empty");
return;
}

while (top1 != NULL)

{
printf("%d ", top1->info);
top1 = top1->ptr;
}
}

/* Pop Operation on stack */

void pop()
{
top1 = top;

if (top1 == NULL)
{
 printf("\n Error : Trying to pop from empty stack");
return;
}
else
top1 = top1->ptr;
printf("\n Popped value : %d", top->info);
free(top);
top = top1;
count--;
}

/* Return top element */

int topelement()
{
return(top->info);
}

/* Check if stack is empty or not */

void empty()
{
if (top == NULL)
printf("\n Stack is empty");
else
printf("\n Stack is not empty with %d elements", count);
}

/* Destroy entire stack */

void destroy()
{
top1 = top;

while (top1 != NULL)

{
top1 = top->ptr;
free(top);
top = top1;
top1 = top1->ptr;
}
free(top1);
top = NULL;

printf("\n All stack elements destroyed");

count = 0;
}

Output :-

1 - Push
2 - Pop
3 - Top
4 - Empty
5 - Exit
6 - Display
7 - Stack Count
8 - Destroy stack
Enter choice : 1
Enter data : 10

1 - Push
2 - Pop
3 - Top
4 - Empty
5 - Exit
6 - Display
7 - Stack Count
8 - Destroy stack
Enter choice : 1
Enter data : 20

1 - Push
2 - Pop
3 - Top
4 - Empty
5 - Exit
6 - Display
7 - Stack Count
8 - Destroy stack
Enter choice : 6
20 10
1 - Push
2 - Pop
3 - Top
4 - Empty
5 - Exit
6 - Display
7 - Stack Count
8 - Destroy stack
Enter choice : 2

Popped value : 20
1 - Push
2 - Pop
3 - Top
4 - Empty
5 - Exit
6 - Display
7 - Stack Count
8 - Destroy stack
Enter choice : 6
10
1 - Push
2 - Pop
3 - Top
4 - Empty
5 - Exit
6 - Display
7 - Stack Count
8 - Destroy stack
Enter choice : 5

RESULT:
Thus the program and code for implementation of Stack using array and linked list is
successfully written and executed.

LAB 8:
IMPLEMENTATION OF QUEUE USING ARRAY AND LINKED LIST

AIM:
To execute program based on implementation of Queue using array and linked list.
ALGORITHM:
Queue representing array:
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.
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.

Deleting 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).
Queue representing 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.
Inserting element into Queue:
Step 1 - Create a new Node with given value and set 'new Node → next' to NULL.
Step 2 - Check whether queue is Empty (rear == NULL)
Step 3 - If it is Empty then, set front = new Node and rear = new Node.
Step 4 - If it is Not Empty then, set rear → next = new Node and rear = new Node.
Deleting 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)).

Program :-

#include <stdio.h>
#include <stdlib.h>
#define MAX 50

void insert();
void delete();
void display();
int queue_array[MAX];
int rear = - 1;
int front = - 1;
main()
{
int choice;
while (1)
{
printf("1.Insert\n");
printf("2.Delete\n");
printf("3.Display\n");
printf("4.Quit \n");
printf("Enter your choice : ");
scanf("%d", &choice);
switch (choice)
{
case 1:
insert();
break;
case 2:
delete();
break;
case 3:
display();
break;
case 4:
exit(1);
default:
printf("Wrong choice \n");
}
}
}

void insert()
{
int add_item;
if (rear == MAX - 1)
printf("Queue Overflow \n");
else
{
if (front == - 1)
/*If queue is initially empty */
front = 0;
printf("Inset the element in queue : ");
 scanf("%d", &add_item);
rear = rear + 1;
queue_array[rear] = add_item;
}
}

void delete()
{
if (front == - 1 || front > rear)
{
printf("Queue Underflow \n");
return ;
}
else
{
printf("Element deleted from queue is : %d\n", queue_array[front]);
front = front + 1;
}
}

void display()
{
int i;
if (front == - 1)
printf("Queue is empty \n");
else
{
printf("Queue is : \n");
for (i = front; i <= rear; i++)
printf("%d ", queue_array[i]);
printf("\n");
}
}

Output :-

1.Insert
2.Delete
3.Display
4.Quit
Enter your choice : 1
Inset the element in queue : 30
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice : 1
Inset the element in queue : 40
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice : 3
Queue is :
30 40
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice : 2
Element deleted from queue is : 30
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice : 3
Queue is :
40

Queue Implementation Using Linked List

Program :-

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

struct node
{
int info;
struct node *ptr;
}*front,*rear,*temp,*front1;

int frontelement();
void enq(int data);
void deq();
void empty();
void display();
void create();
void queuesize();

int count = 0;

void main()
{
int no, ch, e;

create();
while (1)
 {
printf("\n 1 - Insert");
printf("\n 2 - Delete");
printf("\n 3 - Front element");
printf("\n 4 - Empty");
printf("\n 5 - Exit");
printf("\n 6 - Display");
printf("\n 7 - Queue size");

printf("\n Enter choice : ");

scanf("%d", &ch);
switch (ch)
{
case 1:
printf("Enter data : ");
scanf("%d", &no);
enq(no);
break;
case 2:
deq();
break;
case 3:
e = frontelement();
if (e != 0)
printf("Front element : %d", e);
else
printf("\n No front element in Queue as queue is empty");
break;
case 4:
empty();
break;
case 5:
exit(0);
case 6:
display();
break;
case 7:
queuesize();
break;
default:
printf("Wrong choice, Please enter correct choice ");
break;
}
}
}

/* Create an empty queue */

void create()
{
front = rear = NULL;
}

/* Returns queue size */

void queuesize()
{
printf("\n Queue size : %d", count);
}

/* Enqueing the queue */

void enq(int data)
{
if (rear == NULL)
{
rear = (struct node *)malloc(1*sizeof(struct node));
rear->ptr = NULL;
rear->info = data;
front = rear;
}
else
{
temp=(struct node *)malloc(1*sizeof(struct node));
rear->ptr = temp;
temp->info = data;
temp->ptr = NULL;

rear = temp;
}
count++;
}

/* Displaying the queue elements */

void display()
{
front1 = front;

if ((front1 == NULL) && (rear == NULL))

{
printf("Queue is empty");
return;
}
while (front1 != rear)
{
printf("%d ", front1->info);
front1 = front1->ptr;
}
if (front1 == rear)
printf("%d", front1->info);
}

/* Dequeing the queue */

void deq()
{
front1 = front;

if (front1 == NULL)
{
printf("\n Error: Trying to display elements from empty queue");
return;
}
else
if (front1->ptr != NULL)
{
front1 = front1->ptr;
printf("\n Dequed value : %d", front->info);
free(front);
front = front1;
}
else
{
printf("\n Dequed value : %d", front->info);
free(front);
front = NULL;
rear = NULL;
}
count--;
}

/* Returns the front element of queue */

int frontelement()
{
if ((front != NULL) && (rear != NULL))
return(front->info);
else
return 0;
}

/* Display if queue is empty or not */

void empty()
{
if ((front == NULL) && (rear == NULL))
printf("\n Queue empty");
else
printf("Queue not empty");
}

Output :-

1 - Insert
2 - Delete
3 - Front element
4 - Empty
5 - Exit
6 - Display
7 - Queue size
Enter choice : 1
Enter data : 10

1 - Insert
2 - Delete
3 - Front element
4 - Empty
5 - Exit
6 - Display
7 - Queue size
Enter choice : 1
Enter data : 20

1 - Insert
2 - Delete
3 - Front element
4 - Empty
5 - Exit
6 - Display
7 - Queue size
Enter choice : 3
Front element : 10
1 - Insert
2 - Delete
3 - Front element
4 - Empty
5 - Exit
6 - Display
7 - Queue size
Enter choice : 2

Dequed value : 10
1 - Insert
2 - Delete
3 - Front element
4 - Empty
5 - Exit
6 - Display
7 - Queue size
Enter choice : 7

Queue size : 1
1 - Insert
2 - Delete
3 - Front element
 4 - Empty
5 - Exit
6 - Display
7 - Queue size
Enter choice : 6
20

RESULT:
Thus the program and code for implementation of Queue using array and linked list is
successfully written and executed.

LAB 9:
APPLICATIONS OF STACK, QUEUE

AIM:
To execute program based on applications of stack and queue
ALGORITHM:
1.Allocate and initialize a stack and queue. You may store these structures on either the stack
or the heap, but make sure you free them appropriately.

2.Add the letters 'a', 'b', 'c', and 'd' (in that order) to both the stack and the queue.

3.Remove all items from the stack until it is empty and print them in the order that they are
returned.

4.Remove all items from the queue until it is empty and print them in the order that they are
returned.

Infix to postfix conversion using stack

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 : \n");
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

AB+

#1. josephus problem solution in c using queue linked list

Program :-

#include <stdio.h>
#include <stdlib.h>
struct node
{
int num;
struct node *next;
};

void create(struct node **);

void display(struct node *);
int survivor(struct node **, int);

int main()
{
struct node *head = NULL;
int survive, skip;

create(&head);
printf("The persons in circular list are:\n");
display(head);
printf("Enter the number of persons to be skipped: ");
scanf("%d", &skip);
survive = survivor(&head, skip);
printf("The person to survive is : %d\n", survive);
free(head);

return 0;
}

int survivor(struct node **head, int k)

{
struct node *p, *q;
int i;

q = p = *head;
while (p->next != p)
{
for (i = 0; i < k - 1; i++)
{
q = p;
p = p->next;
}
q->next = p->next;
printf("%d has been killed.\n", p->num);
free(p);
p = q->next;
}
*head = p;

return (p->num);
}

void create (struct node **head)

{
struct node *temp, *rear;
int a;
int n, i;
 printf("Enter number of persons you want to insert:\n");
scanf("%d", &n);

for(i = 0; i < n; i++)

{
printf("Enter number person %d : ", i+1);
scanf("%d", &a);
temp = (struct node *)malloc(sizeof(struct node));
temp->num = a;
temp->next = NULL;
if (*head == NULL)
{
*head = temp;
}
else
{
rear->next = temp;
}
rear = temp;
}
rear->next = *head;
}

void display(struct node *head)

{
struct node *temp;

temp = head;
printf("%d ", temp->num);
temp = temp->next;
while (head != temp)
{
printf("%d ", temp->num);
temp = temp->next;
}
printf("\n");
}

Output :-

Enter number of persons you want to insert:

5
Enter number person 1 : 1
Enter number person 2 : 2
Enter number person 3 : 3
Enter number person 4 : 4
Enter number person 5 : 5
The persons in circular list are:
1 2 3 4 5
Enter the number of persons to be skipped: 2
2 has been killed.
4 has been killed.
1 has been killed.
5 has been killed.
The person to survive is : 3

#2. FIrst in First out scheduling using Queue

Program :-

#include <stdio.h>
#include<stdlib.h>
#define MAX 50
void insert();
void delete();
void display();
int queue_array[MAX];
int rear = - 1;
int front = - 1;
int main()
{
int choice;
while (1)
{
printf("1.Insert element to queue \n");
printf("2.Delete element from queue \n");
printf("3.Display all elements of queue \n");
printf("4.Quit \n");
printf("Enter your choice : ");
scanf("%d", &choice);
switch(choice)
{
case 1:
insert();
break;
case 2:
delete();
break;
case 3:
display();
break;
case 4:
exit(1);
default:
printf("Wrong choice\n");
}
}
}

void insert()
{
int item;
if(rear == MAX - 1)
printf("Queue Overflow\n");
else
{
if(front== - 1)
front = 0;
 printf("Insert the element in queue : ");
scanf("%d", &item);
rear = rear + 1;
queue_array[rear] = item;
}
}
void delete()
{
if(front == - 1 || front > rear)
{
printf("Queue Underflow\n");
return;
}
else
{
printf("Element deleted from queue is : %d\n", queue_array[front]);
front = front + 1;
}
}

void display()
{
int i;
if(front == - 1)
printf("Queue is empty\n");
else
{
printf("Queue is :\n");
for(i = front; i <= rear; i++)
printf("%d ", queue_array[i]);
printf("\n");
}
}

Output :-

1.Insert element to queue

2.Delete element from queue
3.Display all elements of queue
4.Quit
Enter your choice : 1
Insert the element in queue : 10
1.Insert element to queue
2.Delete element from queue
3.Display all elements of queue
4.Quit
Enter your choice : 1
Insert the element in queue : 20
1.Insert element to queue
2.Delete element from queue
3.Display all elements of queue
4.Quit
Enter your choice : 2
Element deleted from queue is : 10
1.Insert element to queue
2.Delete element from queue
3.Display all elements of queue
4.Quit
Enter your choice : 2
Element deleted from queue is : 20
1.Insert element to queue
2.Delete element from queue
3.Display all elements of queue
4.Quit
Enter your choice : 2
Queue Underflow
1.Insert element to queue
2.Delete element from queue
3.Display all elements of queue
4.Quit
Enter your choice : 2
Queue Underflow
1.Insert element to queue
2.Delete element from queue
3.Display all elements of queue
4.Quit
Enter your choice : 3
Queue is :

1.Insert element to queue

2.Delete element from queue
3.Display all elements of queue
4.Quit
Enter your choice : 1
Insert the element in queue : 10
1.Insert element to queue
2.Delete element from queue
3.Display all elements of queue
4.Quit
Enter your choice : 1
Insert the element in queue : 20
1.Insert element to queue
2.Delete element from queue
3.Display all elements of queue
4.Quit
Enter your choice : 4

RESULT: Thus the program and code is successfully written and executed

LAB 10:
IMPLEMENTATION OF TREE USING ARRAY

AIM:
To execute program based on implementation of tree using array
ALGORITHM:
1.root of the tree (A): array position 1
2.root's left child (B): array position 2
3.root's right child (C): array position 3
4....
5.left child of node in array position K: array position 2K
6.right child of node in array position K: array position 2K+1
So D is in position 2*2 (4), E is in position 2*2+1 (5), F is in position 2*3 (6), G is in
position 2*3+1 (7).

Program :-

#include <stdio.h>

/*

D
/\
/ \
/ \
A F
/\ /\
/ \ / \
E BR T
/\ / /\
G Q V J L
*/

// variable to store maximum number of nodes

int complete_node = 15;

// array to store the tree

char tree[] = {'\0', 'D', 'A', 'F', 'E', 'B', 'R', 'T', 'G', 'Q', '\0', '\0', 'V', '\0', 'J', 'L'};

int get_right_child(int index)

{
// node is not null
// and the result must lie within the number of nodes for a complete binary tree
if(tree[index]!='\0' && ((2*index)+1)<=complete_node)
return (2*index)+1;
// right child doesn't exist
return -1;
}

int get_left_child(int index)

{
// node is not null
// and the result must lie within the number of nodes for a complete binary tree
if(tree[index]!='\0' && (2*index)<=complete_node)
return 2*index;
// left child doesn't exist
return -1;
}

void preorder(int index)

{
// checking for valid index and null node
if(index>0 && tree[index]!='\0')
{
printf(" %c ",tree[index]); // visiting root
preorder(get_left_child(index)); //visiting left subtree
preorder(get_right_child(index)); //visiting right subtree
}
}

void postorder(int index)

{
// checking for valid index and null node
if(index>0 && tree[index]!='\0')
{
postorder(get_left_child(index)); //visiting left subtree
postorder(get_right_child(index)); //visiting right subtree
printf(" %c ",tree[index]); //visiting root
}
}

void inorder(int index)

{
// checking for valid index and null node
if(index>0 && tree[index]!='\0')
{
inorder(get_left_child(index)); //visiting left subtree
printf(" %c ",tree[index]); //visiting root
inorder(get_right_child(index)); // visiting right subtree
}
}

int main()
{
printf("Preorder:\n");
preorder(1);
printf("\nPostorder:\n");
postorder(1);
printf("\nInorder:\n");
inorder(1);
printf("\n");
return 0;
}

Output :-

Preorder:
D A E G Q B F R V T J L
Postorder:
G Q E B A V R J L T F D
Inorder:
G E Q A B D V R F J T L

RESULT:
Thus the program and code is successfully written and executed

LAB 11:
IMPLEMENTATION OF BST USING LINKED LIST

AIM:
To execute program based on implementation of BST using linked list
ALGORITHM:
1.Begin
2.Take the nodes of the tree as input.
3.Create a structure nod to take the data d, a left pointer l and a right r as input.
4. Create a function create() to insert nodes into the tree:
5. Initialize c = 0 as number of nodes.
6.Perform while loop till c < 6:
7. Enter the root.
8. Enter the value of the node, if it is greater than root then entered as right otherwise left.
9. Create a function inorder() to traverse the node as inorder as:
Left – Root – Right.
10. Create a function preorder() to traverse the node as preorder as:
Root – Left – Right.
11.Create a function postorder() to traverse the node as preorder as:
Left – Right – Root
12. From main(), call the functions and print the result.
13.End

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

struct btnode
{
int value;
struct btnode *l;
struct btnode *r;
}*root = NULL, *temp = NULL, *t2, *t1;

void delete1();
void insert();
void delete();
void inorder(struct btnode *t);
void create();
void search(struct btnode *t);
void preorder(struct btnode *t);
void postorder(struct btnode *t);
void search1(struct btnode *t,int data);
int smallest(struct btnode *t);
int largest(struct btnode *t);

int flag = 1;

void main()
{
int ch;

printf("\nOPERATIONS ---");
printf("\n1 - Insert an element into tree\n");
printf("2 - Delete an element from the tree\n");
printf("3 - Inorder Traversal\n");
printf("4 - Preorder Traversal\n");
 printf("5 - Postorder Traversal\n");
printf("6 - Exit\n");
while(1)
{
printf("\nEnter your choice : ");
scanf("%d", &ch);
switch (ch)
{
case 1:
insert();
break;
case 2:
delete();
break;
case 3:
inorder(root);
break;
case 4:
preorder(root);
break;
case 5:
postorder(root);
break;
case 6:
exit(0);
default :
printf("Wrong choice, Please enter correct choice ");
break;
}
}
}

/* To insert a node in the tree */

void insert()
{
create();
if (root == NULL)
root = temp;
else
search(root);
}

/* To create a node */
void create()
{
int data;

printf("Enter data of node to be inserted : ");

scanf("%d", &data);
temp = (struct btnode *)malloc(1*sizeof(struct btnode));
temp->value = data;
temp->l = temp->r = NULL;
}

/* Function to search the appropriate position to insert the new node */

void search(struct btnode *t)
{
if ((temp->value > t->value) && (t->r != NULL)) /* value more than root node value insert at
right */
search(t->r);
else if ((temp->value > t->value) && (t->r == NULL))
t->r = temp;
else if ((temp->value < t->value) && (t->l != NULL)) /* value less than root node value insert at
left */
search(t->l);
else if ((temp->value < t->value) && (t->l == NULL))
t->l = temp;
}

/* recursive function to perform inorder traversal of tree */

void inorder(struct btnode *t)
{
if (root == NULL)
{
printf("No elements in a tree to display");
return;
}
if (t->l != NULL)
inorder(t->l);
printf("%d -> ", t->value);
if (t->r != NULL)
inorder(t->r);
}

/* To check for the deleted node */

void delete()
{
int data;

if (root == NULL)
{
printf("No elements in a tree to delete");
return;
}
printf("Enter the data to be deleted : ");
scanf("%d", &data);
t1 = root;
t2 = root;
search1(root, data);
}

/* To find the preorder traversal */

void preorder(struct btnode *t)
{
if (root == NULL)
{
printf("No elements in a tree to display");
return;
}
printf("%d -> ", t->value);
 if (t->l != NULL)
preorder(t->l);
if (t->r != NULL)
preorder(t->r);
}

/* To find the postorder traversal */

void postorder(struct btnode *t)
{
if (root == NULL)
{
printf("No elements in a tree to display ");
return;
}
if (t->l != NULL)
postorder(t->l);
if (t->r != NULL)
postorder(t->r);
printf("%d -> ", t->value);
}

/* Search for the appropriate position to insert the new node */

void search1(struct btnode *t, int data)
{
if ((data>t->value))
{
t1 = t;
search1(t->r, data);
}
else if ((data < t->value))
{
t1 = t;
search1(t->l, data);
}
else if ((data==t->value))
{
delete1(t);
}
}

/* To delete a node */
void delete1(struct btnode *t)
{
int k;

/* To delete leaf node */

if ((t->l == NULL) && (t->r == NULL))
{
if (t1->l == t)
{
t1->l = NULL;
}
else
{
t1->r = NULL;
 }
t = NULL;
free(t);
return;
}

/* To delete node having one left hand child */

else if ((t->r == NULL))
{
if (t1 == t)
{
root = t->l;
t1 = root;
}
else if (t1->l == t)
{
t1->l = t->l;

}
else
{
t1->r = t->l;
}
t = NULL;
free(t);
return;
}

/* To delete node having right hand child */

else if (t->l == NULL)
{
if (t1 == t)
{
root = t->r;
t1 = root;
}
else if (t1->r == t)
t1->r = t->r;
else
t1->l = t->r;
t == NULL;
free(t);
return;
}

/* To delete node having two child */

else if ((t->l != NULL) && (t->r != NULL))
{
t2 = root;
if (t->r != NULL)
{
k = smallest(t->r);
flag = 1;
}
else
 {
k =largest(t->l);
flag = 2;
}
search1(root, k);
t->value = k;
}

/* To find the smallest element in the right sub tree */

int smallest(struct btnode *t)
{
t2 = t;
if (t->l != NULL)
{
t2 = t;
return(smallest(t->l));
}
else
return (t->value);
}

/* To find the largest element in the left sub tree */

int largest(struct btnode *t)
{
if (t->r != NULL)
{
t2 = t;
return(largest(t->r));
}
else
return(t->value);
}

Output :-

OPERATIONS ---
1 - Insert an element into tree
2 - Delete an element from the tree
3 - Inorder Traversal
4 - Preorder Traversal
5 - Postorder Traversal
6 - Exit

Enter your choice : 1

Enter data of node to be inserted : 10

Enter your choice : 1

Enter data of node to be inserted : 20

Enter your choice : 1

Enter data of node to be inserted : 8

Enter your choice : 3

8 -> 10 -> 20 ->
Enter your choice : 4
10 -> 8 -> 20 ->
Enter your choice : 5
8 -> 20 -> 10 ->

RESULT:
Thus the program and code is successfully written and executed

LAB 12:
IMPLEMENTATION OF B-TREES

AIM: To execute program based on implementation of B-Trees

ALGORITHM:
1.Begin
2.function insert() to insert the nodes into the tree:
3. Initialize x as root.
4.If x is leaf and having space for one more info then insert a to x else if x is not leaf, do
5.Find the child of x that is going to be traversed next.
6.If the child is not full, change x to point to the child.if the child is full, split it and change x
to point to one of the two parts of the child.

7.If a is smaller than mid key in the child, then set x as first part of the child.
Else second part of the child.
8.When split the child, move a key from the child to its parent x.
9.End

Program:

#include <bits/stdc++.h>
using namespace std;

#define N 4

struct node {

int key[N - 1];

struct node* child[N];
int isleaf;
int n;
struct node* parent;
};

struct node* searchforleaf(struct node* root, int k,struct node* parent, int chindex)
{
if (root) {

if (root->isleaf == 1)
return root;
else {
int i;
if (k < root->key[0])
root = searchforleaf(root->child[0], k, root, 0);
else
{
for (i = 0; i < root->n; i++)
if (root->key[i] > k)
root = searchforleaf(root->child[i], k, root, i);
if (root->key[i - 1] < k)
root = searchforleaf(root->child[i], k, root, i);
}
}
 }
else {

struct node* newleaf = new struct node;

newleaf->isleaf = 1;
newleaf->n = 0;
parent->child[chindex] = newleaf;
newleaf->parent = parent;
return newleaf;
}
}

struct node* insert(struct node* root, int k)

{
if (root) {
struct node* p = searchforleaf(root, k, NULL, 0);
struct node* q = NULL;
int e = k;

for (int e = k; p; p = p->parent) {

if (p->n == 0) {
p->key[0] = e;
p->n = 1;
return root;
}
if (p->n < N - 1) {
int i;
for (i = 0; i < p->n; i++) {
if (p->key[i] > e) {
for (int j = p->n - 1; j >= i; j--)
p->key[j + 1] = p->key[j];
break;
}
}
p->key[i] = e;
p->n = p->n + 1;
return root;
}

// If number of filled keys is equal to maximum

// and it's not root and there is space in the parent
if (p->n == N - 1 && p->parent && p->parent->n < N) {
int m;
for (int i = 0; i < p->parent->n; i++)
if (p->parent->child[i] == p) {
m = i;
break;
}

// If right sibling is possible

 if (m + 1 <= N - 1)
{
// q is the right sibling
q = p->parent->child[m + 1];

if (q) {

// If right sibling is full

if (q->n == N - 1) {
struct node* r = new struct node;
int* z = new int[((2 * N) / 3)];
int parent1, parent2;
int* marray = new int[2 * N];
int i;
for (i = 0; i < p->n; i++)
marray[i] = p->key[i];
int fege = i;
marray[i] = e;
marray[i + 1] = p->parent->key[m];
for (int j = i + 2; j < ((i + 2) + (q->n)); j+
+)
marray[j] = q->key[j - (i + 2)];

// marray=bubblesort(marray, 2*N)
// a more rigorous implementation will
// sort these elements

// Put first (2*N-2)/3 elements into keys

of p
for (int i = 0; i < (2 * N - 2) / 3; i++)
p->key[i] = marray[i];
parent1 = marray[(2 * N - 2) / 3];

// Put next (2*N-1)/3 elements into keys

of q
for (int j = ((2 * N - 2) / 3) + 1; j < (4 *
N) / 3; j++)
q->key[j - ((2 * N - 2) / 3 + 1)] =
marray[j];
parent2 = marray[(4 * N) / 3];

// Put last (2*N)/3 elements into keys of r

for (int f = ((4 * N) / 3 + 1); f < 2 * N; f+
+)
r->key[f - ((4 * N) / 3 + 1)] =
marray[f];

// Because m=0 and m=1 are children of

the same key,
// a special case is made for them
 if (m == 0 || m == 1) {
p->parent->key[0] = parent1;
p->parent->key[1] = parent2;
p->parent->child[0] = p;
p->parent->child[1] = q;
p->parent->child[2] = r;
return root;
}

else {
p->parent->key[m - 1] = parent1;
p->parent->key[m] = parent2;
p->parent->child[m - 1] = p;
p->parent->child[m] = q;
p->parent->child[m + 1] = r;
return root;
}
}
}
else // If right sibling is not full
{
int put;
if (m == 0 || m == 1)
put = p->parent->key[0];
else
put = p->parent->key[m - 1];
for (int j = (q->n) - 1; j >= 1; j--)
q->key[j + 1] = q->key[j];
q->key[0] = put;
p->parent->key[m == 0 ? m : m - 1] = p->key[p-
>n - 1];
}
}
}
}

/*Cases of root splitting, etc. are omitted

as this implementation is just to demonstrate
the two-three split operation*/
}
else
{
// Create new node if root is NULL
struct node* root = new struct node;
root->key[0] = k;
root->isleaf = 1;
root->n = 1;
root->parent = NULL;
}
}
// Driver code
int main()
{
/* Consider the following tree that has been obtained
from some root split:
6
/\
124789

We wish to add 5. This makes the B*-tree:

47
/\\
125689

Contrast this with the equivalent B-tree, in which

some nodes are less than half full

46
/\\
125789

*/

// Start with an empty root

struct node* root = NULL;
// Insert 6
root = insert(root, 6);

// Insert 1, 2, 4 to the left of 6

root->child[0] = insert(root->child[0], 1);
root->child[0] = insert(root->child[0], 2);
root->child[0] = insert(root->child[0], 4);
root->child[0]->parent = root;

// Insert 7, 8, 9 to the right of 6

root->child[1] = insert(root->child[1], 7);
root->child[1] = insert(root->child[1], 8);
root->child[1] = insert(root->child[1], 9);
root->child[1]->parent = root;

cout << "Original tree: " << endl;

for (int i = 0; i < root->n; i++)
cout << root->key[i] << " ";
cout << endl;
for (int i = 0; i < 2; i++) {
cout << root->child[i]->key[0] << " ";
cout << root->child[i]->key[1] << " ";
 cout << root->child[i]->key[2] << " ";
}
cout << endl;

cout << "After adding 5: " << endl;

// Inserting element '5':

root->child[0] = insert(root->child[0], 5);

// Printing nodes

for (int i = 0; i <= root->n; i++)

cout << root->key[i] << " ";
cout << endl;
for (int i = 0; i < N - 1; i++) {
cout << root->child[i]->key[0] << " ";
cout << root->child[i]->key[1] << " ";
}

return 0;
}

Output:
Original Tree:
6
124789
After adding 5:
47
125689

RESULT:
Thus the program and code is successfully written and executed
LAB 13:
IMPLEMENTATION OF GRAPH USING ARRAY

AIM : To write algorithm for a program to implement Graph using Array.

ALGORITHM :

Program:

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

struct AdjListNode
{
int dest;
struct AdjListNode* next;
};

struct AdjList
{
struct AdjListNode *head;
};

struct Graph
{
int V;
struct AdjList* array;
};

struct AdjListNode* newAdjListNode(int dest)

{
struct AdjListNode* newNode =
(struct AdjListNode*) malloc(sizeof(struct AdjListNode));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}

struct Graph* createGraph(int V)

{
 struct Graph* graph =
(struct Graph*) malloc(sizeof(struct Graph));
graph->V = V;

// Create an array of adjacency lists. Size of

// array will be V
graph->array =
(struct AdjList*) malloc(V * sizeof(struct AdjList));

// Initialize each adjacency list as empty by

// making head as NULL
int i;
for (i = 0; i < V; ++i)
graph->array[i].head = NULL;

return graph;
}

void addEdge(struct Graph* graph, int src, int dest)

{
struct AdjListNode* newNode = newAdjListNode(dest);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;

newNode = newAdjListNode(src);
newNode->next = graph->array[dest].head;
graph->array[dest].head = newNode;
}

void printGraph(struct Graph* graph)

{
int v;
for (v = 0; v < graph->V; ++v)
{
struct AdjListNode* pCrawl = graph->array[v].head;
printf("\n Adjacency list of vertex %d\n head ", v);
while (pCrawl)
{
printf("-> %d", pCrawl->dest);
pCrawl = pCrawl->next;
}
printf("\n");
}
}

void main()
{
int V = 5;
struct Graph* graph = createGraph(V);
addEdge(graph, 0, 1);
addEdge(graph, 0, 4);
addEdge(graph, 1, 2);
addEdge(graph, 1, 3);
addEdge(graph, 1, 4);
addEdge(graph, 2, 3);
 addEdge(graph, 3, 4);

printGraph(graph);
}

Output :-

Adjacency list of vertex 0

head -> 4-> 1

Adjacency list of vertex 1

head -> 4-> 3-> 2-> 0

Adjacency list of vertex 2

head -> 3-> 1

Adjacency list of vertex 3

head -> 4-> 2-> 1

Adjacency list of vertex 4

head -> 3-> 1-> 0

RESULT :
The algorithm for a program to implement Graph using Array is written.
LAB 14:
IMPLEMENTATION OF SHORT PATH ALGORITHM

AIM :
To write algorithm for a program to implementation of short path algorithm.
ALGORITHM :
Dijkstra’s algorithm:
1. Select the source node also called the initial node.
2. Define an empty set N that will be used to hold nodes to which a shortest path has been
found.
3. Label the initial node with 0, and insert it into N.
4. Repeat Steps 5 to 7 until the destination node is in N or there are no more labelled nodes in
N.
5. Consider each node that is not in N and is connected by an edge from the newly inserted
node.
6. (a) If the node that is not in N has no label then SET the label of the node = the label of the
newly inserted node + the length of the edge. (b) Else if the node that is not in N was already
labelled, then SET its new label = minimum (label of newly inserted vertex + length of edge,
old label)
7. Pick a node not in N that has the smallest label assigned to it and add it to N.

Program :-
#include<stdio.h>
#include<conio.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:2

Enter the adjacency matrix:

0 10
1 20

Enter the starting node:10

Distance of node0=1460296256
Path=0<-10
Distance of node1=32766
Path=1<-10

RESULT :
Thus the program for implementation of short path algorithm.
LAB 15: IMPLEMENT MINIMAL SPANNING TIME

AIM :
To write algorithm for implementing minimal spanning time

ALGORITHM :
Prim’s algorithm
Step 1: Select a starting vertex
Step 2: Repeat Steps 3 and 4 until there are fringe vertices
Step 3: Select an edge e connecting the tree vertex and fringe vertex that has minimum
weight Add the selected edge and the vertex to the minimum spanning tree T
Step 4:
[END OF LOOP]
Step 5: EXIT
Kruskal’s algorithm
Step 1: Create a forest in such a way that each graph is a separate tree.
Step 2: Create a priority queue Q that contains all the edges of the graph.
Step 3: Repeat Steps 4 and 5 while Q is NOT EMPTY
Step 4:Remove an edge from Q
Step 5: IF the edge obtained in Step 4 connects two different trees, then Add it to the forest
(for combining two trees into one tree).
ELSE
Discard the edge
Step 6: END

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

#define infinity 9999

#define MAX 20

int G[MAX][MAX],spanning[MAX][MAX],n;
int prims();
int main()
{
int i,j,total_cost;
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]);
 total_cost=prims();
printf("\nspanning tree matrix:\n");

for(i=0;i<n;i++)
{
printf("\n");
for(j=0;j<n;j++)
printf("%d\t",spanning[i][j]);
}

printf("\n\nTotal cost of spanning tree=%d",total_cost);

return 0;
}

int prims()
{
int cost[MAX][MAX];
int u,v,min_distance,distance[MAX],from[MAX];
int visited[MAX],no_of_edges,i,min_cost,j;

//create cost[][] matrix,spanning[][]

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];
spanning[i][j]=0;
}

//initialise visited[],distance[] and from[]

distance[0]=0;
visited[0]=1;

for(i=1;i<n;i++)
{
distance[i]=cost[0][i];
from[i]=0;
visited[i]=0;
}

min_cost=0; //cost of spanning tree

no_of_edges=n-1; //no. of edges to be added

while(no_of_edges>0)
{
//find the vertex at minimum distance from the tree
min_distance=infinity;
for(i=1;i<n;i++)
if(visited[i]==0&&distance[i]<min_distance)
{
v=i;
min_distance=distance[i];
 }

u=from[v];

//insert the edge in spanning tree

spanning[u][v]=distance[v];
spanning[v][u]=distance[v];
no_of_edges--;
visited[v]=1;

//updated the distance[] array

for(i=1;i<n;i++)
if(visited[i]==0&&cost[i][v]<distance[i])
{
distance[i]=cost[i][v];
from[i]=v;
}

min_cost=min_cost+cost[u][v];
}

return(min_cost);
}

Output :-

Enter no. of vertices:3

Enter the adjacency matrix:

012
345
678

spanning tree matrix:

0 1 2
1 0 0
2 0 0

Total cost of spanning tree=3

RESULT :
Thus the program for implementation of minimal spanning time.