Data Structures Lab (R18) II-I (2019-20)

Course Objectives:
 It covers various concepts of C programming language
 It introduces searching and sorting algorithms
 It provides an understanding of data structures such as stacks and queues.

Course Outcomes:
 Ability to develop C programs for computing and real-life applications using basic
elements like control statements, arrays, functions, pointers and strings, and data
structures like stacks, queues and linked lists.
 Ability to implement searching and sorting algorithms

Data Structures Lab Syllabus

CSE, SRITW Page 1
Data Structures Lab (R18) II-I (2019-20)

Page
S.No. List of Experiments
Nos.

Write a program that uses functions to perform the following

1. operations on singly linked list: 3-10
i) Creation ii) Insertion iii) Deletion iv) Traversal

Write a program that uses functions to perform the following

2. operations on doubly linked list: 11-26
i) Creation ii) Insertion iii) Deletion iv) Traversal

Write a program that uses functions to perform the following

3. operations on circular linked list: 27-37
i) Creation ii) Insertion iii) Deletion iv) Traversal

Write a program that implement stack (its operations) using

4. 38-45
i) Arrays ii) Pointers

Write a program that implement Queue (its operations) using

5. 46-55
i) Arrays ii) Pointers

Write a program that implements the following sorting methods to

6. sort a given list of integers in ascending order 56-60
i) Bubble sort ii) Selection sort iii) Insertion sort

Write a program that use both recursive and non recursive functions
to perform the following searching operations for a Key value in a
7. 61-68
given list of integers:
i) Linear search ii) Binary search

8. Write a program to implement the tree traversal methods. 69-71

9. Write a program to implement the graph traversal methods. 72-78

CSE, SRITW Page 2

Data Structures Lab (R18) II-I (2019-20)

1. Write a program that uses functions to perform the following operations on

singly linked list: i) Creation ii) Insertion iii) Deletion iv) Traversal
Introduction to Single Linked List:
The simplest kind of linked list is a singly liked list (SLL) which has one link per
node. It has two parts, one part contains data and other contains address of next node.

A linked list is formed when many such nodes are linked together to form a
chain. Each node points to the next node present in the order. The first node is always
used as a reference to traverse the list and is called HEAD. The last node points to NULL.
Operations on Singly Linked List
1. Node Creation
struct node
{
int data;
struct node *next;
};
2. Insertion: The insertion into a singly linked list can be performed at different
positions.
 Insertion in singly linked list at beginning
 Insertion in singly linked list at the end
 Insertion in singly linked list after specified Node
3. Deletion and Traversing: The Deletion of a node from a singly linked list can be
performed at different positions.
 Deletion in singly linked list at beginning
 Deletion in singly linked list at the end
 Deletion in singly linked list after the specified node

Source Code:

CSE, SRITW Page 3

Data Structures Lab (R18) II-I (2019-20)

#include<stdio.h>
#include<conio.h>
#include<process.h>
struct node
{
int data;
struct node *next;
}*start=NULL,*q,*t;
int main()
{
int ch;
void insert_beg();
void insert_end();
int insert_pos();
void display();
void delete_beg();
void delete_end();
int delete_pos();
while(1)
{
printf("\n\nSingly Linked List(SLL) Menu ");
printf("\n1.Insert\n2.Display\n3.Delete\n4.Exit\n\n");
printf("Enter your choice(1-4):");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("\n Insert Menu");
printf("\n1.Insert at beginning\n2.Insert at end\n3.Insert at specified
position\n4.Exit");
printf("\n\nEnter your choice(1-4):");
scanf("%d",&ch);

CSE, SRITW Page 4

Data Structures Lab (R18) II-I (2019-20)

switch(ch)
{
case 1: insert_beg(); break;
case 2: insert_end(); break;
case 3: insert_pos(); break;
case 4: exit(0);
default: printf("Wrong Choice!!");
}
break;
case 2: display(); break;
case 3: printf("\n Delete Menu");
printf("\n1.Delete from beginning\n2.Delete from end\n3.Delete from
specified position\n4.Exit");
printf("\n\nEnter your choice(1-4):");
scanf("%d",&ch);
switch(ch)
{
case 1: delete_beg(); break;
case 2: delete_end();break;
case 3: delete_pos();break;
case 4: exit(0);
default: printf("Wrong Choice!!");
}
break;
case 4: exit(0);
default: printf("Wrong Choice!!");
}
}
return 0;
}
void insert_beg()
{
int num;

CSE, SRITW Page 5

Data Structures Lab (R18) II-I (2019-20)

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

printf("Enter data:");
scanf("%d",&num);
t->data=num;
if(start==NULL) //If list is empty
{
t->next=NULL;
start=t;
}
else
{
t->next=start;
start=t;
}
}
void insert_end()
{
int num;
t=(struct node*)malloc(sizeof(struct node));
printf("Enter data:");
scanf("%d",&num);
t->data=num;
t->next=NULL;
if(start==NULL) //If list is empty
{
start=t;
}
else
{
q=start;
while(q->next!=NULL)
q=q->next;
q->next=t;

CSE, SRITW Page 6

Data Structures Lab (R18) II-I (2019-20)

}
}
int insert_pos()
{
int pos,i,num;
if(start==NULL)
{
printf("List is empty!!");
return 0;
}
t=(struct node*)malloc(sizeof(struct node));
printf("Enter data:");
scanf("%d",&num);
printf("Enter position to insert:");
scanf("%d",&pos);
t->data=num;
q=start;
for(i=1;i<pos-1;i++)
{
if(q->next==NULL)
{
printf("There are less elements!!");
return 0;
}
q=q->next;
}
t->next=q->next;
q->next=t;
return 0;
}
void display()
{
if(start==NULL)

CSE, SRITW Page 7

Data Structures Lab (R18) II-I (2019-20)

{
printf("List is empty!!");
}
else
{
q=start;
printf("The linked list is:\n");
while(q!=NULL)
{
printf("%d->",q->data);
q=q->next;
}
}
}
void delete_beg()
{
if(start==NULL)
{
printf("The list is empty!!");
}
else
{
q=start;
start=start->next;
printf("Deleted element is %d",q->data);
free(q);
}
}
void delete_end()
{
if(start==NULL)
{
printf("The list is empty!!");

CSE, SRITW Page 8

Data Structures Lab (R18) II-I (2019-20)

}
else
{
q=start;
while(q->next->next!=NULL)
q=q->next;
t=q->next;
q->next=NULL;
printf("Deleted element is %d",t->data);
free(t);
}
}
int delete_pos()
{
int pos,i;
if(start==NULL)
{
printf("List is empty!!");
return 0;
}
printf("Enter position to delete:");
scanf("%d",&pos);
q=start;
for(i=1;i<pos-1;i++)
{
if(q->next==NULL)
{
printf("There are less elements!!");
return 0;
}
q=q->next;
}
t=q->next;

CSE, SRITW Page 9

Data Structures Lab (R18) II-I (2019-20)

q->next=t->next;
printf("Deleted element is %d",t->data);
free(t);
return 0;
}
OUTPUT:
Singly Linked List(SLL) Menu
1.Insert
2.Display
3.Delete
4.Exit
Enter your choice(1-4):1
Insert Menu
1.Insert at beginning
2.Insert at end
3.Insert at specified position
4.Exit
Enter your choice(1-4):1
Enter data:4
Singly Linked List(SLL) Menu
1.Insert
2.Display
3.Delete
4.Exit
Enter your choice(1-4):2
The linked list is:
4->
Singly Linked List(SLL) Menu
1.Insert
2.Display
3.Delete
4.Exit
Enter your choice (1-4):4

CSE, SRITW Page 10

Data Structures Lab (R18) II-I (2019-20)

2. Write a program that uses functions to perform the following operations on

doubly linked list:
i) Creation ii) Insertion iii) Deletion iv) Traversal
Introduction to Double Linked List:
A Doubly Linked List (DLL) contains an extra pointer, typically called previous
pointer, together with next pointer and data which are there in singly linked list.

