Brindavan College of Engineering

Dwarakanagar, Bagalur Main Road, Yelahanka, Bengaluru – 560063

Affiliated to VTU Belagavi, Approved by AICTE, New Delhi, India
Accredited ‘B++’ level by NAAC

www.brindavancollege.com

III Semester
DATA STRUCTURES LAB

BCSL305
ACADEMIC YEAR
2023 – 2024

LABORATORY MANUAL
PREPARED BY
Prof. Avinash N
 Brindavan College of Engineering
Department of Computer Science and Engineering

III Semester

DATA STRUCTURES LAB

BCSL305

ACADEMIC YEAR
2023 – 2024

NAME OF THE STUDENT :

UNIVERSITY SEAT NO. :

BATCH :

PREPARED BY

Prof. Avinash N
Assoc. Prof & HOD
 Brindavan College of Engineering
Department of Computer Science and Engineering

LABORATORY CERTIFICATE

This is to certify that Mr. /Ms.__________________________________________

bearing USN_________________ of __________semester and ________section has
satisfactorily completed the course of experiments in Data Structures Lab SUB code BCSL305
prescribed by the Visvesvaraya Technological University, Belagavi of this Institute for the
academic year 2023– 2024 .

MARKS

Maximum Marks Marks Obtained

Signature of Faculty-In-Charge Head of the Department

Date:
 Brindavan College of Engineering
Dwarakanagar, Bagalur Main Road, Yelahanka, Bengaluru – 560063
Affiliated to VTU Belagavi, Approved by AICTE, New Delhi, India
Accredited B++ level by NAAC

Department of Computer Science and Engineering

DEPARTMENT VISION

To advance the intellectual capacity of student community by imparting

knowledge to be ingenious entrepreneur and competent
professionals.

DEPARTMENT MISSION

 To disseminate technical knowledge with strong emphasis on

curriculum development.
 To impart computing skills to make the graduates globally
competitive.
 To inculcate value based professional ethics, become prevalent in
industry and promoting research activities.
 Brindavan College of Engineering
Dwarakanagar, Bagalur Main Road, Yelahanka, Bengaluru – 56
Affiliated to VTU Belagavi, Approved by AICTE, New Delhi, India
Accredited B++ level by NAAC

Department of Computer Science and Engineering

DOs & DON’Ts IN LABORATORY

DOs

 Be on time and students should carry observation and completed records in all aspects.
 Dress code & wearing ID card is compulsory.
 Electronic gadgets are not allowed inside the lab.
 Students should be at their concerned desktop.
 After execution the students should get it verified by the concerned faculty.
 The executed results should be noted in their observations and get it verified by the
concerned faculty.
 Observe good housekeeping practices. Keep the equipment‟s in proper place after the
conduction.
 Students must ensure that all the switches are in the OFF position; desktop is shutdown
properly after completion of the assignments.
 For circuits lab the components must returned properly.
 For power electronics lab wearing shoes is compulsory.

DON’Ts

 Do not come late to lab.

 Do not touch server computer.
 Do not leave the lab without the permission of the faculty in-charge.
 Do not wear footwear and enter the lab(except power electronics lab).
 Do not insert pen drive/memory card to any computer in the lab.
 Do not upload, delete or alter any software files.
 PREFACE

Data Structure is defined as the group of data elements which provides an efficient way of
storing and organizing data in the computer. So that it can be used efficiently. They are the part
of many Computer Science Algorithms as they enable the programmers to handle the data in an
efficient way and enhancing the performance of software or a program. The Data Structure
Laboratory contributes to educate the undergraduate students of 3rd semester B.E, VTU
Belagavi in the field of Computer Science and Engineering.

The objective of Data Structure Laboratory is to revise some fundamental concepts of

programming, object-oriented programming and basic data structures. Some examples of
Data Structures are arrays, Linked List, Stack, Queue, etc. Data Structures are widely used in
almost every aspect of Computer Science i.e. operating System, Compiler Design, Artificial
intelligence, Graphics and many more.

Demonstration exercises are provided to understand linear data structures and their applications
such as stacks, queues and lists, Non-Linear data structures and their applications such as trees
and graphs, sorting and searching algorithms.

Prof. Avinash N
 DATA STRUCTURES LAB

Course Code: BCS305 CIE Marks: 50

Number of Lecture Hours/Week: 02 Hours
SEE Marks: 50 Exam Hours: 03
CREDITS: 01 RBT Levels L1, L2, L3

Course Outcomes:
The student should be able to:
● Analyse various linear and non-linear data structures.
● Demonstrate the working nature of different types of data structures and their
applications
● Use appropriate searching and sorting algorithms for the given scenario.
● Apply the appropriate data structure for solving real world problems.
 INDEX
Sl. Contents Page
No No
1 Develop a Program in C for the following: 1
a) Declare a calendar as an array of 7 elements (A dynamically Created array)
to represent 7 days of a week. Each Element of the array is a structure having
three fields. The first field is the name of the Day (A dynamically allocated
String), The second field is the date of the Day (A integer), the third field is the
description of the activity for a particular day (A dynamically allocated
String).
b) Write functions create ( ), read ( ) and display (); to create the calendar, to
read the data from the keyboard and to print weeks activity details report on
screen.
2 Develop a Program in C for the following operations on Strings. 4
a. Read a main String (STR), a Pattern String (PAT) and a Replace
String (REP)
b. Perform Pattern Matching Operation: Find and Replace all occurrences
of PAT in STR with REP if PAT exists in STR. Report suitable messages in
case PAT does not exist in STR
Support the program with functions for each of the above Operations. Don't
use Built-in functions.
3 Develop a menu driven Program in C for the following operations on STACK 6
of Integers
a. Push an Element on to Stack
b. Pop an Element from Stack
c. Demonstrate how Stack can be used to check Palindrome
d. Demonstrate Overflow and Underflow situations on Stack
e. Display the status of Stack
f. Exit
Support the program with appropriate functions for each of the above
operations
4 Develop a Program in C for converting an Infix Expression to Postfix 16
Expression. Program should support for both parenthesized and free
parenthesized expressions with the operators: +, -, *, /, % (Remainder), ^
(Power) and alphanumeric operands.
5 Develop a Program in C for the following Stack Applications 19
a. Evaluation of Suffix expression with single digit operands and operators:
+, -, *, /, %, ^
b. Solving Tower of Hanoi problem with n disks
6 Develop a menu driven Program in C for the following 23
operations on Circular QUEUE of Characters (Array Implementation of Queue
with maximum size MAX)
a) Insert an Element on to Circular QUEUE
b) Delete an Element from Circular QUEUE
c) Demonstrate Overflow and Underflow situations on Circular QUEUE
d) Display the status of Circular QUEUE
e) Exit
7 Develop a menu driven Program in C for the following operations 28
on Singly Linked List (SLL) of Student Data with the fields:
USN, Name, Programme, Sem, PhNo
a. Create a SLL of N Students Data by using front insertion.
b. Display the status of SLL and count the number of nodes in it
c. Perform Insertion / Deletion at End of SLL
d. Perform Insertion / Deletion at Front of SLL
e. Exit
8 f. Develop a menu driven Program in C for the following 38
operations on Doubly Linked List (DLL) of Employee Data with
the fields: SSN, Name, Dept, Designation, Sal, PhNo
g. Create a DLL of N Employees Data by using end insertion.
h. Display the status of DLL and count the number of nodes in it
i. Perform Insertion and Deletion at End of DLL
j. Perform Insertion and Deletion at Front of DLL
k. Demonstrate how this DLL can be used as Double Ended
Queue.
l. Exit
9 Develop a Program in C for the following operations on Singly 49
Circular Linked List (SCLL) with header nodes a. Represent and
Evaluate
a. Polynomial P(x,y,z) = 6x2y2z-4yz5 +3x2yz+2xy5z-2xyz3
b. Find the sum of two polynomials POLY1(x,y,z) and
POLY2(x,y,z) and store the result in POLYSUM(x,y,z)
Support the program with appropriate functions for each of the
m. above operations
10 Develop a menu driven Program in C for the following 58
operations on Binary Search Tree (BST) of Integers .
a. Create a BST of N Integers: 6, 9, 5, 2, 8, 15, 24, 14, 7, 8, 5, 2
b. Traverse the BST in Inorder, Preorder and Post Order
c. Search the BST for a given element (KEY) and report the
appropriate message
d. Exit
11 Develop a Program in C for the following operations on Graph(G) of 66
Cities
a. Create a Graph of N cities using Adjacency Matrix.
b. Print all the nodes reachable from a given starting node in a
digraph using DFS/BFS method
12 Given a File of N employee records with a set K of Keys (4- digit)
which uniquely determine the records in file F. Assume that file F is
maintained in memory by a Hash Table (HT) of m memory
locations with L as the set of memory addresses (2- digit) of
locations in HT. Let the keys in K and addresses in L are Integers.
Develop a Program in C that uses Hash function H: K →L as
H(K)=K mod m (remainder method), and implement hashing
technique to map a given key K to the address space L. Resolve the
collision (if any) using linear probing.
 Program 1:
Develop a Program in C for the following:
a) Declare a calendar as an array of 7 elements (A dynamically Created array) to
represent 7 days of a week. Each Element of the array is a structure having three fields.
The first field is the name of the Day (A dynamically allocated String), The second field
is the date of the Day (A integer), the third field is the description of the activity for a
particular day (A dynamically allocated String).
b) Write functions create(), read() and display(); to create the calendar, to read the data
from the keyboard and to print weeks activity details report on screen.
//Implementation
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
// Define the structure for each day of the week
struct Day {
char *name;
int date;
char *activity;
};
// Define an array to store 7 days of the week
struct Day week[7];
// Function to create the calendar
void create( )
{
for (int i = 0; i < 7; i++)
{
week[i].name = (char *)malloc(20 * sizeof(char));
week[i].activity = (char *)malloc(100 * sizeof(char));
printf("Enter the name of day %d: ", i + 1);
scanf("%s", week[i].name);
printf("Enter the date of day %d: ", i + 1);
scanf("%d", &week[i].date);
printf("Enter the activity for day %d: ", i + 1);
getchar();
fgets(week[i].activity, 100, stdin);
}
}
// Function to read data from the keyboard
void read( ) {
create( ); // Reusing the create function for reading data
}
// Function to display the calendar
void display() {
printf("\nDay\tDate\tActivity\n");
for (int i = 0; i < 7; i++)
{
printf("%s\t%d\t%s", week[i].name, week[i].date, week[i].activity);
}
10
}
int main( )
{
printf("Creating a calendar:\n");
create ( );
printf("\displaying the calendar:\n");
display( );
return 0;
}

Output:
Creating a calendar:
Enter the name of day 1: Monday
Enter the date of day 1: 30
Enter the activity for day 1: 3rd Sem starts

Enter the name of day 2: Tuesday

Enter the date of day 2: 31
Enter the activity for day 2: Interaction with juniors
Enter the name of day 3: Wednesday
Enter the date of day 3: 1
Enter the activity for day 3: Kannada Rajyotsava
Enter the name of day 4: Thursday
Enter the date of day 4: 2
Enter the activity for day 4: Technical Talk from Industry Experts
Enter the name of day 5: Friday
Enter the date of day 5: 3
Enter the activity for day 5: Cultural Activities
Enter the name of day 6: Saturday
Enter the date of day 6: 4
Enter the activity for day 6: Hands on session (Web Designing)
Enter the name of day 7: Refreshment
Enter the date of day 7: Sunday

Displaying the calendar:

Day Date Activity
Monday 30 3rd Sem starts
Tuesday 31 Interaction with juniors
Wednesday 1 Kannada Rajyostava
Thursday 2 Technical Talk from Industry Experts
Friday 3 Cultural Activities
Saturday 4 Hands on session (Web Designing)
Sunday 5 Refreshment

11
/*2. Design, develop and Implement a Program in C for the following operations on Strings
a. Read a main String (STR),
b. Pattern String (PAT) and a Replace String (REP)
c. Perform Pattern Matching Operation: Find and Replace all occurrences of PAT in
STR with REP if PAT exists in STR.
Report suitable messages in case PAT does not exist in STR. Support the program with
functions for each of the above operations. Don't use Built-in functions.
//Implementation
#include<stdio.h>
#include<conio.h>
char Mainstr[100],Pat[100],Replace[100],ans[100];
int i,j,c,m,k;
void read()
{
printf("\nEnter a string \n");
gets(Mainstr);
printf("\nEnter a search string \n");
gets(Pat);
printf("\nEnter a replace string \n");
gets(Replace);
}
void find_replace()
{
i = m = c = j = 0;
while ( Mainstr[c] != '\0')
{
if ( Mainstr[m] == Pat[i] ) // matching
{
i++; m++;
if ( Pat[i] == '\0') // found occ
{
//.... copy replace string in ans string .....
for(k=0; Replace[k] != '\0';k++,j++)
{
ans[j] = Replace[k];}
i=0;
c=m;
}
}
else //... mismatch
{
ans[j] = Mainstr[c]; j++;
c++;
m = c; i=0;
}
}
ans[j] = '\0';
printf("\nThe resultant string is\n%s" ,ans);

12
}
void main()
{
clrscr();
read();
find_replace();
getch();
}

/* Output
Enter a string Respected Sir
Enter a search string Respected
Enter a replace string Dear
The resultant string is Dear Sir
*/

13
/* Program 3:Develop a menu driven Program in C for the following
operations on STACK of Integers (Array Implementation of Stack with
maximum size MAX)
a. Push an Element on to Stack
b. Pop an Element from Stack
c. Demonstrate how Stack can be used to check Palindrome
d. Demonstrate Overflow and Underflow situations on Stack
e. Display the status of Stack
f. Exit Support the program with appropriate functions for each of the above
operations. */
//implementation
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 5
int Stack[MAX], top=-1;
void push()
{
int ele;
if(top<MAX-1)
{
printf("Enter the value to be inserted into the stack :");
scanf("%d",&ele);
} Stack[++top] = ele;
else
printf("Stack is Full"); // overflow condition
}
int pop()
{
if(top!=-1)
{
printf("the element deleted from the stack is : %d",Stack[top--]);
}
else
{
printf("Stack is Empty"); //Underflow condition
}
return;
}

