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

Description:
A Singly linked list is a linear collection of data elements, called nodes pointing
to the next node by means of pointer. Under the simplest form, each node is
composed of data and a reference (in other words, a link) to the next node in the
sequence. This structure allows for efficient insertion or removal of elements from
any position in the sequence.

#include<stdio.h>
#include<conio.h>
struct node
{
int data;
struct node *next;
};
struct node *head=NULL;
void insertF(int val)
{

struct node *temp,*temp1;

temp=(struct node *)malloc(sizeof(struct node *));;
temp->next=NULL;
temp->data=val;
if(head==NULL)

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 1
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
{
head=temp;
}
else
{
temp->next=head;
head=temp;
}
}
void insertL(int val)
{
int i=1;
struct node *temp,*temp1;
temp=(struct node *)malloc(sizeof(struct node *));;
temp->next=NULL;
temp->data=val;
if(head==NULL)
{
head=temp;
}
else
{
temp1=head;
while(temp1->next!=NULL)
{
temp1=temp1->next;
}
temp1->next=temp;
}
}
void insert(int pos, int val)
{
int i=1;

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 2
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
struct node *temp,*temp1;
temp=(struct node *)malloc(sizeof(struct node *));;
temp->next=NULL;
temp->data=val;
if(head==NULL)
{
head=temp;
}
else if(pos==1)
{
temp->next=head;
head=temp;
}
else
{
temp1=head;
while(i<pos-1)
{
temp1=temp1->next;
i++;
}
temp->next=temp1->next;
temp1->next=temp;
}
}
int deletionF( )
{
struct node *temp,*temp1;
int b,i=1;
if(head==NULL)
{
printf("\nUnder flow");
return -1;

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 3
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
}
else
{
b=head->data;
temp=head;
head=head->next;
free(temp);
return(b);
}
}
int deletionL( )
{
struct node *temp,*temp1;
int b,i=1;
if(head==NULL)
{
printf("\nstack under flow");
return -1;
}
else if(head->next==NULL)
{
b=head->data;
free(head);
head=NULL;
return b;
}
else
{
temp1=head;
while(temp1->next->next!=NULL)
{
temp1=temp1->next;
}

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 4
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
b=temp1->next->data;
temp=temp1->next;
temp1->next=temp1->next->next;
free(temp);
return b;
}
}
int deletion(int pos)
{
struct node *temp,*temp1;
int b,i=1;
if(head==NULL)
{
printf("\nstack under flow");
return -1;
}
else if(pos==1)
{
b=head->data;
temp=head;
head=head->next;
free(temp);
return(b);
}
else
{
temp1=head;
while(i<pos-1)
{
temp1=temp1->next;
i++;
}
b=temp1->next->data;

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 5
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
temp=temp1->next;
temp1->next=temp1->next->next;
free(temp);
return b;
}
}
void display( )
{
if(head==NULL)
{
printf("\nList is empty");
}
else
{
struct node *temp;
temp=head;
printf("\nList elements:");
while(temp != NULL)
{
printf("%d ",temp->data);
temp=temp->next;
}
}
}
void main( )
{
int ch,pos,val,b;
clrscr( );
printf("\n*** MENU ***\n 1. INSERT FIRST\n 2. INSERT LAST \n 3. INSERT at
POSITION 4. DELETE FIRST\n 5. DELETE LAST \n 6.DELETE at POSITION \n
7. DISPLAY\n 8. EXIT\n");
while(1)
{

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 6
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
printf("\nEnter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1: printf("\nEnter the value to insert:");
scanf("%d",&val);
insertF(val);
break;
case 2: printf("\nEnter the value to insert:");
scanf("%d",&val);
insertL(val);
break;
case 3: printf("\nEnter the position and value to insert:");
scanf("%d%d",&pos,&val);
insert(pos,val);
break;
case 4: b=deletionF( );
if(b!=-1)
printf("\n Deleted:%d ",b);
break;
case 5: b=deletionL( );
if(b!=-1)
printf("\n Deleted:%d ",b);
break;
case 6: printf("\nEnter the position:");
scanf("%d",&pos);
b=deletion(pos);
if(b!=-1)
printf("\n Deleted:%d ",b);
break;
case 7: display( );
break;
case 8: exit(0);

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 7
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
default: printf("*** wrong choice ***\n");
}
}
getch( );
}

Output:

*** MENU ***

1. INSERT FIRST
2. INSERT LAST
3. INSERT at POSITION 4. DELETE FIRST
5. DELETE LAST
6.DELETE at POSITION
7. DISPLAY
8. EXIT

Enter your choice:1

Enter the value to insert:4

Enter your choice:2
Enter the value to insert:5
Enter your choice:3
Enter the position and value to insert:2 6
Enter your choice:7
List elements:4 6 5
Enter your choice:6
Enter the position:2
Deleted:6
Enter your choice:7
List elements:4 5
Enter your choice:5
Deleted:5

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 8
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
Enter your choice:4
Deleted:4
Enter your choice:7
List is empty
Enter your choice:8

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 9
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
2.Write a program that uses functions to perform the following operations on
doubly linked list:
i) Creation ii) Insertion iii) Deletion iv) Traversal

Description:
In this type of liked list each node holds two-pointer field. Pointers exist between
adjacent nodes in both directions. The list can be traversed either forward or
backward.