Operations on Doubly Linked List:

1. Node Creation
struct node
{
int data;
struct node *prev;
struct node *next;
};
2. Insertion: The insertion into a singly linked list can be performed at different
positions.
 Insertion in singly linked list at beginning
 Insertion in singly linked list at the end
 Insertion in singly linked list after specified Node
3. Deletion and Traversing: The Deletion of a node from a singly linked list can be
performed at different positions.
 Deletion in singly linked list at beginning
 Deletion in singly linked list at the end
 Deletion in singly linked list after the specified node

Source Code:
CSE, SRITW Page 11
Data Structures Lab (R18) II-I (2019-20)

#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 from the following list ...\n");
printf("\n1.Insert in begining\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\n");
printf("\nEnter your choice?\n");
scanf("\n%d",&choice);
switch(choice)
{
case 1: insertion_beginning();
break;

CSE, SRITW Page 12

Data Structures Lab (R18) II-I (2019-20)

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 valid choice..");
}
}
}
void insertion_beginning()
{
struct node *ptr;
int item;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter Item value");
scanf("%d",&item);

CSE, SRITW Page 13

Data Structures Lab (R18) II-I (2019-20)

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->prev=ptr;
head=ptr;
}
printf("\nNode inserted\n");
}
}
void insertion_last()
{
struct node *ptr,*temp;
int item;
ptr = (struct node *) malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter value");
scanf("%d",&item);
ptr->data=item;
if(head == NULL)

CSE, SRITW Page 14

Data Structures Lab (R18) II-I (2019-20)

{
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));
if(ptr == NULL)
{
printf("\n OVERFLOW");
}
else
{
temp=head;
printf("Enter the location");
scanf("%d",&loc);

CSE, SRITW Page 15

Data Structures Lab (R18) II-I (2019-20)

for(i=0;i<loc;i++)
{
temp = temp->next;
if(temp == NULL)
{
printf("\n There are less than %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("\n UNDERFLOW");
}
else if(head->next == NULL)
{
head = NULL;
free(head);
printf("\nnode deleted\n");
}
else

CSE, SRITW Page 16

Data Structures Lab (R18) II-I (2019-20)

{
ptr = head;
head = head -> next;
head -> prev = NULL;
free(ptr);
printf("\nnode deleted\n");
}
}
void deletion_last()
{
struct node *ptr;
if(head == NULL)
{
printf("\n UNDERFLOW");
}
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");
}
}

CSE, SRITW Page 17

Data Structures Lab (R18) II-I (2019-20)

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("\n printing values...\n");
ptr = head;
while(ptr != NULL)
{

CSE, SRITW Page 18

Data Structures Lab (R18) II-I (2019-20)

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)

CSE, SRITW Page 19

Data Structures Lab (R18) II-I (2019-20)

{
printf("\nItem not found\n");
}
}

}
OUTPUT:
*********Main Menu*********
Choose one option from the following list ...
1. Insert in begining
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 begining
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

CSE, SRITW Page 20

Data Structures Lab (R18) II-I (2019-20)

Node inserted
*********Main Menu*********
Choose one option from the following list ...
1. Insert in begining
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 begining
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
12
*********Main Menu*********

CSE, SRITW Page 21

Data Structures Lab (R18) II-I (2019-20)

Choose one option from the following list ...

1. Insert in begining
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 begining
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 begining
2. Insert at last
3. Insert at any random location

CSE, SRITW Page 22

Data Structures Lab (R18) II-I (2019-20)

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
12
89
*********Main Menu*********
Choose one option from the following list ...
1. Insert in begining
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 begining
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

CSE, SRITW Page 23

Data Structures Lab (R18) II-I (2019-20)

7. Search
8. Show
9. Exit
Enter your choice? 5
node deleted
*********Main Menu*********
Choose one option from the following list ...
1. Insert in begining
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 begining
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

CSE, SRITW Page 24

Data Structures Lab (R18) II-I (2019-20)

*********Main Menu*********
Choose one option from the following list ...
1. Insert in begining
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 begining
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 begining
2. Insert at last

CSE, SRITW Page 25

Data Structures Lab (R18) II-I (2019-20)

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..

CSE, SRITW Page 26

