A.

NARENDAR
Asst.Prof.

DATA STRUCTURES LAB MANUAL

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

on singly linked list.:
i)Creation ii) Insertion iii) Deletion iv) Traversal
2.Write a program that uses functions to perform the following operations
on doubly linked list.:
i)Creation ii) Insertion iii) Deletion iv) Traversal
3.Write a program that uses functions to perform the following operations
on circular linked list.:
i)Creation ii) Insertion iii) Deletion iv) Traversal
4.Write a program that implement Queue (its operations) using
i)Arrays ii) Pointers
5.Write a program that implement Queue (its operations) using
i) Arrays ii) Pointers
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
7.Write a program that use 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
8.Write a program to implement the tree traversal methods.
9.Write a program to implement the graph traversal methods

1
 A.NARENDAR
Asst.Prof.

1: Write a program that uses functions to perform the following operations on singly
linked list.:
i) Creation ii) Insertion iii) Deletion iv) Traversal
#include<stdio.h>
#include<stdlib.h>
void create();
void display();
void insert_first();
void insert_last();
void insert_before();
void insert_after();
void del_first();
void del_last();
void del_node();
void modify();
void search();
struct slink
{
int data;
struct slink *link;
};
struct slink *start=NULL,*temp,*prev;
void main()
{
int ch;
while(1)
{
printf("\n\n\t *****Single Linked List Operations***** ");
printf("\n 1. Create ");
printf("\n 2. Display ");
printf("\n 3. Insert First ");
printf("\n 4. Insert Last ");
printf("\n 5. Insert After");
printf("\n 6. Insert Before ");
printf("\n 7. Delete First");
printf("\n 8. Delete Last ");
printf("\n 9. Delete Node ");

2
 A.NARENDAR
Asst.Prof.

printf("\n 10. Modify ");

printf("\n 11. Search");
printf("\n 12. Exit ");
printf("\n Enter U R Choice ");
scanf("%d",&ch);
switch(ch)
{
case 1 : create(); break;
case 2 : display(); break;
case 3 : insert_first(); break;
case 4 : insert_last(); break;
case 5 : insert_after(); break;
case 6 : insert_before(); break;
case 7 : del_first();break;
case 8 : del_last();break;
case 9 : del_node(); break;
case 10 : modify(); break;
case 11 : search();break;
case 12 : exit(0); break;
default : printf("\n Invalid Operation");
}
}
}
void create()
{
struct slink *newNode;
char cch='y';
while(cch=='y'||cch=='Y')
{
newNode=(struct slink *)malloc(sizeof(struct slink));
printf("\n Enter New Node ");
scanf("%d",&newNode->data);
newNode->link=NULL;
if(start==NULL)
start=newNode;
else
{
temp=start;

3
 A.NARENDAR
Asst.Prof.

while(temp->link!=NULL)
{
temp=temp->link;
}
temp->link=newNode;
}
printf("\n Do u want to create another node (y/n) :");
fflush(stdin);
scanf("%c",&cch);
}
}
void display()
{
if(start==NULL) // if no nodes are present
printf("\n Sorry No Node to Display ");
else
{
printf("\n Node values are :\n ");
temp=start;
while(temp!=NULL)
{
printf("\t%d",temp->data);
temp=temp->link;
}
}
}
void insert_first()
{
struct slink *newNode;
newNode=(struct slink *)malloc(sizeof(struct slink));
printf("\n Enter New Node ");
scanf("%d",&newNode->data);
newNode->link=NULL;
newNode->link=start;
start=newNode;
printf("\n New Node is inserted as first node ");
}
void insert_last()

4
 A.NARENDAR
Asst.Prof.

{
struct slink *newNode;
newNode=(struct slink *)malloc(sizeof(struct slink));
printf("\n Enter new node ");
scanf("%d",&newNode->data);
newNode->link=NULL;
temp=start;
while(temp->link!=NULL)
{
temp=temp->link;
}
temp->link=newNode;
printf("\n New Node is inserted at last");
}
void insert_after()
{
struct slink *newNode,*ptr;
int n,f=0;
printf("\n Enter Which node after you want to insert");
scanf("%d",&n);
temp=start;
while(temp->link!=NULL)
{
if(temp->data==n)
{
f=1;
newNode=(struct slink *)malloc(sizeof(struct slink));
printf("\n Enter node value ");
scanf("%d",&newNode->data);
newNode->link=NULL;
newNode->link=temp->link;
temp->link=newNode;
printf("\n New Node is inserted after %d node",temp->data);
break;
}
temp=temp->link;
}
if(f==0)

5
 A.NARENDAR
Asst.Prof.

printf("\n No Node Exist with that value");

}
void insert_before()
{
struct slink *newNode;
int n,f=0;
printf("\n Enter Which node after you want to insert ");
scanf("%d",&n);
temp=start;
while(temp->link!=NULL)
{
if(temp->data==n)
{
f=1;
newNode=(struct slink *)malloc(sizeof(struct slink));
printf("\n Enter node ");
scanf("%d",&newNode->data);
newNode->link=NULL;
newNode->link=temp;
prev->link=newNode;
printf("\n New Node is inserted before %d node",n);
}
prev=temp;
temp=temp->link;
}
if(f==0)
printf("\n No Node Exist with that value");
}
void del_first()
{
struct slink *ptr;
ptr=start->link;
free(start);
printf("\n First Node is Deleted ");
start=ptr;
}
void del_last()
{

6
 A.NARENDAR
Asst.Prof.

temp=start;
while(temp->link!=NULL)
{
prev=temp;
temp=temp->link;
}
free(temp);
prev->link=NULL;
printf("\n Last Node is deleted ");
}
void del_node()
{
int dno,f=0;
printf("\n Enter which node you want to delete ");
scanf("%d",&dno);
temp=start;
while(temp!=NULL)
{
if(temp->data==dno)
{
f=1;
prev->link=temp->link;
free(temp);
printf("\n %d node is deleted ",dno);
break;
}
prev=temp;
temp=temp->link;
}
if(f==0)
printf("\n no node exist with that value");
}
void search()
{
int mno,f=0;
if(start==NULL)
printf("\n No nodes to search ");
else

7
 A.NARENDAR
Asst.Prof.

{
printf("\n Enter node data to search ");
scanf("%d",&mno);
temp=start;
while(temp!=NULL)
{
if(temp->data==mno)
{
f=1;
printf("\n %d node is found in a list",temp->data);
break;
}
temp=temp->link;
}
}
if(f==0)
printf("\n No Node with that value..");
}
void modify()
{
int mno,f=0;
if(start==NULL)
printf("\n No nodes to search ");
else
{
printf("\n Enter node data to modify ");
scanf("%d",&mno);
temp=start;
while(temp!=NULL)
{
if(temp->data==mno)
{
f=1;
printf("\n Enter Node Value ");
scanf("%d",&temp->data);
break;
}
temp=temp->link;

8
 A.NARENDAR
Asst.Prof.

}
}
if(f==0)
printf("\n No Node with that value..");
}

