CSE DEPARTMENT DATA STRUCTURES LAB

1
CSE DEPARTMENT DATA STRUCTURES LAB

INDEX

LIST OF EXPERIMENTS

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

2
CSE DEPARTMENT DATA STRUCTURES LAB

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 ");
printf("\n 10. Modify ");

3
CSE DEPARTMENT DATA STRUCTURES LAB

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 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;
4
CSE DEPARTMENT DATA STRUCTURES LAB
temp->link=newNode;
printf("\n New Node is inserted after %d node",temp->data);
break;
}
temp=temp->link;
}
if(f==0)
printf("\n No Node Exist with that value");
}
void insert_before()
{

5
CSE DEPARTMENT DATA STRUCTURES LAB

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()
{
temp=start;
while(temp->link!=NULL)
{
prev=temp;
temp=temp->link;
6
CSE DEPARTMENT DATA STRUCTURES LAB

}
free(temp);
prev->link=NULL;
printf("\n Last Node is deleted ");
}
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;
}
}
if(f==0)
printf("\n No Node with that value..");
}

7
CSE DEPARTMENT DATA STRUCTURES LAB

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
11.Search
12.Exit
Enter u r choice 2
Node Values are :
12 13 14
*****Single Linked List Operations*****
1.Create
8
CSE DEPARTMENT DATA STRUCTURES LAB

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*****
1.Create
2.Display
3.Insert First
4.Insert Last
5.Insert After
6.Insert Before
7.Delete First
9
CSE DEPARTMENT DATA STRUCTURES LAB
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
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

10
CSE DEPARTMENT DATA STRUCTURES LAB

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 Enter u r choice 9
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

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
11
 CSE DEPARTMENT DATA STRUCTURES LAB

*****Single Linked List

Operations*****

12
CSE DEPARTMENT DATA STRUCTURES LAB

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
9.Delete Node
10.Modify

13
CSE DEPARTMENT DATA STRUCTURES LAB

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

14
CSE DEPARTMENT DATA STRUCTURES LAB

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

15
CSE DEPARTMENT DATA STRUCTURES LAB

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;
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;
16
CSE DEPARTMENT DATA STRUCTURES LAB

}
if(f==0)
printf("\n No Node Exist with that value ");
}
else
{
for(temp=start;temp!=NULL;temp=temp->fl)
{
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 ");
}

17
CSE DEPARTMENT DATA STRUCTURES LAB

void delete_list()
{
temp=start; while(temp!
=NULL)
{
start=start->fl;
if(start!=NULL)
start->bl=NULL;
free(temp);
temp=start;
}
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
18
CSE DEPARTMENT DATA STRUCTURES LAB

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
Node values are
1 2 3

19
CSE DEPARTMENT DATA STRUCTURES LAB

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
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
20
CSE DEPARTMENT DATA STRUCTURES LAB

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
Node Values are
123 1 2 200 3

21
 CSE DEPARTMENT DATA STRUCTURES LAB

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

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

case 2:
del();
break;

case 3:
display();

22
 CSE DEPARTMENT DATA STRUCTURES LAB

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

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

23
 CSE DEPARTMENT DATA STRUCTURES LAB

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

24
CSE DEPARTMENT DATA STRUCTURES LAB

25
CSE DEPARTMENT DATA STRUCTURES LAB

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 ");
exit(0);
}

26
CSE DEPARTMENT DATA STRUCTURES LAB

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]);
}
getch();
}

27
CSE DEPARTMENT DATA STRUCTURES LAB

Output:

28
CSE DEPARTMENT DATA STRUCTURES LAB

29
CSE DEPARTMENT DATA STRUCTURES LAB

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)
{
30
CSE DEPARTMENT DATA STRUCTURES LAB

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));
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;
}
31
CSE DEPARTMENT DATA STRUCTURES LAB

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);
}
getch();
}

Output:

32
CSE DEPARTMENT DATA STRUCTURES LAB

33
CSE DEPARTMENT DATA STRUCTURES LAB

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

i) Arrays ii) Pointers

/* program to implement QUEUE by using Arrays */

i) Arrays
#include<stdio.h>
#include<conio.h>
#define max 10
int qt[max];
34
CSE DEPARTMENT DATA STRUCTURES LAB

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 ");
scanf("%d",&i);
if(front==-1&&rear==-1)
{
front++;
rear++;
35
CSE DEPARTMENT DATA STRUCTURES LAB

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]);
}
}
Output:

36
CSE DEPARTMENT DATA STRUCTURES LAB

