S11BLH31 DATA STRUCTURES USING C

LAB MANUAL

S.No Program Category Page No

Closed Ended Problem

1. Implementation of Linked List 03

A Singly Linked List 07

B Doubly Linked List 10

C Circular Linked List 13

D Doubly Circular Linked List

2. Insert an element list at beginning, at end and at a

given position in a linked list

A Singly Linked List 16

B Circular Linked List 22

3. Delete an element list at beginning, at end and at a

given position in a linked list

A Singly Linked List 29

B Circular Linked List 34

Semi Open - Ended Problems

4. Implementation of Stacks 39

1|P age
 5. Implementation of Queues 42

6. Searching Techniques

A Linear Search 45

B Binary Search 45

7. Sorting Techniques

A Bubble Sort 48

B Merge Sort 48

Open Ended Problems

8. Trees 51

9. Graphs 55

2|P age
 CLOSED ENDED PROBLEMS
EXPT NO 1 IMPLEMENTATION OF LINKED LIST

1.A. Singly Linked List

Aim:

To create and display the data stored using single linked list

Algorithm:

Step 1: Initialize a structure with two members one for handling data and the other for
handling address.
Step 2: Declare and call two functions for creation of node list and for display of the
contents stored.

Step 3: Call malloc function for allocating dynamic memory to nodes and till the number
of data entry is reached enter the information

Step 4: Display the data by traversing through the first node to last node.

Program Code:

#include <stdio.h>
#include <stdlib.h>
// Creation of node for linked list
struct node
{
int data; //Data of the node
struct node *next; //Address of the next node
}*newnode;
// Creating function for various operations

3|P age
void createNodeList(int n); // function to create the list
void displayList(); // function to display the list
int main()
{
int n;
printf("\n\n Linked List : To create and display Singly Linked List :\n");
printf("-------------------------------------------------------------\n");
printf(" Input the number of nodes : ");
scanf("%d", &n);
createNodeList(n); // Calling a Function to create a list
printf("\n Data entered in the list : \n");
displayList(); // Calling a function to display the created list
return 0;
}
void createNodeList(int n)
{
struct node *fnNode, *tmp;
int data, i;
newnode = (struct node *)malloc(sizeof(struct node));
if(newnode == NULL) //check whether the fnnode is NULL and if so no memory
allocation
{
printf(" Memory can not be allocated.");
}
else
{
// reads data for the node through keyboard
printf(" Input data for node 1 : ");
scanf("%d", &data);
newnode->data = data;
newnode->next = NULL; // links the address field to NULL
tmp = newnode;

4|P age
// Creating n nodes and adding to linked list
for(i=2; i<=n; i++)
{
fnNode = (struct node *)malloc(sizeof(struct node));
if(fnNode == NULL)
{
printf(" Memory can not be allocated.");
break;
}
else
{
printf(" Input data for node %d : ", i);
scanf(" %d", &data);

fnNode->data= data; // links the num field of fnNode with num

fnNode->next = NULL; // links the address field of fnNode with NULL
tmp->next = fnNode; // links previous node i.e. tmp to the fnNode
tmp = tmp->next;
}
}
}
}
void displayList()
{
struct node *tmp;
if(newnode == NULL)
{
printf(" List is empty.");
}
else
{
tmp = newnode;

5|P age
 while(tmp != NULL)
{
printf(" Data = %d\n", tmp->data); // prints the data of current node
tmp = tmp->next; // increments the position of current node
}
}
}
Ouput

6|P age
1.B. Doubly Linked List
Aim:

To create and display the data stored using double linked list

Algorithm:

Step 1: Initialize a structure with three members one for handling data and the other for
handling address of both forward and previous nodes.
Step 2: Declare and call two functions for creation of node list and for display of the
contents stored.

Step 3: Call malloc function for allocating dynamic memory to nodes and till the number
of data entry is reached enter the information