Output:
*****Single Linked List Operations*****
1.Create
2.Display
3.Insert First
4.Insert Last
5.Insert After
6.Insert Before
7.Delete First
8.Delete Last
9.Delete Node
10.Modify
11.Search
12.Exit
Enter u r choice 1
Enter New Node 12
Do u want to create another node(y/n) : y
Enter New Node 13
Do u want to create another node(y/n) : y
Enter New Node 14
Do u want to create another node(y/n) : n
*****Single Linked List Operations*****
1.Create
2.Display
3.Insert First
4.Insert Last
5.Insert After
6.Insert Before
7.Delete First
8.Delete Last
9.Delete Node
10.Modify

9
 A.NARENDAR
Asst.Prof.

11.Search
12.Exit
Enter u r choice 2
Node Values are :
12 13 14
*****Single Linked List Operations*****
1.Create
2.Display
3.Insert First
4.Insert Last
5.Insert After
6.Insert Before
7.Delete First
8.Delete Last
9.Delete Node
10.Modify
11.Search
12.Exit
Enter u r choice 3
Enter New Node 100
New node is inserted as first node
*****Single Linked List Operations*****
1.Create
2.Display
3.Insert First
4.Insert Last
5.Insert After
6.Insert Before
7.Delete First
8.Delete Last
9.Delete Node
10.Modify
11.Search
12.Exit
Enter u r choice 4
Enter new node 200
New node is inserted at last
*****Single Linked List Operations*****

10
 A.NARENDAR
Asst.Prof.

1.Create
2.Display
3.Insert First
4.Insert Last
5.Insert After
6.Insert Before
7.Delete First
8.Delete Last
9.Delete Node
10.Modify
11.Search
12.Exit
Enter u r choice 5
Enter which node after u want to insert 12
Enter node value 101
New Node is inserted after 12 node
*****Single Linked List Operations*****
1.Create
2.Display
3.Insert First
4.Insert Last
5.Insert After
6.Insert Before
7.Delete First
8.Delete Last
9.Delete Node
10.Modify
11.Search
12.Exit
Enter u r choice 2
Node values are :
100 12 101 13 14 200
*****Single Linked List Operations*****
1.Create
2.Display
3.Insert First
4.Insert Last
5.Insert After

11
 A.NARENDAR
Asst.Prof.

6.Insert Before
7.Delete First
8.Delete Last
9.Delete Node
10.Modify
11.Search
12.Exit
Enter u r choice 6
Enter Which node before you want to insert 101
Enter node 102
New Node is inserted before 101 node
*****Single Linked List Operations*****
1.Create
2.Display
3.Insert First
4.Insert Last
5.Insert After
6.Insert Before
7.Delete First
8.Delete Last
9.Delete Node
10.Modify
11.Search
12.Exit
Enter u r choice 2
Node Values are :
100 12 102 101 13 14 200
*****Single Linked List Operations*****
1.Create
2.Display
3.Insert First
4.Insert Last
5.Insert After
6.Insert Before
7.Delete First
8.Delete Last
9.Delete Node
10.Modify

12
 A.NARENDAR
Asst.Prof.

11.Search
12.Exit
Enter u r choice 7
First Node is Deleted
*****Single Linked List Operations*****
1.Create
2.Display
3.Insert First
4.Insert Last
5.Insert After
6.Insert Before
7.Delete First
8.Delete Last
9.Delete Node
10.Modify
11.Search
12.Exit
Enter u r choice 2
Node values are :
12 102 101 13 14 200
*****Single Linked List Operations*****
1.Create
2.Display
3.Insert First
4.Insert Last
5.Insert After
6.Insert Before
7.Delete First
8.Delete Last
9.Delete Node
10.Modify
11.Search
12.Exit
Enter u r choice 8
Last Node is deleted
*****Single Linked List Operations*****
1.Create
2.Display

13
 A.NARENDAR
Asst.Prof.

