IT 2205 DATA STRUCTURES & ALGORITHMS LAB

List of Experiments

1. Implement singly and doubly linked lists.

2. Represent a polynomial as a linked list and write functions for polynomial addition.

3. Implement stack and use it to convert infix to postfix expression

4. Implement array-based circular queue and use it to simulate a producer-consumer problem.

5. Implement an expression tree. Produce its pre-order, in-order, and post-order traversals.

6. Implement binary search tree.

7. Implement priority queue using heaps

8. Implement hashing techniques

9. Implement Dijkstra's algorithm using priority queues

10. Implement a backtracking algorithm for Knapsack problem

Ex.No :- 1a IMPLEMENTATION OF SINGLY LINKED LIST

Aim
To implement the singly linked list using C- program

Algorithm

1. Create a list of elements one linked to the other using the create function
2. To insert any new element to the list, we have to get the position where to insert it and do
the insertion using insert function.
3. After creating the list, if we have to delete any element we can do it, by getting the position
to be deleted
4. Display the contents using display function
5. Exit the program

Program

/*Singly Linked List*/

#include<stdio.h>
#include<conio.h>
typedef int list;
struct node
{
list data;
struct node *link;
} *p;
list n,c;
void append();
void del();
void disp();
void insert();

void main()
{
list choice;
clrscr();
do
{
clrscr();
printf("\n1.Addnode\n 2.Deletenode\n 3.Insertnode\n 4.Display\n 5.Exit");
printf("\nEnter the choice:-");
scanf("%d",&choice);
switch(choice)
{
case 1:
append();
break;

case 2:
del();
break;

case 3:
insert();
break;

case 4:
disp();
break;

case 5:
exit(0);
}
} while(choice<5);
getch();
}

void append()
{
struct node *q,*t;
printf("\n Enter the Data to add");
scanf("\n %d",&n);
if(p==0)
{
p=(struct node*) malloc(sizeof(struct node));
p->data=n;
p->link=0;
}
else
{
q=p;
while(q->link!=0)
q=q->link;
t=(struct node*) malloc(sizeof(struct node));
t->data=n;
t->link=0;
q->link=t;
}
 getch();
}

void del()
{
struct node *q,*r;
q=p;
printf("\n Enter the Data to be Deleted");
scanf("\n %d",&n);
if(q->data==n)
{
p=q->link;
free(q);
return;
}
while(q!=0)
{
if(q->data==n)
{
r->link=q->link;
return;
}
r=q;
q=q->link;
}
printf("\nELEMENT NOT FOUND");
getch();
}

void insert()
{
struct node *q,*t,*r;
list i;
printf("\n Enter the position to be Inserted:");
scanf("\n %d",&c);
printf("\n Enter the Data:");
scanf("\n %d",&n);
for(i=0,q=p;i<c;i++)
{
q=q->link;
if(q==0)
printf("\n There are less then %d elements",q);
}
r=p;
while(r->link!=q)
r=r->link;
t=(struct node*) malloc(sizeof(struct node));
 t->data=n;

t->link=r->link;
r->link=t;
getch();
}

void disp()
{
struct node *q;
for(q=p;q!=0;q=q->link)
printf("\n %d",q->data);
getch();
}
 OUTPUT

1.Addnode
2.Deletenode
3.Insertnode
4.Display
5.Exit

ADDNODE
Enter the choice:-1
Enter the Data to add:10

Enter the choice:-1

Enter the Data to add:20

Enter the choice:-1

Enter the Data to add:30

INSERTNODE

Enter the choice:-3

Enter the position to be Inserted:1
Enter the Data: 100
DISPLAY
Enter the choice:-4
10
100
20
30
DELETENODE
Enter the choice:-2
Enter the data to be Deleted:20
10
100
30

Result

Thus the C- Program to implement singly linked list was written and verified.
Ex.No:- 1b IMPLEMENTATION OF DOUBLY LINKED LIST

Aim

To implement the Doubly Linked list using C- program

Algorithm

1. Create a class double list with data members and member functions
2. Create the doubly linked list using create function for this create a node with data
And point the next pointer to null and prev pointer to the previous node.
3. Insertion is done by getting the position and point the previous node next to the
New node and the new node’s next to the next node in the list
4. To delete a node, get the position and point the previous node’s next to the node
After the position to be deleted and nodes previous to the previous node of that
Position
5. Search a element by moving through the nodes and report the position
6. Using display() function, display the elements of the list.

Program

#include<stdio.h>
#include<conio.h>
#include<malloc.h>
struct node
{
int data;
struct node *llink,*rlink;
// struct node *rlink;
}*temp,*next,*prev;

typedef struct node node;

struct node *start=NULL,*end;
void main()
{
void insert();
void del();
void display();
void create();
int ch;
clrscr();
create();
do
{
printf("\t\t\nMENU\n");
 printf("\n1.INSERT\n");
printf("2.DELETE\n");
printf("3.DISPLAY\n");

printf("4.EXIT\n");
printf("ENTER UR CHOICE:");
scanf("%d",&ch);
switch(ch)
{
case 1:
insert();
break;
case 2:
del();
break;
case 3:
display();
break;
case 4:
exit();
}
}while(ch<=4);
getch();
}