Data Structures Lab (R18) II-I (2019-20)

3. Write a program that uses functions to perform the following operations on

circular linked list.
i) Creation ii) Insertion iii) Deletion iv) Traversal
Introduction to circular Linked List:
In a circular Singly linked list, the last node of the list contains a pointer to the
first node of the list. Circular linked list is a linked list where all nodes are connected
to form a circle. There is no NULL at the end. A circular linked list can be a singly
circular linked list or doubly circular linked list.
We traverse a circular singly linked list until we reach the same node where we
started. The circular singly liked list has no beginning and no ending. There is no null
value present in the next part of any of the nodes.

Operations on Circular Linked List:

1. Insertion: The insertion into a singly linked list can be performed at different
positions.
 Insertion at beginning
 Insertion at the end
3. Deletion and Traversing: The Deletion of a node from a singly linked list can be
performed at different positions.
 Deletion at beginning
 Deletion at the end

Source Code:
CSE, SRITW Page 27
Data Structures Lab (R18) II-I (2019-20)

#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *head;
void beginsert ();
void lastinsert ();
void randominsert();
void begin_delete();
void last_delete();
void random_delete();
void display();
void search();
void main ()
{
int choice =0;
while(choice != 7)
{
printf("\n*********Main Menu*********\n");
printf("\nChoose one option from the following list ...\n");
printf("\n1.Insert in begining\n2.Insert at last\n3.Delete from Beginning\n4.Delete
from last\n5.Search for an element\n6.Show\n7.Exit\n");
printf("\nEnter your choice?\n");
scanf("\n%d",&choice);
switch(choice)
{
case 1: beginsert();
break;
case 2: lastinsert();
break;

CSE, SRITW Page 28

Data Structures Lab (R18) II-I (2019-20)

case 3: begin_delete();
break;
case 4: last_delete();
break;
case 5: search();
break;
case 6: display();
break;
case 7: exit(0);
break;
default: printf("Please enter valid choice..");
}
}
}
void beginsert()
{
struct node *ptr,*temp;
int item;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter the node data?");
scanf("%d",&item);
ptr -> data = item;
if(head == NULL)
{
head = ptr;
ptr -> next = head;
}

CSE, SRITW Page 29

Data Structures Lab (R18) II-I (2019-20)

else
{
temp = head;
while(temp->next != head)
temp = temp->next;
ptr->next = head;
temp -> next = ptr;
head = ptr;
}
printf("\nnode inserted\n");
}
}
void lastinsert()
{
struct node *ptr,*temp;
int item;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW\n");
}
else
{
printf("\nEnter Data?");
scanf("%d",&item);
ptr->data = item;
if(head == NULL)
{
head = ptr;
ptr -> next = head;
}
else
{

CSE, SRITW Page 30

Data Structures Lab (R18) II-I (2019-20)

temp = head;
while(temp -> next != head)
{
temp = temp -> next;
}
temp -> next = ptr;
ptr -> next = head;
}
printf("\nnode inserted\n");
}
}
void begin_delete()
{
struct node *ptr;
if(head == NULL)
{
printf("\nUNDERFLOW");
}
else if(head->next == head)
{
head = NULL;
free(head);
printf("\nnode deleted\n");
}
else
{ ptr = head;
while(ptr -> next != head)
ptr = ptr -> next;
ptr->next = head->next;
free(head);
head = ptr->next;
printf("\nnode deleted\n");
}

CSE, SRITW Page 31

Data Structures Lab (R18) II-I (2019-20)

}
void last_delete()
{
struct node *ptr, *preptr;
if(head==NULL)
{
printf("\nUNDERFLOW");
}
else if (head ->next == head)
{
head = NULL;
free(head);
printf("\nnode deleted\n");
}
else
{
ptr = head;
while(ptr ->next != head)
{
preptr=ptr;
ptr = ptr->next;
}
preptr->next = ptr -> next;
free(ptr);
printf("\nnode deleted\n");
}
}
void search()
{
struct node *ptr;
int item,i=0,flag=1;
ptr = head;
if(ptr == NULL)

CSE, SRITW Page 32

Data Structures Lab (R18) II-I (2019-20)

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

CSE, SRITW Page 33

Data Structures Lab (R18) II-I (2019-20)

}
}
}
void display()
{
struct node *ptr;
ptr=head;
if(head == NULL)
{
printf("\nnothing to print");
}
else
{
printf("\n printing values ... \n");
while(ptr -> next != head)
{
printf("%d\n", ptr -> data);
ptr = ptr -> next;
}
printf("%d\n", ptr -> data);
}
}
OUTPUT:
*********Main Menu*********
Choose one option from the following list ...
1. Insert in begining
2. Insert at last
3. Delete from Beginning
4. Delete from last
5. Search for an element
6. Show
7. Exit
Enter your choice? 1

CSE, SRITW Page 34

Data Structures Lab (R18) II-I (2019-20)

Enter the node data? 10

node inserted
*********Main Menu*********
Choose one option from the following list ...
1. Insert in begining
2. Insert at last
3. Delete from Beginning
4. Delete from last
5. Search for an element
6. Show
7. Exit
Enter your choice? 2
Enter Data? 20
node inserted
*********Main Menu*********
Choose one option from the following list ...
1. Insert in begining
2. Insert at last
3. Delete from Beginning
4. Delete from last
5. Search for an element
6. Show
7. Exit
Enter your choice? 2
Enter Data? 30
node inserted
*********Main Menu*********
Choose one option from the following list ...
1. Insert in begining
2. Insert at last
3. Delete from Beginning
4. Delete from last
5. Search for an element

CSE, SRITW Page 35

Data Structures Lab (R18) II-I (2019-20)

6. Show
7. Exit
Enter your choice? 3
node deleted
*********Main Menu*********
Choose one option from the following list ...
1. Insert in begining
2. Insert at last
3. Delete from Beginning
4. Delete from last
5. Search for an element
6. Show
7. Exit
Enter your choice? 4
node deleted
*********Main Menu*********
Choose one option from the following list ...
1. Insert in begining
2. Insert at last
3. Delete from Beginning
4. Delete from last
5. Search for an element
6. Show
7. Exit
Enter your choice? 5
Enter item which you want to search? 20
item found at location 1
*********Main Menu*********
Choose one option from the following list ...
1. Insert in begining
2. Insert at last
3. Delete from Beginning
4. Delete from last