3.Insert First
4.Insert Last
5.Insert After
6.Insert Before
7.Delete First
8.Delete Last
9.Delete Node
10.Modify
11.Search
12.Exit
Enter u r choice 9
Enter Which node you want to delete 101
101 node is deleted
*****Single Linked List Operations*****
1.Create
2.Display
3.Insert First
4.Insert Last
5.Insert After
6.Insert Before
7.Delete First
8.Delete Last
9.Delete Node
10.Modify
11.Search
12.Exit
Enter u r choice 2
Node values are :
12 102 13 14
*****Single Linked List Operations*****
1.Create
2.Display
3.Insert First
4.Insert Last
5.Insert After
6.Insert Before
7.Delete First
8.Delete Last

14
 A.NARENDAR
Asst.Prof.

9.Delete Node
10.Modify
11.Search
12.Exit
Enter u r choice 10
Enter node data to modify 13
Enter Node value 104
Node is Modified
*****Single Linked List Operations*****
1.Create
2.Display
3.Insert First
4.Insert Last
5.Insert After
6.Insert Before
7.Delete First
8.Delete Last
9.Delete Node
10.Modify
11.Search
12.Exit
Enter u r choice 11
Enter node data to search 102
102 node is found in a list
*****Single Linked List Operations*****
1.Create
2.Display
3.Insert First
4.Insert Last
5.Insert After
6.Insert Before
7.Delete First
8.Delete Last
9.Delete Node
10.Modify
11.Search
12.Exit
Enter u r choice 2

15
 A.NARENDAR
Asst.Prof.

Node values are :

12 102 104 14
*****Single Linked List Operations*****
1.Create
2.Display
3.Insert First
4.Insert Last
5.Insert After
6.Insert Before
7.Delete First
8.Delete Last
9.Delete Node
10.Modify
11.Search
12.Exit
Enter u r choice 12

2: Write a program that uses functions to perform the following operations on doubly
linked list.:
i) Creation ii) Insertion iii) Deletion iv) Traversal
#include<stdio.h>
#include<stdlib.h>
struct Dlink
{
struct Dlink *bl;
int data;
struct Dlink *fl;

}*start=NULL,*temp,*prev;
void create();

16
 A.NARENDAR
Asst.Prof.

void display();
void insert_first();
void insert_last();
void insert_after();
void insert_before();
void delete_node();
void delete_list();
int main()
{
int ch;
while(1)
{
printf("\n\n Double Linked List Operations ");
printf("\n 1. Create a List ");
printf("\n 2. Display the List ");
printf("\n 3.Add a node at the beginning ");
printf("\n 4.Add a node at the end");
printf("\n 5.Add a node after a given node");
printf("\n 6.Add a node before a given node");
printf("\n 7.Delete a node from a List ");
printf("\n 8. Delete the entire list ");
printf("\n 9. Exit");
printf("\n Select any operation ");
scanf("%d",&ch);
switch(ch)
{
case 1 : create(); break;
case 2 : display();break;
case 3 : insert_first(); break;
case 4 : insert_last();break;
case 5 : insert_after();break;
case 6 : insert_before();break;
case 7 : delete_node(); break;
case 8 : delete_list();break;
case 9 : exit(0);
default : printf("\n Invalid Operation ");
}
}

17
 A.NARENDAR
Asst.Prof.

}
void create()
{
char ch;
struct Dlink *newNode;
int n;
do
{
newNode=(struct Dlink *)malloc(sizeof(struct Dlink));
printf("\n Enter any Data");
scanf("%d",&newNode->data);
newNode->fl=NULL;
newNode->bl=NULL;
if(start==NULL)
{
start=newNode;
}
else
{
temp=start;
while(temp->fl!=NULL)
temp=temp->fl;
temp->fl=newNode;
newNode->bl=temp;
}
printf("\n Do u want to add another node (y/n) ");
fflush(stdin);
scanf("%c",&ch);
}while(ch=='y'||ch=='Y');
}
void display()
{
if(start==NULL)
{
printf("\n sorry no node to print");
}
else
{

18
 A.NARENDAR
Asst.Prof.

printf("\n Node Values are \n");

temp=start;
while(temp!=NULL)
{
printf("\t %d ",temp->data);
temp=temp->fl;
}

}
}
void insert_first()
{

struct Dlink *newNode;

newNode=(struct Dlink *)malloc(sizeof(struct Dlink));
printf("\n Enter Data ");
scanf("%d",&newNode->data);
newNode->fl=NULL;
newNode->bl=NULL;
start->bl=newNode;
newNode->fl=start;
start=newNode;
printf("\n New Node is inserted as First Node");
}
void insert_last()
{
struct Dlink *newNode;
newNode=(struct Dlink *)malloc(sizeof(struct Dlink));
printf("\n Enter data ");
scanf("%d",&newNode->data);
newNode->fl=NULL;
newNode->bl=NULL;
temp=start;
while(temp->fl!=NULL)
{
temp=temp->fl;
}
temp->fl=newNode;

19
 A.NARENDAR
Asst.Prof.

newNode->bl=temp;
printf("\n New Node is inserted at Last ");
}
void insert_after()
{
struct Dlink *newNode;
int ano,f=0;
printf("\n Enter the value after which you want to insert");
scanf("%d",&ano);
newNode=(struct Dlink *)malloc(sizeof(struct Dlink));
printf("\n Enter data : ");
scanf("%d",&newNode->data);
temp=start;
while(temp!=NULL)
{
if(temp->data==ano)
{
newNode->fl=temp->fl;
newNode->bl=temp;
temp->fl=newNode;
printf("\n New Node is inserted after %d node",temp->data);
f=1;
break;
}
temp=temp->fl;
}
if(f==0)
printf("\n No Node Exist with that value ");
}
void insert_before()
{

struct Dlink *newNode;

int bno,f=0;
printf("\n Enter the value after which you want to insert");
scanf("%d",&bno);
newNode=(struct Dlink *)malloc(sizeof(struct Dlink));
printf("\n Enter data : ");

20
 A.NARENDAR
Asst.Prof.

scanf("%d",&newNode->data);
temp=start;
while(temp!=NULL)
{
if(temp->data==bno)
{
newNode->fl=prev->fl;
newNode->bl=prev;
prev->fl=newNode;
temp->bl=newNode;
printf("\n New Node is inserted before %d node",temp->data);
f=1;
break;
}
prev=temp;
temp=temp->fl;
}
if(f==0)
printf("\n No Node Exist with that value ");
}
void delete_node()
{
struct Dlink *ptr;
int dno,f=0;
printf("\n Enter which node you want to delete ");
scanf("%d",&dno);
if(start->data==dno) //to delete first node
{
ptr=start->fl;
printf("\n First Node is Deleted ");
free(temp);
start=ptr;
f=1;
}
else
{
for(temp=start;temp!=NULL;temp=temp->fl)
{

21
 A.NARENDAR
Asst.Prof.

if(temp->data==dno)
{
if(temp->fl==NULL) // to delete last node
{
prev->fl=NULL;
printf("\n Last Node is deleted ");
free(temp);
f=1;
break;
}
else // to delete intermediate node
{
prev->fl=temp->fl;
(prev->fl)->bl=prev;
printf("\n %d node is deleted ",temp->data);
free(temp);
f=1;
break;
}
}
prev=temp;
}
}

if(f==0)
printf("\n No Node exist with that value ");
}
void delete_list()
{
temp=start;
while(temp!=NULL)
{
start=start->fl;
if(start!=NULL)
start->bl=NULL;
free(temp);
temp=start;
}

22
 A.NARENDAR
Asst.Prof.

if(start==NULL)
printf("\n All Nodes are Deleted");
}