#include<stdio.h>
#include<conio.h>
struct node
{
int data;
struct node *next;
struct node *prev;
};
struct node *head=NULL,*tail=NULL;
void insertfirst(int val)
{
struct node *temp;
temp=(struct node *)malloc(sizeof(struct node));;
temp->data=val;
temp->next=NULL;
temp->prev=NULL;
if(head==NULL&&tail==NULL)

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 10
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
{
head=temp;
tail=temp;
}
else
{
temp->next=head;
head->prev=temp;
head=temp;
}
}
void insertlast(int val)
{
struct node *temp;
temp=(struct node *)malloc(sizeof(struct node));;
temp->data=val;
temp->next=NULL;
temp->prev=NULL;
if(head==NULL&&tail==NULL)
{
head=temp;
tail=temp;
}
else
{
temp->prev=tail;
tail->next=temp;
tail=temp;
}
}
void insertafter(int num, int val)
{
struct node *temp,*temp1;

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 11
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
if(head==NULL&&tail==NULL)
{
printf("No elements");
}
else
{
temp=(struct node *)malloc(sizeof(struct node));;
temp->next=NULL;
temp->data=val;
temp->prev=NULL;
temp1=head;
while(temp1->data!=num&&temp1!=NULL)
temp1=temp1->next;
if(temp1==NULL)
printf("No element");
else
{
temp->next=temp1->next;
temp->prev=temp1;
temp1->next->prev=temp;
temp1->next=temp;
}
}

}
void insertbefore(int num, int val)
{
struct node *temp,*temp1;
if(head==NULL&&tail==NULL)
{
printf("No elements");
}
else

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 12
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
{
temp=(struct node *)malloc(sizeof(struct node));;
temp->next=NULL;
temp->data=val;
temp->prev=NULL;
temp1=tail;
while(temp1->data!=num&&temp1!=NULL)
temp1=temp1->prev;
if(temp1==NULL)
printf("No element");
else
{
temp->next=temp1;
temp->prev=temp1->prev;
temp1->prev->next=temp;
temp1->prev=temp;
}
}

}
int deleteelement(int num)
{
int b;
struct node *temp,*temp1;
if(head==NULL&&tail==NULL)
{
printf("No elements");
return -1;
}
else
{
if(head->data==num)
{

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 13
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
b=head->data;
temp=head;
head=head->next;
head->prev=NULL;
free(temp);
return(b);
}
else
{
temp1=head;
while(temp1->next->data!=num&&temp1->next!=NULL)
{
temp1=temp1->next;
}
if(temp1->next==NULL)
{
printf("No element");
return -1;
}
else
{
b=temp1->next->data;
temp=temp1->next;
temp1->next=temp1->next->next;
temp1->next->prev=temp1;
free(temp);
return b;
}
}
}
}
int deletionF( )
{

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 14
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
int b;
struct node *temp;
if(head==NULL&&tail==NULL)
{
printf("\nEmpty");
return -1;
}
else if(head==tail)
{
temp=head;
head=NULL;
tail=NULL;
b=temp->data;
free(temp);
return(b);
}
else
{
temp=head;
head=head->next;
head->prev=NULL;
b=temp->data;
free(temp);
return b;
}
}
int deletionL( )
{
int b;
struct node *temp;
if(head==NULL&&tail==NULL)
{
printf("\nEmpty");

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 15
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
return -1;
}
else if(head==tail)
{
temp=head;
head=NULL;
tail=NULL;
b=temp->data;
free(temp);
return(b);
}
else
{
temp=tail;
tail=tail->prev;
tail->next=NULL;
b=temp->data;
free(temp);
return b;
}
}
void display( )
{
if(head==NULL)
{
printf("\nList is empty");
}
else
{
struct node *temp;
temp=head;
printf("\nList elements:");
while(temp != NULL)

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 16
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
{
printf("%d ",temp->data);
temp=temp->next;
}
}
}
void displayr( )
{
if(head==NULL)
{
printf("\nList is empty");
}
else
{
struct node *temp;
temp=tail;
printf("\nList elements:");
while(temp != NULL)
{
printf("%d ",temp->data);
temp=temp->prev;
}
}
}