void create()
{
int data;
temp=(node *)malloc(sizeof(node));
temp->llink=NULL;
temp->rlink=NULL;
printf("\nENTER THE ELEMENT:");
scanf("%d",&data);
temp->data=data;
start=temp;
}

void insert()
{
int p,data,i;
temp=(node *)malloc(sizeof(node));
printf("\nENTER THE POSITION TO BE INSERTED:");
scanf("%d",&p);
printf("\nENTER THE ELEMENT:");
scanf("%d",&data);
temp->data=data;
if(p==1)
{
temp->llink=NULL;
 temp->rlink=start;
start->llink=temp;
start=temp;
}
else
{
i=1;
next=start;
while(i<p-1)
{
next=next->rlink;
i++;
}
temp->llink=next;
temp->rlink=next->rlink;
next->rlink->llink=temp;
next->rlink=temp;
}
printf("\n\nNODE INSERTED SUCCESSFULLY");
}

void del()
{
int p,i;
printf("\nENTER THE POSITION TO BE DELETED:");
scanf("%d",&p);
if(p==1)
{
temp=start;
start=temp->rlink;

start->llink=NULL;
}
else
{
i=1;
next=start;
while(i<p-1)
{
next=next->rlink;
i++;
}
temp=next->rlink;
next->rlink=temp->rlink;
prev=next->rlink;
prev->llink=next;
}
free(temp);
printf("\n\nNODE REMOVED SUCCESSFULLY");
}
void display()
{
temp=start;
printf("\nTHE ELEMENTS IN THE DOUBLY LINKED LIST ARE:");
if(temp==NULL)
{
printf("\nTHERE ARE NO NODES IN THE LIST");
}
else
{
while(temp->rlink!=NULL)
{
printf("\t%d",temp->data);
temp=temp->rlink;
}
printf("\t%d",temp->data);
}
}
OUTPUT:

ENTER THE ELEMENT:10

MENU
1.INSERT
2.DELETE
3.DISPLAY
4.EXIT

ENTER UR CHOICE:1
ENTER THE POSITION TO BE INSERTED:2
ENTER THE ELEMENT:20
NODE INSERTED SUCCESSFULLY

MENU
1.INSERT
2.DELETE
3.DISPLAY
4.EXIT

ENTER UR CHOICE:3
THE ELEMENTS IN THE DOUBLY LINKED LIST ARE: 10 20

MENU
1.INSERT
2.DELETE
3.DISPLAY
4.EXIT

ENTER UR CHOICE:1
ENTER THE POSITION TO BE INSERTED:3
ENTER THE ELEMENT:30
NODE INSERTED SUCCESSFULLY

MENU
1.INSERT
2.DELETE
3.DISPLAY
4.EXIT

ENTER UR CHOICE:3
 THE ELEMENTS IN THE DOUBLY LINKED LIST ARE: 10 20 30

MENU

1.INSERT
2.DELETE
3.DISPLAY
4.EXIT

ENTER UR CHOICE:2
ENTER THE POSITION TO BE DELETED:3
NODE REMOVED SUCCESSFULLY

MENU
1.INSERT
2.DELETE
3.DISPLAY
4.EXIT

ENTER UR CHOICE:3
THE ELEMENTS IN THE DOUBLY LINKED LIST ARE: 10 20

MENU
1.INSERT
2.DELETE
3.DISPLAY
4.EXIT

ENTER UR CHOICE:4
 Result
Thus the C program for doubly linked list was written and executed successfully.

Ex.No:- 2 POLYNOMIAL ADDITION USING LINKED LIST

Aim

To Represent a polynomial as a linked list and to write functions for polynomial addition.

Algorithm

1. First of all create two linked polynomials

2. For addition of two polynomials if exponents of both the polynomials are same then we add
the coefs.
3. For the result we create the third linked list
4. Print the resultant polynomial

Program

#include <stdio.h>
#include<conio.h>
//#include<malloc.h>

struct polynode
{
float coeff;
int exp;
struct polynode *next;
};

void create_poly(struct polynode**,float,int);

void display(struct polynode*);
void add_poly(struct polynode*,struct polynode*,struct polynode**);

void main()
{
struct polynode *first,*second,*total;
int i=0;
first=second=total=NULL;
create_poly(&first,1.4,5);
create_poly(&first,1.5,4);
create_poly(&first,1.7,2);
create_poly(&first,1.8,1);
create_poly(&first,1.9,0);
clrscr();
display(first);
create_poly(&second,1.5,6);
create_poly(&second,2.5,5);
create_poly(&second,2.6,4);
create_poly(&second,4.5,3);
create_poly(&second,6.5,1);

printf("\n\n");
display(second);

/* draws a dashed horizontal line */

printf("\n");
while(i++<79)
printf("-");
printf("\n\n");
add_poly(first,second,&total);
display(total);
}

/* adds a term to a polynomial */

void create_poly(struct polynode **q,float x,int y)