Output:
Double Linked List Operations
1.Create a List
2.Display the List
3.Add a node at the beginning
4.Add a node at the end
5.Add a node after a given node
6.Add a node before a given node
7.Delete a node from a list
8.Delete the entire list
9.Exit
Select any operation 1
Enter any Data 1
Do u want to add another node(y/n) y
Enter any Data 2
Do u want to add another node(y/n) y
Enter any Data 3
Do u want to add another node(y/n) n
Double Linked List Operations
1.Create a List
2.Display the List
3.Add a node at the beginning
4.Add a node at the end
5.Add a node after a given node
6.Add a node before a given node
7.Delete a node from a list
8.Delete the entire list
9.Exit
Select any operation 2

23
 A.NARENDAR
Asst.Prof.

Node values are

1 2 3
Double Linked List Operations
1.Create a List
2.Display the List
3.Add a node at the beginning
4.Add a node at the end
5.Add a node after a given node
6.Add a node before a given node
7.Delete a node from a list
8.Delete the entire list
9.Exit
Select any operation 3
Enter data 100
New Node is inserted as First Node
Double Linked List Operations
1.Create a List
2.Display the List
3.Add a node at the beginning
4.Add a node at the end
5.Add a node after a given node
6.Add a node before a given node
7.Delete a node from a list
8.Delete the entire list
9.Exit
Select any operation 4
Enter data 121
New Node is inserted at last
Double Linked List Operations
1.Create a List
2.Display the List
3.Add a node at the beginning
4.Add a node at the end
5.Add a node after a given node
6.Add a node before a given node
7.Delete a node from a list
8.Delete the entire list
9.Exit

24
 A.NARENDAR
Asst.Prof.

Select any operation 2

100 1 2 3 121
Double Linked List Operations
1.Create a List
2.Display the List
3.Add a node at the beginning
4.Add a node at the end
5.Add a node after a given node
6.Add a node before a given node
7.Delete a node from a list
8.Delete the entire list
9.Exit
Select any operation 5
Enter the value after which node you want to insert 2
Enter data : 200
New Node is inserted after 2 node
Double Linked List Operations
1.Create a List
2.Display the List
3.Add a node at the beginning
4.Add a node at the end
5.Add a node after a given node
6.Add a node before a given node
7.Delete a node from a list
8.Delete the entire list
9.Exit
Select any operation 6
Enter the value before which you want to insert 1
Enter data : 123
New Node is inserted before 1 node
Double Linked List Operations
1.Create a List
2.Display the List
3.Add a node at the beginning
4.Add a node at the end
5.Add a node after a given node
6.Add a node before a given node
7.Delete a node from a list

25
 A.NARENDAR
Asst.Prof.

8.Delete the entire list

9.Exit
Select any operation 2
100 123 1 2 200 3 121
Double Linked List Operations
1.Create a List
2.Display the List
3.Add a node at the beginning
4.Add a node at the end
5.Add a node after a given node
6.Add a node before a given node
7.Delete a node from a list
8.Delete the entire list
9.Exit
Select any operation 7
Enter which node you want to delete 100
First Node is Deleted
Double Linked List Operations
1.Create a List
2.Display the List
3.Add a node at the beginning
4.Add a node at the end
5.Add a node after a given node
6.Add a node before a given node
7.Delete a node from a list
8.Delete the entire list
9.Exit
Select any operation 7
Enter which node you want to delete 121
Last Node is deleted
Double Linked List Operations
1.Create a List
2.Display the List
3.Add a node at the beginning
4.Add a node at the end
5.Add a node after a given node
6.Add a node before a given node
7.Delete a node from a list

26
 A.NARENDAR
Asst.Prof.

8.Delete the entire list