void main( )
{
int ch,num,val,b;
clrscr( );
printf("\n*** MENU ***\n 1. INSERT FIRST\n 2. INSERT LAST \n 3. INSERT at
AFTER \n 4. INSERT at BEFORE \n 5. DEL ELEMENT \n 6. DEL First \n 7. DEL
Last \n 8. Display \n 9. Display Rev \n 10. EXIT\n");
while(1)

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 17
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
{
printf("\nEnter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1: printf("\nEnter the value to insert:");
scanf("%d",&val);
insertfirst(val);
break;
case 2: printf("\nEnter the value to insert:");
scanf("%d",&val);
insertlast(val);
break;
case 3: printf("\nEnter the num and value to insert:");
scanf("%d%d",&num,&val);
insertafter(num,val);
break;
case 4: printf("\nEnter the num and value to insert:");
scanf("%d%d",&num,&val);
insertbefore(num,val);
break;
case 5: printf("\nEnter the value to delete:");
scanf("%d",&val);
b=deleteelement(val);
if(b!=-1)
printf("Deleted: %d",b);
break;
case 6: b=deletionF( );
if(b!=-1)
printf("Deleted: %d",b);
break;
case 7: b=deletionL( );
if(b!=-1)

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 18
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
printf("Deleted: %d",b);
break;
case 8: display( );
break;
case 9: displayr( );
break;
case 10: exit(0);
default: printf("*** wrong choice ***\n");
}
}
getch( );
}

Output:
*** MENU ***
1. INSERT FIRST
2. INSERT LAST
3. INSERT at AFTER
4. INSERT at BEFORE
5. DEL ELEMENT
6. DEL First
7. DEL Last
8. Display
9. Display Rev
10. EXIT
Enter your choice:1
Enter the value to insert:6
Enter your choice:2
Enter the value to insert:9
Enter your choice:3

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 19
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
Enter the num and value to insert:6 7
Enter your choice:4
Enter the num and value to insert:9 8
Enter your choice:8
List elements:6 7 8 9
Enter your choice:9
List elements:9 8 7 6
Enter your choice:6
Deleted: 6
Enter your choice:7
Deleted: 9
Enter your choice:8
List elements:7 8
Enter your choice:10

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 20
 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>
struct node
{
int data;
struct node *next;
struct node *prev;
};
struct node *head=NULL, *tail=NULL;
void create(int);
void insertfirst(int);
void insertlast(int);
void deletefirst();
void deletelast();
void display();
void displayr();
void deleten(int);
void search(int);
void insertafter(int ,int);
void insertpos(int,int);
void deletepos(int);
void main()
{
int v,ch,p,key,val,n,v1;
printf("Menu options are \n");
printf("1. Create \n2.Insert first \n3.Insert last \n4.Delete first \n5.Delete last ");
printf("\n6.Display \n7.Display reverse \n8. Delete an element \n9. Search \n10.Insert
after \n11.Insert at position\n12.Delete at position\n13.Exit");
while(1)
{

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 21
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
printf("\nEnter your choice\t");
scanf("%d",&ch);
switch(ch)
{
case 1:printf("\nEnter number of nodes");
scanf("%d",&n);
create(n);break;
case 2: printf("\nEnter the value to be inserted");
scanf("%d",&v);
insertfirst(v);break;
case 3:printf("\nEnter the value to be inserted");
scanf("%d",&v);
insertlast(v);break;
case 4:deletefirst();
break;
case 5:deletelast();
break;
case 6:display(); break;
case 7:displayr();break;
case 8:printf("Enter the value to be deleted");
scanf("%d",&v);
deleten(v);break;
case 9: printf("\nEnter the key to be searched");
scanf("%d",&key);
search(key);break;
case 10: printf("enter the value after which the value to be inserted");
scanf("%d",&val);
printf("Enter the value to be inserted");
scanf("%d",&v1);
insertafter(val,v1);break;
case 11:printf("\nEnter the value to be inserted");
scanf("%d",&v);
printf("\n Enter the position to be inserted");

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 22
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
scanf("%d",&p);
insertpos(v,p);break;
case 12: printf("\n Enter the position to be deleted");
scanf("%d",&p);
deletepos(p);break;
case 13:exit(0);
default:printf("Invalid choice");
}
}
}
void create(int n)
{
int val,i;
struct node *temp,*temp1;
for(i=0;i<n;i++)
{
temp=(struct node*)malloc(sizeof(struct node));
printf("\nEnter the value of node%d:",i+1);
scanf("%d",&val);
temp->next=NULL;
temp->prev=NULL;
temp->data=val;
if(head==NULL&&tail==NULL)
{
head=temp;
tail=temp;
}
else
{
tail->next=temp;
temp->prev=tail;
tail=temp;
tail->next=head;

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 23
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
head->prev=tail;
}
}
}
void insertfirst(int x)
{
struct node *t;
t=(struct node*)malloc(sizeof(struct node));
t->next=NULL;
t->prev=NULL;
t->data=x;
if(head==NULL&&tail==NULL)
{
head=t;
tail=t;
}
else
{
t->next=head;
head->prev=t;
head=t;
tail->next=head;
head->prev=tail;
}
}
void insertlast(int x)
{
struct node *t;
t=(struct node*)malloc(sizeof(struct node));
t->next=NULL;
t->prev=NULL;
t->data=x;
if(head==NULL&&tail==NULL)

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 24
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
{
head=t;
tail=t;
}
else
{
tail->next=t;
t->prev=tail;
tail=t;
tail->next=head;
head->prev=tail;
}

}
void deletefirst()
{
struct node *t;
int b;
if(head==NULL&&tail==NULL)
printf("\nList is empty");
else if(head==tail)
{
t=head;
head=NULL;
tail=NULL;
b=t->data;
free(t);
printf("deleted element is %d",b);
}
else
{
t=head;
head=head->next;

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 25
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
head->prev=tail;
tail->next=head;
b=t->data;
free(t);
printf("deleted element is %d",b);
}
}
void deletelast()
{
struct node *t;
int b;
if(head==NULL&&tail==NULL)
printf("\nList is empty");
else if(head==tail)
{
t=head;
head=tail=NULL;
b=t->data;
free(t);
printf("deleted element is %d",b);
}
else
{
t=tail;
tail=tail->prev;
tail->next=head;
head->prev=tail;
b=t->data;
free(t);
printf("deleted element is %d",b);
}
}

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 26
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
void display()
{
struct node *t;
if(head==NULL)
printf("\nList is empty");
else
{
t=head;
printf("\n List elements are :\t");
while(t->next!=head)
{
printf("\t%d",t->data);
t=t->next;
}
printf("\t%d",t->data);
}
}

void displayr()
{
struct node *t;
if(head==NULL)
printf("\nList is empty");
else
{
t=tail;
printf("\n List elements are :\t");
while(t->prev!=tail)
{
printf("\t%d",t->data);
t=t->prev;
}
printf("\t%d",t->data);

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 27
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
}
}
void deleten(int num)
{
struct node *temp,*temp1;
int b;
if(head==NULL&&tail==NULL)
printf("list is empty");
else
{
if(head->data==num)
{
b=head->data;
temp=head;
head=head->next;
head->prev=tail;
tail->next=head;
free(temp);
printf("deleted element is %d",b);
}
else
{
temp1=head;
while(temp1->next->data!=num&&temp1->next->next!=head)
temp1=temp1->next;
if(temp1->next->next==head&&temp1->next->data!=num)
printf("element is not in the list");
else
{
b=temp1->next->data;
temp=temp1->next;
temp1->next->prev=temp1;
temp1->next=temp1->next->next;

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 28
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
free(temp);
printf("deleted element is %d",b);
}
}
}
}
void search(int key)
{
struct node *temp;
temp=head;
if(head==NULL&&tail==NULL)
printf("List is empty");
else
{
while(temp->data!=key&&temp->next!=head)
temp=temp->next;
if(temp->data==key&&temp->next==head)
printf("\nElement found");
else if (temp->next==head)
printf("element not found");
else
printf("Element found");
}
}
void insertafter(int v, int v1)
{
struct node *t,*temp;
t=(struct node*)malloc(sizeof(struct node));
t->next=NULL;
t->prev=NULL;
t->data=v1;
temp= head;
if(head==NULL&&tail==NULL)

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 29
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
printf("List is empty");
while(temp->data!=v&&temp->next!=head)
temp=temp->next;
if(temp->next==head)
printf("Element not found");
else
{
t->next=temp->next;
temp->next->prev=t;
temp->next=t;
t->prev=temp;
}
}
void insertpos(int x,int p)
{
struct node *temp,*t;
int i=1;
temp=(struct node*)malloc(sizeof(struct node));;
temp->prev=NULL;
temp->next=NULL;
temp->data=x;
if(head==NULL&&tail==NULL)
{
head=temp;
tail=temp;
}
else if(p==1)
{
temp->next=head;
head->prev=temp;
head=temp;
head->prev=tail;
tail->next=head;

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 30
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
}
else
{
t=head;
while(i<p-1)
{
t=t->next;
i++;
}
temp->next=t->next;
t->next->prev=temp;
temp->prev=t;
t->next=temp;
}
}
void deletepos(int p)
{
struct node *temp,*t;
int b,i=1;
if(head==NULL&&tail==NULL)
printf("\nList is empty");
else if(p==1)
{
b=head->data;
temp=head;
head=head->next;
head->prev=tail;
tail->next=head;
free(temp);
printf("deleted element is %d",b);
}
else
{

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 31
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
t=head;
while(i<p-1)
{
t=t->next;
i++;
}
b=t->next->data;
temp=t->next;
t->next=t->next->next;
t->next->prev=t;
free(temp);
printf("deleted element is %d",b);
}
}

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 32
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
4. i) Write a program that implement stack (its operations) using Arrays

Description:
A stack is an abstract data type that serves as a collection of elements, with two
principal operations: push, which adds an element to the collection, and pop,
which removes the most recently added element that was not yet removed. The
order in which elements come off a stack gives rise to its alternative name, LIFO
(for last in, first out).

#include <stdio.h>
#include<conio.h>
void push(int val);
int pop( );
void display( );
int s[20];
int top=-1;
void main( )
{
int b,val,ch;
clrscr( );
while(1)
{
printf("\nMenu");
printf("\n1. Push 2. Pop 3. Display 4. Exit");
printf("\nEnter your choice");
scanf("%d",&ch);
switch(ch)

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 33
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
{
case 1: printf("\nEnter the value");
scanf("%d",&val);
push(val);
break;
case 2: b=pop( );
if(b!=-1)
printf("\nDeleted: %d",b);
break;
case 3: display( );
break;
case 4: exit(0);
break;
}
}
}
void push(int val)
{
if(top==19)
printf("\nStack Overflow");
else
{
top++;
s[top]=val;
}
}
int pop( )
{
int b;
if(top==-1)
{
printf("\nStack Underflow");
return -1;

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 34
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
}
else
{
b=s[top];
top--;
return b;
}
}
void display( )
{
int i;
if(top==-1)
{
printf("\nStack Empty");
}
else
{
printf("\nStack elements: ");
for(i=0;i<=top;i++)
printf("%d ",s[i]);
}
}
Output:

Menu
1. Push 2. Pop 3. Display 4. Exit
Enter your choice1
Enter the value4
Menu
1. Push 2. Pop 3. Display 4. Exit
Enter your choice1
Enter the value6
Menu

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 35
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
1. Push 2. Pop 3. Display 4. Exit
Enter your choice3
Stack elements: 4 6
Menu
1. Push 2. Pop 3. Display 4. Exit
Enter your choice2
Deleted: 6
Menu
1. Push 2. Pop 3. Display 4. Exit
Enter your choice2
Deleted: 4
Menu
1. Push 2. Pop 3. Display 4. Exit
Enter your choice2
Stack Underflow
Menu
1. Push 2. Pop 3. Display 4. Exit
Enter your choice4

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 36
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
4. ii) Write a program that implement stack (its operations) using Pointers