Step 4: Display the data by traversing through the first node to last node.

// implementation of double linked list

#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node * next;
struct node * prev;
}*head,*newnode, *temp;
void create(); // function to create the list
void display(); // function to display the list
int main()
{
int n;
printf("\n\n Linked List : To create and display Double Linked List :\n");

7|P age
printf("-------------------------------------------------------------\n");
create(); // Calling a Function to create a list
printf("\n Data entered in the list : \n");
display(); // Calling a function to display the created list
return 0;
}

void create()
{
head = 0;
int choice,data;
while(choice)
{
newnode = (struct node*)malloc(sizeof(struct node));
printf("enter data");
scanf("%d",&data);
newnode->data = data;
newnode->next = 0;
newnode->prev = 0;
if(head==0)
{
head = temp = newnode;
}
else
{
temp->next = newnode;
newnode->prev = temp;
}
printf("do you want to continue- enter 1 to continue");
scanf("%d",&choice);
}
//free(temp);

8|P age
}
void display()
{
temp = head;
while(temp!=NULL)
{
printf("%d",temp->data);
temp = temp->next;
}
}
Ouput

9|P age
1.C. Circular Linked List
Aim:

To create and display the data stored using single linked list

Algorithm:

Step 1: Initialize a structure with two members one for handling data and the other for
handling address.
Step 2: Declare and call two functions for creation of node list and for display of the
contents stored.

Step 3: Call malloc function for allocating dynamic memory to nodes and till the number
of data entry is reached enter the information

Step 4: Display the data by traversing through the first node to last node.

Program Code:

// implementation of Circular linked list

#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node * next;
}*head,*newnode,*temp;
void create();
void display();
int main()
{
//int n;

10 | P a g e
printf("\n\n Linked List : To create and display Circular Linked List :\n");
printf("-------------------------------------------------------------\n");
create(); // Calling a Function to create a list
printf("\n Data entered in the list : \n");
display(); // Calling a function to display the created list
return 0;
}

void create()
{
head=0;
int choice;
while(choice)
{
newnode = (struct node *)malloc(sizeof(struct node));
printf(" Enter data : ");
scanf("%d", &newnode->data);
newnode->next=0;
if(head==0)
{
head=temp=newnode;
}
else
{
temp->next=newnode;
temp=newnode;
temp->next=head;
}
printf("Enter 1 to continue");
scanf("%d", &choice);
}
}

11 | P a g e
void display()
{
temp = head;
while(temp->next!=head)
{
printf("%d",temp->data);
temp = temp->next;
}
}
Ouput

12 | P a g e
1.D. Circularly Double Linked List
Aim:

To create and display the data stored using single linked list

Algorithm:

Step 1: Initialize a structure with two members one for handling data and the other for
handling address.
Step 2: Declare and call two functions for creation of node list and for display of the
contents stored.

Step 3: Call malloc function for allocating dynamic memory to nodes and till the number
of data entry is reached enter the information

Step 4: Display the data by traversing through the first node to last node.

// implementation of Circularly Double linked list

// implementation of double linked list
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node * next;
struct node * prev;
}*head,*newnode, *temp;
void create(); // function to create the list
void display(); // function to display the list
int main()
{
int n;

13 | P a g e
printf("\n\n Linked List : To create and display Circular Double Linked List :\n");
printf("-------------------------------------------------------------\n");
create(); // Calling a Function to create a list
printf("\n Data entered in the list : \n");
display(); // Calling a function to display the created list
return 0;
}
void create()
{
head = 0;
int choice,data;
while(choice)
{
newnode = (struct node*)malloc(sizeof(struct node));
printf("enter data");
scanf("%d",&data);
newnode->data = data;
newnode->next = 0;
newnode->prev = 0;
if(head==0)
{
head = temp = newnode;
}
else
{
temp->next = newnode;
newnode->prev = temp;
}
printf("do you want to continue- enter 1 to continue");
scanf("%d",&choice);
}
//free(temp);

14 | P a g e
}
void display()
{
temp = head;
while(temp->next!=head)
{
printf("%d",temp->data);
temp = temp->next;
}
printf("\t");
printf("%d",temp->data);
}
Ouput