9.Exit
Select any operation 2
Node Values are
123 1 2 200 3
Double Linked List Operations
1.Create a List
2.Display the List
3.Add a node at the beginning
4.Add a node at the end
5.Add a node after a given node
6.Add a node before a given node
7.Delete a node from a list
8.Delete the entire list
9.Exit
Select any operation 7
Enter which node you want to delete 200
200 node is deleted
Double Linked List Operations
1.Create a List
2.Display the List
3.Add a node at the beginning
4.Add a node at the end
5.Add a node after a given node
6.Add a node before a given node
7.Delete a node from a list
8.Delete the entire list
9.Exit
Select any operation 7
Enter which node you want to delete 1000
No Node exist with that value
Double Linked List Operations
1.Create a List
2.Display the List
3.Add a node at the beginning
4.Add a node at the end
5.Add a node after a given node
6.Add a node before a given node

27
 A.NARENDAR
Asst.Prof.

7.Delete a node from a list

8.Delete the entire list
9.Exit
Select any operation 8
All Nodes are Deleted
Double Linked List Operations
1.Create a List
2.Display the List
3.Add a node at the beginning
4.Add a node at the end
5.Add a node after a given node
6.Add a node before a given node
7.Delete a node from a list
8.Delete the entire list
9.Exit
Select any operation 2
Sorry no node to print
Double Linked List Operations
1.Create a List
2.Display the List
3.Add a node at the beginning
4.Add a node at the end
5.Add a node after a given node
6.Add a node before a given node
7.Delete a node from a list
8.Delete the entire list
9.Exit
Select any operation 9
Press any key to continue..

28
 A.NARENDAR
Asst.Prof.

3: Write a program that uses functions to perform the following operations on circular
linked list.:
i) Creation ii) Insertion iii) Deletion iv) Traversal

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

typedef struct Node

{
int info;
struct Node *next;
}node;

node *front=NULL,*rear=NULL,*temp;

void create();
void del();
void display();

int main()
{
int chc;
do
{
printf("\nMenu\n\t 1 to create the element : ");
printf("\n\t 2 to delete the element : ");
printf("\n\t 3 to display the queue : ");
printf("\n\t 4 to exit from main : ");
printf("\nEnter your choice : ");
scanf("%d",&chc);

29
 A.NARENDAR
Asst.Prof.

switch(chc)
{
case 1:
create();
break;

case 2:
del();
break;

case 3:
display();
break;

case 4:
return 1;

default:
printf("\nInvalid choice :");
}
}while(1);

return 0;
}

void create()
{
node *newnode;
newnode=(node*)malloc(sizeof(node));
printf("\nEnter the node value : ");
scanf("%d",&newnode->info);
newnode->next=NULL;
if(rear==NULL)
front=rear=newnode;
else
{
rear->next=newnode;
rear=newnode;
}

rear->next=front;
}

30
 A.NARENDAR
Asst.Prof.

void del()
{
temp=front;
if(front==NULL)
printf("\nUnderflow :");
else
{
if(front==rear)
{
printf("\n%d",front->info);
front=rear=NULL;
}
else
{
printf("\n%d",front->info);
front=front->next;
rear->next=front;
}

temp->next=NULL;
free(temp);
}
}

void display()
{
temp=front;
if(front==NULL)
printf("\nEmpty");
else
{
printf("\n");
for(;temp!=rear;temp=temp->next)
printf("\n%d address=%u next=%u\t",temp->info,temp,temp-
>next);
printf("\n%d address=%u next=%u\t",temp->info,temp,temp-
>next);
}
}

31
 A.NARENDAR
Asst.Prof.

32
 A.NARENDAR
Asst.Prof.

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

i) Arrays ii)Pointers

i) Arrays
#include<stdio.h>
#include<conio.h>
#define max 10
void push();
void pop();
void display();
int st[max];
int top=-1;
void main()
{ int ch;
while(1)
{
clrscr();
printf("\n \t S T A C K O P E R A T I O N S ");
printf("\n 1. PUSH \n 2. POP \n 3. DISPLAY \n 4. Exit ");
printf("\n Enter U R Choice ");
scanf("%d",&ch);
switch(ch)
{
case 1 : push(); break;
case 2 : pop(); break;
case 3 : display();break;
case 4 : exit(0);
}
}
}
void push()
{
int val;
if(top==max-1)
{
printf("\n Stack is Full ");

33
 A.NARENDAR
Asst.Prof.

exit(0);
}
printf("\n Enter elements to push ");
scanf("%d",&val);

if(top==-1)
{
top++;
st[top]=val;
}
else
{
top++;
st[top]=val;
}
}
void pop()
{
if(top==-1)
printf("\n Stack is Empty ");
else
{
printf("\n Poped Element is : %d ",st[top]);
top--;
}
getch();
}
void display()
{
int i;
if(top==-1)
printf("\n Stack is Empty ");
else
{
printf("\n Elements are : ");
for(i=top;i>=0;i--)
printf("\n \t %d ",st[i]);
}

34
 A.NARENDAR
Asst.Prof.

getch();
}

Output:

35
 A.NARENDAR
Asst.Prof.

36
 A.NARENDAR
Asst.Prof.

ii)Pointers