#include<stdio.h>
#include<conio.h>
struct node
{
int data;
struct node *next;
};
struct node *top=NULL;
void push(int val)
{
struct node *temp;
temp=(struct node *)malloc(sizeof(struct node));;
temp->next=NULL;
temp->data=val;
if(top==NULL)
{
top=temp;
}
else
{
temp->next=top;
top=temp;
}
}
int pop( )
{
struct node *temp;
int b;
if(top==NULL)
{
printf("\nstack under flow");
--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 37
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
return -1;
}
else
{
b=top->data;
temp=top;
top=top->next;
free(temp);
return(b);
}

}
void display( )
{
if(top==NULL)
{
printf("\nstack is empty");
}
else
{
struct node *temp;
temp=top;
printf("\nstack elements:");
while(temp != NULL)
{
printf("%d ",temp->data);
temp=temp->next;
}
}
}

void main( )
{

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 38
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
int val,ch,b;
clrscr( );
printf("\n\n1.PUSH\n2.POP\n3.DISPLAY\n4.EXIT");
while(1)
{
printf("\nEnter ur choice:");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("\nEnter an element");
scanf("%d",&val);
push(val);
break;
case 2:
b=pop( );
if(b!=-1)
printf("\nDeleted:%d",b);
break;
case 3:
display( );
break;
case 4:
exit(0);
}
}

Output:

1.PUSH

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 39
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
2.POP
3.DISPLAY
4.EXIT
Enter ur choice:1
Enter an element25
Enter ur choice:1
Enter an element67
Enter ur choice:1
Enter an element54
Enter ur choice:3
stack elements:54 67 25
Enter ur choice:2
Deleted:54
Enter ur choice:2
Deleted:67
Enter ur choice:4

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 40
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
5 i)Write a program that implement Queue (its operations) using Arrays.

Description:
A queue is a particular kind of abstract data type or collection in which the entities
in the collection are kept in order and the principal (or only) operations on the
collection are the addition of entities to the rear terminal position, known as
enqueue, and removal of entities from the front terminal position, known as
dequeue. This makes the queue a First-In-First-Out (FIFO) data structure. In a
FIFO data structure, the first element added to the queue will be the first one to
be removed.

#include <stdio.h>
int front=-1,rear=-1,q[20];
void enqueue(int val);
int dequeue( );
void display( );
void main( )
{
int ch,val,b;
clrscr( );
printf("\n*** MENU ***\n 1.Enqueue\n 2.Dequeue\n 3.Display\n 4. Exit\n");
while(1)
{
printf("\nEnter your choice:");
scanf("%d",&ch);
switch(ch)
{

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 41
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
case 1: printf("\nEnter the value to insert:");
scanf("%d",&val);
enqueue(val);
break;
case 2: b=dequeue( );
if(b!=-1)
printf("\n Deleted:%d ",b);
break;
case 3: display( );
break;
case 4: exit(0);
default: printf("*** wrong choice ***\n");
}
}
getch( );
}
void enqueue(int val)
{
if(rear==19)
printf("\nQueue is full");
else if(front==-1&&rear==-1)
{
front=0;
rear=0;
q[rear]=val;
}
else
{
rear++;
q[rear]=val;
}
}
int dequeue( )

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 42
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
{
int b;
if((front==-1&&rear==-1)||(front==rear+1))
{
printf("\nQueue is empty");
return -1;
}
else
{
b=q[front];
front++;
return b;
}
}
void display( )
{
int i;
if((front==-1&&rear==-1)||front==rear+1)
printf("\nQueue is empty");
else
{
printf("\nQueue: ");
for(i=front;i<=rear;i++)
printf(" %d ",q[i]);
}
}

Output:

*** MENU ***

1.Enqueue
2.Dequeue

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 43
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
3.Display
4. Exit
Enter your choice:1
Enter the value to insert:4
Enter your choice:1
Enter the value to insert:6
Enter your choice:3
Queue: 4 6
Enter your choice:2
Deleted:4
Enter your choice:2
Deleted:6
Enter your choice:2
Queue is empty
Enter your choice:4

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 44
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
5.ii) Write a program that implement Queue (its operations) using Pointers.

#include<stdio.h>
#include<conio.h>
struct node
{
int data;
struct node *next;
};
struct node *front=NULL;
struct node *rear=NULL;

void enqueue(int val)

{
struct node *temp;
temp=(struct node *)malloc(sizeof(struct node));
temp->next=NULL;
temp->data=val;
if(front==NULL&&rear==NULL)
{
front=temp;
rear=temp;
}
else
{
rear->next=temp;
rear=temp;
}
}
int dequeue( )
{
struct node *temp;
int b;
if(front==NULL && rear==NULL)

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 45
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
{
printf("\nQueue is empty");
return -1;
}
else if(front==rear)
{
b=front->data;
temp=front;
front=NULL;
rear=NULL;
free(temp);
return b;
}
else
{
b=front->data;
temp=front;
front=front->next;
free(temp);
return b;
}

}
void display( )
{
struct node *temp;
if(front==NULL)
{
printf("\nQueue is empty");
return;
}
else
{

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 46
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
temp=front;
printf("\nQueue elements:");
while(temp != NULL)
{
printf("%d ",temp->data);
temp=temp->next;
}
}
}
void main( )
{
int val,ch,b;
clrscr( );
printf("\n*** MENU ***\n 1.Enqueue\n 2.Dequeue\n 3.Display\n 4. Exit\n");
while(1)
{
printf("\nEnter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("\n enter a element");
scanf("%d",&val);
enqueue(val);
break;
case 2:
b=dequeue( );
if(b!=-1)
printf("\nDeleted:%d",b);
break;
case 3:
display( );
break;

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 47
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
case 4:
exit(0);
}
}
}
Output:
*** MENU ***
1.Enqueue
2.Dequeue
3.Display
4. Exit
Enter your choice:1
enter a element65
Enter your choice:1
enter a element98
Enter your choice:1
enter a element34
Enter your choice:3
Queue elements:65 98 34
Enter your choice:2
Deleted:65
Enter your choice:2
Deleted:98
Enter your choice:4

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 48
 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

Description:

In Bubble sort, the list is divided into two sublist, sorted and unsorted.
In each pass, the smallest element is bubbled from unsorted sublist and moved to
the sorted sublist. Or In each pass, the biggest element is bubbled from unsorted
sublist and moved to the sorted sublist.
A list of n elements requires atmost of n-1 passes to sort.

#include<stdio.h>
#include<conio.h>
void bubble(int a[ ], int n);
void main( )
{
int a[20],n,i;
clrscr( );
printf("\nEnter the no. of elements:");
scanf("%d",&n);
printf("\nEnter the elements:");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
bubble(a,n);
getch( );
}
void bubble(int a[ ], int n)
{
int i,j,k,temp;
printf("\nOriginal list: ");
for(k=0;k<n;k++)
printf("%d ",a[k]);
for(i=0;i<n-1;i++)

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 49
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
{
for(j=n-1;j>i;j--)
{
if(a[j]<a[j-1])
{
temp=a[j];
a[j]=a[j-1];
a[j-1]=temp;
}
}
printf("\nAfter pass %d: ",i+1);
for(k=0;k<n;k++)
printf("%d ",a[k]);
}
}

Output:

Enter the no. of elements:5

