PROGRAMMING
AND
DATA STRUCTURES LAB
(MC9217)
LAB MANUAL
Department of Computer Applications
RajalakshmiEngineeringCollege
Thandalam
Chennai – 602 105
- Lab Exercises
- Represent the given sparse matrix using Arrays
- Create a Stack and do the basic operations using Arrays
- Create a Queue and do the basic operations using Arrays
- Implement the basic operations on Singly Linked List
- Represent the given sparse matrix using Linked List
- Create a Stack and do the basic operations using Linked List
- Create a Queue and do the basic operations using Linked List
- Implement the basic operations on Doubly Linked List
- Implement the basic operations on Circular Linked List
- Binary Tree Traversals
- Binary Search Tree implementation
- Sort the given list of numbers using Heap Sort
- Sort the given list of elements using Quick Sort
- Depth First Search
- Breadth First Search
- Dijkstra’s Algorithm
Data Structures Lab Manual, Dept. of Computer Applications, REC 1
RajalakshmiEngineeringCollege
Department of Computer Applications
Lab Exercises
600151 DATA STRUCTURES LABORATORY
- Represent the given sparse matrix using one dimensional array and linked list.
- Create a Stack and do the following operations using arrays and linked lists
(i)Push (ii) Pop (iii) Peep
- Create a Queue and do the following operations using arrays and linked lists
(i)Add (ii) Remove
- Implement the operations on singly linked list, doubly linked list and circular linked list.
- Create a binary search tree and do the following traversals
(i)In-order (ii) Pre order (iii) Post order
- Implement the following operations on a binary search tree.
(i) Insert a node (ii) Delete a node
- Sort the given list of numbers using heap and quick sort.
- Perform the following operations in a given graph
(i) Depth first search (ii) Breadth first search
- Find the shortest path in a given graph using Dijkstra algorithm
*****
Ex. No : 1 /Represent the given sparse matrix using Arrays
Date :Aim: To write a program to represent Sparse Matrix using one dimensional Array
Algorithm:
- Start
- Declare a two dimensional array variable
- Get the order from the user
- If the order is 1 then perform row-major order and display the result
- If the order is 2 then perform column-major order and display the result
- If the order is 3 then exit
- Stop
Logical Description
A matrix that has relatively few non-zero entries. It may be represented in much less than n × m space. An n × m matrix with k non-zero entries is sparse if k < n × m. It may be faster to represent the matrix compactly as a list of the non-zero indexes and associated entries, as a list of lists of entries (one list for each row), coordinate format (the values and their row/column positions), or by a point access method.
Program Code
#include<stdio.h>
void main()
{
int a[10][10],s[10][10];
int i,j,m,n,k=0,l=0;
clrscr();
printf("\n Enter the no of rows: ");
scanf("%d",&n);
printf("\n Enter the no of columns: ");
scanf("%d",&m);
printf("\n Enter the elements in the array : ");
for(i=0;i<n;i++)
for(j=0;j<m;j++)
scanf("%d",&a[i][j]);
printf("\n Elements of the matrix \n : ");
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
printf("\t %d",a[i][j]);
printf("\n");
}
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
if(a[i][j]!=0)
{
s[k][l]=i;
s[k][++l]=j;
s[k][++l]=a[i][j];
k++;
l=0;
}
}
}
printf("\n Elements of sparse matrix \n: ");
for(i=0;i<k;i++)
{
for(j=0;j<3;j++)
printf("\t %d",s[i][j]);
printf("\n");
}
getch();
}
Expected Output:
Enter the no of rows: 3
Enter the no of columns: 3
Enter the elements in the array :
1
0
7
5
0
0
3
4
7
Elements of the matrix:
1 0 7
5 0 0
3 4 7
Elements of sparse matrix:
0 0 1
0 2 7
1 0 5
2 0 3
2 1 4
2 2 7
Ex. No : 2 /Create a Stack and do the basic operations using Arrays
Date :Aim: To write a program to create a Stack and manipulate it using one dimensional Array
Algorithm:
- Start
- Declare an one dimensional array variable
- Using Switch case statement select one appropriate operation
- PUSH:
- Read an element
- Store it at the top of the stack
- Increment the TOS
- POP
- Read the element from the top of the stack
- Display it
- Decrement the TOS
- PEEK
- Read the element from the top of the stack
- Display it
- Stop
Logical Description
The program implements the Stack using one dimensional array. Initially an array variable is declared, and variable TOS is to point the top of the stack is also declared. PUSH operation is done by reading an element from the user and storing it at TOS position. POP operation retrieves the value at TOS and removes the element; TOS now points the next element. PEEK operation retrieves the element but it is not deleted from the stack.
Program Code
/*Stack Using Arrays*/
#include<stdio.h>
#include<conio.h>
#define SIZE 4
int a[SIZE],top=0,ch=1,i,n;
void display();
void create();
void push();
void pop();
void peek();
void main()
{
clrscr();
printf("\n\t\tStack Using Arrays");
printf("\n\t\t------");
printf("\n\t\t 1.Create");
printf("\n\t\t 2.Push");
printf("\n\t\t 3.Pop");
printf("\n\t\t 4.Peek");
printf("\n\t\t 5.Exit\n");
do
{
printf("\t\tEnter Your Choice :");
scanf("%d",&ch);
switch(ch)
{
case 1: create();break;
case 2: push();break;
case 3: pop();break;
case 4: peek();break;
default: printf("\t\tExit");
break;
}
}while(ch!=5);
getch();
}
void create()
{
if(top==0)
{
printf("\t\tNumber of Element:");
scanf("%d",&n);
if(n>SIZE)
printf("\t\tSize of Stack is Large\n");
else
{
printf("\t\tPushing Element :");
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
top=n;
display();
}
}
else
{
printf("\tStack Already Exists");
}
}
void push()
{
if(top==SIZE)
printf("\t\tStack Overflow\n");
else
{
printf("\t\tPushing Element :");
scanf("%d",&a[++top]);
display();
}
}
void pop()
{
if(top==0)
printf("\t\tStack Underflow\n");
else
{
printf("\t\tPop Element :%d\n",a[top--]);
display();
}
}
void display()
{
if(top==0)
printf("\t\tStack is Empty");
else
{
printf("\t\tStack Contains :");
for(i=top;i>=1;i--)
printf("%d ",a[i]);
}
printf("\n");
}
void peek()
{
if(top==0)
printf("\t\tStack Empty\n");
else
printf("\t\tTop Element is %d\n",a[top]);
}
Expected Output
IMPLEMENTATION OF STACK USING ARRAYS
Choose the option
- Push
- Pop
- Peek
- Display
- Exit
Enter your option:1
Enter the element to be pushed into the stack: 12
Choose the option
- Push
- Pop
- Peek
- Display
- Exit
Enter your option:1
Enter the element to be pushed into the stack: 15
Choose the option
- Push
- Pop
- Peek
- Display
- Exit
Enter your option:1
Enter the element to be pushed into the stack: 34
Choose the option
- Push
- Pop
- Peek
- Display
- Exit
Enter your option:4
The elements in the stack are: 12
15
34
Choose the option
- Push
- Pop
- Peek
- Display
- Exit
Enter your option:2
The Popped value is: 34
Choose the option
- Push
- Pop
- Peek
- Display
- Exit
Enter your option:4
The elements in the stack are: 12
15
Choose the option
- Push
- Pop
- Peek
- Display
- Exit
Enter your option:3
The Popped value is: 15
Ex. No : 3 /Create a Queue and do the basic operations using Arrays
Date :Aim: To write a program to create a Queue using one dimensional Array
Algorithm:
- Start
- Read ch and n value
- check (ch!=4) and if (rear =n) then read value
- Assign value to q(rear) and increment the rear, else Display as queue if full
- if (front=rear) then print front value of queue and increment front
Else Display as queue is empty
- if (rear=0) then assign front to I and write q[i].
Else Display as queue is empty
- Go to step 3
- stop
Logical Description
A collection of items in which only the earliest added item may be accessed. Basic operations are add (to the tail) or enqueue and delete (from the head) or dequeue. Delete returns the item removed. Also known as "first-in, first-out" or FIFO.
Formal Definition: It is convenient to define delete or dequeue in terms of remove and a new operation, front. The operations new(), add(v, Q), front(Q), and remove(Q) may be defined with axiomatic semantics as follows.
- new() returns a queue
- front(add(v, new())) = v
- remove(add(v, new())) = new()
- front(add(v, add(w, Q))) = front(add(w, Q))
- remove(add(v, add(w, Q))) = add(v, remove(add(w, Q)))
Program Code
#include<stdio.h>
#include<conio.h>
void main()
{
int q[50],i,j,n,op,front,rear,no;
clrscr();
printf("Enter the size of the queue:");
scanf("%d",&n);
printf("QUEUE OPERATIONS:\n1.Insert\n2.Delete\n3.Display\n4.Exit\n");
printf("Enter the operation to be performed:");
scanf("%d",&op);
front=0;rear=-1;
while(op!=4){
switch(op)
{
case 1:{
if(rear==n-1)
printf("\nQueue is full!\n");
else
{
printf("Enter the element to be inserted:");
scanf("%d",&no);
q[++rear]=no;
printf("\n%d is inserted!",no);
}
break;}
case 2:{
if(front==0 & rear==-1)
printf("\nQueue is empty!");
else
{
printf("\n%d is deleted!",q[front]);
q[front]=0;
for(j=front;j<rear;j++)
q[j]=q[j+1];
rear=rear-1;
}
break;}
case 3:{
printf("\nQueue is:\n");
for(i=front;i<=rear;i++)
printf("%d\t",q[i]);
break;}
}
printf("\nEnter the operation to be performed:");
scanf("%d",&op);
}
getch(); }
Expected Output
Enter the size of the queue:3
QUEUE OPERATIONS:
1.Insert
2.Delete
3.Display
4.Exit
Enter the operation to be performed:1
Enter the element to be inserted:12
12 is inserted!
Enter the operation to be performed:1
Enter the element to be inserted:32
32 is inserted!
Enter the operation to be performed:3
Queue is:
12 32
Enter the operation to be performed:2
12 is deleted!
Enter the operation to be performed:3
Queue is:
32
Enter the operation to be performed:2
32 is deleted!
Enter the operation to be performed:2
Queue is empty!
Enter the operation to be performed:3
Queue is:
Enter the operation to be performed: 4
Ex. No : 4 /Implement the basic operations on Singly Linked List
Date :Aim: To write a program to implement the basic operations on Singly Linked List
Algorithm:
- Start
- Read the value of ch
- If ch =1 then read item of number
set n as malloc to size, set n of into as num and next as list
- If ch=2 to check if list =0 then print “Empty list”
elseif n is list then delete the node n
- If ch=3 then read position value and set n as malloc size and read num value and store in n.
- If ch =4 then check list as NULL or not. If NULL then print “ Empty list”
Else check I not equal to pos then print info of p then delete the node p
- If ch=5 then set n and allocate malloc size and read num.
Else next not as Null then n as next of p
- If ch=6 then check pos Null and print “Empty list”
Else delete the node p
- stop
Logical Description
The singly-linked list is the most basic of all the linked data structures. A singly-linked list is simply a sequence of dynamically allocated objects, each of which refers to its successor in the list. Despite this obvious simplicity, there are myriad implementation variations.
Program Code
struct node
{
int data;
struct node *link;
}*head;
typedef struct node node;
void maintain(void);
void create(node *);
void insertion(node *);
void deletion(node *);
void display(node *);
int count=0;
#include"stdio.h"
#include"alloc.h"
main()
{
head=malloc(sizeof(node));
create(head);
maintain();
getch();
return;
}
void maintain()
{
int n;
clrscr();
printf(" MAINTANENCE\n\n1. Insertion\n2. Deletion\n3. Display\n4. Exit");
printf("\n\nYour choice: ");
scanf("%d",&n);
switch(n)
{
case 1:
{
insertion(head);
break;
}
case 2:
{
deletion(head);
break;
}
case 3:
{
display(head);
break;
}
case 4:
{
exit();
}
}
}
void create(node *p)
{
int i;
node *q;
clrscr();
printf("\nCreation of Linked List\n");
printf("\nEnter the data('0' to terminate)\n");
scanf("%d",&i);
p->data=i; count++;
scanf("%d",&i);
while(i!=0)
{
q=malloc(sizeof(node));
q->data=i; count++;
p->link=q;
scanf("%d",&i);
if(i!=0)
{
p=malloc(sizeof(node));
p->data=i; count++;
q->link=p;
}
else
{
q->link=NULL;
return;
}
scanf("%d",&i);
}
p->link=NULL;
maintain();
}
void insertion(node *p)
{
int n,m,i=1;
node *new,*next,*tail;
clrscr();
while(i==1)
{
clrscr();
p=head;
printf("\tINSERTION\n\n1. Insertion at first\n2. Insertion at last\n3. Insertion
inbetween\n\nYour choice: ");
scanf("%d",&n);
printf("\nEnter the data: ");
scanf("%d",&i);
new=malloc(sizeof(node));
new->data=i;
switch(n)
{
case 1:
{
new->link=head;
head=new;
count++; break;
}
case 2:
{
while(p->link!=NULL)
p=p->link;
p->link=new;
new->link=NULL;
count++; break;
}
case 3:
{
printf("\nEnter the location: ");
scanf("%d",&n);
if(n<2 || n>=count)
{
clrscr();
printf("Sorry!!! Location doesn't fall within the limit");
break;
}
m=1;
while(m<n-1)
{
p=p->link;
m++;
}
next=p->link;
p->link=new;
new->link=next;
count++; break;
}
}
printf("\n\nDo you want to continue insertion(1/0): ");
scanf("%d",&i);
}
maintain();
}
void deletion(node *p)
{
int n,m,i=1;
node *next,*tail;
clrscr();
while(i==1)
{
clrscr();
p=head;
printf("\tDELETION\n\n1. Deletion at first\n2. Deletion at last\n3. Deletion
inbetween\n\nYour choice: ");
scanf("%d",&n);
switch(n)
{
case 1:
{
head=head->link;
count--; break;
}
case 2:
{
while((p->link)->link!=NULL)
p=p->link;
p->link=NULL;
count--; break;
}
case 3:
{
printf("\nEnter the location: ");
scanf("%d",&n);
if(n<2 || n>=count)
{
clrscr();
printf("Sorry!!! Location doesn't fall within the limit");
break;
}
m=1;
while(m<n-1)
{
p=p->link;
m++;
}
next=p->link;
p->link=next->link;
count--; break;
}
}
printf("\n\nDo you want to continue deletion(1/0): ");
scanf("%d",&i);
}
maintain();
}
void display(node *p)
{
clrscr();
printf("\nCreated List");
printf("\n\nTotal no of elements %d\n",count);
while(p!=NULL)
{
printf("%d ",p->data);
p=p->link;
}
getch();
maintain();
}
Expected Output
Creation of Linked List
Enter the data('0' to terminate)
2 3 4 6 7 8 9 0
MAINTANENCE
1. Insertion
2. Deletion
3. Display
4. Exit
Your choice: 1
INSERTION
1. Insertion at first
2. Insertion at last
3. Insertion inbetween
Your choice: 1
Enter the data: 1
Created List
Total no of elements 7
1 2 3 4 6 7 8 9
Do you want to continue insertion(1/0):
Ex. No : 5 /Represent the given sparse matrix using Linked List
Date :Aim: To write a program to represent Sparse Matrix using Linked list
Algorithm:
- start
- Enter the row and column matrix
- Read the value of m and n
- Set for loop i< row as i=1 and another loop i < col as j=1
- Read value of x
Next j and i
- If we choose insert then check if (sparse == Null ) then sparse =p
Else check while (q-> next != Null ) then q = q-> next; q-> next =p
- If we choose display than for i=1 to r then check p=p->next
- stop
Logical Description
A matrix that has relatively few non-zero entries. It may be represented in much less than n × m space.
An n × m matrix with k non-zero entries is sparse if k < n × m. It may be faster to represent the matrix compactly as a list of the non-zero indexes and associated entries, as a list of lists of entries (one list for each row), coordinate format (the values and their row/column positions), or by a point access method. It is implemented with linked list
Program Code
#include<stdio.h>
struct node
{
int row;
int col;
int data;
struct node *link;
}*head=NULL,*curr=NULL,*p=NULL;
void main()
{
int i,j,m,n,a[50][50];
clrscr();
printf("\nSparse Matrix using Linked List\n");
printf("\nEnter the number of rows of the matrix:");
scanf("%d",&m);
printf("Enter the number of columns of the matrix:");
scanf("%d",&n);
printf("Enter the elements:");
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&a[i][j]);
if(a[i][j]!=0)
{
curr=(struct node*)malloc(sizeof(struct node));
curr->row=i;
curr->col=j;
curr->data=a[i][j];
curr->link=NULL;
if(head==NULL)
head=curr;
else
{
p=head;
while(p->link!=NULL)
p=p->link;
p->link=curr;
}
}
}
}
printf("\nSparse matrix using linked list:\nRow\tColumn\tElement\t\n");
p=head;
if(head==NULL)
printf("\nSparse matrix empty!\n");
else
{
while(p->link!=NULL)
{
printf("%d\t%d\t%d\n",p->row,p->col,p->data);
p=p->link;
}
printf("%d\t%d\t%d\n",p->row,p->col,p->data);
}
getch();
}
Expected Output:
Sparse Matrix using Linked List
Enter the number of rows of the matrix:3
Enter the number of columns of the matrix:3
Enter the elements:
1
8
0
0
7
0
7
0
0
Sparse matrix using linked list:
Row Column Element
0 0 1
0 1 8
1 1 7
2 0 7
Ex. No : 6 /Create a Stack and do the basic operations using Linked List
Date :Aim : To write a program to create Stack using Linked list
Algorithm :
- Start
- Read the value of ch
- Allocate the malloc size to a variable
- Get the item and store in data then link to Null value
- Link the temp to top. Then check the top is Null then display as “ Stack is Empty”
- If not as Null then print the top value
- Print data as temp becomes Null
- Stop
Logical Description
The stack is a common data structure for representing things that need to maintain in a particular order. Conceptually, a stack is simple: a data structure that allows adding and removing elements in a particular order. Every time an element is added, it goes on the top of the stack; the only element that can be removed is the element that was at the top of the stack. Consequently, a stack is said to have "first in last out" behavior (or "last in, first out"). The first item added to a stack will be the last item removed from a stack.
Stacks have some useful terminology associated with them:
- Push To add an element to the stack
- Pop To remove an element from the stock
- Peek To look at elements in the stack without removing them
- LIFO Refers to the last in, first out behavior of the stack
Program Code
#include<stdio.h>
#include<conio.h>
struct node
{
int data;
struct node* link;
}*head,*top,*curr;
void push(int data)
{
curr=(struct node*)malloc(sizeof(struct node));
curr->data=data;
curr->link=NULL;
if(top==NULL)
{
head=curr;
top=curr;
}
else
{
top->link=curr;
top=curr;
}
}
int pop()
{
int d=0;
d=top->data;
curr=head;
if(curr->link==NULL)
{
head=NULL;
top=NULL;
}
else
{
while(curr->link->link!=NULL)
{
curr=curr->link;
}
curr->link=NULL;
top=curr;
}
return d;
}
int peep()
{
return top->data;
}
void main()
{
int op,data;
clrscr();
do
{
printf("\nSTACK OPERATIONS:\n1.Push\n2.Pop\n3.Peep\n4.Exit\n");
printf("Enter the operation to be performed:");
scanf("%d",&op);
switch(op)
{
case 1:
{
printf("Enter the elemen to b pushed:");
scanf("%d",&data);
push(data);
break;
}
1case 2:
{
printf("Popped element: %d",pop());
break;
}
case 3:
{
printf("Peeped element: %d",peep());
break;
}
case 4:
break;
default:
{
printf("\nEnter a proper option!\n");
}
}
}while(op!=4);
getch();
}
Expected Output
STACK OPERATIONS:
1.Push
2.Pop
3.Peep
4.Exit
Enter the operation to be performed:1
Enter the elemen to b pushed:12
STACK OPERATIONS:
1.Push
2.Pop
3.Peep
4.Exit
Enter the operation to be performed:1
Enter the elemen to b pushed:70
STACK OPERATIONS:
1.Push
2.Pop
3.Peep
4.Exit
Enter the operation to be performed:3
Peeped element: 70
STACK OPERATIONS:
1.Push
2.Pop
3.Peep
4.Exit
Enter the operation to be performed:2
Popped element: 70