CSE, SRITW Page 36

Data Structures Lab (R18) II-I (2019-20)

5. Search for an element

6. Show
7. Exit
Enter your choice? 6
printing values ...
20
*********Main Menu*********
Choose one option from the following list ...
1. Insert in begining
2. Insert at last
3. Delete from Beginning
4. Delete from last
5. Search for an element
6. Show
7. Exit

Enter your choice?

7

4. Write a program that implement stack (its operations) using

CSE, SRITW Page 37

Data Structures Lab (R18) II-I (2019-20)

i) Arrays ii) Pointers

Introduction to Stacks:
Stack is a linear data structure which follows a particular order in which the
operations are performed. The order may be LIFO(Last In First Out) or FILO(First In
Last Out).

Stack operations:

 Push: Adds an item in the stack. If the stack is full, then it is said to be an Overflow
condition.
 Pop: Removes an item from the stack. The items are popped in the reversed order in
which they are pushed. If the stack is empty, then it is said to be an Underflow
condition.
 Top: Returns top element of stack.
 isEmpty: Returns true if stack is empty, else false.

CSE, SRITW Page 38

Data Structures Lab (R18) II-I (2019-20)

i) Program to implement Stack using Arrays

Source Code:
#include<stdio.h>
int stack[100],choice,n,top,x,i;
void push(void);
void pop(void);
void display(void);
int main()
{
top=-1;
printf("\n Enter the size of STACK[MAX=100]:");
scanf("%d",&n);
printf("\n\t STACK OPERATIONS USING ARRAY");
printf("\n\t 1.PUSH\n\t 2.POP\n\t 3.DISPLAY\n\t 4.EXIT");
do
{
printf("\n Enter the Choice:");
scanf("%d",&choice);
switch(choice)
{
case 1: push();
break;
case 2:pop();
break;
case 3:display();
break;
case 4:printf("\n\t EXIT POINT ");
break;
default: printf ("\n\t Please Enter a Valid Choice(1/2/3/4)");
}
} while(choice!=4);
return 0;
}

CSE, SRITW Page 39

Data Structures Lab (R18) II-I (2019-20)

void push()
{
if(top>=n-1)
{
printf("\n\tSTACK is over flow");
}
else
{
printf(" Enter a value to be pushed:");
scanf("%d",&x);
top++;
stack[top]=x;
}
}
void pop()
{
if(top<=-1)
{
printf("\n\t Stack is under flow");
}
else
{
printf("\n\t The popped elements is %d",stack[top]);
top--;
}
}
void display()
{
if(top>=0)
{
printf("\n The elements in STACK \n");
for(i=top; i>=0; i--)
printf("\n%d",stack[i]);

CSE, SRITW Page 40

Data Structures Lab (R18) II-I (2019-20)

printf("\n Press Next Choice");

}
else
{
printf("\n The STACK is empty");
}

}
OUTPUT:
Enter the size of STACK [MAX=100]:10
STACK OPERATIONS USING ARRAY
1. PUSH
2. POP
3. DISPLAY
4. EXIT
Enter the Choice: 1
Enter a value to be pushed: 12
STACK OPERATIONS USING ARRAY
1. PUSH
2. POP
3. DISPLAY
4. EXIT
Enter the Choice: 1
Enter a value to be pushed: 24
STACK OPERATIONS USING ARRAY
1. PUSH
2. POP
3. DISPLAY
4. EXIT
Enter the Choice: 1
Enter a value to be pushed: 98
STACK OPERATIONS USING ARRAY
1. PUSH

CSE, SRITW Page 41

Data Structures Lab (R18) II-I (2019-20)

2. POP
3. DISPLAY
4. EXIT
Enter the Choice: 3
The elements in STACK
98
24
12
STACK OPERATIONS USING ARRAY
1. PUSH
2. POP
3. DISPLAY
4. EXIT
Press Next Choice
Enter the Choice: 2
The popped elements is 98
STACK OPERATIONS USING ARRAY
1. PUSH
2. POP
3. DISPLAY
4. EXIT
Enter the Choice:3
The elements in STACK
24
12
Press Next Choice
STACK OPERATIONS USING ARRAY
1. PUSH
2. POP
3. DISPLAY
4. EXIT
Enter the Choice: 4
EXIT POINT

CSE, SRITW Page 42

Data Structures Lab (R18) II-I (2019-20)

ii) Program to implement Stack using Pointers

Source Code:
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define MAX_SIZE 3
void push(int i);
void pop(void);
int choice, i;
int *tos, *p1, arr_stack[MAX_SIZE];
int exit_p = 1;
int main() {
int value;
tos = arr_stack; /* tos points to the top of stack */
p1 = arr_stack; /* initialize p1 */
printf("\n Simple Stack Example - Pointers");
do {
printf("\nStack Pointer : Main Menu");
printf("\n1.Push \t2.Pop \tOthers to exit : Your Choice : ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter value: ");
scanf("%d", &value);
push(value);
break;
case 2:
pop();
break;
default:
exit_p = 0;
break;
}

CSE, SRITW Page 43

Data Structures Lab (R18) II-I (2019-20)

} while (exit_p);
return 0;
}
void push(int i) {
if (p1 == (tos + MAX_SIZE)) {
printf("\nStatus : Stack Overflow.\n");
} else {
*p1 = i;
printf("\nPush Value : %d ", *(p1));
p1++;
}
}
void pop(void) {
if (p1 == tos) {
printf("\nStatus : Stack Underflow.\n");
} else {
p1--;
printf("\nPop Value : %d ", *(p1));
}
}
OUTPUT:

Simple Stack Example - Array and Pointers