Enter the elements:6 8 3 5 2

Original list: 6 8 3 5 2
After pass 1: 2 6 8 3 5
After pass 2: 2 3 6 8 5
After pass 3: 2 3 5 6 8
After pass 4: 2 3 5 6 8

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 50
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------

6. ii) Selection sort

Description:

In Selection sort, the list is divided into two sublists, sorted and unsorted.
In selection sort, we find the smallest element from the unsorted sublist and swap it
with the element at the beginning of the unsorted sublist.
After each selection and swapping, the wall between sorted and unsorted sublists
moves one element ahead.
Each time we move one element from unsorted sublist to sorted sublist, we say that
we have completed a sort pass.
A list of n elements requires atmost of n-1 passes to sort.

#include<stdio.h>
#include<conio.h>
void selection(int a[ ], int n);
void main( )
{
int a[20],n,i;
clrscr( );
printf("\nEnter the no. of elements:");
scanf("%d",&n);
printf("\nEnter the elements:");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
selection(a,n);
getch( );
}
void selection(int a[ ], int n)
{
int i,j,k,temp,small;
printf("\nOriginal list: ");
for(k=0;k<n;k++)
--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 51
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
printf("%d ",a[k]);
for(i=0;i<n-1;i++)
{
small=i;
for(j=i+1;j<n;j++)
{
if(a[small]>a[j])
small=j;
}
temp=a[small];
a[small]=a[i];
a[i]=temp;
printf("\nAfter pass %d: ",i+1);
for(k=0;k<n;k++)
printf("%d ",a[k]);
}
}

Output:
Enter the no. of elements:5

Enter the elements:8 2 5 9 3

Original list: 8 2 5 9 3
After pass 1: 2 8 5 9 3
After pass 2: 2 3 5 9 8
After pass 3: 2 3 5 9 8
After pass 4: 2 3 5 8 9

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 52
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
6.iii) Insertion Sort

Description:

In Insertion sort, the list is divided into two sublist, sorted and unsorted.
In each pass, the first element of unsorted sublist is picked up and transferred
into the sorted sublist by inserting it at the appropriate place.
Insertion sort starts with one (first) element in the sorted sublist.
A list of n elements requires atmost of n-1 passes to sort.

#include<stdio.h>
#include<conio.h>
void insertion(int a[ ], int n);
void main( )
{
int a[20],n,i;
clrscr( );
printf("\nEnter the no. of elements:");
scanf("%d",&n);
printf("\nEnter the elements:");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
insertion(a,n);
getch( );
}
void insertion(int a[ ], int n)
{
int i,j,k,temp;
printf("\nOriginal list: ");
for(k=0;k<n;k++)
printf("%d ",a[k]);
for(i=1;i<n;i++)
{

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 53
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
for(j=i;j>0;j--)
{
if(a[j]<a[j-1])
{
temp=a[j];
a[j]=a[j-1];
a[j-1]=temp;
}
else
break;
}
printf("\nAfter pass %d: ",i);
for(k=0;k<n;k++)
printf("%d ",a[k]);
}
}

Output:

Enter the no. of elements:5

Enter the elements:8 4 3 7 2
Original list: 8 4 3 7 2
After pass 1: 4 8 3 7 2
After pass 2: 3 4 8 7 2
After pass 3: 3 4 7 8 2
After pass 4: 2 3 4 7 8

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 54
 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

Description:
Linear search is used when the list is not ordered. In linear search, we start
searching for the target (key) from the beginning of the list, and continue until we find
the target (key) or until we are sure that it is not in the list. If the target (key) is found
in the list we say that the search is successful otherwise the search is unsuccessful.
The time complexity of linear search to search n elements is O(n).

#include<stdio.h>
#include<conio.h>
void linear(int a[ ], int n,int key);
void main( )
{
int a[20],n,i,key;
clrscr( );
printf("\nEnter the no. of elements:");
scanf("%d",&n);
printf("\nEnter the elements:");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\nEnter the element to search:");
scanf("%d",&key);
linear(a,n,key);
getch( );
}
void linear(int a[ ], int n,int key)
{
int i,flag=0;
for(i=0;i<n;i++)
{
if(a[i]==key)

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 55
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
{
printf("\nElement found at %d position",i+1);
flag=1;
break;
}
}
if(flag==0)
{
printf("\nElement not found in the list");
}
}

Output:

Enter the no. of elements:5

Enter the elements:7 3 5 9 2

Enter the element to search:5

Element found at 3 position

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 56
 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:

ii) Binary search (recursive)

Description:
Binary search is used when the list is sorted. The binary search starts by searching
for the target (key) at the middle of the list (array). If the target (key) is at the middle,
the search completes otherwise if the target (key) is less than the value at middle,
the search is applied only to first half otherwise the search is applied only to second
half.

#include<stdio.h>
#include<conio.h>
void rbinary(int a[ ],int key,int first,int last);
void main( )
{
int a[20],n,i,key,flag=0,first,last,mid;
clrscr( );
printf("\nEnter the no. of elements:");
scanf("%d",&n);
printf("\nEnter the elements in sorted order:");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\nEnter the element to search:");
scanf("%d",&key);
first=0;
last=n-1;
rbinary(a,key,first,last);
getch( );
}

void rbinary(int a[ ],int key,int first,int last)

{
int mid;

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 57
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
if(first>last)
{
printf("\nElement not found");
}
else
{
mid = (first + last)/2;
if(key == a[mid])
{
printf("The element is at position %d\n",mid+1);
}
else if(key < a[mid])
{
last = mid - 1;
rbinary(a,key,first,last);
}
else
{
first = mid + 1;
rbinary(a,key,first,last);
}
}
}

Output:
Enter the no. of elements: 5
Enter the elements in sorted order: 2 3 5 7 9
Enter the element to search: 7
The element is at position 4

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 58
 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:

ii) Binary search (Non-recursive)

#include<stdio.h>
#include<conio.h>
void nrbinary(int a[ ],int key,int first,int last);
void main( )
{
int a[20],n,i,key,flag=0,first,last,mid;
clrscr( );
printf("\nEnter the no. of elements:");
scanf("%d",&n);
printf("\nEnter the elements in sorted order:");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\nEnter the element to search:");
scanf("%d",&key);
first=0;
last=n-1;
nrbinary(a,key,first,last);
getch( );
}
void nrbinary(int a[ ],int key,int first,int last)
{
int mid,flag=0;
while(first<=last)
{
mid=(first+last)/2;
if(key==a[mid])
{
printf("\nElement found at position %d",mid+1);
flag=1;
break;

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 59
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
}
else if(key>a[mid])
{
first=mid+1;
}
else
{
last=mid-1;
}
}
if(flag==0)
{
printf("\nElement not found in the list");
}
}

Output:

Enter the no. of elements:5

Enter the elements in sorted order:2

4
6
7
8

Enter the element to search:4

Element found at position 2

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 60
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
8. Write a program to implement the tree traversal methods.

Description:
In-order

If each node is visited between visiting its left and right subtrees, then it's an in-order
traversal. The in-order traversal is:

1. Do an in-order traversal of the left subtree

2. Visit root node
3. Do an in-order traversal of the right subtree

Pre-order

If each node is visited before both of its subtrees, then it's called a pre-order traver-
sal. The pre-order traversal is:

1. Visit the root node

2. Do a pre-order traversal of the left subtree
3. Do a pre-order traversal of the right subtree

Post-order

If each node is visited after its subtrees, then it's a post-order traversal. The post-or-
der traversal is:

1. Do a post-order traversal of the left subtree

2. Do a post-order traversal of the right subtree
3. Visit the root node

#include<stdio.h>
#include<conio.h>
struct node
{
int data;
struct node *left;
struct node *right;
};
struct node *root=NULL;
void insert(int ch)
{
--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 61
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
struct node *temp1,*temp;
temp=(struct node*)malloc(sizeof(struct node));
temp->data=ch;
temp->left=NULL;
temp->right=NULL;
if(root==NULL)
{
root=temp;
}
else
{
temp1=root;
while(temp1!=NULL)
{
if(ch<temp1->data)
{
if(temp1->left==NULL)
{
temp1->left=temp;
break;
}
else
temp1=temp1->left;
}
else
{
if(temp1->right==NULL)
{
temp1->right=temp;
break;
}
else
temp1=temp1->right;

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 62
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
}
}
}
}
void display(struct node *temp1)
{
if(temp1==NULL)
return ;
display(temp1->left);
printf("%4d",temp1->data);
display(temp1->right);
}
void inorder(struct node *temp1)
{
if(temp1==NULL)
return ;
inorder(temp1->left);
printf("%4d",temp1->data);
inorder(temp1->right);
}
void preorder(struct node *temp1)
{
if(temp1==NULL)
return ;
printf("%4d",temp1->data);
preorder(temp1->left);
preorder(temp1->right);
}
void postorder(struct node *temp1)
{
if(temp1==NULL)
return ;
postorder(temp1->left);

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 63
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
postorder(temp1->right);
printf("%4d",temp1->data);
}
void main( )
{
int ch,n,i,val;
clrscr( );
printf("\n1.Insert\n2.Display \n3.Preorder Traversal");
printf("\n4.Inorder Traversal\n5.Postorder Traversal");
printf("\n6.Exit");
while(1)
{
printf("\n\nEnter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("\n\nEnter no of elements to insert:");
scanf("%d",&n);
printf("\n enter the elements");
for(i=1;i<=n;i++)
{
scanf("%d",&val);;
insert(val);
}
break;
case 2:
display(root);
break;
case 3:
preorder(root);
break;
case 4:

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 64
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
inorder(root);
break;
case 5:
postorder(root);
break;
case 6:
exit(0);
}
}
}

Output:

1.Insert
2.Display
3.Preorder Traversal
4.Inorder Traversal
5.Postorder Traversal
6.Exit

Enter your choice:1

Enter no of elements to insert:5

enter the elements6 3 2 4 8

Enter your choice:2

2 3 4 6 8

Enter your choice:3

6 3 2 4 8

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 65
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------

Enter your choice:4

2 3 4 6 8

Enter your choice:5

2 4 3 8 6

Enter your choice:6

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 66
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
8. Write a program to implement the tree traversal methods.(Non-recursive)