15 | P a g e
 EXPT NO 2 INSERT AN ELEMENT IN LINKED LIST

2.A. Singly Linked List

Aim:
To insert and display the data stored using single linked list
Algorithm:
Step 1: Initialize a structure with two members one for handling data and the other for
handling address.
Step 2: Declare and call two functions for creation of node list and for display of the
contents stored.
Step 3: Call malloc function for allocating dynamic memory to nodes and till the number
of data entry is reached enter the information
Step 4: Display the data by traversing through the first node to last node.
Step 5: Call various functions to insert the element at given position, end and at
beginning and display the same

Program Code:
#include <stdio.h>
#include <stdlib.h>
// Creation of node for linked list
struct node
{
int data; //Data of the node
struct node *next; //Address of the next node
}*newnode;
// Creating function for various operations
void createNodeList(int n); // function to create the list
void NodeInsertatEnd(int data); // function to insert at end
void NodeInsertatBegin(int data); // function to insert at beginning
void insertNodeAtMiddle(int data, int pos); // function to insert in the middle
void displayList(); // function to display the list

16 | P a g e
int main()
{
int n,data,pos;
printf("\n\n Linked List : To create and display Singly Linked List :\n");
printf("-------------------------------------------------------------\n");
printf(" Input the number of nodes : ");
scanf("%d", &n);
createNodeList(n); // Calling a Function to create a list
printf("\n Data entered in the list : \n");
displayList(); // Calling a function to display the created list
printf(" Input the number to be inserted : ");
scanf("%d", &data);
NodeInsertatEnd(data); // Calling a function to insert at END
printf("\n Data entered in the list after insert: \n");
displayList(); // Calling a function to display the created list after insert
printf(" Input the number to be inserted : ");
scanf("%d", &data);
NodeInsertatBegin(data); // Calling a function to insert at BEGINING
printf("\n Data entered in the list after insert: \n");
displayList(); // Calling a function to display the created list after insert
printf(" Input the number to be inserted : ");
scanf("%d%d", &data,&pos);
insertNodeAtMiddle(data,pos); // Calling a function to insert at given POSITION
printf("\n Data entered in the list after insert: \n");
displayList(); // Calling a function to display the created list after insert
return 0;
}
void createNodeList(int n)
{
struct node *fnNode, *tmp;
int data, i;

17 | P a g e
 newnode = (struct node *)malloc(sizeof(struct node));
if(newnode == NULL) //check whether the fnnode is NULL and if so no memory allocation
{
printf(" Memory can not be allocated.");
}
else
{
// reads data for the node through keyboard
printf(" Input data for node 1 : ");
scanf("%d", &data);
newnode->data = data;
newnode->next = NULL; // links the address field to NULL
tmp = newnode;
// Creating n nodes and adding to linked list
for(i=2; i<=n; i++)
{
fnNode = (struct node *)malloc(sizeof(struct node));
if(fnNode == NULL)
{
printf(" Memory can not be allocated.");
break;
}
else
{
printf(" Input data for node %d : ", i);
scanf(" %d", &data);

fnNode->data= data; // links the num field of fnNode with num

fnNode->next = NULL; // links the address field of fnNode with NULL
tmp->next = fnNode; // links previous node i.e. tmp to the fnNode
tmp = tmp->next;
}

18 | P a g e
 }
}
}
void NodeInsertatEnd(int data)
{
struct node *fnNode, *tmp;
fnNode = (struct node*)malloc(sizeof(struct node));
if(fnNode == NULL)
{
printf(" Memory can not be allocated.");
}
else
{
printf(" Input data for insert : ");
scanf("%d", &data);
fnNode->data = data; //Links the data part
fnNode->next = NULL;
tmp = newnode;
while(tmp->next != NULL)
tmp = tmp->next;
tmp->next = fnNode; //Links the address part
}
}