37
CSE DEPARTMENT DATA STRUCTURES LAB

/*--------------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();
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()
p;
else
rear->next=temp;
38
CSE DEPARTMENT DATA STRUCTURES LAB

rear=temp;
printf("\n Do U want to continue (y/n) : ");
fflush(stdin);
scanf("%c",&cch);
getch();
}
}

39
CSE DEPARTMENT DATA STRUCTURES LAB

free(front);
front=ptr;

}
getch();
}

Output:

40
CSE DEPARTMENT DATA STRUCTURES LAB

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) 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]);
41
CSE DEPARTMENT DATA STRUCTURES LAB

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

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

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

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

42
CSE DEPARTMENT DATA STRUCTURES LAB

Output:

43
CSE DEPARTMENT DATA STRUCTURES LAB

ii) Selection sort

#include<stdio.h>
int main()
{
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];
44
CSE DEPARTMENT DATA STRUCTURES LAB

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()
{
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+
+)
{
45
CSE DEPARTMENT DATA STRUCTURES LAB

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:

46
CSE DEPARTMENT DATA STRUCTURES LAB

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

i) Linear search
47
CSE DEPARTMENT DATA STRUCTURES LAB

/*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++)
if(n<=0)
return -1;
if(x[n]==ele)
return n;
else
return lin_search(x,n-1,ele);}

Output:

48
CSE DEPARTMENT DATA STRUCTURES LAB

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

49
CSE DEPARTMENT DATA STRUCTURES LAB

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

#include<stdio.h>
#include<conio.h>
main()
{
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(n<=0)
return -1;
if(x[n]==ele)

50
CSE DEPARTMENT DATA STRUCTURES LAB

return n;
else
return lin_search(x,n-1,ele);
}

Output:

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

51
CSE DEPARTMENT DATA STRUCTURES LAB

ii) Binary search

binary search using non-recursive and Recursive functions.

#include <stdio.h>
#define MAX_LEN
10

/* Non-Recursive function*/
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);
);
}

52
CSE DEPARTMENT DATA STRUCTURES LAB

/* 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);
}
return -1;
}

void read_list(int l[],int n)

{
int i;
int ch,pos;
clrscr();

53
CSE DEPARTMENT DATA STRUCTURES LAB

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);
printf("\n\nEnter the element you want to search:\n\n");
scanf("%d",&ele);

switch(ch)
{
}
}
getch();
}

54
CSE DEPARTMENT DATA STRUCTURES LAB

Output:

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

Enter your Choice:1

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

55
CSE DEPARTMENT DATA STRUCTURES LAB

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>

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

and a pointer to right child */

struct node

int data;
struct node* left;

56
CSE DEPARTMENT DATA STRUCTURES LAB

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

return;

// first recur on left subtree

printPostorder(node->left);

57
CSE DEPARTMENT DATA STRUCTURES LAB

// then recur on right subtree

printPostorder(node->right);

// now deal with the node

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

void printPreorder(struct node* node)

{

58
CSE DEPARTMENT DATA STRUCTURES LAB

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

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

59
CSE DEPARTMENT DATA STRUCTURES LAB

printInorder(root);

printf("\nPostorder traversal of binary tree is \n");

printPostorder(root);

getchar();
return 0;

Output:

Preorder traversal of binary tree is

12453
60
CSE DEPARTMENT DATA STRUCTURES LAB

Inorder traversal of binary tree is

42513

Postorder traversal of binary tree is

45231

61
CSE DEPARTMENT DATA STRUCTURES LAB

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

62
CSE DEPARTMENT DATA STRUCTURES LAB

do
{
for(i=1;i<=n;i++)
vis[i]=0; printf("\
nMENU"); printf("\
n1.B.F.S");
}
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)
{

63
CSE DEPARTMENT DATA STRUCTURES LAB

for(i=1;i<=n;i++) if((a[p][i]!
=0)&&(vis[i]==0))
{
add(i);
vis[i]=1;
}
p=delete();
if(p!=0)
printf(" %d ",p);
}
for(i=1;i<=n;i++)
if(vis[i]==0)
else q[+
+rear]=item;
}
}
int delete()
{
int k; if((front>rear)||
(front==-1)) return(0);
else
{
k=q[front++];

64
CSE DEPARTMENT DATA STRUCTURES LAB

return(k);
}
}

//***************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
65
CSE DEPARTMENT DATA STRUCTURES LAB

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

66
CSE DEPARTMENT DATA STRUCTURES LAB

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

program */

Output of BFS and DFS Program

Output of BFS and DFS Program

67