14
void Palindrome()
{
int i=0, len=top,flag=0;
int stack1[5];
while(top!=-1)
{
stack1[i]=Stack[top--];
i++;
}
for (i = 0; i < len; i++)
{
if (stack1[i] != Stack[i])
{ flag=1;
break;
}
}
if(flag==0)
printf("It is a Palindrome \n");
else
printf("It is not a palindrome");
}
void display()
{
int i;
if(top==-1)
{
printf("stack is empty");
}
else
{
printf("\ nElements in the stack are \n");
{
for(i=0;i<=top;i++)

printf("%d\n",Stack[i]);
}
}
}
void main()
{
int choice;
clrscr();
while(1)
{
printf("\n\n\n\t1.push...\t2.pop..\t3.palindrome...\t4.Display...\t5.Exit...");
printf("\n\n\n\tEnter Your Choice: ");
scanf("%d",&choice);
switch(choice)

15
 {
case 1: push();break;
case 2: pop();break;
case 3: Palindrome(); break;
case 4: display(); break;
case 5:exit(0);
default: printf("\n\n\n\tEnter proper Choice....");
}
}
}
/* Output
Run 1:
********
1.push... 2.pop.. 3.palindrome... 4.Display... 5.Exit...
Enter Your Choice: 1
Enter the value to be inserted into the stack :1

1.push... 2.pop.. 3.palindrome... 4.Display... 5.Exit...

Enter Your Choice: 4
Elements in the stack are
1
2
1

Run 2:
*******
1.push... 2.pop.. 3.palindrome... 4.Display... 5.Exit...

Enter Your Choice: 2

The element deleted from the stack is : 1

1.push... 2.pop.. 3.palindrome... 4.Display... 5.Exit...

Enter Your Choice: 4
Elements in the stack are
1
2

Run 3:
*****
1.push... 2.pop.. 3.palindrome... 4.Display... 5.Exit...
Enter Your Choice: 4
Elements in the stack are
1
2
1
1.push... 2.pop.. 3.palindrome... 4.Display... 5.Exit...
Enter Your Choice: 3
It is a Palindrome

16
/* 4. Design, Develop and Implement a Program in C for converting an Infix Expression to
Postfix Expression. Program should support for both parenthesized and free parenthesized
expressions with the operators: +, -, *, /, %(Remainder), ^(Power) and alphanumeric
operands.*/

//implementation

#define SIZE 50 /* Size of Stack */

#include <ctype.h>
#include <stdio.h>
char s[SIZE];
int top = -1; /* Global declarations */

void push(char elem) /* Function for PUSH operation */

{
s[++top] = elem;
}

char pop() /* Function for POP operation */

{
return (s[top--]);
}

int pr(char elem) /* Function for precedence */

{
switch (elem)
{
case '#':return 0;
case '(':return 1;
case '+':
case '-':return 2;
case '*':
case '/':
case '%':return 3;
case '^':return 4;
}
}

void main() /* Main Program */

{
char infx[50], pofx[50], ch, elem;
int i = 0, k = 0;
clrscr();
printf("\n\nRead the Infix Expression ? ");
scanf("%s", infx);
push('#');
while ((ch = infx[i++]) != '\0')
{
if (ch == '(')
17
push(ch);
else if (isalnum(ch))
pofx[k++] = ch;
else if (ch == ')')
{
while (s[top] != '(')
pofx[k++] = pop();
elem = pop(); /* Remove ( */
}
else /* Operator */
{
while (pr(s[top]) >= pr(ch))
pofx[k++] = pop();
push(ch);
}
}
while (s[top] != '#') /* Pop from stack till empty */
pofx[k++] = pop();
pofx[k] = '\0'; /* Make pofx as valid string */
printf("\n\nGiven Infix Expn: %s Postfix Expn: %s\n", infx, pofx);
getch();
}
/* Output Run 1:
Read the Infix Expression ? a*b+c^d
Given Infix Expn: a*b+c^d
Postfix Expn: ab*cd^+
*/

18
/* PROGRAM 5A
Design, develop and Implement a Program in C for the following Stack Applications
a. Evaluation of Suffix expression with single digit operands and operators: +, -, *, /, %, ^ */

//Implementation
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#define MAX 50

int stack[MAX];
char post[MAX];
int top=-1;

void pushstack(int tmp);

void calculator(char c);
void main()
{
int i;
clrscr();
printf("Insert a postfix notation :: ");
scanf("%s",post);
for(i=0;i<strlen(post);i++)
{
if(post[i]>='0' && post[i]<='9')
{
pushstack(i);
}
if(post[i]=='+' || post[i]=='-' || post[i]=='*' || post[i]=='/' || post[i]==‟^‟)
{
calculator(post[i]);
}
printf("\n\nResult :: %d",stack[top]);
getch():
}
void pushstack(int tmp)
{
top++;
stack[top]=(int)(post[tmp]-48);
}

void calculator(char c)
{
int a,b,ans;
b=stack[top];
stack[top]='\0';
top--;
a=stack[top];
stack[top]='\0';
19
 top--;
switch(c)
{
case '+':
ans=b+a;
break;
case „-„:
ans=b-a;
break;
case '*':
ans=b*a;
break;
case '/':
ans=b/a;
break;
case '^':
ans=pow(b,a);
break;
default
ans=0;
}
top++;
stack[top]=ans;
}
/* Output
Insert a postfix notation :: 22^32*+

Result :: 10
*/

20
/* 5b.c Tower of Honoi */
#include<stdio.h>
void towers(int, char, char, char);
void main()
{
int num;
clrscr();
printf("enter the number of disks : ");
scanf("%d", &num);
printf("the sequence of moves involved in the tower of honai are : \n");
towers(num, 'A','C','B');
getch();
}
void towers(int num, char frompeg, char topeg, char auxpeg)
{
if(num == 1)
{
printf("\n MOVE DISK 1 FROM PEG %c TO PEG %c", frompeg, topeg);
return;
}
towers( num -1, frompeg, auxpeg ,topeg);
printf("\n MOVE DISK %d FROM PEG %c TO PEG %c", num, frompeg, topeg);
return 1;
}
tower(n-1,s,d,t);
printf("\n Move disc %d from %c to %c",n,s,d); count++;
tower(n-1,t,s,d);
}

int main( )
{
printf("\n Enter the no. of discs:");
scanf("%d",&n); tower(n,'A','B','C');
printf("\n The no. of disc moves is:%d",count);
getch( );
}

Output 1:
Enter the no. of discs:2

Move disc 1 fromAto B

Move disc 2 from A to C
Move disc 1 from B to C
The no. of disc moves is:3

21
Program 6:
Develop a menu driven Program in C for the following operations on Circular QUEUE of
Characters (Array Implementation of Queue with maximum size MAX)
a. Insert an Element onto Circular QUEUE
b. Delete an Element from Circular QUEUE
c. Demonstrate Overflow and Underflow situations on Circular QUEUE
d. Display the status of Circular QUEUE
e. Exit
Supportthe program with appropriate functions for each of the above operations.
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define SIZE 5
int q[SIZE], i, r=-1, f=0, option, count=0, j;
int main( )
{
for(;;)
{
printf("\n 1.Insert 2.Delete\n 3.Display 4.Exit");
printf("\nEnter your option:");
scanf("%d",&option);
switch(option)
{
case 1: //Inserting items to Queue
if(count==SIZE)
printf("\n Q is Full\n");
else
{
r=(r+1)%SIZE;
printf("\nEnter the item:");
scanf("%d",&q[r]);
count++;
}
break;
case 2: //Deleting items from Queue
if(count==0)
printf("\nQ is empty\n");
else
{
printf("\nDeleted item is: %d",q[f]);
count--;
f=(f+1)%SIZE;
}
break:
case 3: //Displaying items from Queue
if(count==0)
printf("\nQ is Empty\n");
else
{
22
 i=f;
for(j=0;j<count;j++)
{
printf(" %d",q[i]);
\ i=(i+1)%SIZE;
}
}
break;
default: exit(0);
}
}
}

Output:
1.Insert 2.Delete 3.Display 4.Exit
Enter your option:1
Enter the item:10

1.Insert 2.Delete 3.Display 4.Exit

Enter your option:1
Enter the item:20

1.Insert 2.Delete 3.Display 4.Exi

Enter your option:1
Enter the item:30

1.Insert 2.Delete 3.Display 4.Exit

Enter your option:1
Enter the item:40

1.Insert 2.Delete 3.Display 4.Exit

Enter your option:1
Enter the item:50