void NodeInsertatBegin(int data)

{
struct node *fnNode;
fnNode = (struct node*)malloc(sizeof(struct node));
if(fnNode == NULL)
{
printf(" Memory can not be allocated.");

19 | P a g e
 }
else
{
printf(" Input data for insert : ");
scanf("%d", &data);
fnNode->data = data; //Links the data part
fnNode->next = newnode; //Links the address part
newnode = fnNode; //Makes stnode as first node
}
}

void insertNodeAtMiddle(int data, int pos)

{
int i;
struct node *fnNode, *tmp;
fnNode = (struct node*)malloc(sizeof(struct node));
if(fnNode == NULL)
{
printf(" Memory can not be allocated.");
}
else
{
printf(" Input data for insert : ");
scanf("%d", &data);
fnNode->data = data; //Links the data part
fnNode->next = NULL;
tmp = newnode;
for(i=2; i<=pos-1; i++)
{
tmp = tmp->next;

20 | P a g e
 if(tmp == NULL)
break;
}
if(tmp != NULL)
{
fnNode->next = tmp->next; //Links the address part of new node
tmp->next = fnNode;
}
else
{
printf(" Insert is not possible to the given position.\n");
}
}
}

void displayList()
{
struct node *tmp;
if(newnode == NULL)
{
printf(" List is empty.");
}
else
{
tmp = newnode;
while(tmp != NULL)
{
printf(" Data = %d\n", tmp->data); // prints the data of current node
tmp = tmp->next; // increments the position of current node
}
}
}

21 | P a g e
Output

2.B. Circular Linked List

Aim:
To insert and display the data stored using Circular linked list
Algorithm:
Step 1: Initialize a structure with two members one for handling data and the other for
handling address.
Step 2: Declare and call two functions for creation of node list and for display of the
contents stored.
Step 3: Call malloc function for allocating dynamic memory to nodes and till the number
of data entry is reached enter the information
Step 4: Display the data by traversing through the first node to last node.

22 | P a g e
 Step 5: Call various functions to insert the element at given position, end and at
beginning and display the same

Program Code:
#include <stdio.h>
#include <stdlib.h>
// Creation of node for linked list
struct node
{
int data; //Data of the node
struct node *next; //Address of the next node
}*newnode;
// Creating function for various operations
void createNodeList(int n); // function to create the list
void NodeInsertatEnd(int data); // function to insert at end
void NodeInsertatBegin(int data); // function to insert at beginning
void insertNodeAtMiddle(int data, int pos); // function to insert in the middle
void displayList(); // function to display the list

