Data structures and algorithms Lab manual for II year IT

Department of Information Technology

LAB MANUAL

IT2205 – Data Structures and Algorithm Lab

(III Semester IT)

Prepared by,
L.Priya
(Senior Lecturer /IT)

RAJALAKSHMI ENGINEERING COLLEGE

Rajalakshmi Nagar, Thandalam, Chennai – 602 105

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

INDEX

1. Array Implementation Of Stack

2. Application Of Stack – Conversion Of Infix To Postfix

3. Implementation Of Linear Queue Using Arrays

4. Array Implementation Of Circular Queue

5. Linked List Implementation Of Stack

6. Singly linked list – Linked list implementation

7. Doubly linked list – Linked list implementation

8. Polynomial Manipulation

9. Tree Traversals

10. Expression Tree

11. Priority Queue Using Heap

12. Hashing Technique

13. Dijkstra’s Algorithm

14. Back tracking algorithm – knap sack problem

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

Ex. no.: 1

Date :

ARRAY IMPLEMENTATION OF STACK

Aim
To write a C-program to implement stack using array data structure.
And perform the following stack operations
1. POP
2. PUSH
3. PEEP

Algorithm
STEP 1:Start
STEP 2:Initialize stack, will=1,i, num
STEP 3:Add element in stack
PUSH(S,TOP,X)
3.a. [Check overflow condition]
If(TOP>=N) then
Write(“Stack is full”)
3.b. [Insert element]
[Increment TOP]
TOP <- TOP+1
S[TOP]<- X
3.c. [Finish the process]
STEP 4: Delete element in stack
POP(S,TOP)
4.a. [Check for underflow condition]
If(TOP <- 0) then
Write(“Stack is empty”)

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

4.b. [Delete element]

[Decrement TOP]
TOP<- TOP-1
Delete S[TOP+1]
4.c.[Finish the process]
STEP 5:Stop
Coding:

#include<stdio.h>
#include<conio.h>
#define size 10
int stack[size],top=0,b;
int res;
void push();
void pop();
void display();
void main()
{
int c;
clrscr();
printf("\n1.Push\n2.Pop\n3.Display");
do
{
printf("\n\nEnter your Choice :: ");
scanf("%d",&c);
switch(c)
{
case 1:

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

push();
break;
case 2:
pop();
break;
case 3:
printf("\n\nContents of stack is \t");
display();
break;
default:
printf("\nInvalid Choice......");
exit(0);
}
}while(c<4);
getch();
}
void push()
{
if(top>=size)
{
printf("\nStack Overflow");
return;
}
else
{
printf("\nEnter the number to be pushed into the stack :: ");
scanf("%d",&b);
top++;

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

stack[top]=b;
printf("\nNumber pushed is %d",stack[top]);
return;
}
}
void pop()
{
if(top==0)
{
printf("\nStack Underflow");
return;
}
else
{
res=stack[top];
top--;
printf("\nDeleted element is %d",res);
return;
}
}
void display()
{
int i;
if(top==0)
{
printf("\nStack Underflow");
return;
}

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

for(i=top;i>0;i--)
printf("%d , ",stack[i]);
}

Output:

1.Push
2.Pop
3.Display

Enter your Choice :: 1

Enter the number to be pushed into the stack :: 3

Number pushed is 3

Enter your Choice :: 1

Enter the number to be pushed into the stack :: 5

Number pushed is 5

Enter your Choice :: 3

Contents of stack is 5,3,

Enter your Choice :: 2

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

Deleted element is 5

Enter your Choice :: 3

Contents of stack is 3,

Enter your Choice :: 8

Invalid Choice......

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

Ex. No.:2
Date :

CONVERSION OF INFIX EXPRESSION TO POSTFIX

Aim
To write a C-program to convert the given infix expression to its postfix format.

Algorithm