{
struct polynode *temp;
temp=*q;

/* creates a new node if the list is empty */

if(*q==NULL)
{
*q=malloc(sizeof(struct polynode));
temp=*q;
}
else
{
/* traverse the entire linked list */

while(temp->next!=NULL)
temp=temp->next;

/* creates new nodes at intermediate stages */

temp->next=malloc(sizeof(struct polynode));
temp=temp->next;
}

/* assign coefficient and expoent*/

temp->coeff=x;
temp->exp=y;
temp->next=NULL;
}

/* displays the contents of liked list representing a polynomial */

void display(struct polynode *q)

{
/* traverse till the end of the linked list*/
while(q!=NULL)
{
printf("%.1f x^%d , ",q->coeff,q->exp);
q=q->next;
}
printf("\b\b\b");
}

/* adds two polynomials */

void add_poly(struct polynode *x,struct polynode *y,struct polynode **s)
{
struct polynode *z;

/* if boh linked lists are empty */

if(x==NULL && y==NULL)
return;

/* traverse till one of the list ends */

while(x!=NULL && y!=NULL)

{
/* create a new node if the list is empty */
if(*s==NULL)
{
*s=malloc(sizeof(struct polynode));
z=*s;
}

/* sreate new nodes at intermediate stages */

else
{
z->next=malloc(sizeof(struct polynode));
z=z->next;
}
/* store a term of the larger degree polynomial */

if(x->exp < y->exp)

{
z->coeff=y->coeff;
z->exp=y->exp;
y=y->next;
}

else
{
if(x->exp>y->exp)
{
z->coeff =x->coeff;
z->exp=x->exp;
x=x->next;
}
else
{
if(x->exp==y->exp)
{
/* assigning the added coefficient */
z->coeff=x->coeff+y->coeff;
z->exp=x->exp;
x=x->next;
y=y->next;

}
}
}
}

/* assign remaning terms of the first polynomial to the result */

while(x!=NULL)
{
if(*s==NULL)
{
*s=malloc(sizeof(struct polynode));
z=*s;
}
else
{
z->next=malloc(sizeof(struct polynode));
z=z->next;
}
/* assign coefficient and exponen */
z->coeff=x->coeff;
z->exp=x->exp;
x=x->next;
}
 /* assign remaining terms of the second polynomial to the result */

while(y!=NULL)
{
if(*s==NULL)
{
*s=malloc(sizeof(struct polynode));
z=*s;
}
else
{
z->next=malloc(sizeof(struct polynode));
z=z->next;
}
/* assign coeff and exp */
z->coeff=y->coeff;
z->exp=y->exp;
y=y->next;
}
z->next=NULL;
}

Output

1.4 x^5 1.5x^4 1.7x^2 1.8x^1 1.9x^0

1.5x^6 2.5x^5 2.6x^4 4.5x^3 6.5x^1

---------------------------------------------------------------------------------

1.5x^6 3.9x^5 4.1x^4 4.5x^3 1.7x^2 .3x^1 .9x^0

Result:

Thus the c program to represent a polynomial as a linked list and write functions for
polynomial addition was written and executed successfully.
EX.NO:- 3 CONVERSION OF INFIX TO POSTFIX EXPRESSION USING STACK

Aim
To write a ‘C’ program to implement stack and use it to convert infix to postfix expression

Algorithm

1: Start the program.

2: Declare the structure with required numbers.
3: Initialize the stack.
4: Read the value from the user.
5: While (post Exp! = NULL).
6: C= get the character from post Exp.
7: If(C=operand) then read the value of C.
8: End of step 8 while structure.
9: Pop the data from the stack and return the pop data.
10: Stop the program.

Program

#include<stdio.h>
#include<conio.h>
#include<ctype.h>
struct
{
int stack[20];
int top;
}s;
void push(int);
int pop();
int evalpost(char[]);
int calc(int,int,char);
void print_error();
void main()
{
char poststr[20];
s.top=-1;
clrscr();
printf("\n\tEnter the postfix expression");
scanf("\n\t%s",poststr);
printf("\n\t The evluated value of %s is %d",poststr,evalpost(poststr));
getch();
}
 void push(int value)
{
s.top++;
s.stack[s.top]=value;
}

int pop()
{
int popped;
if(s.top==-1)
return -1;
popped=s.stack[s.top];
s.stack[s.top]=NULL;
s.top--;
return popped;
}
int calc(int a,int b,char expr)
{
switch(expr)
{
case '+':return a+b;
case '-':return b-a;
case '*':return a*b;
case '/':return a/b;
}
}
int value(char c)
{
int val;
printf("\n\t Enter the value of %c",c);
scanf("\n\t %d",&val);
return val;
}
int evalpost(char postexp[])
{
int i=0,op1,op2,ans;
char c;
c=postexp[i];
while(c!='\0')
{
if(c==' ')
continue;
if((tolower(c)>='a')&&(tolower(c)<='z'))
push(value(c));
else if((c=='+')||(c=='-')||(c=='*')||(c=='/'))
{
op1=pop();
op2=pop();
if((op1==-1)||(op2==-1))
print_error();
 push(calc(op1,op2,c));
}
i++;
c=postexp[i];
}
ans=pop();
if(ans==-1)
print_error();
return ans;
}
void print_error()
{
printf("\n\tThe given postfix expression is wrong");
getch();
exit(0);
}

Output