int main()
{
int n,data,pos;
printf("\n\n Linked List : To create and display Singly Linked List :\n");
printf("-------------------------------------------------------------\n");
printf(" Input the number of nodes : ");
scanf("%d", &n);
createNodeList(n); // Calling a Function to create a list
printf("\n Data entered in the list : \n");
displayList(); // Calling a function to display the created list
printf(" Input the number to be inserted : ");
scanf("%d", &data);
NodeInsertatEnd(data); // Calling a function to insert at END

23 | P a g e
 printf("\n Data entered in the list after insert: \n");
displayList(); // Calling a function to display the created list after insert
printf(" Input the number to be inserted : ");
scanf("%d", &data);
NodeInsertatBegin(data); // Calling a function to insert at BEGINING
printf("\n Data entered in the list after insert: \n");
displayList(); // Calling a function to display the created list after insert
printf(" Input the number to be inserted : ");
scanf("%d%d", &data,&pos);
insertNodeAtMiddle(data,pos); // Calling a function to insert at given POSITION
printf("\n Data entered in the list after insert: \n");
displayList(); // Calling a function to display the created list after insert
return 0;
}
void createNodeList(int n)
{
struct node *fnNode, *tmp;
int data, i;
newnode = (struct node *)malloc(sizeof(struct node));
if(newnode == NULL) //check whether the fnnode is NULL and if so no memory allocation
{
printf(" Memory can not be allocated.");
}
else
{
// reads data for the node through keyboard
printf(" Input data for node 1 : ");
scanf("%d", &data);
newnode->data = data;
newnode->next = head; // links the address field to head
tmp = newnode;
// Creating n nodes and adding to linked list

24 | P a g e
 for(i=2; i<=n; i++)
{
fnNode = (struct node *)malloc(sizeof(struct node));
if(fnNode == NULL)
{
printf(" Memory can not be allocated.");
break;
}
else
{
printf(" Input data for node %d : ", i);
scanf(" %d", &data);

fnNode->data= data; // links the num field of fnNode with num

fnNode->next = NULL; // links the address field of fnNode with NULL
tmp->next = fnNode; // links previous node i.e. tmp to the fnNode
tmp = tmp->next;
}
}
}
}
void NodeInsertatEnd(int data)
{
struct node *fnNode, *tmp;
fnNode = (struct node*)malloc(sizeof(struct node));
if(fnNode == NULL)
{
printf(" Memory can not be allocated.");
}
else
{
printf(" Input data for insert : ");

25 | P a g e
 scanf("%d", &data);
fnNode->data = data; //Links the data part
fnNode->next = NULL;
tmp = newnode;
while(tmp->next != head)
tmp = tmp->next;
tmp->next = fnNode; //Links the address part
}
}

void NodeInsertatBegin(int data)

{
struct node *fnNode;
fnNode = (struct node*)malloc(sizeof(struct node));
if(fnNode == NULL)
{
printf(" Memory can not be allocated.");
}
else
{
printf(" Input data for insert : ");
scanf("%d", &data);
fnNode->data = data; //Links the data part
fnNode->next = newnode; //Links the address part
newnode = fnNode; //Makes stnode as first node
}
}
void insertNodeAtMiddle(int data, int pos)
{
int i;
struct node *fnNode, *tmp;

26 | P a g e
 fnNode = (struct node*)malloc(sizeof(struct node));
if(fnNode == NULL)
{
printf(" Memory can not be allocated.");
}
else
{
printf(" Input data for insert : ");
scanf("%d", &data);
fnNode->data = data; //Links the data part
fnNode->next = NULL;
tmp = newnode;
for(i=2; i<=pos-1; i++)
{
tmp = tmp->next;
if(tmp == NULL)
break;
}
if(tmp != NULL)
{
fnNode->next = tmp->next; //Links the address part of new node
tmp->next = fnNode;
}
else
{
printf(" Insert is not possible to the given position.\n");
}
}
}

void displayList()
{

27 | P a g e
 struct node *tmp;
if(newnode == NULL)
{
printf(" List is empty.");
}
else
{
tmp = newnode;
while(tmp->next != head)
{
printf(" Data = %d\n", tmp->data); // prints the data of current node
tmp = tmp->next; // increments the position of current node
}
}
}

Output:

28 | P a g e
 EXPT NO 3 DELETE AN ELEMENT IN LINKED LIST

3.A. Singly Linked List

Aim:
To delete and display the data stored using single linked list
Algorithm:
Step 1: Initialize a structure with two members one for handling data and the other for
handling address.
Step 2: Declare and call two functions for creation of node list and for display of the
contents stored.
Step 3: Call malloc function for allocating dynamic memory to nodes and till the number
of data entry is reached enter the information
Step 4: Display the data by traversing through the first node to last node.
Step 5: Call various functions to delete the element at given position, end and at
beginning and display the same