Stack Pointer : Main Menu
1. Push 2.Pop Others to exit : Your Choice : 1
Enter value: 100
Push Value: 100
Stack Pointer: Main Menu
1.Push 2.Pop Others to exit : Your Choice : 1
Enter value: 200
Push Value : 200
Stack Pointer : Main Menu
1.Push 2.Pop Others to exit : Your Choice : 1
Enter value: 300
CSE, SRITW Page 44
Data Structures Lab (R18) II-I (2019-20)

Push Value : 300

Stack Pointer : Main Menu
1.Push 2.Pop Others to exit : Your Choice : 1
Enter value: 400
Status : Stack Overflow.
Stack Pointer : Main Menu
1.Push 2.Pop Others to exit : Your Choice : 1
Enter value: 500
Status : Stack Overflow.
Stack Pointer : Main Menu
1.Push 2.Pop Others to exit : Your Choice : 1
Enter value: 2
Status : Stack Overflow.
Stack Pointer : Main Menu
1.Push 2.Pop Others to exit : Your Choice : 2
Pop Value : 300
Stack Pointer : Main Menu
1.Push 2.Pop Others to exit : Your Choice : 2
Pop Value : 200
Stack Pointer : Main Menu
1.Push 2.Pop Others to exit : Your Choice : 2
Pop Value : 100
Stack Pointer : Main Menu
1.Push 2.Pop Others to exit : Your Choice : 2
Status : Stack Underflow.
Stack Pointer : Main Menu
1.Push 2.Pop Others to exit : Your Choice : 3
------------------
(program exited with code: 0)

CSE, SRITW Page 45

Data Structures Lab (R18) II-I (2019-20)

5. Write a program that implement Queue (its operations) using

i) Arrays ii) Pointers
Introduction to Queues:
Queue is abstract data type in data structure which works as FIFO principle. FIFO means
“First in First out”, i.e the element which we have inserted first will be deleted first and
the element that we have inserted last will be deleted last. Two variables are used to
implement queue, i.e “rear” and “front”. Insertion (enQueue) will be done at rear side
and deletion (deQueue) will be performed at front side.

Operation on a queue:
The basic operations that can be perform on queue are;
 Insert an element in a queue.
 Delete an element from the queue.

i) Program to implement Queue using Arrays

CSE, SRITW Page 46
Data Structures Lab (R18) II-I (2019-20)

#include<stdio.h>
#include<conio.h>
#define SIZE 10
void enQueue(int);
void deQueue();
void display();
int queue[SIZE], front = -1, rear = -1;
void main()
{
int value, choice;
clrscr();
while(1){
printf("\n\n***** MENU *****\n");
printf("1. Insertion\n2. Deletion\n3. Display\n4. Exit");
printf("\nEnter your choice: ");
scanf("%d",&choice);
switch(choice){
case 1: printf("Enter the value to be insert: ");
scanf("%d",&value);
enQueue(value);
break;
case 2: deQueue();
break;
case 3: display();
break;
case 4: exit(0);
default: printf("\nWrong selection!!! Try again!!!");
}
}
}
void enQueue(int value){

CSE, SRITW Page 47

Data Structures Lab (R18) II-I (2019-20)

if(rear == SIZE-1)
printf("\nQueue is Full!!! Insertion is not possible!!!");
else{
if(front == -1)
front = 0;
rear++;
queue[rear] = value;
printf("\nInsertion success!!!");
}
}
void deQueue(){
if(front == rear)
printf("\nQueue is Empty!!! Deletion is not possible!!!");
else{
printf("\nDeleted : %d", queue[front]);
front++;
if(front == rear)
front = rear = -1;
}
}
void display(){
if(rear == -1)
printf("\nQueue is Empty!!!");
else{
int i;
printf("\nQueue elements are:\n");
for(i=front; i<=rear; i++)
printf("%d\t",queue[i]);
}
}
OUTPUT:

CSE, SRITW Page 48

Data Structures Lab (R18) II-I (2019-20)

***** MENU *****

1. Insertion
2. Deletion
3. Display
4. Exit
Enter your choice: 1

Enter the value to be insert: 10

Insertion success
***** MENU *****
1. Insertion
2. Deletion
3. Display
4. Exit
Enter your choice: 1

Enter the value to be insert: 20

Insertion success
***** MENU *****
1. Insertion
2. Deletion
3. Display
4. Exit
Enter your choice: 1

Enter the value to be insert: 30

Insertion success
***** MENU *****
1. Insertion
2. Deletion
3. Display
4. Exit
Enter your choice: 2
Deleted : 10
***** MENU *****

CSE, SRITW Page 49

Data Structures Lab (R18) II-I (2019-20)

1. Insertion
2. Deletion
3. Display
4. Exit
Enter your choice: 3

Queue elements are:

20 30
***** MENU *****
1. Insertion
2. Deletion
3. Display
4. Exit
Enter your choice: 4

iI) Program to implement Queue using Pointers

CSE, SRITW Page 50

Data Structures Lab (R18) II-I (2019-20)