Enter the postfix expression ab+cd-*

Enter the value of a 10

Enter the value of b 20

Enter the value of c 30

Enter the value of d 40

The evluated value of ab+cd-* is -300

Result

Thus the implementation of Postfix Expression is done and the program is executed.
Ex.NO:4 CIRULCAR QUEUE

Aim

To Implement a Circular queue where insertion and deletion operations are possible .

Algorithm

1: Start the program.

2: Check whether queue is full or not.
3: Insert the element.
4: Check whether the element is empty or not.
5: Delete the element from queue.
6: Print the main menu().
7: Enter the menu choice.
8: Check for the condition.
9: Stop the program.

Program

#include<stdio.h>
#include<conio.h>
#define MAX 10

void insertque(int *,int,int *,int *);

int deleteque(int *,int *,int *);
void display(int *);

void main()
{
int a[MAX];
int i,front,rear;
clrscr();
front=rear=-1;
for(i=0;i<MAX;i++)
a[i]=0;
insertque(a,10,&front,&rear);
insertque(a,25,&front,&rear);
insertque(a,11,&front,&rear);
insertque(a,8,&front,&rear);
insertque(a,20,&front,&rear);
printf("elements in the circular queue");
display(a);
i=deleteque(a,&front,&rear);
printf("item deleted:%d",i);
i=deleteque(a,&front,&rear);
printf("\n\nitem deleted:%d",i);
printf("\n\nelements in the circular queue after deletion");
display(a);
insertque(a,2,&front,&rear);
insertque(a,14,&front,&rear);
insertque(a,12,&front,&rear);
insertque(a,5,&front,&rear);
insertque(a,1,&front,&rear);
printf("elements in the circular queue after addition:");
display(a);
insertque(a,30,&front,&rear);
printf("elements in the circular queue after addition:");
display(a);
getch();
}
/* Adds an element to the queue */

void insertque(int *a,int item,int *pfront,int *prear)

{
if((*prear==MAX-1 && *pfront==0)||(*prear+1==*pfront))
{
printf("\n Queue is Full");
return;
}
if(*prear==MAX-1)
*prear=0;
else
(*prear)++;
a[*prear]=item;
if(*pfront==-1)
*pfront=0;
}

/* removes an element from the queue */

int deleteque(int *a,int *pfront,int *prear)

{
int data;
if(*pfront==-1)
{
printf("queue is empty");
return NULL;
}
data=a[*pfront];
a[*pfront]=0;
if(*pfront==*prear)
 {
*pfront=-1;
*prear=-1;
}
else
{
if(*pfront==MAX-1)
*pfront=0;
else
(*pfront)++;
}
return data;
}

/* display element in a queue */

void display(int *arr)

{
int i;
printf("\n");
for(i=0;i<MAX;i++)
printf("%d\t",arr[i]);
printf("\n");
}

Output

elements in the circular queue

10 25 11 8 20 0 0 0 0 0

item deleted:10

item deleted:25

elements in the circular queue after deletion

0 0 11 8 20 0 0 0 0 0

elements in the circular queue after addition:

0 0 11 8 20 2 14 12 5 1

elements in the circular queue after addition:

30 0 11 8 20 2 14 12 5 1
Result

Thus the implementation of De-Queue using array is done and the program is executed.

Ex.NO :- 5 IMPLEMENTATION OF EXPRESSION TREE

Aim

To write a ‘C’ program to implement expression tree.

Algorithm

1: Start the program.

2: Declare the node.
3: Using get node operation, enter new elements.
4: Using insert operation, insert the element.
5: Using inorder, preorder, postorder traverse tree.
6: Using left and right operation, place the elements.
7: End the program.

Program

#include<stdio.h>
#include<conio.h>
#include<alloc.h>
struct btreenode
{
struct btreenode *leftchild;
int data;
struct btreenode *rightchild;
};
void main()
{
struct btreenode *bt;
int req,i=1,num;
bt=NULL;
clrscr();
printf("\n\tSpecify the number of data items to be inserted");
scanf("%d",&req);
while(i++<=req)
{
printf("\n\tEnter the data");
scanf("%d",&num);
insert(&bt,num);
}
 clrscr();
printf("\nInorder traversal");
inorder(bt);
printf("\npreorder traversal");
preorder(bt);
printf("\npostorder traversal");
postorder(bt);
}

insert(struct btreenode **sr,int num)

{
if(*sr==NULL)
{
*sr=malloc(sizeof(struct btreenode));
(*sr)->leftchild=NULL;
(*sr)->data=num;
(*sr)->rightchild=NULL;
return;
}
else
{
if(num<(*sr)->data)
insert(&((*sr)->leftchild),num);
else
insert(&((*sr)->rightchild),num);
}
return;
}
inorder(struct btreenode *sr)
{
if(sr!=NULL)
{
inorder(sr->leftchild);
printf("\t\t%d",sr->data);
inorder(sr->rightchild);
}
else
return;
}
preorder(struct btreenode *sr)
{
if(sr!=NULL)
{
printf("\t%d",sr->data);
preorder(sr->leftchild);
preorder(sr->rightchild);
}

else
return;
}

postorder(struct btreenode *sr)