Program Code:
#include <stdio.h>
#include <stdlib.h>
// Creation of node for linked list
struct node
{
int data; //Data of the node
struct node *next; //Address of the next node
}*newnode, *tmp,*head,*prevnode;
// Creating function for various operations
void createNodeList(int n); // function to create the list
void deleteend(); // function to delete at end
void deletegivenpos(); // function to delete in the middle
void displayList(); // function to display the list

29 | P a g e
int main()
{
int n,data,pos;
printf("\n\n Linked List : To create and display Singly Linked List :\n");
printf("-------------------------------------------------------------\n");
printf(" Input the number of nodes : ");
scanf("%d", &n);
createNodeList(n); // Calling a Function to create a list
printf("\n Data entered in the list : \n");
displayList(); // Calling a function to display the created list
//printf(" Input the number to be deleted : ");
//scanf("%d", &data);
deleteend(); // Calling a function to delete at END
printf("\n Data entered in the list after delete: \n");
displayList(); // Calling a function to display the created list after delete
deletegivenpos(); // Calling a function to delete at given POSITION
printf("\n Data entered in the list after delete: \n");
displayList(); // Calling a function to display the created list after delete
return 0;
}

void createNodeList(int n)
{
struct node *fnNode, *tmp;
int data, i;
newnode = (struct node *)malloc(sizeof(struct node));
if(newnode == NULL) //check whether the fnnode is NULL and if so no memory
allocation
{
printf(" Memory can not be allocated.");
}
else

30 | P a g e
 {
// reads data for the node through keyboard
printf(" Input data for node 1 : ");
scanf("%d", &data);
newnode->data = data;
newnode->next = head; // links the address field to head
tmp = newnode;
// Creating n nodes and adding to linked list
for(i=2; i<=n; i++)
{
fnNode = (struct node *)malloc(sizeof(struct node));
if(fnNode == NULL)
{
printf(" Memory can not be allocated.");
break;
}
else
{
printf(" Input data for node %d : ", i);
scanf(" %d", &data);

fnNode->data= data; // links the num field of fnNode with num

fnNode->next = NULL; // links the address field of fnNode with NULL
tmp->next = fnNode; // links previous node i.e. tmp to the fnNode
tmp = tmp->next;
}
}
}
}

void deleteend()

31 | P a g e
{
struct node*prevnode;
tmp = head;
while(tmp->next!=0)
{
prevnode = tmp;
tmp = tmp->next;
if(tmp == head)
{
tmp = 0;
free(tmp);
}
else
{
prevnode->next = 0;
free(tmp);
}
}
}
void deletegivenpos()
{
struct node*nextnode;
int pos,i=1;
tmp = head;
printf("enter the position");
scanf("%d",&pos);
while(i<pos-1)
{
tmp = tmp->next;
i++;
}
nextnode = tmp->next;

32 | P a g e
tmp->next = nextnode->next;
free(nextnode);
}
void displayList()
{
struct node *tmp;
if(newnode == NULL)
{
printf(" List is empty.");
}
else
{
tmp = newnode;
while(tmp->next != 0)
{
printf(" Data = %d\n", tmp->data); // prints the data of current node
tmp = tmp->next; // increments the position of current node
}
}
//printf("\t");
printf(" Data = %d\n", tmp->data);
}
Output:

33 | P a g e
3.B. Circular Linked List

Aim:
To delete and display the data stored using circular linked list
Algorithm:
Step 1: Initialize a structure with two members one for handling data and the other for
handling address.
Step 2: Declare and call two functions for creation of node list and for display of the
contents stored.
Step 3: Call malloc function for allocating dynamic memory to nodes and till the number
of data entry is reached enter the information
Step 4: Display the data by traversing through the first node to last node.
Step 5: Call various functions to delete the element at given position, end and at
beginning and display the same

Program Code:
#include <stdio.h>
#include <stdlib.h>
// Creation of node for linked list
struct node
{
int data; //Data of the node
struct node *next; //Address of the next node
}*newnode, *tmp,*head,*prevnode;
// Creating function for various operations
void createNodeList(int n); // function to create the list
void deleteend(); // function to delete at end
void deletegivenpos(); // function to delete in the middle
void displayList(); // function to display the list