#define true 1
#define false 0
#include<stdio.h>
#include<conio.h>
#include<process.h>
struct q_point
{
int ele;
struct q_point* n;
};
struct q_point *f_ptr = NULL;
int e_que(void);
void add_ele(int);
int rem_ele(void);
void show_ele();
void main()
{
int ele,choice,j;
while(1)
{
clrscr();
printf("\n\n****IMPLEMENTATION OF QUEUE USING POINTERS****\n");
printf("\n\t\t MENU\n");
printf("\n\t[1] To insert an element");
printf("\n\t[2] To remove an element");
printf("\n\t[3] To display all the elements");
printf("\n\t[4] Exit");
printf("\n\n\tEnter your choice:");
scanf("%d", &choice);
switch(choice)
{
case 1: printf("\n\tElement to be inserted:");
scanf("%d",&ele);

CSE, SRITW Page 51

Data Structures Lab (R18) II-I (2019-20)

add_ele(ele);
getch();
break;
case 2: if(!e_que())
{
j=rem_ele();
printf("\n\t%d is removed from the queue",j);
getch();
}
else
{
printf("\n\tQueue is Empty.");
getch();
break;
case 3: show_ele();
getch();
break;
case 4: exit(1);
break;
default: printf("\n\tInvalid choice.");
getch();
break;
}
}
}
int e_que(void)
{
if(f_ptr==NULL)
return true;
return false;
}

void add_ele(int ele)

CSE, SRITW Page 52

Data Structures Lab (R18) II-I (2019-20)

{
struct q_point *queue = (struct q_point*)malloc(sizeof(struct q_point));
queue->ele = ele;
queue->n = NULL;
if(f_ptr==NULL)
f_ptr = queue;
else
{
struct q_point* ptr;
ptr = f_ptr;
for(ptr=f_ptr ;ptr->n!=NULL; ptr=ptr->n);
ptr->n = queue;
}
}
int rem_ele()
{
struct q_point* queue=NULL;
if(e_que()==false)
{
int j = f_ptr->ele;
queue=f_ptr;
f_ptr = f_ptr->n;
free (queue);
return j;
}
else
{
printf("\n\tQueue is empty.");
return -9999;
}
}

void show_ele()

CSE, SRITW Page 53

Data Structures Lab (R18) II-I (2019-20)

{
struct q_point *ptr=NULL;
ptr=f_ptr;
if(e_que())
{
printf("\n\tQUEUE is Empty.");
return;
}
else
{
printf("\n\tElements present in Queue are:\n\t");
while(ptr!=NULL)
{
printf("%d\t",ptr->ele);
ptr=ptr->n;
}
}
}
OUTPUT:
****IMPLEMENTATION OF QUEUE USING POINTERS****
MENU
[1] To insert an element
[2] To remove an element
[3] To display all the elements
[4] Exit
Enter your choice: 1
Element to be inserted: 23
****IMPLEMENTATION OF QUEUE USING POINTERS****
MENU
[1] To insert an element
[2] To remove an element
[3] To display all the elements
[4] Exit

CSE, SRITW Page 54

Data Structures Lab (R18) II-I (2019-20)

Enter your choice: 3

Elements present in Queue are: 23
****IMPLEMENTATION OF QUEUE USING POINTERS****
MENU
[1] To insert an element
[2] To remove an element
[3] To display all the elements
[4] Exit
Enter your choice: 2
23 is removed from the queue
****IMPLEMENTATION OF QUEUE USING POINTERS****
MENU
[1] To insert an element
[2] To remove an element
[3] To display all the elements
[4] Exit
Enter your choice:4
Exit

CSE, SRITW Page 55

Data Structures Lab (R18) II-I (2019-20)

6. Write a program that implements the following sorting methods to sort a

given list of integers in ascending order
i) Bubble sort ii) Selection sort iii) Insertion sort
i) Program for Bubble sort
Source Code:
#include <stdio.h>
int main()
{
int array[100], n, i, d, swap;
printf("Enter number of elements\n");
scanf("%d", &n);
printf("Enter %d integers\n", n);
for (i = 0; i < n;i++)
{
scanf("%d", &array[i]);
}
for (i = 0 ; i < n - 1; i++)
{
for (d = 0 ; d < n - c - 1; d++)
{
if (array[d] > array[d+1])
{
swap = array[d];
array[d] = array[d+1];
array[d+1] = swap;
}
}
}
printf("Sorted list in ascending order:\n");
for (i = 0; i < n; i++)
printf("%d\n", array[i]);
return 0;
}

CSE, SRITW Page 56

Data Structures Lab (R18) II-I (2019-20)

OUTPUT:
Enter number of elements 5
Enter 5 integers
2
-4
7
8
4
Sorted list in ascending order:
-4
2
4
7
8

CSE, SRITW Page 57

Data Structures Lab (R18) II-I (2019-20)

ii) Program for Selection sort

Source Code:
#include <stdio.h>
int main()
{
int array[100], n, c, d, position, swap;
printf("Enter number of elements\n");
scanf("%d", &n);
printf("Enter %d integers\n", n);
for (c = 0; c < n; c++)
scanf("%d", &array[c]);
for (c = 0; c < (n - 1); c++)
{
position = c;
for (d = c + 1; d < n; d++)
{
if (array[position] > array[d])
position = d;
}
if (position != c)
{
swap = array[c];
array[c] = array[position];
array[position] = swap;
}
}
printf("Sorted list in ascending order:\n");
for (c = 0; c < n; c++)
printf("%d\n", array[c]);
return 0;
}

CSE, SRITW Page 58

Data Structures Lab (R18) II-I (2019-20)

OUTPUT:
Enter number of elements 6
Enter 6 integers
2
1
10
5
8
3
Sorted list in ascending order:
1
2
3
5
8
10

CSE, SRITW Page 59

Data Structures Lab (R18) II-I (2019-20)

ii) Program for Insertion sort

Source Code:
#include <stdio.h>
int main()
{
int n, array[1000], c, d, temp;
printf("Enter number of elements\n");
scanf("%d", &n);
printf("Enter %d integers\n", n);
for (c = 0; c < n; c++)
scanf("%d", &array[c]);
for (c = 1 ; c <= n - 1; c++) {
d = c;
while ( d > 0 && array[d-1] > array[d]) {
temp = array[d];
array[d] = array[d-1];
array[d-1] = temp;
d--; }
}
printf("Sorted list in ascending order:\n");
for (c = 0; c <= n - 1; c++) {
printf("%d\n", array[c]);
}
return 0;
}
OUTPUT:
Enter number of elements 3
Enter 5 integers
2 -4 7
Sorted list in ascending order:
-4
2

CSE, SRITW Page 60

Data Structures Lab (R18) II-I (2019-20)

7. Write a program that uses both recursive and non recursive functions to
perform the following searching operations for a Key value in a given list of
integers:
i) Linear search ii) Binary search
Introduction to Searching:
Searching is the process of finding some particular element in the list. If the
element is present in the list, then the process is called successful and the process
returns the location of that element, otherwise the search is called unsuccessful.
There are two popular search methods that are widely used in order to search some
item into the list. However, choice of the algorithm depends upon the arrangement of
the list.
 Linear Search
 Binary Search
