DATA STRUCTURES WITH C

LABORATORY
MYSORE COLLEGE OF ENGINEERING AND MANAGEMENT

DATA STRUCTURE USING C (BEC456D)

LAB MANUAL

Course Syllabi with CO’s

Faculty Name : Divyashree. G Academic Year: 2023-24
Department: ECE

Contact Total
Course Core/Electiv Hours
Course Title Prerequisite Hrs/
Code e
L T P Sessions
DATA Programming with C
STRUCTURE 13
21EC584 S CORE 3
LABORATOR
Y
This laboratory course enable students to get practical experience in design, develop,
implement,
analyze and evaluation/testing of
Objectives • Asymptotic performance of algorithms.
• 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
Laboratory Experiments Covered as per Syllabus
1. Design, Develop and Implement a menu driven Program in C for the following
Array operations
a. Creating an Array of N Integer Elements
b. Display of Array Elements with Suitable Headings
c. Inserting an Element (ELEM) at a given valid Position (POS)
d. Deleting an Element at a given valid Position(POS)
e. Exit.
Support the program with functions for each of the above operations.

2. Design, Develop and Implement a Program in C for the following operations on Strings
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. Design, Develop and Implement 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
DIVYASHREE.G Assistant Professor dept of ECE, MyCEM Page 1
 DATA STRUCTURES WITH C
LABORATORY
Support the program with appropriate functions for each of the above operations

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.
5. Design, Develop and Implement a Program in C for the following Stack
Applications
a. Evaluation of Suffix expression with single digit operands and operators: +, -, *, /, %, ^
b. Solving Tower of Hanoi problem with n disks

6. Design, Develop and Implement 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 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
Support the program with appropriate functions for each of the above operations

7. Design, Develop and Implement a menu driven Program in C for the following operations on
Singly Linked List (SLL) of Student Data with the fields: USN, Name, Branch, 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

8. Design, Develop and Implement 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

9. Design, Develop and Implement 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 the result in
POLYSUM(x,y,z)
Support the program with appropriate functions for each of the above operations

10. Design, Develop and Implement 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
e. Exit

DIVYASHREE.G Assistant Professor dept of ECE, MyCEM Page 2

 DATA STRUCTURES WITH C
LABORATORY
11. Design, Develop and Implement a Program in C for the following operations on Graph(G)
of 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. Design
and 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.
On the completion of this laboratory course, the students will be able to:
• Analyze and Compare various linear and non-linear data structures
Course • Code, debug and demonstrate the working nature of different types of data structures and
Outcomes their applications
• Implement, analyze and evaluate the searching and sorting algorithms
• Choose the appropriate data structure for solving real world problems

DIVYASHREE.G Assistant Professor dept of ECE, MyCEM Page 3

 DATA STRUCTURES WITH C++ LABORATORY

DATA STRUCTURES

Data Structures:
The logical or mathematical model of a particular organization of data is called data
structures. Data structures is the study of logical relationship existing between individualdata
elements, the way the data is organized in the memory and the efficient way of storing, accessing
and manipulating the data elements.

Choice of a particular data model depends on two considerations: it must be rich enough in
structure to mirror the actual relationships of the data in the real world. On the other hand, the
structure should be simple enough that one can effectively process the data when necessary.

Data Structures can be classified as:

1. Primitive datastructures
2. Non-Primitive data
structures.

Primitive data structures are the basic data structures that can be directly
manipulated/operated by machine instructions. Some of these are character, integer, real, pointers
etc.

Non-primitive data structures are derived from primitive data structures, they cannot be
directly manipulated/operated by machine instructions, and these are group of homogeneous or
heterogeneous data items. Some of these are Arrays, stacks, queues, trees,graphs etc.

Data structures are also classified as

Linear data structures
Non-Linear data structures.

In the Linear data structures processing of data items is possible in linear fashion, i.e., datacan
be processed one by one sequentially.
Example of such data structures are:
Array
Linked list
Stacks
Queues
A data structure in which insertion and deletion is not possible in a linear fashion is called
as non linear data structure. i.e., which does not show the relationship of logical adjacency between
the elements is called as non-linear data structure. Such as trees, graphsand files.

DIVYASHREE.G Assistant Professor dept of ECE, MyCEM Page 4

 DATA STRUCTURES WITH C++ LABORATORY

1. Design, Develop and Implement a menu driven program in c for the followingArray operations,
a. Creating an Array of N integer elements.
b. Display of Array elements with suitable headings.
c. Inserting an element (ele) at a given valid position(pos).
d. Deleting an element at a given valid position (pos).
e. Exit.
Support the program with functions for each of the above operations.

#include<stdio.h>
#include<conio.h>
int n,a[50];