int main()
{
34 | P a g e
 int n,data,pos;
printf("\n\n Linked List : To create and display Singly Linked List :\n");
printf("-------------------------------------------------------------\n");
printf(" Input the number of nodes : ");
scanf("%d", &n);
createNodeList(n); // Calling a Function to create a list
printf("\n Data entered in the list : \n");
displayList(); // Calling a function to display the created list
//printf(" Input the number to be deleted : ");
//scanf("%d", &data);
deleteend(); // Calling a function to delete at END
printf("\n Data entered in the list after delete: \n");
displayList(); // Calling a function to display the created list after delete
deletegivenpos(); // Calling a function to delete at given POSITION
printf("\n Data entered in the list after delete: \n");
displayList(); // Calling a function to display the created list after delete
return 0;
}

void createNodeList(int n)
{
struct node *fnNode, *tmp;
int data, i;
newnode = (struct node *)malloc(sizeof(struct node));
if(newnode == NULL) //check whether the fnnode is NULL and if so no memory
allocation
{
printf(" Memory can not be allocated.");
}
else
{
// reads data for the node through keyboard

35 | P a g e
 printf(" Input data for node 1 : ");
scanf("%d", &data);
newnode->data = data;
newnode->next = head; // links the address field to head
tmp = newnode;
// Creating n nodes and adding to linked list
for(i=2; i<=n; i++)
{
fnNode = (struct node *)malloc(sizeof(struct node));
if(fnNode == NULL)
{
printf(" Memory can not be allocated.");
break;
}
else
{
printf(" Input data for node %d : ", i);
scanf(" %d", &data);

fnNode->data= data; // links the num field of fnNode with num

fnNode->next = head; // links the address field of fnNode with NULL
tmp->next = fnNode; // links previous node i.e. tmp to the fnNode
tmp = tmp->next;
}
}
}
}

void deleteend()
{
struct node*prevnode;

36 | P a g e
tmp = head;
while(tmp->next!=0)
{
prevnode = tmp;
tmp = tmp->next;
if(tmp == head)
{
tmp = 0;
free(tmp);
}
else
{
prevnode->next = 0;
free(tmp);
}
}
}
void deletegivenpos()
{
struct node*nextnode;
int pos,i=1;
tmp = head;
printf("enter the position");
scanf("%d",&pos);
while(i<pos-1)
{
tmp = tmp->next;
i++;
}
nextnode = tmp->next;
tmp->next = nextnode->next;
free(nextnode);

37 | P a g e
}
void displayList()
{
struct node *tmp;
if(newnode == NULL)
{
printf(" List is empty.");
}
else
{
tmp = newnode;
while(tmp->next != head)
{
printf(" Data = %d\n", tmp->data); // prints the data of current node
tmp = tmp->next; // increments the position of current node
}
}
//printf("\t");
printf(" Data = %d\n", tmp->data);
}
Output:

38 | P a g e
 SEMI OPEN ENDED PROBLEMS

Expt No: 4 IMPLEMENTATION OF STACKS

Aim:
To implement a stack using arrays and perform push and pop operation.
Algorithm:
1. Implementation of stacks using arrays

Step 1: Initialize an array to represent the stack.

Step 2: Use the end of the array to represent the top of the stack.
Step 3: Implement push (add to end), pop (remove from the end),
and peek (check end) operations, ensuring to handle empty and full stack
conditions.

2. Algorithm for Push Operation

Step 1: Before pushing the element to the stack, we check if the stack is full
Step 2: If the stack is full (top == capacity-1) , then Stack Overflows and we cannot
insert the element to the stack
Step 3: Otherwise, we increment the value of top by 1 (top = top + 1) and the new value
is inserted at top position .
Step 4: The elements can be pushed into the stack till we reach the capacity of the stack.