{
if(sr!=NULL)
{
postorder(sr->leftchild);
postorder(sr->rightchild);
printf("\t%d",sr->data);
}
else
return;
getch();
}

Output

Specify the number of data items to be inserted 3

Enter the data a

Enter the data +
Enter the data b

Inorder traversal a + b
preorder traversal + a b
postorder traversal a b +

Result
 Thus the implementation of Expression tree is done and the program is executed.

Ex.NO:-6 IMPLEMENTATION OF BINARY SEARCH TREE

Aim

To write a ‘C’ program to implement binary search tree.

Algorithm

1: Start the program.

2: Declare the node.
3: Using get node operation, enter new elements.
4: Using insert operation, insert the element.
5: Using inorder, preorder, postorder traverse tree.
6: Using left and right operation, place the elements.
7: End the program.

Program

#include<stdio.h>
#include<conio.h>
#include<alloc.h>
typedef struct btree
{
int data;
struct btree *left,*right;
}*tree;
tree head;
void main()
{
int ch=0,n,val;
void create();
void display();
clrscr();
printf("\n\n\t\t\t BINARY TREE TRAVERSALS\n");
while(1)
{
printf("\n\n 1-CREATE\t2-DIAPLAY\t3-EXIT");
printf("\n\nyour option ");
scanf("%d",&ch);
switch(ch)
{
case 1: create();
break;
case 2: display();
 break;
case 3: exit(0);
}
}
}
tree getnewnode()
{
tree temp;
printf("\n ENTER THE DATA: ");
temp=(tree)malloc(sizeof(struct btree));
scanf("%d",&temp->data);
temp->left=0;
temp->right=0;
return(temp);
}
void inorder(tree root)
{
tree temp;
temp=root;
if(temp)
{
inorder(temp->left);
printf("\t%d",temp->data);
inorder(temp->right);
}
}
void preorder(tree root)
{
tree temp;
temp=root;
if(temp)
{
printf("\t%d",temp->data);
preorder(temp->left);
preorder(temp->right);
}
}
void postorder(tree root)
{
tree temp;
temp=root;
if(temp)
{
postorder(temp->left);
postorder(temp->right);
printf("\t%d",temp->data);
}
}
void create()
{
tree temp,newnode;
int flag=0,n;
do
{
temp=head;
if(temp->left==NULL)
{
temp->left=getnewnode();
temp=temp->left;
}
else
 temp=temp->left;
flag=0;
newnode=getnewnode();
while(flag==0)
{
if(newnode->data<temp->data)
{
if(temp->left==NULL)
{
temp->left=newnode;
printf("\n%d is attached to the left of %d",
newnode->data,temp->data);
flag=1;
}
else
temp=temp->left;
}
else
{
if(temp->right==NULL)
{
temp->right=newnode;
printf("%d is attached to right of %d\n",
newnode->data,temp->data);
flag=1;
}
else
temp=temp->right;
}
}
printf("\n\n DO YOU WANT TO CONTINUE Y/N");
}
while(getch()=='Y');
}
void display()
{
printf("\n\n IN ORDER :");
inorder(head->left);
printf("\n\n PRE ORDER :");
preorder(head->left);
printf("\n\nPOST ORDER :");
postorder(head->left);
}
Output

1.CREATE 2.DIAPLAY 3.EXIT

YOUR OPTION 1

ENTER THE DATA : 10

ENTER THE DATA : 5
5 is attached to the left of 10

DO YOU WANT TO CONTINUE Y/N:Y

ENTER THE DATA : 7

7 is attached to right of 5

DO YOU WANT TO CONTINUE Y/N:Y

ENTER THE DATA : 1

1 is attached to the left of 5

DO YOU WANT TO CONTINUE Y/N:Y

ENTER THE DATA : 18

18 is attached to right of 10

DO YOU WANT TO CONTINUE Y/N:Y

ENTER THE DATA : 4

4 is attached to right of 1

DO YOU WANT TO CONTINUE Y/N:N

1.CREATE 2.DISPLAY 3.EXIT

YOUR OPTION: 2

IN ORDER : 1 4 5 7 10 18
PRE ORDER : 10 5 1 4 7 18
POST ORDER : 4 1 7 5 18 10

1.CREATE 2.DISPLAY 3.EXIT

YOUR OPTION : 3
Result

Thus the implementation of Binary search tree is done and the program is executed.

Ex.No:- 7 IMPLEMENT PRIORITY QUEUE USING BINARY HEAPS

Aim
To implement the priority queue using binary heaps

Algorithm

1. get the number of elements in the heap

2. get the elements and create a heap tree with those elements
3. display the tree with all its elements
4. to delete, consume the element with highest priority
put the next top value in that position and decrement the top value
5. Check upto top/2, whether the value is smaller than its children, if it is not so swap the
contents
6. Display the heap after all operations were done using a for loop