#include<stdio.h>
#include<conio.h>
#define max 10
void push();
void pop();
void display();
struct stack
{
int data;
struct stack *next;
};
struct stack *temp,*top=NULL;
void main()
{ int ch;
while(1)
{
clrscr();
printf("\n \t S T A C K O P E R A T I O N S ");
printf("\n 1. PUSH \n 2. POP \n 3. DISPLAY \n 4. Exit ");
printf("\n Enter U R Choice ");
scanf("%d",&ch);
switch(ch)
{
case 1 : push(); break;
case 2 : pop(); break;
case 3 : display();break;
case 4 : exit(0);
}
}
}
void push()
{
int ch='y';
do
{
temp=(struct stack *)malloc(sizeof(struct stack));

37
 A.NARENDAR
Asst.Prof.

printf("\n Enter Element To Push ");

scanf("%d",&temp->data);
temp->next=NULL;
if(top==NULL)
top=temp;
else
{
temp->next=top;
top=temp;
}
printf("\n Do U want to push one more element into stack ");
fflush(stdin);
scanf("%c",&ch);
}while(ch=='y'||ch=='Y');
}
void pop()
{
struct stack *ptr;
if(top==NULL)
printf("\n stack is empty ");
else
{
printf("\n Poped Element is : %d",top->data);
ptr=top->next;
top=ptr;
}
getch();
}
void display()
{
if(top==NULL)
printf("\n Stack is Empty ");
else
{
printf("\n Node Values are .. ");
for(temp=top;temp!=NULL;temp=temp->next)
printf("\n \t %d",temp->data);
}

38
 A.NARENDAR
Asst.Prof.

getch();
}

Output:

39
 A.NARENDAR
Asst.Prof.

5: Write a program that implement Queue (itsoperations) using

i) Arrays ii) Pointers

/* program to implement QUEUE by using Arrays */

i) Arrays

40
 A.NARENDAR
Asst.Prof.

#include<stdio.h>
#include<conio.h>
#define max 10
int qt[max];
int front=-1;
int rear=-1;
void create();
void del();
void display();
void main()
{
int ch;
clrscr();
while(1)
{
printf("\n 1. create ");
printf("\n 2. delete ");
printf("\n 3. display ");
printf("\n 4. exit ");
printf("\n Enter U R Choice ");
scanf("%d",&ch);
switch(ch)
{
case 1 : create(); break;
case 2 : del(); break;
case 3 : display(); break;
case 4 : exit(0);
}
}
}
void create()
{
int i;
if(rear>=max)
printf("\n QUEUE is Full ");
else
{
printf("\n Enter Any Data ");

41
 A.NARENDAR
Asst.Prof.

scanf("%d",&i);
if(front==-1&&rear==-1)
{
front++;
rear++;
qt[front]=i;
qt[rear]=i;
}
else
{
rear++;
qt[rear]=i;
}
}
}
void del()
{
int val;
if(rear==-1&&front==-1)
printf("\n QUEUE is Empty ");
else
{
val=qt[front];
front++;
printf("\n deleted element is : %d",val);
}
}
void display()
{
int i;
if(front==-1&&rear==-1)
printf("\n QUEUE is empty ");

else
{
printf("\n queue elements are ..");
for(i=front;i<=rear;i++)
printf("\t -->%d",qt[i]);

42
 A.NARENDAR
Asst.Prof.

}
}
Output:

43
 A.NARENDAR
Asst.Prof.

/*--------------program to implement queue by using linked list------------- */

ii) Pointers
#include<stdio.h>
#include<conio.h>
void add();
void show();
void del();
struct queue
{
int data;
struct queue *next;
};
struct queue *front=NULL,*rear=NULL,*temp;

void main()
{
char ch;
while(1)
{
clrscr();

44
 A.NARENDAR
Asst.Prof.

printf("\n 1. add \n 2.show \n 3. remove \n 4. Exit ");

printf("\n Enter U R Choice ");
scanf("%d",&ch);
switch(ch)
{
case 1 : add(); break;
case 2 : show(); break;
case 3 : del(); break;
case 4 : exit(0);
}
}
}
void add()
{
char cch='y';
while(cch=='y'||cch=='Y')
{
temp=(struct queue *)malloc(sizeof(struct queue));
printf("\n Enter element to add ");
scanf("%d",&temp->data);
temp->next=NULL;
if(front==NULL)
front=temp;
else
rear->next=temp;

rear=temp;
printf("\n Do U want to continue (y/n) : ");
fflush(stdin);
scanf("%c",&cch);
getch();
}
}
void show()
{
clrscr();
if(front==NULL)
printf("\n Sorry queue is empty ");

45
 A.NARENDAR
Asst.Prof.

else
{
printf("\n Node values are ...\n");
for(temp=front;temp!=NULL;temp=temp->next)
printf("\t %d ", temp->data);
}
getch();
}
void del()
{
struct queue *ptr;
clrscr();
if(front==NULL)
printf("\n Sorry Queue is Empty ");
else
{
ptr=front->next;
printf("\n deleted element is %d ", front->data);
free(front);
front=ptr;

}
getch();
}

Output:

46
 A.NARENDAR
Asst.Prof.

6: Write a program that implements the following sorting methods to sort a given
list of integers in ascending order

47
 A.NARENDAR
Asst.Prof.

i) Bubble sort ii) Selection sort iii) Insertion sort

i) Bubble sort

/* program to implement bubble sort */

#include<stdio.h>

#include<conio.h>

void main()

int a[100], i, n , temp, j;

clrscr();

printf("\n Enter Array Size ");

scanf("%d",&n);
for(i=0;i<n;i++)

{
printf("\n Enter %d Element : ",i);

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

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

for(j=0;j<n-i-1;j++)

{ if(a[j]>a[j+1])

48
 A.NARENDAR
Asst.Prof.

temp=a[j+1];
a[j+1]=a[j];
a[j]=temp;

printf("\n \t sorted list : ");

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

printf("\n \t %d ",a[i]);

getch();

Output:

49
 A.NARENDAR
Asst.Prof.

ii) Selection sort

#include<stdio.h>
int main()

50
 A.NARENDAR
Asst.Prof.

{
int a[100], i, n , temp, j;
printf("\n Enter Number of Elements ");
scanf("%d",&n);
printf("\n Enter %d Elements",n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
if(a[i]>a[j])
{
temp=a[j];
a[j]=a[i];
a[i]=temp;
}
}
}
printf("\n sorted list ");
for(i=0;i<n;i++)
printf("\n \t %d ",a[i]);

iii) Insertion sort