1.Insert 2.Delete 3.Display 4.Exit

Enter your option:1
Q is Full

23
 Program 7:
Develop a menu driven Program in C for the following operations on Singly Linked List (SLL)
ofStudent Data with the fields: USN, Name, Programme, Sem, PhNo
a. Create a SLL of N Students Data by using front insertion.
b. Display the status of SLL and count the number of nodes in it.
c. Perform Insertion / Deletion at End of SLL
d. Perform Insertion / Deletion at Front of SLL(Demonstration of stack)
e. Exit

Implementation:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct student
{
char usn[11];
char name[25];
int sem;
char branch[5];
unsigned long long phno;
};
typedef struct student STUD;
struct node
{
char usn[11];
char name[25];
int sem;
char branch[5];
unsigned long long phno;
struct node *next;
};
typedef struct node NODE;
NODE *first;
NODE* copyNode(STUD s)
{
NODE * temp;
temp= (NODE *)malloc(sizeof(NODE));
if(temp==NULL)
{
printf("Memory cannot be allocated\n");
}
else
{
strcpy(temp->usn,s.usn);
strcpy(temp->name, s.name);
strcpy(temp->branch, s.branch);
temp->sem=s.sem;
temp->phno=s.phno;
temp->next=NULL;
24
 return temp;
}
}
void addrear(STUD s)
{
NODE *temp,*cur;
temp=copyNode(s) ;
if(first==NULL)
{
temp=first;
return;
}
cur=first;
while(cur->next != NULL)
{
cur=cur->next;
}
cur->next =temp;
return ;
}
void addfront(STUD s)
{
NODE *temp;
temp=copyNode(s); //ssn,name, dept, design,salary, pno);
if (first== NULL)
{
first=temp;

}
else
{
temp->next=first;
first=temp;
}
return ;
}
void display(NODE *temp)
{
printf("%s \t", temp->usn);
printf("%s \t", temp->name);
printf("%s \t", temp->branch);
printf("%d \t",temp->sem);
printf("%llu \n", temp->phno);
}
void deletefront()
{
NODE *temp;
int num;
temp=first;
if(first==NULL)
{
printf("List is Empty");
25
 return;
}
if(first->next==NULL)

first=NULL;
else
{
first=first->next;
}
printf("Deleted Node is:\n");
display(temp);
free(temp);
return;
}
void deleterear()
{
NODE *cur,*prev;
cur=first;
prev=NULL;
if(first==NULL)
{
printf("List is Empty");
return;
}
if(first->next==NULL)
{
display(cur);
first=NULL;
free(cur);
return;
}
while(cur->next!=NULL)
{
prev=cur;
cur=cur->next;
}
prev->next=NULL;
printf("Deleted Node is:\n");

display(cur);
free(cur);
return;
}
void displayList()
{
NODE *r;
r=first;
printf("USN\tName\tBrh\tSem\tPhone\n");
if(r==NULL)
return;
while(r!=NULL)

26
 {
display(r);
r=r->next;
}
printf("\n");
}
STUD input()
{
STUD s;
printf("Enter USN: ");
scanf("%s",s.usn);
printf("Enter Name : ");
scanf("%s",s.name);
printf("Enter Branch: ");
scanf("%s",s.branch);
printf("Enter Sem:");
scanf("%d",&s.sem);
printf("Enter Phone no : ");
scanf("%llu",&s.phno);
return s;
}
int count()
{
NODE *n;
int c=0;
n=first;
while(n!=NULL)
{
n=n->next;
c++;
}
return c;
}
int main()
{
STUD s;
int i,ch, n;
first=NULL;
while(1)
{
printf("\nList Operations\n");
printf("===============\n");
printf("1.Create List of n students by using front Insert\n");
printf("2.Display the status and count the nodes\n");
printf("3.Perform Insertion and Deletion at End of SLL\n");
printf("4.Perform Insertion and Deletion at Front of SLL\n");
printf("5.Exit\n");
printf("Enter your choice : ");
scanf("%d",&i);
switch(i)
{

27
 case 1 : printf("Enter the number of students\n");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
printf("\nEnter the details of student %d\n",i);
s=input();
addfront(s);
}
break;
case 2 : if(first==NULL)
{
printf("List is Empty\n");
}
else
printf(" Node Count=%d\t & Elements in the list are : \n", count());
displayList();
}
break;
case 3 : printf(" 1. Insert at End and 2 Delete From End=");
scanf("%d",&ch);
if(ch==1)
{
s=input();
addrear(s);
}
else if(ch==2)
deleterear();
else
printf(" Sorry wrong operation\n");
break;
case 4 : printf(" 1. Insert at Front and 2.Delete From Front=");
scanf("%d",&ch);
if(ch==1)
{
s=input();
addfront(s);
}
else if(ch==2)
deletefront();
else
printf(" Sorry wrong operation\n");
case 5 :exit (0);
default : printf("Invalid option\n");
}
}
return 0;
}

28
Output
List Operations
===============
1. Create List of n students by using front Insert
2.Display the status and count the nodes
3.Perform Insertion and Deletion at End of SLL
4.Perform Insertion and Deletion at Front of SLL
5.Exit
Enter your choice : 1
Enter the number of students
2
Enter the details of student 1
Enter USN: 1mp22is001
Enter Name : aishwarya
Enter Branch: ise
Enter Sem:3
Enter Phone no : 8765432192

Enter the details of student 2

Enter USN: 1mp22cs002
Enter Name : abhishek
Enter Branch: cse
Enter Sem:3
Enter Phone no : 9876543213

List Operations
===============
1.Create List of n students by using front Insert
2.Display the status and count the nodes
3.Perform Insertion and Deletion at End of SLL
4.Perform Insertion and Deletion at Front of SLL
5.Exit
Enter your choice : 3
1. Insert at End and 2 Delete From End=1
2. Enter USN: 1mp22ec003
Enter Name : asha
Enter Branch: ec
Enter Sem:3
Enter Phone no : 8976543218

29
List Operations
===============
1.Create List of n students by using front Insert
2.Display the status and count the nodes
3.Perform Insertion and Deletion at End of SLL
4.Perform Insertion and Deletion at Front of SLL
5.Exit
Enter your choice : 2
Node Count=3 & Elements in the list are :
USN Name Brh Sem Phone
1mp22cs002 abhishek cse 3 9876543213
1mp22is001 aishwarya ise 3 8765432192
1mp22ec003 asha ec 3 8976543218

List Operations
===============
1.Create List of n students by using front Insert
2.Display the status and count the nodes
3.Perform Insertion and Deletion at End of SLL
4.Perform Insertion and Deletion at Front of SLL
5.Exit
Enter your choice : 2
Node Count=3 & Elements in the list are :
USN Name Brh Sem Phone
1bo22cs002 abhishek cse 3 9876543213
1 bo22is001 aishwarya ise 3 8765432192
1 bo22ec003 asha ec 3 8976543218

List Operations
===============
1.Create List of n students by using front Insert
2.Display the status and count the nodes
3.Perform Insertion and Deletion at End of SLL
4.Perform Insertion and Deletion at Front of SLL
5.Exit
Enter your choice : 4
1. Insert at Front and 2.Delete From Front=2
Deleted Node is:
1mp22cs002 abhishek cse 3 9876543213