Linear Search
Linear search is the simplest search algorithm and often called sequential search.
In this type of searching, we simply traverse the list completely and match each element
of the list with the item whose location is to be found. If the match found then location
of the item is returned otherwise the algorithm return NULL.
Binary Search
Binary search is the search technique which works efficiently on the sorted lists.
Hence, in order to search an element into some list by using binary search technique, we
must ensure that the list is sorted.
Binary search follows divide and conquer approach in which, the list is divided
into two halves and the item is compared with the middle element of the list. If the
match is found then, the location of middle element is returned otherwise, we search
into either of the halves depending upon the result produced through the match.

CSE, SRITW Page 61

Data Structures Lab (R18) II-I (2019-20)

Non- Recursive Programs:

i. linear search
SOURCE CODE
#include <stdio.h>
#include<stdlib.h>
int main() {
int key,n,i;
printf(“\n Enter the size of the array : “);
scanf(“%d”, &n);
printf(“\n Enter %d integers : “, n);
for(i = 0; i < n; i++)
scanf(“%d”, &a[i]);
printf(“\n Enter a value to be searched : “);
scanf(“%d”, &key);
for(i = 0; i < n; i++)
if(key == a[i]) {
printf(“\n Key value is found at position 8.\n”, i + 1);
exit(0);
}
printf(“\n Given key is not found in the list. \n”);
return 0;
}
OUTPUT:
Enter the size of the array: 10
Enter 10 integers: 10 23 45 63 2 3 4 38 36 54
Enter a value to be searched: 4
Key value is found at position 8.

Enter the size of the array: 5

Enter 10 integers: 23 3 38 36 54
Enter a value to be searched: 4
Given key is not found in the list

CSE, SRITW Page 62

Data Structures Lab (R18) II-I (2019-20)

ii. Binary search

SOURCE CODE
#include <stdio.h>
int main()
{
int c, first, last, middle, n, search, array[100];
printf("Enter number of elements\n");
scanf("%d",&n);
printf("Enter %d integers\n", n);
for (c = 0; c < n; c++)
scanf("%d",&array[c]);
printf("Enter value to find\n");
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.\n", 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.\n", search);
return 0;
}

CSE, SRITW Page 63

Data Structures Lab (R18) II-I (2019-20)

OUTPUT:
Enter number of elements 6
Enter 6 integers
20 27 40 50 58 99
Enter value to find 27
27 found at location 2

Enter number of elements 6

Enter 6 integers
20 27 40 50 58 99
Enter value to find 21
Not found!21 isn't present in the list

CSE, SRITW Page 64

Data Structures Lab (R18) II-I (2019-20)

Recursive Programs:
iii. linear search using recursion
SOURCE CODE
#include<stdio.h>
int a[5];
int linear(int num,int position) //function definition
{
if(num==a[position])
{
return position;
}
else
{
position++;
return linear(num,position);
}
}
void main()
{
int i,n,ans;
printf("Enter 5 numbers\n");
for(i=0;i<=4;i++)
{
scanf("%d", &a[i]);
}
printf("\nEnter the number to be searched\n");
scanf("%d",&n);
ans=linear(n,0); //function call
if(ans<=4)
{
printf("Number (%d) found at position (%d)",n,ans+1);
}
else

CSE, SRITW Page 65

Data Structures Lab (R18) II-I (2019-20)

{
printf("Didnot find the number (%d)",n);
}

}
OUTPUT:
Enter 5 numbers
10 12 4 78 99
Enter the number to be searched 99
Number 99 found at position 5

Enter 5 numbers
10 12 4 78 99
Enter the number to be searched 2
Didnot find the number 2

CSE, SRITW Page 66

Data Structures Lab (R18) II-I (2019-20)

iv. Binary search using recursion

SOURCE CODE
#include<stdio.h>
int binarySearch(int[], int, int, int);
void main ()
{
int arr[10] = {16, 19, 20, 23, 45, 56, 78, 90, 96, 100};
int item, location=-1;
printf("Enter the item which you want to search ");
scanf("%d",&item);
location = binarySearch(arr, 0, 9, item);
if(location != -1)
{
printf("Item found at location %d",location);
}
else
{
printf("Item not found");
}
}
int binarySearch(int a[], int beg, int end, int item)
{
int mid;
if(end >= beg)
{
mid = (beg + end)/2;
if(a[mid] == item)
{
return mid+1;
}
else if(a[mid] < item)
{
return binarySearch(a,mid+1,end,item);

CSE, SRITW Page 67

Data Structures Lab (R18) II-I (2019-20)

}
else
{
return binarySearch(a,beg,mid-1,item);
}

}
return -1;
}
OUTPUT:
Enter the item which you want to search
19
Item found at location 2

Enter the item which you want to search

22
Item not found

CSE, SRITW Page 68

Data Structures Lab (R18) II-I (2019-20)

8. Write a program to implement the tree traversal methods.

Traversing a tree means visiting every node in the tree.
There are three ways which we use to traverse a tree −
 In-order Traversal
 Pre-order Traversal
 Post-order Traversal
Inorder traversal
1. First, visit all the nodes in the left subtree
2. Then the root node
3. Visit all the nodes in the right subtree
Preorder traversal
1. Visit root node
2. Visit all the nodes in the left subtree
3. Visit all the nodes in the right subtree
Postorder traversal
1. visit all the nodes in the left subtree
2. visit the root node
3. visit all the nodes in the right subtree

SOURCE CODE:
#include <stdio.h>
#include <stdlib.h>

CSE, SRITW Page 69

Data Structures Lab (R18) II-I (2019-20)

struct node
{
int data;
struct node* left;
struct node* right;
};
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
void printPostorder(struct node* node)
{
if (node == NULL)
return;
printPostorder(node->left);
printPostorder(node->right);
printf("%d ", node->data);
}
void printInorder(struct node* node)
{
if (node == NULL)
return;
printInorder(node->left);
printf("%d ", node->data);

printInorder(node->right);
}
void printPreorder(struct node* node)

CSE, SRITW Page 70

Data Structures Lab (R18) II-I (2019-20)