Program

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
int i,j,temp;
void insert(int *a,int top,int p)
{
a[top]=p;
i=top;
while(i>1&&a[i]<a[i/2])
{
temp=a[i];
a[i]=a[i/2];
a[i/2]=temp;
i=i/2;
}
}
void consume(int *a,int top)
{
i=1;
a[i]=a[top];
top--;
while(i<=top/2)
{
if(a[2*i]<a[(2*i)+1])
 j=2*i;
else j=2*i+1;
if(a[i]>a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
i=j;
}
else
{i++;}
}
}
void disp(int *a,int s)
{
int l,k;
int lp=1;
i=1;
while(i<=s)
{
for(j=0;j<lp;j++)
{
if(i<=s)
{
if(i==1)
l=4;
else if(i>1&&i<4)
l=3;
else if(i>3&&i<8)
l=2;
else if(i>7&&i<16)
l=1;
for(k=0;k<l;k++)
printf("\t");
printf("%d",a[i]);
i++;
}
}
lp=lp*2;
printf("\n\n\n");
}
}
void main()
{
int top=0,a[20],op,v,i;
a[0]=0;
clrscr();
while(1)
{
printf("\n1.Insert\n2.Consume\n3.Display\n4.Exit\n\nEnter your Option:");
scanf("%d",&op);
 switch(op)
{
case 1:
{
if(top==19)
{
printf("\nTree if FULL.");
break;
}
else
{
printf("\nEnter priority value to insert:");
scanf("%d",&v);
top++;
insert(a,top,v);
break;
}
}
case 2:
{
if(top==-1)
{
printf("\nTree is Empty.");
break;
}
else
{
consume(a,top);
top--;
printf("\nThe highest priority get consumed.");
break;
}
}
case 3:
{
/*for(i=1;i<=top;i++)
printf(a[i]<<"-->"; */
disp(a,top);
break;
}
case 4:
exit(1);
}
}
}
Output

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

Enter your Option:1

Enter priority value to insert:6

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

Enter your Option:1

Enter priority value to insert:1

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

Enter your Option:3

1

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

Enter your Option:4

 Result

Thus the program to implement the priority queue using binary heaps

Ex.No :- 8 HASHING WITH OPEN ADDRESSING

Aim

To implement Hashing with Open Addressing

Algorithm

1. Get the number of buckets or hashsize

2. Using insert function get the elements to be inserted.
3. The insertion is done using the hash function by modular dividing the element value by
bucket Size.
4. After getting the hash value the elements are allotted to the appropriate position in the
hash table.
5. Display the table.
6. Deletion of any element is done using the delete function.

Program
#include<stdio.h>
#include<conio.h>
#include<math.h>

int tabsize=10;
int tab[20];
void main()
{
int i,j,ch,res;
int store(int);
void retrieve(int,int *);
void removed(int);
void display();
/* Making the entries in the Table to be Empty */
clrscr();
for(i=0;i<tabsize;i++)
tab[i]=0;
do
{
printf("\n Hashing with Open Addressing");
printf("\n 1. Store Operation");
printf("\n 2. Retrieve Operation");
printf("\n 3. Remove Operation");
printf("\n 4. Display");
printf("\n 5.Exit");
printf("\n enter your choice");
scanf("%d",&ch);

switch(ch)
{
case 1:
printf("Enter the item to be placed in a table");
scanf("%d",&i);
res=store(i);
if(res==1)
printf("Item stored in the table");
else if(res==2)
printf("there is no free place in the table");
else if(res==0)
printf("item already exists in the table");
getch();
break;

case 2:
printf("Enter the item to be retrieved from the table");
scanf("%d",&i);
retrieve(i,&j);
if(j==1)
printf("item is in the table");
else
printf("Item is not on the table");
getch();
break;
case 3:
printf("enter the item to be deleted from the table");
scanf("%d",&i);
removed(i);
break;
case 4:
display();
getch();

case 5:
break;
}
}while(ch!=5);
}
/* This function stores an item in the hash table */

int store(int item)

{
int loc,ploc;
int k=1;
int flag=0;
loc=item%tabsize;
ploc=loc;
if(loc==tabsize)
loc=0;
while(1)
{
if(tab[loc]==0)
{
/* if collision does not occur in the hash table */
tab[loc]=item;
return 1;
}
else if((tab[loc]!=0) && (tab[loc]!=item))
{
/* if collision occurs in the Hash Table */
loc=loc+1;
//k++;
if(loc>=tabsize)
loc=0;
if(ploc==loc)
return 2;
continue;
}
else if(tab[loc]==item)
{
printf("item already already exists in the table");
getch();
return 0;
}
else
{
loc=loc+1;
if(loc==tabsize)
loc=0;
if(ploc==loc)
return 2;
continue;
}
}
}

void retrieve(int item,int *j)

{
int loc,ploc,k=1;
loc=item%tabsize;
ploc=loc;
if(tab[loc]==item)
{
*j+1;
return;
}
else
{
loc=loc+pow(k,2);
while(ploc!=loc)
{
if(tab[loc]==item)
{
*j=1;
return;
}
if(loc==tabsize)
loc=0;
else
{
loc=loc+1;
}
}
*j=0;
return;
}
}