30
Program 8:
Develop a menu driven Program in C for the following operations on Doubly Linked List
(DLL) of Employee Data with the fields: SSN, Name, Dept, Designation, Sal, PhNo
a. Create a DLL of N Employees Data by using end insertion.
b. Display the status of DLL and count the number of nodes in it.
c. Perform Insertion and Deletion at End of DLL
d. Perform Insertion and Deletion at Front of DLL
e. Demonstrate how this DLL can be used as Double Ended Queue.
f. Exit
//Implementation

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct employee
{
char ssn[11];
char name[21];
char dept[15];
char design[15];
int salary;
unsigned long long phno;
};
typedef struct employee EMP;
struct node
{
char ssn[11];
char name[21];
char dept[15];
char design[15];
int salary;
unsigned long long phno;
struct node *next;
struct node *prev;
};
typedef struct node NODE;
NODE *first;

NODE* copyNode(EMP e)
{
NODE * temp;
temp= (NODE *)malloc(sizeof(NODE));
if(temp==NULL)
{
printf("Memory cannot be allocated\n");
}
else
{
strcpy(temp->ssn,e.ssn);
31
strcpy(temp->name, e.name);
strcpy(temp->dept, e.dept);
strcpy(temp->design, e.design);
temp->salary=e.salary;
temp->phno=e.phno;
temp->next=NULL;
temp->prev=NULL;
return temp;
}
}
void addrear(EMP e)
{
NODE *temp,*cur, *prev;
temp=copyNode(e) ;
if(first==NULL)
{
first=temp;
return;
}
cur=first;
prev=NULL;
while(cur->next != NULL)
{
prev=cur;
cur=cur->next;
}
cur->next =temp;
temp->prev=prev;
return ;
}