{
if (node == NULL)
return;
printf("%d ", node->data);
printPreorder(node->left);
printPreorder(node->right);
}
int main()
{
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
printf("\nPreorder traversal of binary tree is \n");
printPreorder(root);
printf("\nInorder traversal of binary tree is \n");
printInorder(root);
printf("\nPostorder traversal of binary tree is \n");
printPostorder(root);
getch();
return 0
}
Output:
Preorder traversal of binary tree is
12453
Inorder traversal of binary tree is
42513
Postorder traversal of binary tree is
45231
9. Write a program to implement the graph traversal methods.
Graph Traversal Methods:

CSE, SRITW Page 71

Data Structures Lab (R18) II-I (2019-20)

Traversing the graph means examining all the nodes and vertices of the graph. There
are two standard methods by using which, we can traverse the graphs.
 Breadth First Search
 Depth First Search
Breadth First Search (BFS) Algorithm
Breadth first search is a graph traversal algorithm that starts traversing the
graph from root node and explores all the neighboring nodes. Then, it selects the
nearest node and explores all the unexplored nodes
The algorithm starts with examining the node A and all of its neighbors. In the
next step, the neighbors of the nearest node of A are explored and process continues in
the further steps. The algorithm explores all neighbors of all the nodes and ensures that
each node is visited exactly once and no node is visited twice.

Depth First Search (DFS) Algorithm

Depth first search (DFS) algorithm starts with the initial node of the graph G, and
then goes to deeper and deeper until we find the goal node or the node which has no
children. The algorithm, then backtracks from the dead end towards the most recent
node that is yet to be completely unexplored.
The data structure which is being used in DFS is stack. The process is similar to
BFS algorithm. In DFS, the edges that lead to an unvisited node are called discovery
edges while the edges that lead to an already visited node are called block edges.

i) BREADTH FIRST SEARCH

SOURCE CODE:

CSE, SRITW Page 72

Data Structures Lab (R18) II-I (2019-20)

#include<stdio.h>
#include<stdlib.h>
#define MAX 100
#define initial 1
#define waiting 2
#define visited 3
int n;
int adj[MAX][MAX];
int state[MAX];
void create_graph();
void BF_Traversal();
void BFS(int v);
int queue[MAX], front = -1,rear = -1;
void insert_queue(int vertex);
int delete_queue();
int isEmpty_queue();
int main()
{
create_graph();
BF_Traversal();
return 0;
}
void BF_Traversal()
{
int v;
for(v=0; v<n; v++)
state[v] = initial;
printf("Enter Start Vertex for BFS: \n");
scanf("%d", &v);
BFS(v);
}
void BFS(int v)
{

CSE, SRITW Page 73

Data Structures Lab (R18) II-I (2019-20)

int i;
insert_queue(v);
state[v] = waiting;
while(!isEmpty_queue())
{
v = delete_queue( );
printf("%d ",v);
state[v] = visited;
for(i=0; i<n; i++)
{
if(adj[v][i] == 1 && state[i] == initial)
{
insert_queue(i);
state[i] = waiting;
}
}
}
printf("\n");
}
void insert_queue(int vertex)
{
if(rear == MAX-1)
printf("Queue Overflow\n");
else
{
if(front == -1)
front = 0;
rear = rear+1;
queue[rear] = vertex ;
}
}
int isEmpty_queue()
{

CSE, SRITW Page 74

Data Structures Lab (R18) II-I (2019-20)

if(front == -1 || front > rear)

return 1;
else
return 0;
}
int delete_queue()
{
int delete_item;
if(front == -1 || front > rear)
{
printf("Queue Underflow\n");
exit(1);
}
delete_item = queue[front];
front = front+1;
return delete_item;
}
void create_graph()
{
int count,max_edge,origin,destin;
printf("Enter number of vertices : ");
scanf("%d",&n);
max_edge = n*(n-1);
for(count=1; count<=max_edge; count++)
{
printf("Enter edge %d( -1 -1 to quit ) : ",count);
scanf("%d %d",&origin,&destin);
if((origin == -1) && (destin == -1))
break;
if(origin>=n || destin>=n || origin<0 || destin<0)
{
printf("Invalid edge!\n");
count--;

CSE, SRITW Page 75

Data Structures Lab (R18) II-I (2019-20)

}
else
{
adj[origin][destin] = 1;
}
}
}
OUTPUT:

Enter number of vertices: 9

Enter edge 1( -1 -1 to quit ) : 0 1
Enter edge 2( -1 -1 to quit ) : 0 3
Enter edge 3( -1 -1 to quit ) : 0 4
Enter edge 4( -1 -1 to quit ) : 1 2
Enter edge 5( -1 -1 to quit ) : 3 6
Enter edge 6( -1 -1 to quit ) : 4 7
Enter edge 7( -1 -1 to quit ) : 6 4
Enter edge 8( -1 -1 to quit ) : 6 7
Enter edge 9( -1 -1 to quit ) : 2 5
Enter edge 10( -1 -1 to quit ) : 4 5
Enter edge 11( -1 -1 to quit ) : 7 5
Enter edge 12( -1 -1 to quit ) :7 8
Enter edge 13( -1 -1 to quit ) : -1
Enter start vertex for BFS :
0
013426578

ii) DEPTH FIRST SEARCH

SOURCE CODE:
#include<stdio.h>

void DFS(int);

CSE, SRITW Page 76

Data Structures Lab (R18) II-I (2019-20)

int G[10][10],visited[10],n; //n is no of vertices and graph is sorted in array

G[10][10]

void main()

int i,j;

printf("Enter number of vertices:");

scanf("%d",&n);

//read the adjecency matrix

printf("\nEnter adjecency matrix of the graph:");

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

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

scanf("%d",&G[i][j]);

//visited is initialized to zero

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

visited[i]=0;

DFS(0);

void DFS(int i)

int j;

printf("\n%d",i);

visited[i]=1;

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

CSE, SRITW Page 77

Data Structures Lab (R18) II-I (2019-20)

if(!visited[j]&&G[i][j]==1)

DFS(j);

OUTPUT:
Enter number of vertices: 8
Enter adjacency matrix of the graph:
01111000
10000100
10000100
10000010
10000010
01100001
00011001
00000110

0
1
5
2
7
6
3
4

CSE, SRITW Page 78