void removed(int i)
{
int k=1;
int loc,ploc;
loc=i%tabsize;
ploc=loc;
if(tab[loc]==i)
{
tab[loc]=0;
printf("item removed from the hash table");
getch();
return;
}

else
{
loc=loc+1;
while((loc!=ploc)&&(tab[loc]!=i))
{
loc=loc+i;
if(loc==tabsize)
loc=0;
}
if((tab[loc]==i)&&(loc!=ploc))
{
tab[loc]=0;
printf("\n item removed from the hash tble....");
getch();
return;
}
else if((loc==ploc)&&(tab[loc]!=i))
{
printf("item not found in the hash table");
getch();
return;
}
}
}

void display()
{
int i;
for(i=0;i<tabsize;i++)
printf("%d",tab[i]);
}
Output

Hashing with Open Addressing

1. Store Operation
2. Retrieve Operation
3. Remove Operation
4. Display
5.Exit
enter your choice :-1
Enter the item to be placed in a table  10
Item stored in the table

Hashing with Open Addressing

1. Store Operation
2. Retrieve Operation
3. Remove Operation
4. Display
5.Exit
enter your choice :1
Enter the item to be placed in a table  20
Item stored in the table

Hashing with Open Addressing

1. Store Operation
2. Retrieve Operation
3. Remove Operation
4. Display
5.Exit
enter your choice 4
10 20 0 0 0 0 0 0 0 0

Hashing with Open Addressing

1. Store Operation
2. Retrieve Operation
3. Remove Operation
4. Display
5.Exit
 enter your choice 2
Enter the item to be retrieved from the table 20
item is in the table

Hashing with Open Addressing

1. Store Operation
2. Retrieve Operation
3. Remove Operation
4. Display
5.Exit
enter your choice: 3
enter the item to be deleted from the table 10
item removed from the hash table

Hashing with Open Addressing

1. Store Operation
2. Retrieve Operation
3. Remove Operation
4. Display
5.Exit
enter your choice 4
0 20 0 0 0 0 0 0 0 0

Result

Thus the C- program to implement Hashing with Open Addressing was implemented
successfully.
Ex. NO:- 9 DIJKSTRA’S ALGORITHM

Aim

To implement Dijkstra’s Algorithm

Algorithm

1. Create the class path with all its member variables and member functions.
2. Get the total number of nodes in the graph
3. Get the cost for every edges between the vertices of the graph
4. Assign the lowest cost edges, to form a path from the first nodes to the last vertex
Of the graph
5. Display the minimum weight for the graph with the path
Program

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
int a[10][10];
void path(int n)
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(i==j)
a[i][i]=0;
else
{
printf("Enter the value of%d:%d:::path\n",i,j);
printf("If no path exist,enter any value > than 999\n");
scanf("%d",&a[i][j]);
}
}
}
}
int minv(int a[10][10],int s)
{
 int i,v=9999,pos;
for(i=2;i<=s;i++)
if(v>a[1][i])
{
v=a[1][i];
pos=i;
}
return pos;
}
void fsp(int n)
{
int i,s=n;
while(s>1)
{
int sma=minv(a,s);
s=s-1;
for(i=1;i<=n;i++)
if(i!=sma)
{
if(a[1][i]>a[1][sma]+a[sma][i])
a[1][i]=a[1][sma]+a[sma][i];
}
}
}
void disp(int n)
{
int i;
for(i=1;i<=n;i++)
printf("the path from 1 to %d : %d\n",i,a[1][i]);
}
void main()
{
int n;
clrscr();
printf("enter the number of nodes:");
scanf("%d",&n);
path(n);
fsp(n);
disp(n);
getch();
}
Output

enter the number of nodes:3

Enter the value of1:2:::path
If no path exist,enter any value > than 999
10
Enter the value of1:3:::path
If no path exist,enter any value > than 999
999
Enter the value of2:1:::path
If no path exist,enter any value > than 999
20
Enter the value of2:3:::path
If no path exist,enter any value > than 999
30
Enter the value of3:1:::path
If no path exist,enter any value > than 999
40
Enter the value of3:2:::path
If no path exist,enter any value > than 999
50
the path from 1 to 1 : 0
the path from 1 to 2 : 10
the path from 1 to 3 : 40
Result

Thus the C- program to implement Dijkstra’s Algorithm was implemented

successfully.

Ex.NO:- 10a PRIM’S ALGORITHM

Aim

To Implement Prim’s algorithm using priority queues to find MST of an undirected graph

Algorithm

1. Create the class prim with all its member variables and member functions.
2. Get the total number of nodes in the graph
3. Get the cost for every edges between the vertices of the graph
4. Assign the lowest cost edges, to form a path from the first nodes to the last vertex
Of the graph
5. Display the minimum cost spanning tree for the graph with the path
6. Produce the total minimum cost.

Program

/*prims alg prg*/

#include<stdio.h>
#include<conio.h>
#include<process.h>
float lcost[100],a[100][100];
int closest[100],i,j,k,min,n;
int v1,v2,wt,c=0;
void get_mat()
{
printf("Enter the No of Vertices:");
scanf("%d",&n);
printf("enter 1000 for no path \n");
printf("enter weighted matrix\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("cost between the edge\t%d,%d:\t",i,j);
scanf("%f",&a[i][j]);
}
}
 }