#include<stdio.h>
#define MAX 100
int main()

51
 A.NARENDAR
Asst.Prof.

{
int arr[MAX];
int i,j,k,temp,n;
printf("\n Enter number of Elements ");
scanf("%d",&n);
printf("\n Enter %d Elements",n);
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
for(i=1;i<=n;i++)
{
for(j=0;j<i;j++)
{
if(arr[j]>arr[i])
{
temp=arr[j];
arr[j]=arr[i];
for(k=i;k>j;k--)
arr[k]=arr[k-1];
arr[k+1]=temp;
}
}
}
printf("\n array after sorting : ");
for(i=0;i<n;i++)
printf("%d\t",arr[i]);
}

Output:

52
 A.NARENDAR
Asst.Prof.

7: Write a program that use 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

53
 A.NARENDAR
Asst.Prof.

i) Linear search

/*Write a C program Linear Search Using Recursive Functions*/

#include<stdio.h>
#include<conio.h>45
int lin_search(int[],int,int);
main()
{
int a[100],n,i,ele;
clrscr();
printf("Enter Size");
scanf("%d",&n);
printf("Enter %d elements",n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("The array elements");
for(i=0;i<n;i++)
printf("%4d",a[i]);
printf("\nEnter element to search");
scanf("%d",&ele);
i=lin_search(a,n-1,ele);
if(i!=-1)
printf("\nThe element %d found at %d location",ele,i+1);
else
printf("\nThe element %d is not found",ele);
getch();
}
int lin_search(int x[100],int n,int ele)
{
if(n<=0)
return -1;
if(x[n]==ele)
return n;
else
return lin_search(x,n-1,ele);}

54
 A.NARENDAR
Asst.Prof.

Output:

Enter Size5
Enter 5 elements25
30
12
54
60
The array elements

25 30 12 54 60
Enter element to search

60

The element 60 found at 5 location

/*Write a C program Linear Search Using Non-Recursive Functions*/

#include<stdio.h>
#include<conio.h>
main()

55
 A.NARENDAR
Asst.Prof.

{
int a[100],i,n,ele,loc=-1;
clrscr();
printf("Enter Size");
scanf("%d",&n);
printf("Enter %d elements",n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("The array elements");
for(i=0;i<n;i++)
printf("%4d",a[i]);
printf("\nEnter element to search");
scanf("%d",&ele);
for(i=0;i<=n-1;i++)
{
if(ele==a[i])
{
loc=i;
break;
}
}
if(loc>=0)
printf("\nThe element %d found at %d location",ele,loc+1);
else
printf("\nThe element %d is not found",ele);
getch();
}
int lin_search(int x[100],int n,int ele)
{
if(n<=0)
return -1;
if(x[n]==ele)
return n;
else
return lin_search(x,n-1,ele);
}

Output:

56
 A.NARENDAR
Asst.Prof.

Enter Size5
Enter 5 elements12
30
25
4
85
The array elements 12 30 25 4 85
Enter element to search25

The element 25 found at 3 location

ii) Binary search

binary search using non-recursive and Recursive functions.

#include <stdio.h>
#define MAX_LEN 10

/* Non-Recursive function*/

57
 A.NARENDAR
Asst.Prof.

void b_search_nonrecursive(int l[],int num,int ele)

{
int l1,i,j, flag = 0;
l1 = 0;
i = num-1;
while(l1 <= i)
{
j = (l1+i)/2;
if( l[j] == ele)
{
printf("\nThe element %d is present at position %d in list\n",ele,j);
flag =1;
break;
}
else
if(l[j] < ele)
l1 = j+1;
else
i = j-1;
}
if( flag == 0)
printf("\nThe element %d is not present in the list\n",ele);
}

/* Recursive function*/
int b_search_recursive(int l[],int arrayStart,int arrayEnd,int a)
{
int m,pos;
if (arrayStart<=arrayEnd)
{
m=(arrayStart+arrayEnd)/2;
if (l[m]==a)
return m;
else if (a<l[m])
return b_search_recursive(l,arrayStart,m-1,a);
else
return b_search_recursive(l,m+1,arrayEnd,a);
}

58
 A.NARENDAR
Asst.Prof.

return -1;
}

void read_list(int l[],int n)

{
int i;
printf("\nEnter the elements:\n");
for(i=0;i<n;i++)
scanf("%d",&l[i]);
}

void print_list(int l[],int n)

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

/*main function*/
void main()
{
int l[MAX_LEN], num, ele,f,l1,a;
int ch,pos;
clrscr();
printf("======================================================");
printf("\n\t\t\tMENU");
printf("\n=====================================================");
printf("\n[1] Binary Search using Recursion method");
printf("\n[2] Binary Search using Non-Recursion method");
printf("\n\nEnter your Choice:");
scanf("%d",&ch);
if(ch<=2 & ch>0)
{
printf("\nEnter the number of elements : ");
scanf("%d",&num);
read_list(l,num);
printf("\nElements present in the list are:\n\n");
print_list(l,num);

59
 A.NARENDAR
Asst.Prof.

printf("\n\nEnter the element you want to search:\n\n");

scanf("%d",&ele);

switch(ch)
{
case 1:printf("\nRecursive method:\n");
pos=b_search_recursive(l,0,num,ele);
if(pos==-1)
{
printf("Element is not found");
}
else
{
printf("Element is found at %d position",pos);
}
getch();
break;
case 2:printf("\nNon-Recursive method:\n");
b_search_nonrecursive(l,num,ele);
getch();
break;
}
}
getch();
}

Output:

======================================================
MENU
=====================================================
[1] Binary Search using Recursion method
[2] Binary Search using Non-Recursion method

Enter your Choice:1

60
 A.NARENDAR
Asst.Prof.

Enter the number of elements : 5

Enter the elements:
12
03
52
68
98
Elements present in the list are:

12 3 52 68 98

Enter the element you want to search:

68

Element is found at 3 position

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

// C program for different tree traversals

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

61
 A.NARENDAR
Asst.Prof.

/* A binary tree node has data, pointer to left child

and a pointer to right child */

struct node
{
int data;
struct node* left;
struct node* right;

};

/* Helper function that allocates a new node with the

given data and NULL left and right pointers. */
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);
}