void create()
{
int i;
printf("enter the value of n\n");
scanf("%d",&n);
printf("enter %d array elements\n",n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
}

void display()
{
int i;
printf("entered elements are\n");
for(i=0;i<n;i++) printf("%d\n",a[i]);
}

void insertion()
{
int i,POS,ELEM;
printf("enter the position and its value\n");
scanf("%d%d",&POS,&ELEM);
for(i=n;i>=POS;i--)
a[i]=a[i-1];
a[POS]=ELEM;
n=n+1;
display();
}

void deletion()
{
int i,POS,ELEM;
printf("enter the position to be deleted\n");
scanf("%d",&POS);
ELEM=a[POS];
for(i=POS;i<=n-1;i++)
a[i]=a[i+1];
printf("the deleated element is %d\n",ELEM);
n=n-1;
display();
}

DIVYASHREE.G Assistant Professor dept of ECE, MyCEM Page 5

 DATA STRUCTURES WITH C++ LABORATORY
void main()
{
int ch;
while(1)
{
printf("enter your choice\n");
printf("1.creat\n2.display\n3.insertion\n4.deletion\n5.exit\n");
scanf("%d",&ch);
switch(ch)
{
case 1: create();
break;
case 2: display();
break;
case 3: insertion();
break;
case 4: deletion();
break;
case 5: exit(0);
}
}
}

DIVYASHREE.G Assistant Professor dept of ECE, MyCEM Page 6

 DATA STRUCTURES WITH C++ LABORATORY

2. Design, Develop and Implement a program in c for the following operations onstrings
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 ofpat in str with rep if
pat exits in str. Report with suitable messages in case pat does not exists in str.
Support the program with functions for each of the above operations. Don’t usebuilt in functions.

#include<stdio.h>
char STR[100],PAT[100],REP[100],ANS[100];
int i,j,c,m,k,flag=0;
void read()
{
printf("\n Enter MAIN string:\n");
gets(STR);
printf("\n Entre PATTERN string:\n");
gets(PAT);
printf("\n Enter REPLACE string\n");
gets(REP);
}

void replace()
{
i=m=c=j=0;
while(STR[c]!='\0')
{
if(STR[m]==PAT[i])
{
i++;m++;
if(PAT[i]=='\0')
{
for(k=0;REP[k]!='\0';k++,j++)
ANS[j]=REP[k];
i=0;
c=m;flag=1;
}
}
else
{
ANS[j]=STR[c];
j++;c++;m=c;i=0;
}
}
if(flag==0)
printf("pattern doesen't found!!!\n");
else
{
ANS[j]='\0';
printf("\n the RESULTANT string\n is %s \n",ANS);
}
}

void main()
{
clrscr();
read();
replace();
getch();

DIVYASHREE.G Assistant Professor dept of ECE, MyCEM Page 7

 DATA STRUCTURES WITH C++ LABORATORY

3. Design, Develop and Implement a menu driven program in c for the following operations on STACK of
integers(Array implementation of stack with maximumsize MAX)
a. Push an element onto the stack.
b. Pop an element from the stack.
c. Demonstrate how stack can be used to check palindrome.
d. Demonstrate overflow and underflow situations on stack.
e. Display the status of the stack.
f. Exit
Support the program with appropriate functions for each of the aboveoperations.

#include<stdio.h>
#include<conio.h>
#include<math.h>
#define max 5
int s[max],stop;
int ele,st[max],sp,ch;

void push(int ele,int s[],int *stop)

{
if(*stop>=max-1)
printf("stock overflow\n");
else
s[++*stop]=ele;
}

int pop(int s[],int *top)

{
if(*top==-1)
{
printf("stock empty\underflow\n");
return 0;
}
else return(s[(*top)--]);
}

void palindrome(int ele,int st[])

{
int rem,rev=0,temp=ele,i=0;
while(temp!=0)
{
rem=temp%10;
push(rem,st,&sp);
temp=temp/10;
}
while(sp!=-1)
rev=rev+(pop(st,&sp)*pow(10,i++));
if(ele==rev)
printf("palendrome\n");
else
printf("not a palindrome\n");

DIVYASHREE.G Assistant Professor dept of ECE, MyCEM Page 8

 DATA STRUCTURES WITH C++ LABORATORY
}

void display(int s[],int *stop)

{
int i; if(*stop==-
1)
printf("stalk is empty\n");
else
for(i=*stop;i>-1;i--)
printf("%d\n",s[i]);
}

void main()
{
stop= -1;
sp= -1;

while(1)
{
printf("enter tne choice\n");
printf("enter 1 to insert an element into the STACK\n");
printf("enter 2 to delete an element from the STACK\n");
printf("enter 3 to check an element is palindrome or not\n");
printf("enter 4 to check the status of the STACK\n");
printf("enter 5 to exit\n");
scanf("%d",&ch);
switch(ch)
{
case 1:printf("enter the elements to de inserted to STACK\n");
scanf("%d",&ele);
push(ele,s,&stop);
break;
case 2:ele=pop(s,&stop);
if(ele!=0)
printf("element poped is %d\n",ele);break;
case 3:printf("enter the elements to chech weather it is a palindrome\n");
scanf("%d",&ele);
palindrome(ele,st);
break;
case 4:printf("the status of the STACK \n");
display(s,&stop);
break;
case5:exit(0
);
}
}
}

DIVYASHREE.G Assistant Professor dept of ECE, MyCEM Page 9

 DATA STRUCTURES WITH C++ LABORATORY
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.

#include<stdio.h>
#include<conio.h>
#include<string.h>
int F(char symbol)
{
switch(symbol)
{
case '+':
case '-':return 2;case
'*':
case '%':
case '/':return 4;case
'^':
case '$':return 5;
case '(':return 0;
case '#':return -1;
default :return 8;
}
}
int G(char symbol)
{
switch(symbol)
{
case '+':
case '-':return 1;case
'*':
case '%':
case '/':return 3;case
'^':
case '$':return 6;
case '(':return 9;
case ')':return 0;
default :return 7;
}
}
void infix_postfix(char infix[],char postfix[])
{
int top,i,j; char
s[30]; char
symbol; top=-1;
s[++top]='#';j=0;
for(i=0;i<strlen(infix);i++)
{
symbol=infix[i];
while(F(s[top])>G(symbol))
postfix[j++]=s[top--];

if(F(s[top])!=G(symbol))
s[++top]=symbol;
else top--;

DIVYASHREE.G Assistant Professor dept of ECE, MyCEM Page 10

 DATA STRUCTURES WITH C++ LABORATORY
}

while(s[top]!='#')
postfix[j++]=s[top--];

postfix[j]='\0';
}

void main()
{
char infix[20]; char
postfix[20];
printf("enter a valid infix expression\n");
scanf("%s",infix);
infix_postfix(infix,postfix);
printf("the postfix expression is\n");
printf("%s\n",postfix);

DIVYASHREE.G Assistant Professor dept of ECE, MyCEM Page 11

 DATA STRUCTURES WITH C++ LABORATORY
5. Design, develop, and implement a program in C for the following stackapplications
a. Evaluation of suffix expression with single digit operands and operators:
+, - , *, /, % , ^
b. Solving Tower of Hanoi problem with n disks.

#include<stdio.h>
#include<string.h>
#include<math.h>
int count=0, top=-1;
int operate(char symb, int op1, int op2)
{
switch(symb)
{
case '+':return op1+op2; case '-
':return op1-op2; case '/':return
op1/op2; case '*':return op1*op2;
case '%':return op1%op2;
case '^':return pow(op1,op2);
}
}
void push(int stack[],int d)
{
stack[++top]=d;
}
int pop(int stack[])
{
return(stack[top--]);
}
void tower( int n,char src, char intr, char des)
{
if(n)
{
tower(n-1,src,des,intr);
printf("disk %d moved from %c to %c\n",n,src,des);
count++;
tower(n-1,intr,src,des);
}
}

void main()
{
int n, choice,i,op1,op2,ans,stack[50];char
expr[20],symb;
while(1)
{
printf("\nprogram to perform evaluation of suffix expression and tower ofhanoi problem\n");
printf("\n1.evaluate suffix expression\n2.Tower of hanoi\n3.Exit\n ");
printf("\nenter the choice\n");
scanf("%d",&choice);
switch(choice)
{
case 1: printf("enter the suffix expression : ");
scanf("%s",expr);
for(i=0;expr[i]!= '\0';i++)

DIVYASHREE.G Assistant Professor dept of ECE, MyCEM Page 12

 DATA STRUCTURES WITH C++ LABORATORY
{
symb=expr[i];
if(symb>='0' && symb<='9')
push(stack, symb-'0');
else
{
op2=pop(stack);
op1=pop(stack);
printf("given expr is %d %d %c\n",op2,op1,symb);

ans=operate(symb,op1,op2); push(stack,ans);
}
}
ans=pop(stack);
printf("The result of the suffix expression is %d",ans);
break;

case 2: printf("enter the number of disks\n");scanf("%d",&n);

tower(n,'a','b','c');
printf("number of moves taken to move disks from source to
destination %d",count);
break;
case 3: return;
}
}
}

b. Solving Tower of Hanoi problem with n disks.

#include<stdio.h>
#include<stdlib.h>
#include<math.h> int
count=0,top=-1;
int operate(char symb,int r)
{
switch (symb)
{
case '+':return op1+op2; case '-
':return op1-op2; case '*':return
op1*op2; case '%':return
op1%op2;case '/':return op1/op2;
case '^':return pow(op1^op2);
}
}
void push(int stack[],int d)
stack[++top]=d;
int pop(int stack[]); return
(stack[top--]);
void tower(int n,char src,char intr,char des)
{
if(n)

DIVYASHREE.G Assistant Professor dept of ECE, MyCEM Page 13

 DATA STRUCTURES WITH C++ LABORATORY
{
tower (n-1,src,des,intr);
printf("disk % moved from %c to% \n",n,src,des);count ++;
tower (n-1,intr,src,des);
}
}
void main()
{
int n,choice,op1,op2,ans,stack[50];char
expr[20],symb;
clrscr();
while(1)
{
printf("program to evaluate suffix expression\n");
printf("1.enter the expression\n 2.tower of hanoi 3.exit\n");
printf("Enter the choice\n");
scanf("%d",&choice);
}
switch (choice)
{
case 1:printf("enter the suffix expression\n");
scanf("%s",expression);
for(i=0,expr[i]!='\0';i++)
{
symb=expr[i];
if(symb>='0'&&symb<=9)
push(stack,symb,'0')
else
{
op2=pop(stack);
op1=pop(stack);
printf("%d %d %c\n",op2.op1,symb);
ans=operate (symb,op1,op2) push(stack,ans);
}
}
ans=pop(stack);
printf("the rewsulatnt string is %d\n");
break;
case 2:printf("enter the number of disk\n");
scanf("%d",&n);
tower(n,'a','b','c');
printf("the number of string is moved from source file to destination file \n");
break;

case 3:exit(0);
}
}
}

DIVYASHREE.G Assistant Professor dept of ECE, MyCEM Page 14

 DATA STRUCTURES WITH C++ LABORATORY

6. Design, Develop and Implement a menu driven Program in C for the followingoperations on Circular
QUEUE of Characters (Array Implementation of Queue withmaximum 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
Support the program with appropriate functions for each of the above operations.

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX 5
int front=0,rear=-1,count=0,it1;
char cqueue[MAX],element;
void insert();
void delete(); void
display();

void main()
{
int choice;

while(1)
{
printf("\n\nprogram to ililstrate operations on CIRCULAR QUEUE of characters\n");
printf("\n\t1=>insert an element on to CIRCULAR QUEUE\n\t2=>delete an element fromCIRCULAR
QUEUE\n\t3=>display the status of CIRCULAR QUEUE\n\t4=>exit\n");
scanf("%d",&choice);
switch(choice)
{
case 1:insert();
break;
case 2:delete();
break;
case 3:display();
break;
case 4:return;
}
}
}

void insert()
{

if(count==MAX)
{
printf("CIRCULAR QUEUE is full,elements can not be inserted\n");
return;
}
rear=(rear+1)%MAX;
printf("\n enter the element to be inserted into the CIRCULAR QUEUE\n");
element=getche();
cqueue[rear]=element;

DIVYASHREE.G Assistant Professor dept of ECE, MyCEM Page 15

 DATA STRUCTURES WITH C++ LABORATORY
count++;
}

void delete()
{
if(count==0)
{
printf("CIRCULAR QHEUE is empty,no element to delete\n");
return;
}
it1=cqueue[front];
front=(front+1)%MAX;
printf("the element deleted is %c\n",it1);count-=1;
}

void display()
{
int i;
if(count==0)
{
printf("CIRCULAR QUEUE is empty , no element to display\n");
return;
}
printf("CIRCULAR QUEUE contants are\n");
for(i=front;i<=count;i++)
printf("%c",cqueue[i]);
}

DIVYASHREE.G Assistant Professor dept of ECE, MyCEM Page 16

 DATA STRUCTURES WITH C++ LABORATORY
7. Design, Develop and Implement a menu driven Program in C for the followingoperations on
Singly Linked List (SLL) of Student Data with the fields: USN, Name, Branch, 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 and Deletion at End of SLL
d. Perform Insertion and Deletion at Front of SLL
e. Demonstrate how this SLL can be used as STACK and QUEUE
f. Exit

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

typedef struct
{
int usn;
char name[20];
char branch[20];
int semester;
char phone[20];
}
STUDENT;

struct node
{
int usn;
char name[20];
char branch[20];
int semester;
char phone[20];
struct node *link;
};

typedef struct node*NODE;

NODE getnode()
{
NODE x;
x=(NODE)malloc(sizeof(struct node));
if(x==NULL)
{
printf("out of memory\n");
exit(0);
}
return x;
}

NODE insert_front(STUDENT item,NODE first)

{
NODE temp;
temp=getnode(); temp-
>usn=item.usn;
strcpy(temp->name,item.name);
strcpy(temp->branch,item.branch);
temp->semester=item.semester;

DIVYASHREE.G Assistant Professor dept of ECE, MyCEM Page 17

 DATA STRUCTURES WITH C++ LABORATORY
strcpy(temp->phone,item.phone);
temp->link=NULL; if(first==NULL)
return temp;
temp->link=first;
return temp;
}

NODE insert_rear(STUDENT item,NODE first)

{
NODE temp,cur;
temp=getnode();
temp->usn=item.usn;
strcpy(temp->name,item.name);
strcpy(temp->branch,item.branch);
temp->semester=item.semester;
strcpy(temp->phone,item.phone);
temp->link=NULL;
if(first==NULL)
return temp;
cur=first;
while(cur->link!=NULL)
{
cur=cur->link;
}
cur->link=temp;
return first;
}
NODE delete_front(NODE first)
{
NODE temp;
if(first==NULL)
{
printf("student list is empty\n");
return NULL;
}
temp=first;
temp=temp->link;
printf("delete student record:USN=%d\n",first->usn);
free(first);
return temp;
}

NODE delete_rear(NODE first)

{
NODE cur,prev;
if(first==NULL)
{
printf("student list is empty cannot delete\n");
return first;
}
if(first->link==NULL)
{
printf("delete student record:USN=%d\n",first->usn);
free(first);
return NULL;
}

DIVYASHREE.G Assistant Professor dept of ECE, MyCEM Page 18

 DATA STRUCTURES WITH C++ LABORATORY
prev=NULL;
cur=first;
while(cur->link!=NULL)
{
prev=cur;
cur=cur->link;
}
printf("delete student record:USN=%d\n",cur->usn);
free(cur);
prev->link=NULL;
return first;
}

void display(NODE first)

{
NODE cur; int
count=0;
if(first==NULL)
{
printf("student list is empty\n");
return;
}
cur=first;
while(cur!=NULL)
{
printf("%d\t%s\t%s\t%d\t%s\t\n",cur->usn,cur->name,cur->branch,cur->semester,cur-
>phone); cur=cur-
>link;
count++;
}
printf("numbrt of students=%d\n",count);
}
void main()
{
NODE first;
int choice;
STUDENT item;
first=NULL;
clrscr();
for(;;)
{
printf("1.insert_front\n2.insert_rear\n3.delete_front\n4.delete_rear\n5.display\n6.exit\n");
printf("Enter the choice\n");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("USN :\n");
scanf("%d",&item.usn);
printf("name :\n");
scanf("%s",item.name);
printf("branch :\n");
scanf("%s",item.branch);
printf("semester:\n");
scanf("%d",&item.semester);
printf("phone :\n");
scanf("%s",item.phone);

DIVYASHREE.G Assistant Professor dept of ECE, MyCEM Page 19

 DATA STRUCTURES WITH C++ LABORATORY
first=insert_front(item,first); break;
case 2:
printf("USN :\n");
scanf("%d",&item.usn);
printf("name :\n");
scanf("%s",item.name);
printf("branch :\n");
scanf("%s",item.branch);
printf("semester:\n");
scanf("%d",&item.semester);
printf("phone :\n");
scanf("%s",item.phone);
first=insert_rear(item,first); break;
case 3:
first=delete_front(first);break;
case 4:
first=delete_rear(first);break;
case 5:
display(first);
break;
default:
exit(0);
}
}
}

DIVYASHREE.G Assistant Professor dept of ECE, MyCEM Page 20

 DATA STRUCTURES WITH C++ LABORATORY
8. Design, Develop and Implement a menu driven Program in C for the followingoperations 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

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct node
{
int ssn;
char name[20],department[20],designation[20],phone[20];
float salary;
struct node *llink;
struct node *rlink;
}
typedef struct node *NODE;
struct node *item;
NODE getnode()
{
NODE x;
x=(NODE)malloc(sizeof(struct node));
if(x==NULL)
{
printf("out of memory\n");
exit(0);
}
return x;
}
void read()
{
item=getnode();
printf("ssn:");
scanf("%d",&item->ssn);
printf("name:");
scanf("%s",item->name);
printf("department:");
scanf("%s",item->department);
printf("designation:");
scanf("%s",item->designation);
printf("salary:");
scanf("%f",&item->salary);
printf("phone:");
scanf("%s",item->phone);
item->llink=item->rlink=NULL;
}
NODE insert_front(NODE first)
{
read();
if(first==NULL) return item;
item->rlink=first;
first->llink=item;
return item;

DIVYASHREE.G Assistant Professor dept of ECE, MyCEM Page 21

 DATA STRUCTURES WITH C++ LABORATORY
}
NODE insert_rear(NODE first)
{
NODE cur;
read();
if(first==NULL) return item;
cur=first;
while(cur->rlink!=NULL)
{
cur=cur->rlink;
}
cur->rlink=item;
item->llink=cur;
return first;

}
NODE delete_front(NODE first)
{
NODE second;
if(first==NULL)
{
printf("employee list is empty\n");
return NULL;
}
if(first->rlink==NULL)
{
printf("employee details deleted:ssn:=%d\n",first->ssn);
free(first);
return NULL;
}
second=first->rlink;
second->llink=NULL;
printf("employee details deleted:ssn:=%d\n",first->ssn);
free(first);
return second;
}
NODE delete_rear(NODE first)
{
NODE cur,prev;
if(first==NULL)
{
printf("list is empty cannot delete\n");
return first;
}
if(first->rlink==NULL)
{
printf("employee details deleted:ssn:=%d\n",first->ssn);
free(first);
return NULL;
}
prev=NULL;
cur=first;
while(cur->rlink!=NULL)
{
prev=cur; cur=cur-
>rlink;
}
printf("employee details deleted:ssn:=%d\n",cur->ssn);free(cur);
prev->rlink=NULL;return
first;

DIVYASHREE.G Assistant Professor dept of ECE, MyCEM Page 22

 DATA STRUCTURES WITH C++ LABORATORY
}
void display(NODE first)
{
NODE temp,cur; int
count=0;
if(first==NULL)
{
printf("employee list is empty\n");
return;
}
cur=first;
while(cur!=NULL)
{
printf("%d %f %s %s %s %s\n",cur->ssn,cur->salary,cur->name,cur-
>department,cur->designation,cur->phone); cur=cur->rlink;
count++;
}
printf("number of employees=%d\n",count);
}
void main()
{
NODE first; int
choice;
first=NULL;
for(;;)
{
printf("1:insert_front\n2:insert_rear\n");
printf("3:delete_front\n4:delete_rear\n");
printf("5:display\n6:exit\n"); printf("enter the choice\n");
scanf("%d",&choice);
switch(choice)
{
case 1:first=insert_front(first);break;
case 2:first=insert_rear(first);break;
case 3:first=delete_front(first);break;
case 4:first=delete_rear(first);break;
case 5:display(first);
break; default:exit(0);
}
}
}

DIVYASHREE.G Assistant Professor dept of ECE, MyCEM Page 23

 DATA STRUCTURES WITH C++ LABORATORY
9. Design, Develop and Implement a Program in C for the following operations onSingly 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

#include<stdio.h>

#include<math.h>

#include<stdlib.h>

#include<math.h>
typedef struct node

int expo,coef; struct node *next; }node;

node * insert(node *,int,int); node * create();

node * add(node *p1,node *p2); int eval(node *p1);void

display(node *head);

node *insert(node*head,int expo1,int coef1)

node *p,*q;

p=(node *)malloc(sizeof(node)); p->expo=expo1; p->coef=coef1; p->next=NULL;if(head==NULL)

head=p; head->next=head; return(head);

if(expo1>head->expo)

p->next=head->next; head->next=p; head=p; return(head);

if(expo1==head->expo)

DIVYASHREE.G Assistant Professor dept of ECE, MyCEM Page 24

 DATA STRUCTURES WITH C++ LABORATORY
head->coef=head->coef+coef1; return(head);

q=head;
while(q->next!=head&&expo1>=q->next->expo) q=q->next;

if(p->expo==q->expo) q-
>coef=q->coef+coef1;else

p->next=q->next; q->next=p;

return(head);

node *create()

int n,i,expo1,coef1; node *head=NULL;

printf("\n\nEnter no of terms of polynomial==>");

scanf("%d",&n);

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

printf("\n\nEnter coef & expo==>"); scanf("%d%d",&coef1,&expo1);head=insert(head,expo1,coef1);

return(head);

node *add(node *p1,node *p2)

node *p;

node *head=NULL;

printf("\n\n\nAddition of polynomial==>"); p=p1->next;do

DIVYASHREE.G Assistant Professor dept of ECE, MyCEM Page 25

 DATA STRUCTURES WITH C++ LABORATORY

head=insert(head,p->expo,p->coef); p=p->next;

}while(p!=p1->next); p=p2->next;do

head=insert(head,p->expo,p->coef); p=p->next;

}while(p!=p2->next); return(head);

int eval(node *head)

node *p; int x,ans=0;

printf("\n\nEnter the value of x="); scanf("%d",&x);p=head-

>next; do

ans=ans+p->coef*pow(x,p->expo); p=p->next; }while(p!=head->next); return(ans);

