DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

LABORATORY MANUAL

COURSE CODE : CS3311

COURSE NAME : DATA STRUCTURES LABORATORY

REGULATION : R2021

CLASS & SEMESTER : II B.E CSE

Ex. No. 1a Array implementation of Stack ADT

Date:

1
 Aim:
To implement stack operations using array.

Algorithm:
1. Start
2. Define a array stack of size max = 5
3. Initialize top = -1
4. Display a menu listing stack operations
5. Accept choice
6. If choice = 1 then
If top < max -1
Increment top
Store element at current position of top
Else
Print Stack overflow
Else If choice = 2 then
If top < 0 then
Print Stack underflow
Else
Display current top
element Decrement top
Else If choice = 3 then
Display stack elements starting from top
7. Stop

2
Program:
/* Stack Operation using Arrays */
#include <stdio.h>
#include <conio.h> #define
max 5
static int stack[max]; int
top = -1;

void push(int x)
{
stack[++top] = x;
}

int pop()
{
return (stack[top--]);
}

void view()
{
int i;
if (top < 0)
printf("\n Stack Empty \n"); else
{
printf("\n Top-->");
for(i=top; i>=0; i--)
{
printf("%4d", stack[i]);
}
printf("\n");
}
}
main()
{
int ch=0, val;
clrscr();
while(ch != 4)
{
printf("\n STACK OPERATION \n");
printf("1.PUSH ");
printf("2.POP ");
printf("3.VIEW ");
printf("4.QUIT \n"); printf("Enter
Choice : ");

3
 scanf("%d", &ch);
switch(ch)
{
case 1:
if(top < max-1)
{
printf("\nEnter Stack element : ");
scanf("%d", &val);
push(val);
}
else
printf("\n Stack Overflow \n"); break;
case 2:
if(top < 0)
printf("\n Stack Underflow \n"); else
{
val = pop();
printf("\n Popped element is %d\n", val);
}
break;
case 3:
view(); break;
case 4:
exit(0);
default:
printf("\n Invalid Choice \n");
}
}
}

4
Output

STACK OPERATION
1.PUSH 2.POP 3.VIEW 4.QUIT
Enter Choice : 1
Enter Stack element : 12
STACK OPERATION
1.PUSH 2.POP 3.VIEW 4.QUIT
Enter Choice : 1
Enter Stack element : 23
STACK OPERATION
1.PUSH 2.POP 3.VIEW 4.QUIT
Enter Choice : 1
Enter Stack element : 34
STACK OPERATION
1.PUSH 2.POP 3.VIEW 4.QUIT
Enter Choice : 1
Enter Stack element : 45
STACK OPERATION
1.PUSH 2.POP 3.VIEW 4.QUIT
Enter Choice : 3
Top--> 45 34 23 12
STACK OPERATION
1.PUSH 2.POP 3.VIEW 4.QUIT
Enter Choice : 2 Popped
element is 45
STACK OPERATION
1.PUSH 2.POP 3.VIEW 4.QUIT
Enter Choice : 3
Top--> 34 23 12
STACK OPERATION
1. PUSH 2.POP 3.VIEW 4.QUIT
Enter Choice : 4

Result
Thus the program for push and pop operations of a stack using array was
5
executed and verified successfully.

6
Ex. No. 1b Array implementation of Queue ADT
Date:

Aim
To implement queue operations using array.

Algorithm
1. Start
2. Define a array queue of size max = 5
3. Initialize front = rear = –1
4. Display a menu listing queue operations
5. Accept choice
6. If choice = 1
then If rear <
max -1
Increment rear
Store element at current position of rear
Else
Print Queue Full
Else If choice = 2
then If front = –1
then
Print Queue empty
Else
Display current front element
Increment front
Else If choice = 3 then
Display queue elements starting from front to rear.
7. Stop

7
Program
/* Queue Operation using Arrays */
#include <stdio.h>
#include <conio.h> #define
max 5
static int queue[max]; int
front = -1;
int rear = -1;
void insert(int x)
{
queue[++rear] = x; if
(front == -1)
front = 0;
}
int remove()
{
int val;
val = queue[front];
if (front==rear && rear==max-1) front
= rear = -1;
else
front ++;
return (val);
}
void view()
{
int i;

if (front == -1)
printf("\n Queue Empty \n"); else
{
printf("\n Front-->"); for(i=front;
i<=rear; i++)
printf("%4d", queue[i]);
printf(" <--Rear\n");
}
}
main()
{
int ch= 0,val;
clrscr();
while(ch != 4)
{
printf("\n QUEUE OPERATION \n");
printf("1.INSERT ");
printf("2.DELETE ");
printf("3.VIEW ");
printf("4.QUIT\n"); printf("Enter
8
 Choice : "); scanf("%d", &ch);

switch(ch)
{
case 1:
if(rear < max-1)
{
printf("\n Enter element to be inserted : "); scanf("%d",
&val);
insert(val);
}
else
printf("\n Queue Full \n"); break;
case 2:
if(front == -1)
printf("\n Queue Empty \n"); else
{
val = remove();
printf("\n Element deleted : %d \n", val);
}
break;
case 3:
view(); break;
case 4:
exit(0);
default:
printf("\n Invalid Choice \n");
}
}
}

9
Output

QUEUE OPERATION
1.INSERT 2.DELETE 3.VIEW 4.QUIT
Enter Choice : 1
Enter element to be inserted : 12 QUEUE
OPERATION
1.INSERT 2.DELETE 3.VIEW 4.QUIT
Enter Choice : 1
Enter element to be inserted : 23 QUEUE
OPERATION
1.INSERT 2.DELETE 3.VIEW 4.QUIT
Enter Choice : 1
Enter element to be inserted : 34 QUEUE
OPERATION
1.INSERT 2.DELETE 3.VIEW 4.QUIT
Enter Choice : 1
Enter element to be inserted : 45 QUEUE
OPERATION
1.INSERT 2.DELETE 3.VIEW 4.QUIT
Enter Choice : 1
Enter element to be inserted : 56 QUEUE
OPERATION
1.INSERT 2.DELETE 3.VIEW 4.QUIT
Enter Choice : 1
Queue Full
QUEUE OPERATION
1. INSERT 2.DELETE 3.VIEW 4.QUIT
Enter Choice : 3

Front--> 12 23 34 45 56 <--Rear

Result
Thus the program for insert and delete operations of a queue using array was
executed and verified successfully.
10
Ex. No. 1c Array implementation of Circular Queue ADT
Date:

Aim
To implement circular queue operations using array.

Algorithm
1. Start
2. Define a array queue of size max = 5
3. Initialize front = rear = –1
4. Display a menu listing queue operations
5. Accept choice
6. If choice = 1
then If rear <
max -1
Increment rear
Store element at current position of rear
Else
Print Queue Full
Else If choice = 2
then If front = –1
then
Print Queue empty
Else
Display current front element
Increment front
Else If choice = 3 then
Display queue elements starting from front to rear.
7. Stop

11
Program:
#include <stdio.h>
# define max 6
int queue[max]; // array declaration
int front=-1;
int rear=-1;
// function to insert an element in a circular queue
void enqueue(int element)
{
if(front==-1 && rear==-1) // condition to check queue is empty
{
front=0;
rear=0;
queue[rear]=element;
}
else if((rear+1)%max==front) // condition to check queue is full
{
printf("Queue is overflow..");
}
else
{
rear=(rear+1)%max; // rear is incremented
queue[rear]=element; // assigning a value to the queue at the rear p
osition.
}
}
// function to delete the element from the queue
int dequeue()
{
if((front==-1) && (rear==-1)) // condition to check queue is empty
{
printf("\nQueue is underflow..");
}
else if(front==rear)
{
printf("\nThe dequeued element is %d", queue[front]);
front=-1;
rear=-1;
}
else
{
printf("\nThe dequeued element is %d", queue[front]);
front=(front+1)%max;
}
}
// function to display the elements of a queue
void display()
{
12
 int i=front;
if(front==-1 && rear==-1)
{
printf("\n Queue is empty..");
}
else
{
printf("\nElements in a Queue are :");
while(i<=rear)
{
printf("%d,", queue[i]);
i=(i+1)%max;
}
}
}
int main()
{
int choice=1,x; // variables declaration

while(choice<4 && choice!=0) // while loop

{
printf("\n Press 1: Insert an element");
printf("\nPress 2: Delete an element");
printf("\nPress 3: Display the element");
printf("\nEnter your choice");
scanf("%d", &choice);

switch(choice)
{
case 1:
printf("Enter the element which is to be inserted");
scanf("%d", &x);
enqueue(x);
break;
case 2:
dequeue();
break;
case 3:
display();
}}
return 0;
}

13
Output:

Result

14
 Thus t h e p r o g r a m f o r various o p e r a t i o n s o n circular queue
using array was executed and verified successfully.

Ex. No. 2 Implementation of Singly Linked List

Date:

Aim
To define a singly linked list node and perform operations such as
insertions and
deletions dynamically.

Algorithm
1. Start
2. Define single linked list node as self referential structure
3. Create Head node with label = -1 and next = NULL using
4. Display menu on list operation
5. Accept user choice
6. If choice = 1 then
Locate node after which insertion is to be
done Create a new node and get data part
Insert new node at appropriate position by manipulating
address Else if choice = 2
Get node's data to be deleted.
Locate the node and delink the
node Rearrange the links
Else
Traverse the list from Head node to node which points to null
7. Stop

15
Program

/* Single Linked List */

#include <stdio.h>
#include <conio.h>
#include <process.h>
#include <alloc.h>
#include <string.h>
struct node
{
int label;
struct node *next;
};
main()
{
int ch, fou=0; int
k;
struct node *h, *temp, *head, *h1;
/* Head node construction */
head = (struct node*) malloc(sizeof(struct node)); head->label
= -1;
head->next = NULL;
while(-1)
{
clrscr();
printf("\n\n SINGLY LINKED LIST OPERATIONS \n");
printf("1->Add ");
printf("2->Delete ");
printf("3->View ");
printf("4->Exit \n");
printf("Enter your choice : ");
scanf("%d", &ch);

switch(ch)
{
/* Add a node at any intermediate location */ case 1:
printf("\n Enter label after which to add : "); scanf("%d",
&k);

h = head;
fou = 0;

if (h->label == k) fou = 1;
while(h->next != NULL)
{
if (h->label == k)
{
16
 fou=1;
break;
}
h = h->next;
}
if (h->label == k) fou = 1;
if (fou != 1)
printf("Node not found\n"); else
{
temp=(struct node *)(malloc(sizeof(struct node))); printf("Enter
label for new node : "); scanf("%d", &temp->label);
temp->next = h->next; h-
>next = temp;
}
break;
/* Delete any intermediate node */ case 2:
printf("Enter label of node to be deleted\n"); scanf("%d",
&k);
fou = 0;
h = h1 = head;
while (h->next != NULL)
{
h = h->next;
if (h->label == k)
{
fou = 1;
break;
}
}
if (fou == 0)
printf("Sorry Node not found\n"); else
{
while (h1->next != h) h1
= h1->next;
h1->next = h->next;
free(h);
printf("Node deleted successfully \n");
}
break;
case 3:
printf("\n\n HEAD -> ");
h=head;
while (h->next != NULL)
{
h = h->next;
printf("%d -> ",h->label);
}
printf("NULL"); break;
17
 case 4:
exit(0);
}
}}

Output

SINGLY LINKED LIST OPERATIONS

1->Add 2->Delete 3->View 4->Exit Enter
your choice : 1
Enter label after which new node is to be added : -1 Enter label
for new node : 23

SINGLY LINKED LIST OPERATIONS

1->Add 2->Delete 3->View 4->Exit Enter
your choice : 1
Enter label after which new node is to be added : 23 Enter label
for new node : 67

SINGLY LINKED LIST OPERATIONS

1- >Add 2->Delete 3->View 4->Exit
Enter your choice : 3
HEAD -> 23 -> 67 -> NULL

18
Result
Thus the program for various operations on single linked list was executed
and verified successfully.

19
Ex. No. 3a Linked list implementation of Stack ADT
Date:

Aim
To implement stack operations using linked list.

Algorithm
1. Start
2. Define a singly linked list node for stack
3. Create Head node
4. Display a menu listing stack operations
5. Accept choice
6. If choice = 1 then
Create a new node with data
Make new node point to first
node
Make head node point to new
node Else If choice = 2 then
Make temp node point to first node
Make head node point to next of temp
node Release memory
Else If choice = 3 then
Display stack elements starting from head node till null
7. Stop

20
Program
/* Stack using Single Linked List */
#include <stdio.h>
#include <conio.h>
#include <process.h>
#include <alloc.h>
struct node
{
int label;
struct node *next;
};
main()
{
int ch = 0; int
k;
struct node *h, *temp, *head;
/* Head node construction */
head = (struct node*) malloc(sizeof(struct node)); head->next
= NULL;
while(1)
{
printf("\n Stack using Linked List \n"); printf("1-
>Push ");
printf("2->Pop ");
printf("3->View ");
printf("4->Exit \n");
printf("Enter your choice : ");
scanf("%d", &ch);
switch(ch)
{
case 1:
/* Create a new node */
temp=(struct node *)(malloc(sizeof(struct node))); printf("Enter
label for new node : "); scanf("%d", &temp->label);
h = head;
temp->next = h->next; h-
>next = temp; break;

case 2:
/* Delink the first node */ h =
head->next;
head->next = h->next;
printf("Node %s deleted\n", h->label); free(h);
break;
case 3:
printf("\n HEAD -> "); h =
head;
/* Loop till last node */
21
 while(h->next != NULL)
{
h = h->next;
printf("%d -> ",h->label);
}
printf("NULL \n"); break;
case 4:
exit(0);
}
}
}

Output

Stack using Linked List

1->Push 2->Pop 3->View 4->Exit
Enter your choice : 1
Enter label for new node : 23 New
node added

Stack using Linked List

1->Push 2->Pop 3->View 4->Exit
Enter your choice : 1
Enter label for new node : 34

Stack using Linked List

1- >Push 2->Pop 3->View 4->Exit
Enter your choice : 3
HEAD -> 34 -> 23 -> NULL

Result
Thus the program for push and pop operations of a stack using linked list was
executed and verified successfully.

22
Ex. No. 3b Linked list implementation of Linear Queue ADT
Date:

Aim
To implement queue operations using linked list.

Algorithm
1. Start
2. Define a singly linked list node for stack
3. Create Head node
4. Display a menu listing stack operations
5. Accept choice
6. If choice = 1 then
Create a new node with data
Make new node point to first
node
Make head node point to new
node Else If choice = 2 then
Make temp node point to first node
Make head node point to next of temp
node Release memory
Else If choice = 3 then
Display stack elements starting from head node till null
7. Stop

23
Program
/* Queue using Single Linked List */ #include
<stdio.h>
#include <conio.h> #include
<process.h> #include
<alloc.h>

struct node
{
int label;
struct node *next;
};
main()
{
int ch=0;
int k;
struct node *h, *temp, *head;
/* Head node construction */
head = (struct node*) malloc(sizeof(struct node)); head->next
= NULL;
while(1)
{
printf("\n Queue using Linked List \n"); printf("1-
>Insert ");
printf("2->Delete ");
printf("3->View ");
printf("4->Exit \n");
printf("Enter your choice : ");
scanf("%d", &ch);
switch(ch)
{
case 1:
/* Create a new node */
temp=(struct node *)(malloc(sizeof(struct node))); printf("Enter
label for new node : "); scanf("%d", &temp->label);

/* Reorganize the links */ h =

head;
while (h->next != NULL) h =
h->next;
h->next = temp;
temp->next = NULL;
break;

24
 case 2:
/* Delink the first node */ h =
head->next;
head->next = h->next;
printf("Node deleted \n");
free(h);
break;
case 3:
printf("\n\nHEAD -> "); h=head;
while (h->next!=NULL)
{
h = h->next;
printf("%d -> ",h->label);
}
printf("NULL \n"); break;

case 4:
exit(0);
}
}
}

Output

Queue using Linked List

1->Insert 2->Delete 3->View 4->Exit Enter
your choice : 1
Enter label for new node : 12

Queue using Linked List

1->Insert 2->Delete 3->View 4->Exit Enter
your choice : 1
Enter label for new node : 23

Queue using Linked List

1- >Insert 2->Delete 3->View 4->Exit Enter
your choice : 3
HEAD -> 12 -> 23 -> NULL

Result
Thus the program for performing insert and delete operations of a queue using
25
linked list was executed and verified successfully.

26
Ex. No: 4 Implementation of Polynomial Manipulation using Linked list
Date:

Aim
To write a C program to implement the polynomial multiplication.

Algorithm

Step 1: Start the program.

Step 2: Read the input polynomial expressions.
Step 3: call the multiply(A[0..m-1], B[0..n01])
Step 4: Create a product array prod[] of size m+n-1.
Step 5: Initialize all entries in prod[] as 0.
Step 6: Travers array A[] and do following for every element A[i]
...(3.a) Traverse array B[] and do following for every element B[j]
prod[i+j] = prod[i+j] + A[i] * B[j]
Step 7: Return prod[].
Step 8: Print the multiplied expression.
Step 9: Stop

27
Program

#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#define MAX 17
typedef struct node
{
int coeff;
struct node *next;
}node;
node * init();
void read(node *h1);
void print(node *h1);
node * add(node *h1,node *h2);
node * multiply(node *h1,node *h2);
void main()
{
node *h1=NULL,*h2=NULL,*h3=NULL;
int option;
do
{
printf("\n1 : create 1’st polynomial");
printf("\n2 : create 2’nd polynomial");
printf("\n3 : Add polynomials");
printf("\n4 : Multiply polynomials");
printf("\n5 : Quit");
printf("\nEnter your choice :");
scanf("%d",&option);
switch(option)
{
case 1:h1=init();read(h1);break;
case 2:h2=init();read(h2);break;
case 3:h3=add(h1,h2);
printf("\n1’st polynomial -> ");
print(h1);
printf("\n2’nd polynomial -> ");
print(h2);
printf("\n Sum = ");
print(h3);
break;
case 4:h3=multiply(h1,h2);
printf("\n1’st polynomial -> ");
print(h1);
printf("\n2’nd polynomial -> ");
print(h2);
printf("\n Product = ");
print(h3);
break;
}

28
}while(option!=5);
}
void read(node *h)
{
int n,i,j,power,coeff;
node *p;
p=init();
printf("\n Enter number of terms :");
scanf("%d",&n);
/* read n terms */
for (i=0;i<n;i++)
{ printf("\nenter a term(power coeff.)");
scanf("%d%d",&power,&coeff);
for(p=h,j=0;j<power;j++)
p=p->next;
p->coeff=coeff;
}
}
void print(node *p)
{
int i;
for(i=0;p!=NULL;i++,p=p->next)
if(p->coeff!=0)
printf("%dX^%d ",p->coeff,i);
}
node * add(node *h1, node *h2)
{
node *h3,*p;
h3=init();
p=h3;
while(h1!=NULL)
{
h3->coeff=h1->coeff+h2->coeff;
h1=h1->next;
h2=h2->next;
h3=h3->next;
}
return(p);
}
node * multiply(node *h1, node *h2)
{
node *h3,*p,*q,*r;
int i,j,k,coeff,power;
h3=init();
for(p=h1,i=0;p!=NULL;p=p->next,i++)
for(q=h2,j=0;q!=NULL;q=q->next,j++)
{
coeff=p->coeff * q->coeff;
power=i+j;
for(r=h3,k=0;k<power;k++)

29
r=r->next;
r->coeff=r->coeff+coeff;
}
return(h3);
}
node * init()
{
int i;
node *h=NULL,*p;
for(i=0;i<MAX;i++)
{
p=(node*)malloc(sizeof(node));
p->next=h;
p->coeff=0;
h=p;
}
return(h);
}

Output:

1 : create 1’st polynomial

30
2 : create 2’nd polynomial
3 : Add polynomials
4 : Multiply polynomials
5 : Quit
Enter your choice : 1
Enter number of terms : 2
Enter a term(power coeff.) 1 3
Enter a term(power coeff.) 0 4

1 : create 1’st polynomial

2 : create 2’nd polynomial
3 : Add polynomials
4 : Multiply polynomials
5 : Quit
Enter your choice : 2
Enter number of terms : 2
Enter a term(power coeff.) 1 3
Enter a term(power coeff.) 0 4

1 : create 1’st polynomial

2 : create 2’nd polynomial
3 : Add polynomials
4 : Multiply polynomials
5 : Quit
Enter your choice : 3

1’st polynomial -> 4X^0 3X^1

2’nd polynomial -> 4X^0 3X^1
Sum = 8X^0 6X^1
1 : create 1’st polynomial
2 : create 2’nd polynomial
3 : Add polynomials
4 : Multiply polynomials
5 : Quit
Enter your choice : 4
1’st polynomial -> 4X^0 3X^1
2’nd polynomial -> 4X^0 3X^1
Product = 16X^0 24X^1 9X^2

Result
Thus the program for implementing the polynomial addition has been executed
and verified successfully.

31