/* Given a binary tree, print its nodes according to the

"bottom-up" postorder traversal. */
void printPostorder(struct node* node)

62
 A.NARENDAR
Asst.Prof.

if (node == NULL)
return;

// first recur on left subtree

printPostorder(node->left);

// then recur on right subtree

printPostorder(node->right);

// now deal with the node

printf("%d ", node->data);
}

/* Given a binary tree, print its nodes in inorder*/

void printInorder(struct node* node)
{
if (node == NULL)
return;

/* first recur on left child */

printInorder(node->left);

/* then print the data of node */

printf("%d ", node->data);

63
 A.NARENDAR
Asst.Prof.

/* now recur on right child */

printInorder(node->right);
}

/* Given a binary tree, print its nodes in preorder*/

void printPreorder(struct node* node)

{
if (node == NULL)
return;

/* first print data of node */

printf("%d ", node->data);

/* then recur on left sutree */

printPreorder(node->left);

/* now recur on right subtree */

printPreorder(node->right);

/* Driver program to test above functions*/

int main()
{
struct node *root = newNode(1);

64
 A.NARENDAR
Asst.Prof.

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);

getchar();
return 0;
}

Output:
Preorder traversal of binary tree is

12453
Inorder traversal of binary tree is
42513

65
 A.NARENDAR
Asst.Prof.

Postorder traversal of binary tree is

45231

9: Write a program to implement the graph traversal methods.

/* C program to implement BFS(breadth-first search) and DFS(depth-first search)

algorithm */

#include<stdio.h>

int q[20],top=-1,front=-1,rear=-1,a[20][20],vis[20],stack[20];
int delete();

66
 A.NARENDAR
Asst.Prof.

void add(int item);

void bfs(int s,int n);
void dfs(int s,int n);
void push(int item);
int pop();

void main()
{
int n,i,s,ch,j;
char c,dummy;
printf("ENTER THE NUMBER VERTICES ");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("ENTER 1 IF %d HAS A NODE WITH %d ELSE 0 ",i,j);
scanf("%d",&a[i][j]);
}
}
printf("THE ADJACENCY MATRIX IS\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf(" %d",a[i][j]);
}
printf("\n");
}

do
{
for(i=1;i<=n;i++)
vis[i]=0;
printf("\nMENU");
printf("\n1.B.F.S");
printf("\n2.D.F.S");

67
 A.NARENDAR
Asst.Prof.

printf("\nENTER YOUR CHOICE");

scanf("%d",&ch);
printf("ENTER THE SOURCE VERTEX :");
scanf("%d",&s);

switch(ch)
{
case 1:bfs(s,n);
break;
case 2:
dfs(s,n);
break;
}
printf("DO U WANT TO CONTINUE(Y/N) ? ");
scanf("%c",&dummy);
scanf("%c",&c);
}while((c=='y')||(c=='Y'));
}

//**************BFS(breadth-first search) code**************//

void bfs(int s,int n)
{
int p,i;
add(s);
vis[s]=1;
p=delete();
if(p!=0)
printf(" %d",p);
while(p!=0)
{
for(i=1;i<=n;i++)
if((a[p][i]!=0)&&(vis[i]==0))
{
add(i);
vis[i]=1;
}

68
 A.NARENDAR
Asst.Prof.

p=delete();
if(p!=0)
printf(" %d ",p);
}
for(i=1;i<=n;i++)
if(vis[i]==0)
bfs(i,n);
}

void add(int item)

{
if(rear==19)
printf("QUEUE FULL");
else
{
if(rear==-1)
{
q[++rear]=item;
front++;
}
else
q[++rear]=item;
}
}
int delete()
{
int k;
if((front>rear)||(front==-1))
return(0);
else
{
k=q[front++];
return(k);
}
}

69
 A.NARENDAR
Asst.Prof.

//***************DFS(depth-first search) code******************//

void dfs(int s,int n)
{
int i,k;
push(s);
vis[s]=1;
k=pop();
if(k!=0)
printf(" %d ",k);
while(k!=0)
{
for(i=1;i<=n;i++)
if((a[k][i]!=0)&&(vis[i]==0))
{
push(i);
vis[i]=1;
}
k=pop();
if(k!=0)
printf(" %d ",k);
}
for(i=1;i<=n;i++)
if(vis[i]==0)
dfs(i,n);
}
void push(int item)
{
if(top==19)
printf("Stack overflow ");
else
stack[++top]=item;
}
int pop()
{
int k;

70
 A.NARENDAR
Asst.Prof.

if(top==-1)
return(0);
else
{
k=stack[top--];
return(k);
}
}

71
 A.NARENDAR
Asst.Prof.

/* Output of BFS(breadth-first search) and DFS(depth-first search) program */

Output of BFS and DFS Program

Output of BFS and DFS Program

72