void addfront(EMP e)
{
NODE *temp;
temp=copyNode(e);
if (first== NULL)
{
first=temp;
}
else
{
temp->next=first;
first->prev=temp;
first=temp;
return ;
}

void display(NODE *r)

{
printf("%s\t", r->ssn);
printf("%s\t", r->name);
32
printf("%s\t", r->dept);
printf("%s\t",r->design);
printf("%d\t",r->salary);
printf("%llu\n", r->phno);
}
void deletefront()
{
NODE *temp;
int num;
temp=first;
if(first==NULL)
{
printf(" List is Empty \n");
return ;
}
if(first->next==NULL)
{
first=NULL;
else
{
first=first->next;
first->prev=NULL
}
printf("SSN\tName\tDept\tDesignation\tSalary\tPhone\n");
display(temp);
free(temp);
return ;
}

void deleterear()
{
NODE *cur, *prev;
cur=first;
prev=NULL;
if(first==NULL)
{
printf(" List is Empty \n");
return ;
}

33
if(first->next==NULL)
{
first=NULL;
}
else
{
while(cur->next!=NULL)
{
prev=cur;
cur=cur->next;
}
prev->next=NULL;
}
printf("SSN\tName\tDept\tDesignation\tSalary\tPhone\n");
display(cur);
free(cur);
return;
}
void displayList()
{
NODE *r;
r=first;
if(r==NULL)
{
return;

printf("SSN\t Name\t Dept\t Designation\t salary\tPhone\n");

while(r!=NULL)
{
display(r);
r=r->next;
}
printf("\n");
}
int count()
{
NODE *n;
int c=0;
n=first;
while(n!=NULL)
{
n=n->next;
c++;
}

34
return c;
}
EMP input()
{
EMP e;
printf("Enter SSN: ");
scanf("%s",e.ssn);
printf("Enter Name: ");
scanf("%s",e.name);
printf("Enter dept: ");
scanf("%s",e.dept);
printf("Enter Designation :");
scanf("%s",e.design);
printf("Enter Salary:");
scanf("%d",&e.salary);
printf("Enter Phone no : ");
scanf("%llu",&e.phno);
return e;
}
int main()
{

EMP e;
int i, ch, n;
first=NULL;
while(1)
{
printf("\nList Operations\n");
printf("===============\n");
printf("1.Create a DLL of N Employees Data by using end insertion\n");
printf("2.Display the status of DLL and count the number of nodes in it\n");
printf("3.Perform Insertion and Deletion at End of DLL\n");
printf("4.Perform Insertion and Deletion at Front of DLL\n");
printf("5.Demonstration of this DLL as Double Ended Queue\n");
printf("6.Exit\n");
printf("Enter your choice : ");
scanf("%d",&i);
switch(i)
{
case 1 :
printf("Enter the number of Employees\n");
scanf("%d",&n);

35
for(i=1;i<=n;i++)
{
printf("\nEnter the details of Employee %d\n",i);
e=input();
addrear(e);
}
break;
case 2 :
if(first==NULL)
{
printf("List is Empty\n");
}
else
{
printf(" Node Count=%d\t & Elements in the list are : \n", count());
displayList();
}
break;
case 3 :
printf(" 1. Insert at End and 2 Delete From End=");
scanf("%d",&ch);
if(ch==1)
{
e=input();
addrear(e);
}
else if(ch==2)
deleterear();
else
printf(" Sorry wrong operation\n");
break;

case 4 :
printf(" 1. Insert at Front and 2 Delete From Front=");
scanf("%d",&ch);
if(ch==1)
{

36
 e=input();
addfront(e);
}
else if(ch==2)
deletefront();
else
printf(" Sorry wrong operation\n");
break;
case 5:printf("This DLL can be used as Double Ended Queue by inserting and deleting from
both ends \n");
break;
case 6 : exit(0);
default : printf("Invalid option\n");
}
}
return 0;
}
Output:

List Operations
===============
1. Create a DLL of N Employees Data by using end insertion
2.Display the status of DLL and count the number of nodes in it
3.Perform Insertion and Deletion at End of DLL
4.Perform Insertion and Deletion at Front of DLL
5.Demonstration of this DLL as Double Ended Queue
6.Exit
Enter your choice : 1
Enter the number of Employees 2
Enter the details of Employee 1
Enter SSN: 111
Enter Name: Ram
Enter dept: Sales
Enter Designation :Manager
Enter Salary:50000
Enter Phone no : 9141000000

Enter the details of Employee 2

Enter SSN: 222
Enter Name: Sham
Enter dept: Design
Enter Designation :Manager
37
Enter Salary:60000
Enter Phone no : 9876543210

List Operations
===============
1.Create a DLL of N Employees Data by using end insertion
2.Display the status of DLL and count the number of nodes in it
3.Perform Insertion and Deletion at End of DLL
4.Perform Insertion and Deletion at Front of DLL
5.Demonstration of this DLL as Double Ended Queue
6.Exit
Enter your choice : 2
Node Count=2 & Elements in the list are :

SSN Name Dept Designation salary Phone

111 Ram Sales Manager 50000 9141000000
222 Sham Design Manager 60000 9876543210

List Operations
===============
1.Create a DLL of N Employees Data by using end insertion
2.Display the status of DLL and count the number of nodes in it
3.Perform Insertion and Deletion at End of DLL
4.Perform Insertion and Deletion at Front of DLL
5.Demonstration of this DLL as Double Ended Queue
6.Exit
Enter your choice : 3
1. Insert at End and 2 Delete From End=1
Enter SSN: 333
Enter Name: Ravi
Enter dept: Finance
Enter Designation :Manager
Enter Salary:65000
Enter Phone no : 9876500000

List Operations
===============
1.Create a DLL of N Employees Data by using end insertion
2.Display the status of DLL and count the number of nodes in it
3.Perform Insertion and Deletion at End of DLL
4.Perform Insertion and Deletion at Front of DLL
5.Demonstration of this DLL as Double Ended Queue
38
6.Exit
Enter your choice : 2
Node Count=3 & Elements in the list are :
SSN Name Dept Designation salary Phone
111 Ram Sales Manager 50000 9141000000
222 Sham Design Manager 60000 9876543210
333 Ravi Finance Manager 65000 9876500000

List Operations
===============
1.Create a DLL of N Employees Data by using end insertion
2.Display the status of DLL and count the number of nodes in it
3.Perform Insertion and Deletion at End of DLL
4.Perform Insertion and Deletion at Front of DLL
5.Demonstration of this DLL as Double Ended Queue
6.Exit
Enter your choice : 4
1. Insert at Front and 2 Delete From Front=2
SSN Name Dept Designation Salary Phone
111 Ram Sales Manager 50000 9141000000
List Operations
===============
1.Create a DLL of N Employees Data by using end insertion
2.Display the status of DLL and count the number of nodes in it
3.Perform Insertion and Deletion at End of DLL
4.Perform Insertion and Deletion at Front of DLL
5.Demonstration of this DLL as Double Ended Queue
6.Exit
Enter your choice : 2
Node Count=2 & Elements in the list are :
SSN Name Dept Designation salary Phone
222 Sham Design Manager 60000 9876543210
333 Ravi Finance Manager 65000 9876500000
List Operations
===============
1.Create a DLL of N Employees Data by using end insertion
2.Display the status of DLL and count the number of nodes in it
3.Perform Insertion and Deletion at End of DLL

39
4.Perform Insertion and Deletion at Front of DLL
5.Demonstration of this DLL as Double Ended Queue
6.Exit
Enter your choice : 5
This DLL can be used as Double Ended Queue by inserting and deleting from both ends
List Operations
===============
1. Create a DLL of N Employees Data by using end insertion
2. Display the status of DLL and count the number of nodes in it
3. .Perform Insertion and Deletion at End of DLL
4. Perform Insertion and Deletion at Front of DLL
5. Demonstration of this DLL as Double Ended Queue
6.Exit
Enter your choice : 6

40
Program 9:
Develop a Program in C for the following operations on Singly Circular Linked
List(SCLL) with header nodes
a. Represent and Evaluate a Polynomial P(x,y,z) = 6x2y2z-4yz5+3x3yz+2xy5z-2xyz3
b. Find the sum of two polynomials POLY1(x,y,z) and POLY2(x,y,z) and store
theresult in POLYSUM(x,y,z).
Support the program with appropriate functions for each of the above operations.
Implementation:
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int coef,px,py,pz, x,y,z,i;
int val;
struct node
{
int coef,px, py,pz;
struct node *next;
};
typedef struct node NODE;
NODE *first;
void insert(int coef,int px, int py, int pz)
{
NODE *temp,*cur;
temp= (NODE *)malloc(sizeof(NODE));
temp->coef=coef;
temp->px=px;
temp->py=py;
temp->pz=pz;
if(first==NULL
)
{
temp->next=temp;
first=temp;
return;
}
if(first->next==first)
{
first->next=temp;
temp->next=first;
}
cur=first;
while(cur->next!=first)
{
cur=cur->next;
}
cur->next=temp;
temp->next=first;
return;

41
}
void display()
{
NODE *cur;
if(first==NULL
)
{
printf("List is empty\n");
return;
}
cur=first;
while(cur->next!=first)
{
printf("%d ",cur->coef);
printf(" x^%d",cur->px);
printf(" y^%d",cur->py);
printf(" z^%d + ",cur->pz);
cur=cur->next;
}
printf("%d ",cur->coef);
printf(" x^%d",cur->px);
printf(" y^%d",cur->py);
printf(" z^%d\n",cur->pz);
return;
}
int evaluate(int x, int y, int z)
{
NODE *cur; int v,s=0, v1,v2,v3;
if(first==NULL)
{
printf("List is empty\n");
return 0;
}
cur=first;
while(cur->next!=first)
{
v=cur->coef*pow(x, cur->px)*pow(y, cur->py)*pow(z,cur->pz);
s=s+v;
cur=cur->next;
}
v=cur->coef*pow(x, cur->px)*pow(y, cur->py)*pow(z,cur->pz);
s=s+v;
return s;
}
int main()
{
int coef,px,py,pz,
x,y,z,i;
int val;
first=NULL;
while(1)

42
 {
printf("1. Insert polynomial at end\n");
printf("2. Display\n");
printf("3. Evaluate\n");
printf("4. Exit\n");
printf("Enter Choice= \t");
scanf("%d",&i);
switch(i)
{
case 1 : printf("Enter Coefficient= \t");
scanf("%d",&coef);
printf("Enter powers of x y z values= \t");
scanf("%d%d%d",&px, &py,&pz);
insert(coef,px,py,pz);
break;
case 2 : display();
break;
case 3 :
printf("\n Enter x y & z values for evaluation: \t");
scanf("%d%d%d",&x,&y,&z);
val=evaluate(x,y,z);
printf("\nValue=%d\n",val)
;break;
case 4 : return 0;
default : printf(" Wrong choice. Enter 1,2 3\n");
break;
}
}
}

Output:
1. Insert polynomial at end
2. Display
3. Evaluate
4. Exit
Enter Choice= 1
Enter Coefficient= 4
Enter powers of x y z values= 3 3 2
1. Insert polynomial at end
2. Display
3. Evaluate
4. Exit
Enter Choice= 1
Enter Coefficient= 5
Enter powers of x y z values= 3 2 2
1. Insert polynomial at end
43
2. Display
3. Evaluate
4. Exit
Enter Choice= 1
Enter Coefficient= 3
Enter powers of x y z values= 2 2 2
1. Insert polynomial at end
2. Display
3. Evaluate
4. Exit
Enter Choice= 1
Enter Coefficient= 6
Enter powers of x y z values= 1 1 1

1. Insert polynomial at end

2. Display
3. Evaluate
4. Exit
Enter Choice= 2
4 x^3 y^3 z^2 + 5 x^3 y^2 z^2 + 3 x^2 y^2 z^2 + 6 x^1 y^1 z^1
1. Insert polynomial at end
2. Display
3. Evaluate
4. Exit
Enter Choice= 3

Enter x y & z values for evaluation: 3 2

1Value=1548
1. Insert polynomial at end
2. Display
3. Evaluate
4. Exit
Enter Choice= 4

44
Program 9B
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
struct node //Defining Polynomial fields
{
int coef, px, py, pz,flag;
struct node *link;
};
typedef struct node * NODE;
NODE create_list(NODE head) //For creating poly1 & poly2
{
int i,n,cf,px,py,pz;
printf("Enter the number of terms : ");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
printf("Enter the Co-ef, px, py, pz : ");
scanf("%d %d %d %d",&cf,&px,&py,&pz);
insert(head,cf,px,py,pz);
}
return head;
} /*End of create_list()*/
insert(NODE head,int cof,int x,int y, int z) //inserting term to poly
{
NODE cur,tmp;
tmp= (NODE)malloc(sizeof(struct node)); //Allocates memory int cf,px,py,pz;
cur=head->link;
tmp->coef=cof;
tmp->px=x;
tmp->py=y;
tmp->pz=z;
tmp->flag=0;
while(cur->link!=head) //Identifying last node
cur=cur->link;
cur->link=tmp;
tmp->link=head;
}
NODE add_poly(NODE h1,NODE h2,NODE h3)
{
NODE cur1,cur2,scf; cur1=h1->link; cur2=h2->link;
while(cur1 != h1) //Till end of poly1
{
if(cur2 == h2)
cur2=h2->link;
while(cur2 != h2) //Till end of poly2
{
if(cur1->px == cur2->px && cur1->py == cur2->py && cur1->pz == cur2->pz)
{ //Add & insert if co-ef's of both poly is equal
scf = cur1->coef + cur2->coef;
insert(h3,scf,cur1->px,cur1->py,cur1->pz);
45
cur2->flag=1;
cur2=h2->link;
break;
}
cur2=cur2->link;
}
if(cur1 == h1)
break;
if(cur2 == h2) //If co-ef of poly1 is not matched, insert it to poly3
insert(h3,cur1->coef,cur1->px,cur1->py,cur1->pz);
cur1=cur1->link;
}
cur2=h2->link;
while(cur2 != h2) //remaining poly2 nodes inserted to poly3
{
if(cur2->flag==0)
insert(h3,cur2->coef,cur2->px,cur2->py,cur2->pz);
cur2=cur2->link;
}
return h3;
}

void display(NODE head)

{
NODE cur;
if(head->link==head) //if poly is empty
{
printf("List is empty\n");
return;
}
cur=head->link;
while(cur != head) //display all terms till end
{
if(cur->coef > 0)
printf(" +%dx^%dy^%dz^%d ",cur->coef,cur->px,cur->py,cur->pz);
else if (cur->coef < 0)
printf(" %dx^%dy^%dz^%d ",cur->coef,cur->px,cur->py,cur->pz);
cur=cur->link;
}
printf("\n");
}/*End of display() */

46
 void main()
{
int choice,data,item,pos; NODE head1,head2,head3;
head1=(NODE)malloc(sizeof(struct node));
head1->link=head1; //poly1
head2=(NODE)malloc(sizeof(struct node));
head2->link=head2; //poly2
head3=(NODE)malloc(sizeof(struct node));
head3->link=head3; //poly3
printf("\n1.Create Polynomial 1\n");
head1=create_list(head1);
printf("\n2.Create Polynomial 2\n");
head2=create_list(head2);
printf("\nPolynomial 1 is :");
display(head1);
printf("\nPolynomial 2 is :");
display(head2);
head3=add_poly(head1,head2,head3); //Add both polynomials
printf("\nAddition of two Polynomial is :");
display(head3);
}

Output:

1. Create Polynomial 1

Enter the number of terms : 4

Enter the Co-ef, px, py, pz : 5 3 3 3
Enter the Co-ef, px, py, pz : 6 3 3 2
Enter the Co-ef, px, py, pz : 8 2 2 2
Enter the Co-ef, px, py, pz : 9 1 0 1

2. Create Polynomial 2

Enter the number of terms : 4

Enter the Co-ef, px, py, pz : 6 3 3 3
Enter the Co-ef, px, py, pz : 5 2 2 2
Enter the Co-ef, px, py, pz : 8 2 1 2
Enter the Co-ef, px, py, pz : 9 1 1 0

Polynomial 1 is : +5x^3y^3z^3 +6x^3y^3z^2 +8x^2y^2z^2 +9x^1y^0z^1

Polynomial 2 is : +6x^3y^3z^3 +5x^2y^2z^2 +8x^2y^1z^2 +9x^1y^1z^0
Addition of two Polynomial is :
+6x^3y^3z^2 +9x^1y^0z^1 +6x^3y^3z^3 +5x^2y^2z^2 +8x^2y^1z^2 +9x^1y^1z^0

47
Program 10:
Develop a menu driven Program in C for the following operations on Binary Search
Tree (BST)of Integers .
a. Create a BST of N Integers: 6, 9, 5, 2, 8, 15, 24, 14, 7, 8, 5, 2
b. Traverse the BST in Inorder, Preorder and Post Order
c. Search the BST for a given element (KEY) and report the appropriate message
d. Exit
Implementation:
#include <stdio.h>
#include <stdlib.h>
struct BST
{
int data;
struct BST *left;
struct BST *right;
};
typedef struct BST NODE;
NODE *node;
NODE * createtree(NODE *node,int data)
{
if (node == NULL)
{
NODE *temp;
temp= (NODE*)malloc(sizeof(NODE));
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
if(data<(node->data))
{
node->left=createtree(node->left, data);
}
else if(data>node->data)
{
node -> right = createtree(node->right, data);
}
return node;
}

NODE* search(NODE *node, int data)

{
if(node == NULL)
printf("\nElement not found");
else if(data < node->data)
{
node->left=search(node->left, data);
}
 else if(data > node->data)
{
node->right=search(node->right, data);
}
else
printf("\nElement found is: %d", node->data);
return node;
}

void inorder(NODE *node)

{
if(node != NULL)
{
inorder(node->left);
printf("%d\t", node->data);
inorder(node->right);
}
}

void preorder(NODE *node)

{
if(node!=NULL)
{
printf("%d\t", node->data);
preorder(node->left);
preorder(node->right);
}
}

void postorder(NODE *node)

{
if(node != NULL)
{
postorder(node->left);
postorder(node->right);
printf("%d\t", node->data);
}
}

void main()
{
int data, ch, i, n;
NODE *root=NULL;
clrscr();
while (1)
{
printf("\n1.Insertion in Binary Search Tree");
printf("\n2.Search Element in Binary Search Tree");
 printf("\n3.Inorder\n4.Preorder\n5.Postorder\n6.Exit");
printf("\nEnter your choice: ");
scanf("%d", &ch);
switch (ch)
{
case 1: printf("\nEnter N value: " );
scanf("%d", &n);
printf("\nEnter the values to create BST \n");
for(i=0;i<n;i++)
{
scanf("%d", &data);
root=createtree(root, data);
}
break;

case 2:printf("\nEnter the element to search: ");

scanf("%d", &data);
root=search(root, data);
break;

case 3:printf("\nInorder Traversal: \n");

inorder(root);
break;
case 4:printf("\nPreorder Traversal: \n");
preorder(root);
break;
case 5:printf("\nPostorder Traversal: \n");
postorder(root);
break;
case 6:exit(0);

default:printf("\nWrong option");
break;

}
}
}
Output:
Program 11:

Design, develop and implement a Program in C for the following operations on Graph
(G) of Cities Create a Graph of N cities using Adjacency Matrix. Print all the nodes
reachable from agiven starting node in a digraph using BFS method
//Implementation:
#include<stdio.h>
#include<stdlib.h>
int n, a[10][10],i,j,source,s[10],choice,count;
void bfs(int n,int a[10][10],int source,int s[]) //BFS Algorithm
{
int q[10],u;
int front=1,rear=1;
s[source]=1;
q[rear]=source;
while(front<=rear)
{
u=q[front];
front=front+1;
for(i=1;i<=n;i++)
if(a[u][i]==1 && s[i]==0)
{
rear=rear+1;
q[rear]=i;
s[i]=1;
}
}
}
int main()
{
printf("Enter the number of nodes : ");
scanf("%d",&n);
printf("\n Enter the adjacency matrix\n");
for(i=1;i<=n;i++) //Provide matrix of 0’s and 1’s
for (j=1;j<=n;j++)
scanf("%d",&a[i][j]);
while(1)
{
printf("\nEnter your choice\n");
printf("1.BFS\n 2.Exit\n");
scanf("%d",&choice);
switch(choice)
{
case 1: printf("\n Enter the source :");
scanf("%d",&source); //Provide source for BFS
for(i=1;i<=n;i++)
s[i]=0;
bfs(n,a,source,s);
for(i=1;i<=n;i++)
 {
if(s[i]==0)
printf("\n The node %d is not reachable",i);
else
printf("\n The node %d is reachable",i);
}
break;
case 2:
exit(0);
}
}
}
Output:
Enter the number of nodes : 5
Enter the adjacency matrix
01010
00100
10000
00100
00110

Enter your choice 1.BFS

2. Exit
1
Enter the source : 5

The node 1 is reachable

The node 2 is reachable
The node 3 is reachable
The node 4 is reachable
The node 5 is reachable
 PROGRAM 12:

Given a File of N employee records with a set K of Keys (4-digit) which uniquely
determine the records in file F. Assume that file F is maintained in memory by a Hash
Table (HT) of m memory locations with L as the set of memory addresses (2-digit) of
locations in HT. Let the keys in K andaddresses in L are Integers.

Develop a Program in C that uses Hash function H: K →L as H(K)=K mod m

(remainder method), and implement hashing technique to map a given key K to the
address space L. Resolve the collision (if any) using linear probing.
//Implementation
#include <stdio.h>
#define m 5
int HT[10];
int hash(int key)
{
return key%m;
}
void linear_probe(int hk,int key)
{
int i,flag=0;
for (i=hk+1;i<m;i++)
{
if (HT[i]==999)
{
HT[i]=key;
flag=1;
break;
}
for(i=0;i<hk&&flag==0;i++)
{
if (HT[i]==999)
{
HT[i]=key;
flag=1;
break;
}
}
if (!flag)
printf("HASH Table is Full!!!\n");
}
}
void main()
{
FILE *fp;

int N,i,key,hk;
char name[100];
clrscr();
for (i=0;i<m;i++)
HT[i]=999;
fp=fopen("emp.txt","r");
while(!feof(fp))
{
fscanf(fp,"%d%s",&key,name);
hk=hash(key);
if (HT[hk]==999)
HT[hk]=key;
else
{
printf("Collision for key %d:\n",key);
printf("Collision solved by Linear Probing\n\n");
linear_probe(hk,key);
}
}
printf("-------------------------------\n");
printf("HASH TABLE\n");
printf("-------------------------------\n");
printf("Address\tKeys\n");
for (i=0;i<m;i++)
printf("%d\t%d\n",i,HT[i]);
getch();
}

Output :
Create one text file emp.txt
Enter empid and name in below format

111 abc
222 ccc
122 ddf
123 dfr
 VIVA QUESTIONS AND ANSWERS

1) What is data structure?

Data structures refers to the way data is organized and manipulated. It seeks to find ways to
make data access more efficient. When dealing with data structure, we not only focus on one
piece of data, but rather different set of data and how they can relate to one another in an
organized manner.
2) Differentiate file structure from storage structure.
Basically, the key difference is the memory area that is being accessed. When dealing with the
structure that resides the main memory of the computer system, this is referred to as storage
structure. When dealing with an auxiliary structure, we refer to it as file structures.
3) When is a binary search best applied?
A binary search is an algorithm that is best applied to search a list when the elements are
already in order or sorted. The list is search starting in the middle, such that if that middle value
is not thetarget search key, it will check to see if it will continue the search on the lower half of
the list or the higher half. The split and search will then continue in the same manner.
4) What is a linked list?
A linked list is a sequence of nodes in which each node is connected to the node following it.
This forms a chain-like link of data storage.
5) How do you reference all the elements in a one-dimension array?
To do this, an indexed loop is used, such that the counter runs from 0 to the array size minus
one. In this manner, we are able to reference all the elements in sequence by using the loop
counter asthe array subscript.
6) In what areas do data structures applied?
Data structures is important in almost every aspect where data is involved. In general,
algorithms that involve efficient data structure is applied in the following areas: numerical
analysis, operating system, A.I., compiler design, database management, graphics, and
statistical analysis, to name a few.
7) What is LIFO?
LIFO is short for Last In First Out, and refers to how data is accessed, stored and retrieved.
Using this scheme, data that was stored last , should be the one to be extracted first. This also
means that in order to gain access to the first data, all the other data that was stored before this
first data must first be retrieved and extracted.
8 ) What is a queue?
A queue is a data structures that can simulates a list or stream of data. In this structure, new
elements are inserted at one end and existing elements are removed from the other end.
9) What are binary trees?
A binary tree is one type of data structure that has two nodes, a left node and a right node. In
programming, binary trees are actually an extension of the linked list structures.
10) Which data structures is applied when dealing with a recursive function?
Recursion, which is basically a function that calls itself based on a terminating condition,
makes use of the stack. Using LIFO, a call to a recursive function saves the return address so
that it knows how to return to the calling function after the call terminates.
11) What is a stack?
A stack is a data structure in which only the top element can be accessed. As data is stored in
the stack, each data is pushed downward, leaving the most recently added data on top.
12) Explain Binary Search Tree
A binary search tree stores data in such a way that they can be retrieved very efficiently. The
left subtree contains nodes whose keys are less than the node‟s key value, while the right
subtree contains nodes whose keys are greater than or equal to the node‟s key value. Moreover,
both subtrees are also binary search trees
13) What are multidimensional arrays?
Multidimensional arrays make use of multiple indexes to store data. It is useful when storing
data that cannot be represented using a single dimensional indexing, such as data representation
in a board game, tables with data stored in more than one column.
14) Are linked lists considered linear or non-linear data structures?
It actually depends on where you intend to apply linked lists. If you based it on storage, a linked
list is considered non-linear. On the other hand, if you based it on access strategies, then a
linked list is considered linear.
15) How does dynamic memory allocation help in managing data?
Aside from being able to store simple structured data types, dynamic memory allocation can
combine separately allocated structured blocks to form composite structures that expand and
contract as needed.
16) What is FIFO?
FIFO is short for First-in, First-out, and is used to represent how data is accessed in a queue.
Data has been inserted into the queue list the longest is the one that is removed first.
17) What is an ordered list?
An ordered list is a list in which each node‟s position in the list is determined by the value of
its key component, so that the key values form an increasing sequence, as the list is traversed.
18) What is merge sort?
Merge sort takes a divide-and-conquer approach to sorting data. In a sequence of data, adjacent
ones are merged and sorted to create bigger sorted lists. These sorted lists are then merged
again to form an even bigger sorted list, which continuous until you have one single sorted list.
19) Differentiate NULL and VOID.
Null is actually a value, whereas Void is a data type identifier. A variable that is given a Null
value simply indicates an empty value. Void is used to identify pointers as having no initial
size.
20) What is the primary advantage of a linked list?
A linked list is a very ideal data structure because it can be modified easily. This means that
modifying a linked list works regardless of how many elements are in the list.
21) What is the difference between a PUSH and a POP?
A push denotes data being added to it, meaning data is being “pushed” into the stack. On the
other hand, a pop denotes data retrieval, and in particular refers to the topmost data being
accessed.
22) What is a linear search?
A linear search refers to the way a target key is being searched in a sequential data structure.
Using this method, each element in the list is checked and compared against the target key, and
is repeated until found or if the end of the list has been reached.
23) How does variable declaration affect memory allocation?
The amount of memory to be allocated or reserved would depend on the data type of the
variable being declared. For example, if a variable is declared to be of integer type, then 32 bits
of memory storage will be reserved for that variable.
24) What is the advantage of the heap over a stack?
Basically, the heap is more flexible than the stack. That‟s because memory space for the
heap can be dynamically allocated and de-allocated as needed. However, memory of the heap
can at times be slower when compared to that stack.
25) What is a postfix expression?
A postfix expression is an expression in which each operator follows its operands. The
advantage of this form is that there is no need to group sub-expressions in parentheses or to
consider operator precedence.
26) What is a balanced tree?
A binary tree is balanced if the depth of two subtrees of every node never differ by more than
one)
27). Which data structure is needed to convert infix notations to post fix notations?
Stack
27). What is data structure or how would you define data structure?
In programming the term data structure refers to a scheme for organizing related piece of
information. Data Structure = Organized Data + Allowed Operations.)
28. Which data structures we can implement using link list?
Queue and Stack
29. List different types of data structures?
Link list, queue, stack, trees, files, graphs
30) What is Hashing
Hashing is a technique to convert a range of key values into a range of indexes of an array.