#include<stdio.h>
#include<conio.h>
struct node
{
int data;
struct node *left;
struct node *right;
};
struct node *root=NULL;
struct node *stk[50];
int top=-1;
void insert(int ch)
{
struct node *temp1,*temp;
temp=(struct node*)malloc(sizeof(struct node));
temp->data=ch;
temp->left=NULL;
temp->right=NULL;
if(root==NULL)
{

root=temp;
}
else
{
temp1=root;
while(temp1!=NULL)
{
if(ch<temp1->data)
{
if(temp1->left==NULL)
{
temp1->left=temp;
--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 67
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
break;
}
else
temp1=temp1->left;
}
else
{
if(temp1->right==NULL)
{
temp1->right=temp;
break;
}
else
temp1=temp1->right;
}
}
}
}
void display(struct node *temp1)
{
if(temp1==NULL)
return ;
display(temp1->left);
printf("%4d",temp1->data);
display(temp1->right);
}
void push(struct node *t)
{
top++;
stk[top]=t;
}
struct node* pop( )
{

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 68
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
struct node *p;
p=stk[top];
top--;
return p;
}
void preordernr(struct node *temp1)
{
while(temp1!=NULL)
{
printf(" %d",temp1->data);
if(temp1->right!=NULL)
push(temp1->right);
temp1=temp1->left;
if(temp1==NULL && top>=0)
{
temp1=pop( );
}
}
}
void inordernr(struct node *temp1)
{
while(temp1!=NULL)
{
push(temp1);
temp1=temp1->left;
while(temp1==NULL && top>=0)
{
temp1=pop( );
printf(" %d ",temp1->data);
temp1=temp1->right;
}
}
}

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 69
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
void postordernr(struct node *temp1)
{
struct node *temp2=temp1;
while(temp1!=NULL)
{
for( ;temp1->left!=NULL;temp1=temp1->left)
push(temp1);
while(temp1!=NULL && (temp1->right==NULL || temp1->right==temp2))
{
printf(" %d ",temp1->data);
temp2=temp1;
if(top==-1)
return;
temp1=pop( );
}
push(temp1);
temp1=temp1->right;
}
}
void main( )
{
int ch,n,i,val;
clrscr( );
printf("\n1.Insert\n2.Display \n3.Preorder Traversal");
printf("\n4.Inorder Traversal\n5.Postorder Traversal");
printf("\n6.Exit");
while(1)
{
printf("\n\nEnter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1:

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 70
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
printf("\n\nEnter no of elements to insert:");
scanf("%d",&n);
printf("\n enter the elements");
for(i=1;i<=n;i++)
{
scanf("%d",&val);;
insert(val);
}
break;
case 2:
display(root);
break;
case 3:
preordernr(root);
break;
case 4:
inordernr(root);
break;
case 5:
postordernr(root);
break;
case 6:
exit(0);
}
}
}

Output:

1.Insert
2.Display
3.Preorder Traversal
4.Inorder Traversal

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 71
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
5.Postorder Traversal
6.Exit

Enter your choice:1

Enter no of elements to insert:3
enter the elements6 4 8
Enter your choice:2
4 6 8

Enter your choice:3

6 4 8

Enter your choice:4

4 6 8

Enter your choice:5

4 8 6

Enter your choice:6

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 72
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
9. Write a program to implement the graph traversal methods.

i) DFS

Description:

Depth-first search (DFS) is an algorithm for traversing or searching tree or

graph data structures. One starts at the root (selecting some arbitrary node as
the root in the case of a graph) and explores as far as possible along each
branch before backtracking.

#include<stdio.h>
#include<conio.h>
int adjmat[10][10]={0},i,j,k,n,cv,visited[10]={0};
int m;
int s[20],top=-1;
void push(int val)
{
top++;
s[top]=val;
}
int pop( )
{
int b;
b=s[top];
top--;
return b;
}
int isempty( )
{
if(top==-1)
return 1;
else
return 0;
}
--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 73
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
void dfs(int cv)
{
while(!isempty( ))
{
cv=pop( );
for(j=1;j<=n;j++)
if(adjmat[cv][j]!=0 && visited[j]!=1)
{
printf(" %d ",j);
visited[j]=1;
push(cv);
cv=j;
j=0;
continue;
}
}
}
void main( )
{
printf("Enter the no. of vertices and edges:");
scanf("%d%d",&n,&m);
printf("Enter the vertex pair for each edge:");
for(k=1;k<=m;k++)
{
scanf("%d%d",&i,&j);
adjmat[i][j]=1;
adjmat[j][i]=1;
}
printf("Enter the initial vertex to start the traversal:");
scanf("%d",&cv);
printf("Visited vertices: %d ",cv);
visited[cv]=1;
push(cv);

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 74
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
dfs(cv);
}

Output:

Enter the no. of vertices and edges:5

6
Enter the vertex pair for each edge:
12
13
24
34
35
54
Enter the initial vertex to start the traversal:1
Visited vertices: 1 2 4 3 5

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 75
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
9. Write a program to implement the graph traversal methods.

ii) BFS

Description:

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph

data structures. It starts at the tree root (or some arbitrary node of a graph,
sometimes referred to as a 'search key') and explores the neighbor nodes first,
before moving to the next level neighbors.

#include<stdio.h>
#include<conio.h>
int adjmat[10][10]={0},i,j,k,n,cv,visited[10]={0};
int m;
int q[20],front=-1,rear=-1;
void enqueue(int val)
{
if(front==-1 && rear==-1)
{
front=0;
rear=0;
q[rear]=val;
}
else
{
rear++;
q[rear]=val;
}
}
int dequeue( )
{
int b;
b=q[front];
front++;
--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 76
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
return b;
}
int isempty( )
{
if((front==-1&&rear==-1)||(front==rear+1))
{
return 1;
}
else
return 0;
}
void bfs(int cv)
{
while(!isempty( ))
{
cv=dequeue( );
for(j=1;j<=n;j++)
if(adjmat[cv][j]!=0 && visited[j]!=1)
{
printf(" %d ",j);
visited[j]=1;
enqueue(j);
}
}
}
void main( )
{
printf("Enter the no. of vertices and edges:");
scanf("%d%d",&n,&m);
printf("Enter the vertex pair for each edge:");
for(k=1;k<=m;k++)
{
scanf("%d%d",&i,&j);

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 77
 Data Structures LAB
----------------------------------------------------------------------------------------------------------------
adjmat[i][j]=1;
adjmat[j][i]=1;
}
printf("Enter the initial vertex to start the traversal:");
scanf("%d",&cv);
visited[cv]=1;
enqueue(cv);
printf("Visited vertices: %d ",cv);
bfs(cv);
}

Output:
Enter the no. of vertices and edges:5
6
Enter the vertex pair for each edge:
12
13
24
34
35
54
Enter the initial vertex to start the traversal:1
Visited vertices: 1 2 3 4 5

--------------------------------------------------------------------------------------------------------------------------------------
Department of CSE, BRECW 78