3. Algorithm for Pop Operation

Step 1: Before popping the element from the stack, we check if the stack is empty
Step 2: If the stack is empty (top == -1), then Stack Underflows and we cannot remove
any element from the stack.
Step 3: Otherwise, we store the value at top, decrement the value of top by 1 (top = top –
1) and return the stored top value
39 | P a g e
Program Code:

40 | P a g e
Program Code:

41 | P a g e
Output:

Expt No: 5 IMPLEMENTATION OF QUEUES

Aim:
To implement a queues using arrays and perform push and pop operation.
Algorithm:
1. To implement queues using arrays
Step 1: Create an array arr of size n and take two variables front and rear both of which
will be initialized to 0 which means the queue is currently empty.

Step 2: rear is the index up to which the elements are stored in the array and front is the
index of the first element of the array.
Step 3: Initialize front and rear as 0, but in general we have to initialize it with -1.
Step 4: If we assign rear as 0, rear will always point to next block of the end element, in
fact , rear should point the index of last element,
Step 5: front=rear = 0
Step 6: void queueEnqueue(int data) else part will be executed,
so arr[rear] =data;// rear =0, rear pointing to the latest element
rear++; //now rear = 1, rear pointing to the next block after end element not the
end element

42 | P a g e
Program Code:

43 | P a g e
Program Code:

Output:

44 | P a g e
Expt No: 6 SEARCHING TECHNIQUES
Aim:
To identify an element using linear search algorithm and Binary Search algorithm.
Algorithm:
To search an element using Linear Search
Step 1: Create an array and initialize the necessary Variables.
Step 2: Enter the elements of array and also input the element to be searched.
Step 3: Traverse through the array till the end and Identify whether the element in an
array is equal Search element.
Step 4: If array[i] = = search, then display the index and element value
Step 5: Else display element not found

To search an element using Binary Search

Hint: The elements should be sorted before start searching an element
Step 1: Create an array and initialize the necessary Variables.
Step 2: Enter the elements of array and also input the element to be searched.
Step 3: Identify the middle element
Step 4: If middle element == search element then display middle element
Step 5: If middle element is < search element, increment the index position from middle
else decrement the index position
Step 6: Start the comparison and repeat the steps form 4-5 till search element is reached

Program Code for Linear Search:

45 | P a g e
Output:

46 | P a g e
Program Code for Binary Search:

47 | P a g e
Output:

Expt No: 7 SORTING TECHNIQUES

Aim:
To sort the elements in the required order using bubble sort and merge sort.
Algorithm:
1. Algorithm for sorting the elements using bubble sort

Step 1: Create an array

Step 2: Enter the elements of array
Step 3: Compare two immediate elements of an array
Step 4: If arr[i] > arr[i+1] swap the values else leave in the same position
Step 5: Continue step 4 till all the elements are sorted

48 | P a g e
 2. Algorithm for sorting the elements using merge sort

Step 1: If it is only one element in the list, consider it already sorted, so

return.
Step 2: Divide the list recursively into two halves until it can no more be
divided
Step 3: Merge the smaller lists into new list in sorted order.

Program Code for bubble sort:

49 | P a g e
Output:

Program Code for merge sort:

50 | P a g e
Output:

Expt No: 8 Trees

Question:
Using C program implement a self - balanced tree and insert an element in it.
Aim:

Algorithm:

51 | P a g e
Program Code:

52 | P a g e
53 | P a g e
Output:

54 | P a g e
Expt No: 9 Graphs
Question:
Given a weighted graph and a source vertex in the graph, find the shortest paths from the source
to all the other vertices in the given graph.
Note: The given graph does not contain any negative edge.

Aim:

55 | P a g e
Algorithm:

56 | P a g e
Program Code:

57 | P a g e
Program Code:

58 | P a g e
Ouput:

59 | P a g e