void prim1()
{
for(i=2;i<=n;i++)
{
lcost[i]=a[1][i];
closest[i]=1;
}
printf("minimum cost spanning tree edges are\n");
for(i=2;i<=n;i++)
{
min=lcost[2];
k=2;
for(j=3;j<=n;j++)
{
if(lcost[j]<min)
{
min=lcost[j];
k=j;
}
}
c=c+min;
printf("(%d,%d)\tcost=%d\t",closest[k],k,min);
lcost[k]=2000;
for(j=2;j<=n;j++)
if((a[k][j]<lcost[j])&&(lcost[j]<2000))
{
lcost[j]=a[k][j];
closest[j]=k;
}
printf("\n");
}
printf("\n\nWeight of minimum cost spanning tree :%d",c);
getch();
}
void main()
{
int ch;
clrscr();
do
{
printf("\n1.get\n2.find path with minimum cost\n3.exit\nenter ur choice\n");
scanf("%d",&ch);
switch(ch)
{
case 1:
get_mat();
break;
case 2:
prim1();
break;
 case 3:
exit(0);
break;
}
}while(ch<=3);
getch();
}

Output

1.get
2.find path with minimum cost
3.exit
enter ur choice
1
Enter the No of Vertices:3
enter 1000 for no path
enter weighted matrix
cost between the edge 1,1: 10
cost between the edge 1,2: 1000
cost between the edge 1,3: 20
cost between the edge 2,1: 60
cost between the edge 2,2: 40
cost between the edge 2,3: 20
cost between the edge 3,1: 1000
cost between the edge 3,2: 20
cost between the edge 3,3: 90

1.get
2.find path with minimum cost
3.exit
enter ur choice
2
minimum cost spanning tree edges are
(1,3) cost=20
(3,2) cost=20

Weight of minimum cost spanning tree :40

1.get
2.find path with minimum cost
3.exit
enter ur choice
3

Result
Thus the C program To Implement Prim’s algorithm using priority queues to find MST of an
undirected graph was written and executed successfully.

Ex.NO:- 10b KRUSKAL’S ALGORITHM

Aim

To Implement Kruskal’s algorithm using priority queues to find MST of an undirected graph

Algorithm

1. Create the class Kruskal with all its member variables and member functions.
2. Get the total number of nodes in the graph
3. Get the cost for every edges between the vertices of the graph
4. Assign the lowest cost edges, to form a path from the first nodes to the last vertex
Of the graph
5. Display the minimum cost spanning tree for the graph with the path
6. Produce the total minimum cost.

Program

#include<stdio.h>
#include<conio.h>
#define MAX 100
struct edge_info
{
int u, v, weight;
} edge[MAX];
int tree[MAX][2], set[MAX];
int n;
int readedges()
{
int i, j, k, cost;
k = 1;
printf("\nEnter the number of Vertices in the Graph : ");
scanf("%d",&n);
printf("\n");
for (i = 1; i <= n; i++)
for (j = 1; j < i; j++)
{
printf("Enter the cost from\t%d\tto\t%d:",i,j);
scanf("%d",&cost);
if (cost != 999)
{
 edge[k].u = i;
edge[k].v = j;
edge[k++].weight = cost;
}
}
return (k-1);
}

void makeset()
{
int i;
for (i = 1; i <= n; i++)
set[i] = i;
}
int find(int vertex)
{
return (set[vertex]);
}
void join(int v1, int v2)
{
int i, j;
if (v1 < v2)
set[v2] = v1;
else
set[v1] = v2;
}
void arrange_edges(int k)
{
int i, j;
struct edge_info temp;
for (i = 1; i < k; i++)
for (j = 1; j <= k - i; j++)
if (edge[j].weight > edge[j + 1].weight)
{
temp = edge[j];
edge[j] = edge[j + 1];
edge[j + 1] = temp;
}
}
void spanningtree(int k)
{
int i, t, sum;
arrange_edges(k);
t = 1;
sum = 0;
printf("Edges before finding the minimum cost:\n");
for (i=1;i<=k;i++)
printf("(%d,%d)-- %d\n",edge[i].u,edge[i].v,edge[i].weight);
getch();
for (i = 1; i <= k; i++)
if (find (edge[i].u) != find (edge[i].v))
 {
join (edge[t].u, edge[t].v);
t++;
}

printf("\nThe Edges of the Minimum Cost Spanning Tree are\n\n");

for (i = 1; i<n; i++)
{
printf("%d - %d\n",edge[i].u,edge[i].v);
sum += edge[i].weight;
}
printf("\nThe Cost of the Minimum Spanning Tree is : %d",sum);
}
int main()
{
int ecount, totalcost;
clrscr();
ecount = readedges();
makeset();
spanningtree(ecount);
getch();
return;
}

Output

Enter the number of Vertices in the Graph : 3

Enter the cost from 2 to 1:10

Enter the cost from 3 to 1:20
Enter the cost from 3 to 2:30
Edges before finding the minimum cost:
(2,1)-- 10
(3,1)-- 20
(3,2)-- 30

The Edges of the Minimum Cost Spanning Tree are

2-1
3-1

The Cost of the Minimum Spanning Tree is : 30

Result

Thus the C- program To Implement Kruskal’s algorithm using priority queues to find MST
of an undirected graph was written and executed successfully.