void display(node *head)

node *p,*q; int n=0; q=head->next; p=head->next; do

n++; q=q->next;

}while(q!=head->next); printf("\n\n\tThe polynomial is==>"); do

if(n-1)

printf("%dx^(%d) + ",p->coef,p->expo); p=p->next;

else

DIVYASHREE.G Assistant Professor dept of ECE, MyCEM Page 26

 DATA STRUCTURES WITH C++ LABORATORY

printf(" %dx^(%d)",p->coef,p->expo); p=p->next;

n--;

} while(p!=head->next);

void main()

int a,x,ch;

node *p1,*p2,*p3; p1=p2=p3=NULL; while(1)

printf("\n\t----------------<< MENU >> --------------------------------- "); printf("\n\tPolynomial Operations :");

printf(" 1.Add"); printf("\n\t\t\t\t2.Evaluate"); printf("\n\t\t\t\t3.Exit"); printf("\n\t");

printf("\n\n\n\tEnter your
choice==>"); scanf("%d",&ch);

switch(ch)

case 1 : p1=create(); display(p1); p2=create(); display(p2); p3=add(p1,p2); display(p3);break;

case 2 : p1=create(); display(p1);

a=eval(p1);

printf("\n\nValue of polynomial=%d",a); break;case 3 :

exit(0); break; default : printf("\n\n\tinvalid choice"); break;

DIVYASHREE.G Assistant Professor dept of ECE, MyCEM Page 27

 DATA STRUCTURES WITH C++ LABORATORY
10. Design, Develop and Implement a menu driven Program in C for the followingoperations 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. Delete an element(ELEM) from BST
e. Exit

#include<stdio.h>
#include<stdlib.h>struct
node
{
int info;
struct node*llink;
struct node*rlink;
};
typedef struct node*NODE;
NODE getnode()
{
NODE x;
x=(NODE)malloc(sizeof(struct node));
if(x==NULL)
{
printf("out of memory\n");
exit(0);
}
return x;
}
void preorder(NODE root)
{
if(root==NULL)return;
printf("%d ",root->info);
preorder(root->llink);
preorder(root->rlink);
}
void postorder(NODE root)
{
if(root==NULL)
return;
postorder(root->llink);
postorder(root->rlink);
printf("%d ",root->info);
}
void inorder(NODE root)
{
if(root==NULL)
return;
inorder(root->llink); printf("%d
",root->info);inorder(root-
>rlink);
}
void display(NODE root,int level)
{
int i;
if(root==NULL)
return;

DIVYASHREE.G Assistant Professor dept of ECE, MyCEM Page 28

 DATA STRUCTURES WITH C++ LABORATORY
display(root->rlink,level+1);
for(i=0;i<level;i++)
printf(" ");
printf("%d\n",root->info);
display(root->llink,level+1);
}
NODE insert(int item,NODE root)
{
NODE temp,cur,prev;
temp=getnode(); temp-
>info=item; temp-
>llink=NULL; temp-
>rlink=NULL;
if(root==NULL) return
temp; prev=NULL;
cur=root;
while(cur!=NULL)
{
prev=cur; if(item<cur-
>info)cur=cur->llink;
else
cur=cur->rlink;
}
if(item<prev->info)prev-
>llink=temp; else
prev->rlink=temp;
return root;
}
NODE search(int item,NODE root)
{
NODE cur;
if(root==NULL)
return NULL;
cur=root;
while(cur!=NULL)
{
if(item==cur->info)
return cur; if(item<cur-
>info) cur=cur->llink;
else
cur=cur->rlink;
}
return NULL;
}
void main()
{
NODE root,cur;int
choice,item;
root=NULL;
clrscr();
for(;;)
{
printf("1.insert 2.preorder\n");

DIVYASHREE.G Assistant Professor dept of ECE, MyCEM Page 29

 DATA STRUCTURES WITH C++ LABORATORY
printf("3.postorder 4.inorder\n");
printf("5.search 6.exit\n"); printf("enter
the choice\n"); scanf("%d",&choice);
switch(choice)
{
case 1:printf("enter the item to be inserted\n");
scanf("%d",&item); root=insert(item,root);
break;
case 2:if(root==NULL)
{
printf("tree is empty\n");break;
}
printf("the given tree in tree form is\n");
display(root,1);
printf("preorder traversing is\n");
preorder(root);
printf("\n");
break;
case 3:if(root==NULL)
{
printf("tree is empty\n");break;
}
printf("the given tree in tree form is\n");
display(root,1);
printf("postorder traversing is\n");
postorder(root);
printf("\n");
break;
case 4:if(root==NULL)
{
printf("tree is empty\n");break;
}
printf("the given tree in tree form is\n");
display(root,1);
printf("inorder traversing is\n");
inorder(root);
printf("\n");
break;
case 5:printf("enter the item to be search\n");
scanf("%d",&item); cur=search(item,root);
if(cur==NULL) printf("item not
found\n");else
printf("item found\n");
break;
default:exit(0);
}
}

DIVYASHREE.G Assistant Professor dept of ECE, MyCEM Page 30

 DATA STRUCTURES WITH C++ LABORATORY

11. Design, Develop and Implement a Program in C for the following operations onGraph(G) of
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 BFSmethod
c. Check whether a given graph is connected or not using DFS method.

#include<stdio.h>
#include<conio.h> int
a[10][10],s[10],n;
void bfs(int u)
{
int f,r,q[10],v;
printf("the nodes visited from %d ",u);f=0,r=-1;
q[++r]=u;
s[u]=1;
printf("%d ",u);
while(f<=r)
{
u=q[f++]; for(v=0;v<n;v++)
{
if(a[u][v]==1)
{
if(s[v]==0)
{
printf(" %d ",v);
s[v]=1;
q[++r]=v;
}
}
}
}
printf("\n");
}
void dfs(int u)
{
int v;
s[u]=1;
printf(" %d ",u); for(v=0;v<n;v++)
{
if(a[u][v]==1&&s[v]==0) dfs(v);
}
}
void main()
{
int i,j,choice,source,s1;
clrscr();
printf("enter the no of nodes\n");
scanf("%d",&n);
printf("enter the adjacency matrix\n");

DIVYASHREE.G Assistant Professor dept of ECE, MyCEM Page 31

 DATA STRUCTURES WITH C++ LABORATORY
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
scanf("%d",&a[i][j]);
}
for(;;)
{
printf("\n1:reachable nodes using bfs\n 2:reachable nodes using
dfs\n3:exit\n");
scanf("%d",&choice);
switch(choice)
{

case 1:printf("enter the source node\n");

scanf("%d",&s1);
bfs(s1);
break;
case 2:for(source=0;source<n;source++)
{
for(i=0;i<n;i++)
s[i]=0;
printf("\n reachable node from %d: ",source);dfs(source);

}
break;

case 3:exit(0);
}

}
}

DIVYASHREE.G Assistant Professor dept of ECE, MyCEM Page 32

 DATA STRUCTURES WITH C++ LABORATORY
12. Given a File of N employee records with a set K of Keys(4-digit) which uniquelydetermine 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 thekeys in K and
addresses in L are Integers. Design and develop a Program in C that uses Hashfunction H: K ®L
as H(K)=K mod m (remainder method), and implement hashing technique to map agiven key K
to the address space L. Resolve the collision (if any) using linear probing.

#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<stdlib.h> #define
HASH_SIZE 5 typedef struct
empolyee
{
int id;
char name[20];char
des[20];
}EMPLOYEE;
void intialize_hash_table(EMPLOYEE a[])
{
int i; for(i=0;i<HASH_SIZE;i++)
{
a[i].id=0;
// a[i].name={""};
// a[i].des=NULL;
}
}
void insert_hash_table(int id,char des[],char name[],EMPLOYEE a[])
{
int i,index,h_value;
h_value=id%HASH_SIZE;
for(i=0;i<HASH_SIZE;i++)
{
index=(h_value+i)%HASH_SIZE;
if(a[index].id==0)
{
a[index].id=id;
strcpy(a[index].name,name);
strcpy(a[index].des,des); break;
}
}
if(i==HASH_SIZE)
printf("table full");
}
int search_hash_table(int key,EMPLOYEE a[])
{
int i,index,h_value;
h_value=key%HASH_SIZE;
for(i=0;i<HASH_SIZE;i++)
{

DIVYASHREE.G Assistant Professor dept of ECE, MyCEM Page 33

 DATA STRUCTURES WITH C++ LABORATORY
index=(h_value+i)%HASH_SIZE;
if(key==a[index].id)
return 1; if(a[index].id==0)
return 0;
}
if(i==HASH_SIZE)
return 0;
}

void display_hash_table(EMPLOYEE a[],int n)

{
int i; printf("\n\tid\tname\tdes\n");
for(i=0;i<n;i++)
{
if(a[i].id!=0) printf("a[%d]=%d\t%s\t%s\n",i,a[i].id,a[i].name,a[i].des);
}
}
void main()
{
EMPLOYEE a[10];
char name[20],des[20];int
key,id,choice,flag; clrscr();
intialize_hash_table(a);for(;;)
{
printf("1:insert\n2:search\n3:display\n4:exit\n"); scanf("%d",&choice);
switch(choice)
{
case 1:printf("enter emp id emp name des\n");
scanf("%d%s%s",&id,name,des);
insert_hash_table(id,des,name,a); break;
case 2:printf("enter key"); scanf("%d",&key);
flag=search_hash_table(key,a);
if(flag==0)
printf("key not found");else
printf("key found");
break;
case 3:printf("contents of hash table are");
display_hash_table(a,HASH_SIZE);break;
default:exit(0);
}
}
}

DIVYASHREE.G Assistant Professor dept of ECE, MyCEM Page 34

 DATA STRUCTURES WITH C++ LABORATORY

Viva questions
What is data-structure?

What are various data-structures available?

What is algorithm?
Why we need to do algorithm analysis?
What are the criteria of algorithm analysis?
What is asymptotic analysis of an algorithm?
What are asymptotic notations?
What is linear data structure?
What are common operations that can be performed on a data-structure?
Briefly explain the approaches to develop algorithms.
Give some examples greedy algorithms.
What are some examples of dynamic programming algorithms?
What is a linked-list?
What is stack?
Why do we use stacks?
What operations can be performed on stacks?
What is a queue in data-structure?
Why do we use queues?
What operations can be performed on Queues?
What is linear searching?
What is binary search?
What is bubble sort and how bubble sort works?
Tell me something about 'insertion sort'?
What is selection sort?
How insertion sort and selection sorts are different?
What is merge sort and how it works?
What is shell sort?
How quick sort works?
What is a graph?
How depth first traversal works?
How breadth first traversal works?
What is a tree?What is a binary tree?
What is a binary search tree?
What is tree traversal?
What is tower of hanoi?
What is fibonacci series?
What is hashing?
What is interpolation search technique?
What is the prefix and post fix notation of (a + b) * (c + d)?

Mini project Employee record system using C

The employee record system is very simple and for very beginner mini project. It is based one the
menu-driven program for elementary database management. It employs all the basictechnique of file
handling in C. It consists of following features
• Writing the data in binary file

DIVYASHREE.G Assistant Professor dept of ECE, MyCEM Page 35

 DATA STRUCTURES WITH C++ LABORATORY
• Reading the data from binary file
• Modify the record

DIVYASHREE.G Assistant Professor dept of ECE, MyCEM Page 36

 DATA STRUCTURES WITH C++ LABORATORY
• Delete the record
This project is a learning milestone for a beginner who wants to step into the databasemanagement
project in C. The code is also available on GitHub.

Here are List of Mini projects in C

Source Code
/**
* A menu-driven program for elementary database management
* @author: Bibek Subedi
* @language: C
* This program uses file handling in Binary mode
*/

/// List of library functions

#include <stdio.h> ///for input output functions like printf, scanf#include <stdlib.h>
#include <string.h> ///string operations

// Copied from
// https://stackoverflow.com/questions/35103745/read-a-string-as-an-input-using-scanf
void flush()
{
int c;
while ((c = getchar()) != '\n' && c != EOF);
}

/** Main function started */

int main(){
FILE *fp, *ft; /// file pointerschar another,
choice;

/** structure that represent a employee */struct emp{

char name[40]; ///name of employeeint age; /// age
of employee
float bs; /// basic salary of employee
};

struct emp e; /// structure variable creation

char empname[40]; /// string to store name of the employeelong int recsize; /// size of each

record of employee

/** open the file in binary read and write mode

* if the file EMP.DAT already exists then it open that file in read writemode
* if the file doesn't exit it simply create a new copy
*/
fp = fopen("EMP.DAT","rb+");if(fp ==
NULL){
fp = fopen("EMP.DAT","wb+");if(fp ==
NULL){
printf("Connot open file");exit(1);
}
}

DIVYASHREE.G Assistant Professor dept of ECE, MyCEM Page 37

 DATA STRUCTURES WITH C++ LABORATORY

/// sizeo of each record i.e. size of structure variable erecsize = sizeof(e);

/// infinite loop continues untile the break statement encounterwhile(1){

printf("1. Add Record\n"); /// option for add record
printf("2. List Records\n"); /// option for showing existing recordprintf("3. Modify Records\n"); ///
option for editing record printf("4. Delete Records\n"); /// option for deleting record printf("5.
Exit\n"); /// exit from the program
printf("Your Choice: "); /// enter the choice 1, 2, 3, 4, 5fflush(stdin); /// flush the input buffer
scanf("\n%c", &choice); /// get the input from keyboardswitch(choice){
case '1': /// if user press 1
fseek(fp,0,SEEK_END); /// search the file and move cursor to
end of the file
/// here 0 indicates moving 0 distance
from the end of the file
another = 'y';

while(another == 'y'){ /// if user want to add another recordflush();

printf("\nEnter name: "); fgets(e.name, 40, stdin);
printf("\nEnter age: "); scanf("%d", &e.age);
printf("\nEnter basic salary: ");scanf("%f",
&e.bs);

fwrite(&e,recsize,1,fp); /// write the record in the file

printf("\nAdd another record(y/n) ");fflush(stdin);

scanf("\n%c", &another);
}
break;
case '2':
rewind(fp); ///this moves file cursor to start of the file while(fread(&e,recsize,1,fp)==1){ /// read the
file and fetch
the record one record per fetch
printf("\n%s %d %.2f\n",e.name,e.age,e.bs); /// print thename, age and basic salary
}
break;

case '3': /// if user press 3 then do editing existing recordanother = 'y';
while(another == 'y'){
printf("Enter the employee name to modify: ");scanf("%s",
empname);
rewind(fp);
while(fread(&e,recsize,1,fp)==1){ /// fetch all record if(strcmp(e.name,empname) == 0){ ///if
entered name
matches with that in file
printf("\nEnter new name,age and bs: ");
scanf("%s%d%f",e.name,&e.age,&e.bs);
fseek(fp,-recsize,SEEK_CUR); /// move the cursor 1step back from current
position
fwrite(&e,recsize,1,fp); /// override the recordbreak;

DIVYASHREE.G Assistant Professor dept of ECE, MyCEM Page 38

 DATA STRUCTURES WITH C++ LABORATORY
}
}
printf("\nModify another record(y/n)");fflush(stdin);
scanf("\n%c", &another);
}
break;
case '4':
another = 'y'; while(another ==
'y'){
flush();
printf("\nEnter name of employee to delete: ");fgets(empname,40,
stdin);
ft = fopen("Temp.dat","wb"); /// create a intermediatefile for temporary storage
rewind(fp); /// move record to starting of file while(fread(&e,recsize,1,fp) == 1){ /// read all
records
if(strcmp(e.name,empname) != 0){ /// if the enteredfwrite(&e,recsize,1,ft);
/// move all records except the one that is to
}
}
fclose(fp);
fclose(ft);
remove("EMP.DAT"); /// remove the orginal file rename("Temp.dat","EMP.DAT"); /// rename
the temp file to
original file name
fp = fopen("EMP.DAT", "rb+"); printf("Delete another
record(y/n)");fflush(stdin);
scanf("\n%c", &another);

break;
case '5':
fclose(fp); /// close the file exit(0); /// exit from the
program
}
}
return 0;
}

DIVYASHREE.G Assistant Professor dept of ECE, MyCEM Page 39