STEP 1: Start
STEP 2: Initialize the stack.
STEP 3: While (INSTR!= NULL)
STEP 4: CH= get the character from INSTR.
STEP 5: If( CH= = operand) then
append CH int POSTSTR
else if(CH = = ‘(‘) then
push CH into stack
else if(CH = =’)’) then
pop the data from the stack and append the data into POSTSTR until we get
‘(‘ from the stack
else
while(precedence (TOP) >= precedence (CH))
pop the data from stack and append the data into POSTSTR.
[End of while structure]
[End of if structure]

STEP 6: Push CH into the stack.

STEP 7: [End of second while structure]

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

STEP 8: pop all the data from stack and append data into POSTSTR.
STEP 9: Stop
Coding:
#include<stdio.h>
#include<conio.h>
int stack[20],top=0;
char inf[40],post[40];
void push(int);
void postfix();
char pop();
void main(void)
{
clrscr();
printf("\t\t\t****INFIX TO POSTFIX****\n\n");
printf("Enter the infix expression :: ");
scanf("%s",inf);
postfix();
getch();
}
void postfix()
{
int i,j=0;
for(i=0;inf[i]!=NULL;i++)
{
switch(inf[i])
{
case '+':
while(stack[top]>=1)

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

post[j++]=pop();
push(1);
break;
case '-':
while(stack[top]>=1)
post[j++]=pop();
push(2);
break;
case '*':
while(stack[top]>=3)
post[j++]=pop();
push(3);
break;
case '/':
while(stack[top]>=3)
post[j++]=pop();
push(4);
break;
case '^':
while(stack[top]>=4)
post[j++]=pop();
push(5);
break;
case '(':
push(0);
break;
case ')':
while(stack[top]!=0)

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

post[j++]=pop();
top--;
break;
default:
post[j++]=inf[i];
}
}
while(top>0)
post[j++]=pop();
printf("\nPostfix Expression is :: %s",post);
}
void push(int ele)
{
top++;
stack[top]=ele;
}
char pop()
{
char e;
e=stack[top];
top--;
switch(e)
{
case 1:
e='+';
break;
case 2:
e='-';

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

break;
case 3:
e='*';
break;
case 4:
e='/';
break;
case 5:
e='^';
break;
}
return(e);
}

Output:

Enter the infix expression :: (a+b)/(c*d)

Postfix Expression is :: ab+cd*/

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

Manual Calculation

SE EXPRESSION STACK RESULT FIELD

( (

A A

+ +,( A

B +,( AB

) ),( AB+

/ / AB+

( (,/

C (,/ AB+C

- -,(,/ AB+C

D -,(,/ AB+CD

+ +,(,/ AB+CD-

E +,(,/ AB+CD-E

) ),+,(,/ AB+CD-E+

+ +,/ AB+CD-E+/

F + AB+CD-E/F

- - AB+CD-E/F+

G - AB+CD-E/F+G

AB+CD-E/F+G-

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

Ex.no.3
Date:

IMPLEMENTATION OF LINEAR QUEUE USING ARRAYS

Aim
To write a C-program to implement linear queue data structure using arrays.

Algorithm
STEP 1: Start
STEP 2: [Include all header files]
STEP 3: [Declare the variables]
STEP 4: [If n->1 call the function Enqueue( )]
STEP 5: [If n->2 call the function Dequeue( )]
STEP 6: [If n->3 call the function Peep( )]
STEP 7: [If n->4 call the function Size( )]
STEP 8: [If n->5 call the function View( )]
STEP 9: [else Exit( )]
STEP 10: Stop

Algorithm for Enqueue( )

STEP 1: If[front= =rear]
Initialize front=rear=0
STEP 2: else rear=(rear+1)% qsize
Set queue[rear] =value
[return]
Algorithm for Dequeue( )
STEP 1: If[front = =rear]
1.1: temp=queue[front]

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

1.2: Initialize front=rear=-1

STEP 2:else
2.1: front=(front+1)% qsize
[return]

Algorithm for Peep( )

STEP 1:If [front= =rear]
STEP 1.1: temp=queue[front]
[return]

Algorithm for Size( )

STEP 1:If [front= =rear]

1.1: Set f=front
1.2: Set count=1
STEP 2: If [front!=rear]
2.1: front=(front+1)%qsize
2.2: set count=count+1
[return]

Algorithm for View( )

STEP 1: If [front = =rear]

Write (“Queue is empty”)
STEP 2: else
[display elements]

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

Coding:
#include<stdio.h>
#include<conio.h>
#define size 15
int queue[size],front=0,rear=0,b;
int res;
void enqueue();
void dequeue();
void display();
void main()
{
int c;
clrscr();
printf("\n1.Insertion\n2.Deletion\n3.Display");
do
{
printf("\n\nEnter your Choice :: ");
scanf("%d",&c);
switch(c)
{
case 1:
enqueue();
break;
case 2:
dequeue();
break;

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

case 3:
printf("\n\nContents of queue is \t");
display();
break;
default:
printf("\nInvalid Choice......");
exit(0);
}
}while(c<4);
getch();
}
void enqueue()
{
if(rear>=size)
{
printf("\nOverflow");
return;
}
else
{
printf("\nEnter the number to be entered :: ");
scanf("%d",&b);
rear++;
queue[rear]=b;
printf("\nNumber pushed is %d",queue[rear]);
if(front==0)
front=1;
return;

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

}
}
void dequeue()
{
if(front==0)
{
printf("\nUnderflow");
return;
}
else
{
res=queue[front];
if(front==rear)
{
front=0;
rear=0;
}
else
front++;
}
printf("\nDeleted element is %d",res);
return;
}
void display()
{
int i;
if(front==0)
{

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

printf("\nUnderflow");
return;
}
for(i=front;i<=rear;i++)
printf("%d , ",queue[i]);
}

Output:

1.Insertion
2.Deletion
3.Display

Enter your Choice :: 1

Enter the number to be entered :: 12

Number pushed is 12

Enter your Choice :: 1

Enter the number to be entered :: 2

Number pushed is 2

Enter your Choice :: 3

Contents of queue is 12 , 2 ,

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

Enter your Choice :: 2

Deleted element is 12

Enter your Choice :: 3

Contents of queue is 2,

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

Ex.No.4
Date:

ARRAY IMPLEMENTATION OF CIRCULAR QUEUE

Aim
To write a c program using arrays for implementing circular queue data structure.

Algorithm

Step 1: [Include All Header Files Required]

Step 2: [Define the array size as 5 and declare front and rear pointers]
Step 3: Declare the functions isEmpty() , isFull(), enqueue(), size(),dequeue(), peek() and
view()]
Step 4: [Call the functions]
Choice :1 CALL enqueue()
Choice :2 CALL deenqueue()
Choice :3 CALL peek()
Choice :4 CALL size()
Choice :5 CALL view()

Algorithm for isEmpty( )

Step 1: [Check for underflow]

If ( front -1 and rear -1 )
RETURN -1
Step 2: Else RETURN 0
[Finish the process]

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

Algorithm for isFull( )

Step 1: [Check for overflow]

If (= (rear+1)% qsize front )
RETURN -1
Step 2: Else RETURN 0
[Finish the process]

Algorithm for Enqueue( )

STEP 1: If[front= =rear]

Initialize front=rear=0
STEP 2: else rear=(rear+1)% qsize
Set queue[rear] =value
[return]

Algorithm for Dequeue( )

STEP 1: If[front = =rear]

1.1: temp=queue[front]
1.2: Initialize front=rear=-1
STEP 2:else
2.1: front=(front+1)% qsize
[return]

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

Algorithm for Peek( )

STEP 1:If [front= =rear]

STEP 1.1: temp=queue[front]
[return]
Algorithm for Size( )

STEP 1:If [front= =rear]

1.1: Set f=front
1.2: Set count=1
STEP 2: If [front!=rear]
2.1: front=(front+1)%qsize
2.2: set count=count+1
[return]

Algorithm for View( )

STEP 1: If [front = =rear]

Write (“Queue is empty”)
STEP 2: else
[display elements]

Coding:
#include<stdio.h>
#include<conio.h>
#define qsize 5

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

int queue[qsize],front=-1,rear=-1;
void enqueue(int value);
void dequeue();
void view();
void main()
{
int c,data,item;
clrscr();
printf("\n1.ENQUEUE\n2.DEQUEUE\n3.VIEW");
while(1)
{
printf("\n\nEnter your Choice :: ");
scanf("%d",&c);
switch(c)
{
case 1:
printf("\nEnter the element::");
scanf("%d",&data);
enqueue(data);
break;
case 2:
dequeue();
break;
case 3:
printf("\n\nContents of circular queue is \t");
view();
break;
default:

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

printf("\nInvalid Choice......");
exit(0);
}
}
}
int isfull()
{
extern int queue[],front,rear;
if(front==(rear+1)%qsize)
return(1);
else
return(0);
}
int isempty()
{
extern int queue[],front,rear;
if((front==-1)&&(rear==-1))
return(1);
else
return(0);
}
void enqueue(int value)
{
extern int queue[],front,rear;
if(isfull())
{
printf("\nOverflow");
return;

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

}
else
{
if(isempty())
front=rear=0;
else
rear=(rear+1)%qsize;
queue[rear]=value;
}
}
void dequeue()
{
int value;
extern int queue[],front,rear;
if(isempty())
printf("\n\nQueue is Empty");
else
{
value=queue[front];
printf("\nDequeue value is %d",value);
}
if(front==rear)
{
front=-1;
rear=-1;
}
else
front=(front+1)%qsize;

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

}
void view()
{
extern int queue[],front,rear;
int f;
if(isempty())
printf("\nUnderflow");
else
{
printf("\nFront-->");
for(f=front;f!=rear;f=(f+1)%qsize)
printf("%d ---> ",queue[f]);
printf("%d <--Rear",queue[f]);
}
if(isfull())
printf("\nQueue is full");
}

Output

1.ENQUEUE
2.DEQUEUE
3.VIEW

Enter your Choice :: 1

Enter the element::2

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

Enter your Choice :: 3

Contents of circular queue is

Front-->2 <--Rear

Enter your Choice :: 1

Enter the element::3

Enter your Choice :: 1

Enter the element::5

Enter your Choice :: 3

Contents of circular queue is

Front-->2 ---> 3 ---> 5 <--Rear

Enter your Choice :: 2

Dequeue value is 2

Enter your Choice :: 3

Contents of circular queue is

Front-->3 ---> 5 <--Rear

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

Enter your Choice :: 4

Invalid Choice......

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

Ex.no.:5
Date :

LINKED LIST IMPLEMENTATION OF STACK

Aim
To demonstrate linked list implementation of stack using a C program.

Algorithm

Step 1: [Include all the necessary header files]

Step 2: [Declare the Variables]
Step 3: Read operator
Step 4: IF opt 1 THEN
Step 4.1: READ n
Step 4.2: WHILE (n n-1)
Step 4.2.1: READ d
Step 4.2.2: CALL INSERT( start , d)
Step 4.3: [End of while Structure]
Step 5: IF opt 2 THEN
Step 5.1: READ x
Step 5.2: CALL del(start,x)
Step 6: IF opt 3 THEN
Step 6.1: READ x
Step 6.2: CALL FIND
Step 7: IF opt 4 THEN
Step 7.1: READ x

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

Step 7.2: CALL FINDPREVIOUS

Step 8: IF opt 5 THEN
Step 8.1: READ x
Step 8.2: CALL FINDNEXT(start, x)
Step 9: IF opt 6 THEN
CALL len(Start)
Step 10: IF opt 7 THEN
CALL printlist(Start)
Step 10: IF opt 8 THEN
CALL erase (Start)
Step 12: [End of Main]

Algorithm For Find(struct node*p, int x, int *pos)

Step 1: temp p
Step 2 :*pos 1
Step 3: IF ( TEMP NULL) THEN
RETURN NULL
ELSE
WHILE ( TEMP!= NULL && TEMP DATA!= X)
ASSIGN 1 TO *POS+1 AND TEMP’S LLINK FIELD TO TEMP
RETURN THE TEMP

Algorithm for Previous (struct node*p, int x)

Step 1: temp p
Step2: IF ( TEMP NULL) THEN
RETURN NULL
ELSE
WHILE (TEMP LINK != NULL && TEMP LINK DATA!= X)

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

ASSIGN TEMP’S LINK FIELD TO TEMP

RETURN THE TEMP

Algorithm For Find next(struct node*p, int x)

Step 1: temp p
Step2: IF ( TEMP NULL) THEN
RETURN NULL
ELSE
WHILE (TEMP LINK != NULL && TEMP DATA!= X)
ASSIGN TEMP’S LLINK FIELD TO TEMP
RETURN THE TEMP’S LINK FIELD

Coding:
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
push();
void pop();
void display();
struct node
{
int data;
struct node *next;
}*top=NULL;

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

void main()
{
int ch;
clrscr();
printf("\n\n1.Push\n\n2.Pop\n\n3.Display");
do
{
printf("\n\nEnter your Choice :: ");
scanf("%d",&ch);
switch(ch)
{
case 1:
push();
break;
case 2:
pop();
break;
case 3:
printf("\n\nContents of stack :: \t");
display();
break;
default:
printf("\n\nInvalid Choice......");
getch();
exit(0);
}
}while(ch<4);
getch();

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

}
push()
{
int x;
struct node *newnode;
newnode=malloc(sizeof(struct node));
printf("\n\nEnter the number to be pushed into the stack :: ");
scanf("%d",&x);
newnode->data=x;
if(top==NULL)
{
newnode->next=top;
top=newnode;
}
else
{
newnode->next=top;
top=newnode;
}
printf("\n\nNumber pushed is %d",x);
return(x);
}
void pop()
{
struct node *t;
if(top==NULL)
printf("\n\nStack Underflow");
else

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

{
t=top;
top=top->next;
printf("\nDeleted element is %d",t->data);
free(t);
}
getch();
}
void display()
{
struct node*i;
for(i=top;i!=NULL;i=i->next)
printf("%d , ",i->data);
if(top==NULL)
printf("Stack is empty");
getch();
}

Output:

1.Push
2.Pop
3.Display

Enter your Choice :: 1

Enter the number to be pushed into the stack :: 5

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

Number pushed is 5

Enter your Choice :: 1

Enter the number to be pushed into the stack :: 10

Number pushed is 10

Enter your Choice :: 3

Contents of stack :: 10 , 5 ,

Enter your Choice :: 2

Deleted element is 10

Enter your Choice :: 3

Contents of stack :: 5 ,

Enter your Choice :: 5

Invalid Choice......

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

Ex.no.:6
Date :

LINKED LIST IMPLEMENTATION OF SINGLY LINKED LIST

Aim:
To write a program to implement singly linked list using linked list.
Algorithm:
Step 1: initialize the list as null
Step 2: Display linked list operations insert, delete and display the result.
Step 3: If choice is 1 the read element to be inserted and call the insert function
Step 4: If choice is 2 then read element to be deleted and call the delete function
Step 5: If choice is 3 then call display function
Step 6: If choice is default the exit the program.
Program:
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
void insert(int x);
void deletion(int x);
void display();
struct node
{
int element;
struct node *next;
}*list=NULL,*p;
struct node *find(int s)
{

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

p=list->next;
while(p!=NULL && p->element!=s)
p=p->next;
return p;
}
struct node *findprevious(int s)
{
p=list;
while(p->next!=NULL && p->next->element!=s)
p=p->next;
return p;
}
void main()
{
int data,ch;
clrscr();
printf("\n\n1.INSERT\n\n2.DELETE\n\n3.DISPLAY");
do
{
printf("\n\nEnter your Choice :: ");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("\n\nEnter the element to be inserted::");
scanf("%d",&data);
insert(data);
break;

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

case 2:
printf("\n\nEnter the element to be deleted::");
scanf("%d",&data);
deletion(data);
break;
case 3:
display();
break;
default:
printf("\n\nInvalid Choice......");
getch();
exit(0);
}
}while(ch<4);
}
void insert(int x)
{
struct node *newnode;
int pos;
newnode=malloc(sizeof(struct node));
newnode->element=x;
if(list->next==NULL)
{
list->next=newnode;
newnode->next=NULL;
}
else
{

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

printf("\n\nEnter the value of the element to be inserted ::");

scanf("%d",&pos);
p=find(pos);
newnode->next=p->next;
p->next=newnode;
}
}
void deletion(int x)
{
struct node *temp;
temp=malloc(sizeof(struct node));
p=findprevious(x);
if(p->next!=NULL)
{
temp=p->next;
p->next=temp->next;
printf("\n\nThe deleted element is %d",temp->element);
free(temp);
}
else
printf("\n\nElement is not found in the list!!!");
}
void display()
{
if(list->next==NULL)
printf("\n\nList is empty!!!");
else
{

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

p=list->next;
printf("\n\nThe contents of the list are\n::");
while(p!=NULL)
{
printf("%d ->",p->element);
p=p->next;
}
}
}

Output:

1.INSERT
2.DELETE
3.DISPLAY

Enter your Choice ::1

Enter the element to be inserted::2

Enter your Choice ::1

Enter the element to be inserted::5

Enter the value of the element to be inserted ::2

Enter your Choice :: 3

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

The contents of the list are::2 ->5 ->NULL

Enter your Choice :: 1

Enter the element to be inserted::7

Enter the value of the element to be inserted ::2

Enter your Choice :: 3

The contents of the list are ::2 ->7 ->5 ->NULL

Enter your Choice :: 2

Enter the element to be deleted::5

The deleted element is 5

Enter your Choice :: 3

The contents of the list are ::2 ->7 ->NULL

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

Ex.no.7
Date:

DOUBLY LINKED LIST – LINKED LIST IMPLEMENTATION

Aim:
To write a program to implement doubly linked list using linked list.
Algorithm:
Step 1: Declare header and pointer variables
Step 2: Display the choices
Step 3: If choice is 1 the get the element to be inserted in beginning and call ins_beg function.
Step 4: If choice is 2 the get the element to be inserted in the end and call the ins_end function
Step 5: If choice is 3 then get the element to be deleted and call deletion function.
Step 6: If choice is 4 then call display duncation
Step 7: If choice is default the exit the program
Step 8: Terminate the program execution.
Program:
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
void display(struct node *first);
struct node
{
int data;
struct node *lptr,*rptr;
}*head;
struct node *ins_beg(int x,struct node *first)
{

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

struct node *new1,*cur,*prev;

new1=malloc(sizeof(struct node));
if(first==NULL)
{
new1->data=x;
new1->lptr=NULL;
new1->rptr=NULL;
return new1;
}
else
{
new1->data=x;
new1->lptr=NULL;
new1->rptr=first;
return new1;
}
}
struct node *ins_end(int x,struct node *first)
{
struct node *new1,*cur,*prev;
new1=malloc(sizeof(struct node));
if(first==NULL)
{
new1->data=x;
new1->lptr=NULL;
new1->rptr=NULL;
return new1;
}

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

else
{
cur=first;
while(cur->rptr!=NULL)
{
prev=cur;
cur=cur->rptr;
}
cur->rptr=new1;
new1->data=x;
new1->lptr=cur;
new1->rptr=NULL;
return first;
}
}
struct node *deletion(struct node *first,int del)
{
struct node *prev,*cur;
cur=first;
if(first==NULL)
{
printf("\n\nNo data present!!!");
getch();
}
else if(first->data==del)
{
printf("\n\nData %d is deleted",first->data);
first=first->rptr;

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

getch();
return first;
}
else
{
while(cur->rptr!=NULL && cur->data!=del)
{
prev=cur;
cur=cur->rptr;
}
if(cur->rptr==NULL && cur->data!=del)
printf("\n\nData is not present!!!");
else if(cur->rptr!=NULL && cur->data==del)
{
prev->rptr=cur->rptr;
(cur->rptr)->lptr=prev;
printf("\n\nData % d is deleted",cur->data);
}
else if(cur->rptr==NULL && cur->data==del)
{
prev->rptr=NULL;
printf("\n\nData %d is deleted:",cur->data);
}
getch();
return first;
}
}
void main()

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

{
int x,ch,del;
head=NULL;
clrscr();
printf("\n1.Insert in Begining\n2.Insert in the End\n3.Delete\n4.Display");
while(1)
{
printf("\n\nEnter your Choice :: ");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("\n\nEnter the element to be inserted::");
scanf("%d",&x);
head=ins_beg(x,head);
break;
case 2:
printf("\n\nEnter the element to be inserted::");
scanf("%d",&x);
head=ins_end(x,head);
break;
case 3:
printf("\n\nEnter the element to be deleted::");
scanf("%d",&del);
head=deletion(head,del);
break;
case 4:
display(head);

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

break;
default:
printf("\n\nInvalid Choice......");
getch();
exit(0);
}
}
}
void display(struct node *first)
{
struct node *temp;
temp=first;
if(temp==NULL)
printf("\n\nList is empty!!!");
while(temp!=NULL)
{
printf("%d ->",temp->data);
temp=temp->rptr;
}
getch();
}

Output:
1.Insert in Begining
2.Insert in the End
3.Delete
4.Display

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

Enter your Choice :: 1

Enter the element to be inserted::2

Enter your Choice :: 1

Enter the element to be inserted::3

Enter your Choice :: 4

3 ->2 ->

Enter your Choice :: 2

Enter the element to be inserted::1

Enter your Choice :: 2

Enter the element to be inserted::5

Enter your Choice :: 4

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

3 ->2 ->1 ->5 ->

Enter your Choice :: 3

Enter the element to be deleted::1
Data 1 is deleted
Enter your Choice :: 4
3 ->2 ->5 ->

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

Ex.no.:8
Date :
POLYNOMIAL MANUPULATION
Aim
To implement polynomial manipulation using doubly linked lists.
Algorithm
POLYADD(POLY1: POLY2:POLY)
HEAD:POLY
Step 1: Assign HEAD+=NULL
Step2: While (POLY !=null)
Step3: HEAD=INSERTNODE(HEAD,COPYNODE,(POLY1,1))
Step4: POLY1=POLY1NEXT
Step5: [End of Step2 while structure]
Step6: While(POLY2 1=NULL)
Step7: HEAD =INSERTNODE(HEAD,COPYNODE(POLY2,1))
Step8: POLY2=POLY2NEXT
Step9: [End of Step 6 while Structure]
Step10: Return HEAD
END POLYADD()

Algorithm for polynomial subtraction

POLYSUB(POLY1:POLY, POLY2:POLY)
HEAD:POLY
Step1: Assign HEAD=NULL
Step2: While(POLY1!=NULL)
Step3: HEAD=INSERTNODE(HEAD,COPYNODE(POLY1,1))
Step4: POLY1=POLY1 NEXT

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

Step5: [End of Step2 while Structure]

Step6:While(POLY2!=NULL)
Step7: HEAD=INSERTNODE(HEAD,COPYNODE(POLY2,-1))
Step8: POLY2=POLY2NEXT
Step9: [End of Step 6 While Structure]
Step10: Return HEAD
END POLYSUB()

Coding:
#include<malloc.h>
#include<conio.h>
struct link
{
int coeff;
int pow;
struct link *next;
};
struct link *poly1=NULL,*poly2=NULL,*poly=NULL;
void create(struct link *node)
{
char ch;
do
{
printf("\nEnter the coefficient :");
scanf("%d",&node->coeff);
printf("\nEnter the power :");
scanf("%d",&node->pow);
node->next=(struct link *)malloc(sizeof(struct link));

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

node=node->next;
node->next=NULL;
printf("\nContinue??? (Y/N) :");
ch=getch();
}while(ch=='y' || ch=='Y');
}
void display(struct link *node)
{
while(node->next!=NULL)
{
printf("%dx^%d",node->coeff,node->pow);
node=node->next;
if(node->next!=NULL)
printf(" + ");
}
}
void polyadd(struct link *poly1,struct link *poly2,struct link *poly)
{
while(poly1->next && poly2->next)
{
if(poly->pow > poly2->pow)
{
poly->pow=poly1->pow;
poly->coeff=poly1->coeff;
poly1=poly1->next;
}
else if(poly1->pow < poly2->pow)
{

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

poly->pow=poly2->pow;
poly->coeff=poly2->coeff;
poly2=poly2->next;
}
else
{
poly->pow=poly1->pow;
poly->coeff=poly1->coeff+poly2->coeff;
poly1=poly1->next;
poly2=poly2->next;
}
poly->next=(struct link *)malloc(sizeof(struct link));
poly=poly->next;
poly->next=NULL;
}
while(poly1->next||poly2->next)
{
if(poly1->next)
{
poly->pow=poly1->pow;
poly->coeff=poly1->coeff;
poly1=poly1->next;
}
if(poly2->next)
{
poly->pow=poly2->pow;
poly->coeff=poly2->coeff;
poly2=poly2->next;

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

}
poly->next=(struct link *)malloc(sizeof(struct link));
poly=poly->next;
poly->next=NULL;
}
}
void main()
{
poly1=(struct link *)malloc(sizeof(struct link));
poly2=(struct link *)malloc(sizeof(struct link));
poly=(struct link *)malloc(sizeof(struct link));
clrscr();
printf("\nEnter the first polynomial::");
create(poly1);
printf("\nFirst polynomial is :: \n");
display(poly1);
printf("\nEnter the second polynomial::");
create(poly2);
printf("\nSecond polynomial is :: \n");
display(poly2);
polyadd(poly1,poly2,poly);
printf("\nAddition of the two polynomials::");
display(poly);
getch();
}

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

Output

Enter the first polynomial::

Enter the coefficient :5

Enter the power :3

Continue??? (Y/N) :Y
Enter the coefficient :3

Enter the power :2

Continue??? (Y/N) :
First polynomial is ::
5x^3 + 3x^2
Enter the second polynomial::
Enter the coefficient :7

Enter the power :3

Continue??? (Y/N) :
Second polynomial is ::
7x^3
Addition of the two polynomials::12x^3 + 3x^2

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

Ex.no.:9
Date :

BINARY SEARCH TREE

Aim
To write a C program to implement a stack using binary search tree.
Algorithm
1. [Include all the necessary header files.]
2. [Declare the structure with all necessary variables.]
3. Read x;
4. Call INORDER().
5. Call PREORDER().
6. Call POSTORDER().
7. Call display().
8.

Algorithm For INSERT(P,X)

1. If (pNULL)
Create P
P<-datax.
P->lchild PrchildNULL
Else
2.1 while(TEMP!=NULL)
2.2 Temp2Temp1
2.3 If(temp1datax)
2.4 Else Temp1Temp1rchild
2.5 [End of while structure]
2.6 If(temp2datax)
2.7 Temp 2Temp2lchild

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

2.8 Temp 2datax

2.9 Temp2dataslchildtemp2rchild Null
2.10 Else
2.11 Temp 2Temp2Temp2rchildnull
2.12 Temp2datax
2.13 Temp 2lchildTemp 2rchildnull
2.14 [Return P]

Algorithm For INORDER(p)

1.If(p!=Null)
2. CALL INORDER (pxdhild)
3. WRITE(Ddata)
4.CALL INORDER (prchild)
5. [End the function]

Algorithm for PREORDER

1. If (pl=NULL)
2. WRITE (PData)
3. CALL PREORDER (PlCHILD)
4. CALL PREORDER (P Rchild)
5. [END OF FUNTION]

Algorithm for POSTORDER

1. If (P!=NULL)
2. Call POSTORDER (Plchild)
3. Call POSTORDER (Prchild)
4. Write (Pdata)

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

5. [End of function]

Algorithm for COUNT

If (P==NULL)

1. Return 0
2. Else
3. [Return (1+count(Plchild)+call count(Prchild)) ]
4. Algorithm for postorder

Algorithm for DISPLAY

If (T!=NULL)
1. X(lm+rm)/2
2. Call goto xy (x,4*y)
3. Write (t--.data)
4. Call display (tlchild, lm,x, l+1)
5. Call display (trchild, x, rm,l+1)
6. [END THE FUNCTION}
Algorithm for SEARCH
1. while(temp!=NULL)
2. If (tempdatat)
[Return temp]
3.If (Tempdata>x)
Temptemplchild
4. ELSE
Temptemprchild
5. [RETURN NULL]

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

Ex.no. :10
Date :

EXPRESSION TREE
Aim:
To write a C program to demonstrate an expression tree.
Algorithm for Main ()
Step 1: [ INCLUDE NECESSARY HEADER FILES]
Step 2: [READ X]
Step 3:[ CALL EXPTREE(),CALL DISPLAY(), CALL INORDER(),CALL
PREORDER(),CALL EVALUATE ()]
Algorithm for EXPTREE()

Step 1: Read Character

Step 2: IF Character operator then
CALL PUSH_OP()
Step 3: [IF Character has only numbers]
IF [ is ALnum( str[i] 1 )] THEN
CREATE Newnode
Step 4: Check for ‘ NULL ‘ condition
Step 5: ASSIGN priority
Step 6: IF ( Priority !=0) THEN CALL POP_OP()
Step 7: IF Character = ‘)’ THEN CALL PUSH_OP()

Algorithm for INORDER (tree t)

Step 1: IF (t!=NULL) THEN

CALL INORDER(t left)

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

Step 2: PRINT t element

Step 3: CALL INORDER(t right)

Algorithm for PREORDER (tree t)

Step 1: IF (t!=NULL) THEN
PRINT t element
Step 2: CALL PREORDER(t left)
Step 3: CALL INORDER(t right)

Algorithm for POSTORDER(tree t)

Step 1: IF (t!=NULL) THEN
CALL POSTORDER(t left)
CALL POSTORDER(t right)
Step 2: PRINT t element

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

Ex.no.:11
Date :

PRIORITY QUEUE USING HEAP

Aim:
To implement priority queue using Heap in C program.
Algorithm:
Step 1: [Include necessary header files]
Step 2: [Define maxsize as 15]
Step 3: [Declare necessary variables]
Step 4: READ option, opt
IF opt is 1 THEN CALL INSERT()
IF opt is 2 THEN CALL DELMAX()
IF opt is 3 THEN CALL DIS()
Step 5: [END OF MAIN FUNCTION]

Algorithm For INSERT()

Step 1: I ne1+1
Step 2: IF (I MAXSIZE)
WRITE (“ Heap size exceeded”)
RETURN FALSE
IF ( (I> 1) && (arraysize [i/2]< item) )
array[I] array[i/2]
I I/2
Array[I ] item
RETURN TRUE

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

Algorithm For DELMAX()

Step 1: IF (!nel)
WRITE (“HEAP IS EMPTY”)
ELSE
*item array [I]
Array[i] array [nel--]
CALL adjust (array,I,nel)

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

Ex.no.:12
Date :

HASHING TECHNIQUE

Aim:

To implement a program using Hashing technique.

Algorithm:

Step1: Include necessary header files

Step2: Declare necessary variables

Step3: Check the value of *S

Then call Insert( )

Print “Enter the string”

Read S

Step4: Check the value of *S

Step5: Then print S by calling hGetVal( )

Step6: Call PrintHash( )

Step7: End

Algorithm For hINSERT( ):

Step1: Allocate memory to pointer

Step2: Assign index hGetIndex ( )

Step3: Assign Ptr Key Strdup(key)

Ptr Val Val

Ptr next h[index]

h[index] Ptr

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

Step4: Print “h[index]=key”

Step5: Return

Algorithm For hGETVALUE( ):

Step1: [Ptr=h[hGetIndex(key)]]

Step2: If[Ptr && strcmp(Ptr key)]

Then Ptr Ptr next

Step3: If[Ptr],Check the value of Ptr

[Return Ptr Val]

Step4: [Return -1]

Algorithm For PRINTHASH( ):

Step1: Initialise i=0

Step2: If [i < Hash size]

Then Print i

Assign Ptr h[i]

Check the value of Ptr

If[Ptr!=0]

Then Ptr Ptr next

Print “Ptr key=Ptr Val”

Step3: [Return]

Coding:

#include<conio.h>
#include<stdio.h>
void main()
{

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

int a[10]={0,0,0,0,0,0,0,0,0,0};
int n,value,temp,hashvalue;
clrscr();
printf("Enter the value of n (table size) ::");
scanf("%d",&n);
do
{
printf("\nEnter the hash value ::");
scanf("%d",&value);
hashvalue=value%n;
if(a[hashvalue]==0)
{
a[hashvalue]=value;
printf("\na[%d] The value %d is stored",hashvalue,value);
}
else
{
for(hashvalue++;hashvalue<n;hashvalue++)
{
if(a[hashvalue]==0)
{
printf("Space is allocated!!!Give another value!!!");
a[hashvalue]=value;
printf("\na[%d] The value %d is stored",hashvalue,value);
goto a;
}
}
hashvalue=0;

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

for(hashvalue;hashvalue<n;hashvalue++)
{
if(a[hashvalue]==0)
{
printf("Space is allocated!!!Give another value!!!");
a[hashvalue]=value;
printf("\na[%d] The value %d is stored",hashvalue,value);
goto a;
}
}
}
a:printf("\nDo you want to enter more? :: ");
scanf("%d",&temp);
}while(temp==1);
getch();
}

OUTPUT:

Enter the value of n (table size) ::10

Enter the hash value ::10

a[0] The value 10 is stored

Do you want to enter more? :: 1

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

Enter the hash value ::11

a[1] The value 11 is stored
Do you want to enter more? :: 1

Enter the hash value ::21

Space is allocated!!!Give another value!!!
a[2] The value 21 is stored
Do you want to enter more? :: 1

Enter the hash value ::4

a[4] The value 4 is stored
Do you want to enter more? :: 1

Enter the hash value ::24

Space is allocated!!!Give another value!!!
a[5] The value 24 is stored
Do you want to enter more? :: 1

Enter the hash value ::19

a[9] The value 19 is stored
Do you want to enter more? :: 1

Enter the hash value ::29

Space is allocated!!!Give another value!!!
a[3] The value 29 is stored
Do you want to enter more? :: 1

Enter the hash value ::13

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

Space is allocated!!!Give another value!!!

a[6] The value 13 is stored
Do you want to enter more? :: 0

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

Ex.no.:13

Date :

DIJKSTRA’S ALGORITHM
Aim

To implement Dijkstra’s algorithm to find the shortest path.

Algorithm

Step1: [Include all the header files]

Step2: Call allSelected( )

Step3: Call Shortpath( )

Step4: Access the functions from main

Step5: End

Algorithm For ALLSELECTED( )

Step1: Initialise i=0

Step2: Check whether i<max

Step3: Check whether Selected[i]=0

Return 0

Step4: Else Return 1

Step5: Return

Algorithm For SHORTPATH( )

Step1: Initialise i=0 , Check i<max

Distance[i]=INFINITE

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

Step2: Assign selected[current].distance[0]=0,

Current=0

Step3: While(!allSelected(Selected))

Perform(Selected[i]= =0)

Current=k

Selected[current]=1

Print k

Coding:

#include<stdio.h>
#include<conio.h>
#define max 4
#define INFINITE 998
int allselected( int *selected)
{
int i;
for(i=0;i<max;i++)
if(selected[i]==0)
return 0;
return 1;
}
void shortpath(int cost[][max],int *preceed,int *distance)
{
int selected[max]={0};
int current=0,i,k,dc,smalldist,newdist;
for(i=0;i<max;i++)
distance[i]=INFINITE;
selected[current]=1;
distance[0]=0;

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

current=0;
while(!allselected(selected))
{
smalldist=INFINITE;
dc=distance[current];
for(i=0;i<max;i++)
{
if(selected[i]==0)
{
newdist=dc+cost[current][i];
if(newdist<distance[i])
{
distance[i]=newdist;
preceed[i]=current;
}
if(distance[i]<smalldist)
{
smalldist=distance[i];
k=i;
}
}
}
current=k;
selected[current]=1;
}
}
int main()
{

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

int cost[max][max]={{INFINITE,2,4,INFINITE},{2,INFINITE,1,5},{4,1,INFINITE,2},
{INFINITE,5,2,INFINITE}};
int preceed[max]={0},i,distance[max];
clrscr();
shortpath(cost,preceed,distance);
for(i=0;i<max;i++)
{
printf("The shortest path from 0 to %d is ",i);
printf("%d\n",distance[i]);
}
return 0;
getch();
}

Output:

The shortest path from 0 to 0 is 0

The shortest path from 0 to 1 is 2
The shortest path from 0 to 2 is 3
The shortest path from 0 to 3 is 5

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

Ex.no.14

Date:

BACKTRACKING ALGORITHM – KNAPSACK PROBLEM

Aim:

To write a C program to solve the knapsack problem using backtracking algorithm

Algorithm:

Step 1: Declare the variables, array size and functions

Step 2: Get the value of number of objects and size of knapsack
Step 3: Enter weight and profit of objects
Step 4: Assign the initial values
Step 5: Call the necessary function and display the profit
Step 6: End of program

Coding:

#include <stdio.h>

#define MAXWEIGHT 100

int n = 3; /* The number of objects */

int c[10] = {8, 6, 4}; /* c[i] is the *COST* of the ith object; i.e. what
YOU PAY to take the object */
int v[10] = {16, 10, 7}; /* v[i] is the *VALUE* of the ith object; i.e.
what YOU GET for taking the object */
int W = 10; /* The maximum weight you can take */

void fill_sack()
{
int a[MAXWEIGHT]; /* a[i] holds the maximum value that can be obtained
using at most i weight */
int last_added[MAXWEIGHT]; /* I use this to calculate which object were
added */
int i, j;
int aux;

Department of IT, REC, Thandalam.

Data structures and algorithms Lab manual for II year IT

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

{
a[i] = 0;
last_added[i] = -1;
}

a[0] = 0;
for (i = 1; i <= W; ++i)
for (j = 0; j < n; ++j)
if ((c[j] <= i) && (a[i] < a[i - c[j]] + v[j]))
{
a[i] = a[i - c[j]] + v[j];
last_added[i] = j;
}

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

if (last_added[i] != -1)
printf("Weight %d; Benefit: %d; To reach this weight I added object %d
(%d$ %dKg) to weight %d.\n", i, a[i], last_added[i] + 1, v[last_added[i]], c[last_added[i]], i -
c[last_added[i]]);
else
printf("Weight %d; Benefit: 0; Can't reach this exact weight.\n", i);

printf("---\n");

aux = W;
while ((aux > 0) && (last_added[aux] != -1)) {
printf("Added object %d (%d$ %dKg). Space left: %d\n", last_added[aux] + 1,
v[last_added[aux]], c[last_added[aux]], aux - c[last_added[aux]]);
aux -= c[last_added[aux]];
}

printf("Total value added: %d$\n", a[W]);

}

int main(int argc, char *argv[]) {

fill_sack();

return 0;
}

Department of IT, REC, Thandalam.