B.E EEE CS1203 – DATA STRUCTURES LABORATORY
LIST OF EXPERIMENTS:
1 – A Implement singly linked lists1 – B Implement doubly linked lists
- Represent a polynomial as a linked list and write functions for polynomial addition
- Implement stack and use it to convert infix to postfixexpression
- Implement array-based circular queue and use it simulate a producer-consumer problem
- Implement an expression tree. Produce its pre-order, in-order, and post-order traversals
- Implement binary search tree
- Implement insertion in AVL trees
- Implement priority queue using binary heaps
- Implement hashing with open addressing
- Perform topological sort on a directed graph to decide if it is acyclic
- Implement Dijkstra’s algorithm using priority queues
- Implement prim’s and kruskar’s Algorithm
- Implement a backtracking algorithm for knapsack problems
1-A SINGLY LINKED LIST
AIM:
To write a program to implement singly linked list.
ALGORITHM:
1. Start
2. Creation: Get the number of elements, and create the nodes having structures DATA LINK and store the element inData field, link them together to form a linked list.
3. Insertion: Get the number to be inserted and create a new node store the value in
DATA field. And insert the node in the required position.
4. Deletion: Get the number to be deleted. Search the list from the beginning and locate the node then delete the node.
5. Display: Display all the nodes in the list.
6. Stop.
PROGRAM:
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define NULL 0 typedef struct list
{
int no;
struct list *next;
}LIST;
LIST *p,*t,*h,*y,*ptr,*pt;
void create( void ); void insert( void ); void delet(void ); void display ( void ); int j,pos,k=1,count; voidmain()
{
int n,i = 1,opt;
clrscr();
p = NULL;
printf("%d",sizeof(LIST));
printf( "Enter the no of nodes :\n " );
scanf( "%d",&n );
count = n;
while( i <= n)
{ create(); i++;
}
printf("\nEnter your option:\n");
printf("1.Insert \t 2.Delete \t 3.Display \t 4.Exit\n");
do
{ scanf("%d",&opt); switch( opt )
{
case 1: insert(); count++; break; case 2: delet(); count--;
if ( count == 0 )
{
printf("\n List is empty\n");
} break; case 3:
printf("List elements are:\n");
display();
break;
}
printf("\nEnter your option \n");
}while( opt != 4 );
getch();
}
void create ( )
{
if( p == NULL )
{
p = ( LIST * ) malloc ( sizeof ( LIST ) );
printf( "Enter the element:\n" );
scanf( "%d",&p->no );
p->next = NULL;
h = p;
}
else
{
t = ( LIST * ) malloc (sizeof( LIST ));
printf( "\nEnter the element" );
scanf( "%d",&t->no );
t->next = NULL;
p->next = t;
p = t;
}
}
void insert()
{
t=h;
p = ( LIST * ) malloc ( sizeof(LIST) ); printf("Enter the element to beinsrted:\n"); scanf("%d",&p->no);
printf("Enter the position to insert:\n");
scanf( "%d",&pos );
if( pos == 1 )
{
h = p;
h->next = t;
}
else
{
for(j=1;j<(pos-1);j++)
t = t->next;
p->next = t->next;
t->next = p;
t=p;
}
}
void delet()
{
//t=h;
printf("Enter the position to delete:\n");
scanf( "%d",&pos );
if( pos == 1 )
{
h = h->next ;
}
else
{
t = h;
for(j=1;j<(pos-1);j++)
t = t->next;
pt=t->next->next;
free(t->next);
t->next= pt;
}
}
void display()
{
t = h;
while( t->next != NULL )
{
printf("\t%d",t->no);
t = t->next;
}
printf( "\t %d\t",t->no );
}
1-B DOUBLY LINKED LIST
AIM:
To write a program to implement doubly linked list with Insert, Delete and
Display operations.
ALGORITHM:
1. Start
2. Creation: Get the number of elements to create the list. Then create the node having the structure BLINK DATA FLINK and store the elements in Data field. Link them together to form a doubly linked list.
3. Insertion: Get the number to be Inserted, create a new node to store the value.
Search the list and insert the node in its right position.
4. Deletion: Get the number to be deleted. Search the list from the beginning and try to locate node p with DATA. If found then delete the node.
5. FLINK P’s previous node to P’s Next node. BLINK P’s Next node to P’s
Previous node else display “Data not Found”.
6. Display: Display all the nodes in the list.
7. Stop.
PROGRAM :
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define NULL 0
typedef struct list
{
int no;
struct list *next;
struct list *pre;
}LIST;
LIST *p,*t,*h;
void create( void ); void insert( void ); void delet(void ); void display ( void ); int j,pos,k=1,count;
void main()
{
int n,i = 1,opt;
clrscr();
p = NULL;
printf( "Enter the no of nodes :\n " );
scanf( "%d",&n );
count = n;
while( i <= n)
{ create(); i++;
}
printf("\nEnter your option:\n");
printf("1.Insert \t 2.Delete \t 3.Display \t 4.Exit\n");
do
{
scanf("%d",&opt);
switch( opt )
{
case 1: insert(); count++; break;
case 2: delet(); count--;
if ( count == 0 )
{
printf("\n List is empty\n");
} break; case 3:
printf("List elements are:\n");
display();
break;
}
printf("\nEnter your option \n");
}while( opt != 4 );
getch();
}
void create ( )
{
if( p == NULL )
{
p = ( LIST * ) malloc ( sizeof ( LIST ) );
printf( "Enter the element:\n" );
scanf( "%d",&p->no );
p->next = NULL;
p->pre = NULL;
h = p;
}
else
{
t = ( LIST * ) malloc (sizeof( LIST ));
printf( "\nEnter the element" );
scanf( "%d",&t->no );
t->next = NULL;
p->next = t;
t->pre = p;
p = t;
}
}
void insert()
{
t=h;
p = ( LIST * ) malloc ( sizeof(LIST) ); printf("Enter the element to beinsrted:\n"); scanf("%d",&p->no);
printf("Enter the position to insert:\n");
scanf( "%d",&pos );
if( pos == 1 )
{
h = p;
h->next = t;
t->pre = h;
h->pre = NULL;
}
else
{
for(j=1;j<(pos-1);j++)
t = t->next;
p->next = t->next;
t->next = p;
p->pre = t;
}
}
void delet()
{
printf("Enter the position to delete:\n");
scanf( "%d",&pos );
if( pos == 1 )
{
h = h->next ;
h->pre = NULL;
}
else
{
t = h;
for(j=1;j<(pos-1);j++)
t = t->next;
t->next = t->next->next;
t->next->pre = t;
free( t->next );
}
}
void display()
{
t = h;
while( t->next != NULL )
{printf("%d\n",t->no);
t = t->next;
}
printf( "%d",t->no );
}
2. REPRESENT A POLYNOMIAL AS A LINKED LIST AND WRITE FUNCTIONS FORPOLYNOMIAL ADDITION
AIM:
To develop a program to represent a polynomial as a linked list and write functions for polynomial addition.
ALGORITHM:
1. Start.
2. Create a Linked lists used to represent and manipulate polynomials.
3. A polynomial can be represented as
P(X) = anxne+an-1xn-1e+…+a1x1e +a
Where ai – nonzero coefficients,0<i<n ei – exponent
4. Each node in the polynomial is considered as a node .Each node contains three fields
Node Structure
Coefficient Exponent Link
Coefficient Field - Which holds the coefficient of a term Exponent Field - Which holds the exponent value of that term Link Field - Address of the next term in the polynomial
5. P and Q are two polynomials.P & Q can be represented as linked list.
6. P:5x2+6x+7
7. Q:3x3+4x2+x
8. The resultant polynomial can be represented like this. R:3x3+9x2+7x+7
9. Stop.
PROGRAM
# include <stdio.h>
# include <malloc.h>
struct node
{
float coef;
int expo;
struct node *link;
};
struct node *poly_add(struct node *,struct node *);
struct node *enter(struct node *);
struct node *insert(struct node *,float,int);
main( )
{
struct node *p1_start,*p2_start,*p3_start;
p1_start=NULL; p2_start=NULL; p3_start=NULL; printf("Polynomial 1 :\n"); p1_start=enter(p1_start); printf("Polynomial 2 :\n"); p2_start=enter(p2_start);
p3_start=poly_add(p1_start,p2_start); printf("Polynomial 1 is : "); display(p1_start);
printf("Polynomial 2 is : ");
display(p2_start);
printf("Added polynomial is : ");
display(p3_start);
}/*End of main()*/
struct node *enter(struct node *start)
{
int i,n,ex;
float co;
printf("How many terms u want to enter : ");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
printf("Enter coeficient for term %d : ",i);
scanf("%f",&co);
printf("Enter exponent for term %d : ",i);
scanf("%d",&ex);
start=insert(start,co,ex);
}
return start;
}/*End of enter()*/
struct node *insert(struct node *start,float co,int ex)
{
struct node *ptr,*tmp;
tmp= malloc(sizeof(struct node));
tmp->coef=co;
tmp->expo=ex;
/*list empty or exp greater than first one */
if(start==NULL || ex>start->expo)
{
tmp->link=start;
start=tmp;
}
else
{
ptr=start;
while(ptr->link!=NULL && ptr->link->expo>ex)
ptr=ptr->link;
tmp->link=ptr->link;
ptr->link=tmp;
if(ptr->link==NULL) /*item to be added in the end */
tmp->link=NULL;
}
return start;
}/*End of insert()*/
struct node *poly_add(struct node *p1,struct node *p2)
{
struct node *p3_start,*p3,*tmp;
p3_start=NULL;
if(p1==NULL && p2==NULL)
return p3_start;
while(p1!=NULL && p2!=NULL )
{
tmp=malloc(sizeof(struct node));
if(p3_start==NULL)
{ p3_start=tmp; p3=p3_start;
}
else
{
p3->link=tmp;
p3=p3->link;
}
if(p1->expo > p2->expo)
{
tmp->coef=p1->coef; tmp->expo=p1->expo; p1=p1->link;
}
else
if(p2->expo > p1->expo)
{
tmp->coef=p2->coef; tmp->expo=p2->expo; p2=p2->link;
}
else
if(p1->expo == p2->expo)
{
tmp->coef=p1->coef + p2->coef;
tmp->expo=p1->expo;
p1=p1->link;
p2=p2->link;
}
}/*End of while*/
while(p1!=NULL)
{
tmp=malloc(sizeof(struct node));
tmp->coef=p1->coef;
tmp->expo=p1->expo;
if (p3_start==NULL) /*poly 2 is empty*/
{ p3_start=tmp; p3=p3_start;
}
else
{
p3->link=tmp;
p3=p3->link;
}
p1=p1->link;
}/*End of while */
while(p2!=NULL)
{
tmp=malloc(sizeof(struct node));
tmp->coef=p2->coef;
tmp->expo=p2->expo;
if (p3_start==NULL) /*poly 1 is empty*/
{ p3_start=tmp; p3=p3_start;
}
else
{
p3->link=tmp;
p3=p3->link;
}
p2=p2->link;
}/*End of while*/ p3->link=NULL; returnp3_start;
}/*End of poly_add() */
display(struct node *ptr)
{
if(ptr==NULL)
{ printf("Empty\n"); return;
}
while(ptr!=NULL)
{
printf("(%.1fx^%d) + ", ptr->coef,ptr->expo);
ptr=ptr->link;
}
printf("\b\b \n"); /* \b\b to erase the last + sign */
}/*End of display()*/
3. IMPLEMENT STACK AND USE IT TO CONVERT INFIX TO POSTFIX EXPRESSION
AIM:
To write a program to implement stack and use it to convert infid to postfix expression.
ALGORITHM:
1. Start.
2. Create a stack to store operand and operator.
3. In Postfix notation the operator follows the two operands and in the infix notation the operator is in between the two operands.
4. Consider the sum of A and B. Apply the operator “+” to the operands A and B
and write the sum as A+B is INFIX. + AB is PREFIX. AB+ is POSTFIX
5. Get an Infix Expression as input and evaluate it by first converting it to postfix and then evaluating the postfixexpression.
6. The expressions with in innermost parenthesis must first be converted to postfix so that they can be treated as single operands. In this way Parentheses can be successively eliminated until the entire expression is converted.
7. The last pair of parentheses to be opened with in a group of parentheses encloses the first expression with in thatgroup to be transformed. This last-in first-out immediately suggests the use of Stack. Precedence plays an importantrole in the transforming infix to postfix.
8. Stop.
PROGRAM
#include<stdio.h>
#include<string.h>
#include<math.h>
#define Blank ' '
#define Tab '\t'
#define MAX 50
long int pop ();
long int eval_post();
char infix[MAX], postfix[MAX];
long int stack[MAX];
int top;
main()
{
long int value; char choice='y'; while(choice == 'y')
{
top = 0;
printf("Enter infix : "); fflush(stdin); gets(infix);infix_to_postfix();
printf("Postfix : %s\n",postfix);
value=eval_post();
printf("Value of expression : %ld\n",value); printf("Want to continue(y/n) : ");scanf("%c",&choice);
}
}/*End of main()*/
infix_to_postfix()
{
int i,p=0,type,precedence,len;
char next ; stack[top]='#'; len=strlen(infix);infix[len]='#';
for(i=0; infix[i]!='#';i++)
{
if( !white_space(infix[i]))
{
switch(infix[i])
{
case '(': push(infix[i]); break;
case ')':
while((next = pop()) != '(')
postfix[p++] = next;
break; case '+': case '-': case '*': case '/': case '%': case '^':
precedence = prec(infix[i]);
while(stack[top]!='#' && precedence<= prec(stack[top]))
postfix[p++] = pop();
push(infix[i]);
break;
default: /*if an operand comes */
postfix[p++] = infix[i];
}/*End of switch */
}/*End of if */
} while(stack[top]!='#') postfix[p++] = pop();
postfix[p] = '\0' ; /*End postfix with'\0' to make it a string*/
}/*End of infix_to_postfix()*/
/* This function returns the precedence of the operator */
prec(char symbol )
{
switch(symbol)
{
case '(': return 0; case '+': case '-': return1; case '*': case '/': case '%': return 2; case '^': return 3;
}/*End of switch*/
}/*End of prec()*/
push(long int symbol)
{
if(top > MAX)
{
printf("Stack overflow\n");
exit(1);
}
else
{ top=top+1; stack[top] = symbol;
}
}/*End of push()*/
long int pop()
{
if (top == -1 )
{
printf("Stack underflow \n");
exit(2);
}
else
return (stack[top--]);
}/*End of pop()*/
white_space(char symbol)
{
if( symbol == Blank || symbol == Tab || symbol == '\0')
return 1; else return 0;
}/*End of white_space()*/
long int eval_post()
{
long int a,b,temp,result,len;
int i; len=strlen(postfix); postfix[len]='#'; for(i=0;postfix[i]!='#';i++)
{
if(postfix[i]<='9' && postfix[i]>='0')
push( postfix[i]-48 );
else
{
a=pop(); b=pop(); switch(postfix[i])
{
case '+': temp=b+a; break; case '-':
temp=b-a;break; case '*': temp=b*a;break; case'/':
temp=b/a;break; case '%': temp=b%a;break; case '^': temp=pow(b,a);
}/*End of switch */ push(temp); }/*End of else*/ }/*End of for */
result=pop(); return result; }/*End of eval_post */
4. IMPLEMENT ARRAY-BASED CIRCULAR QUEUE AND USE IT SIMULATE A PRODUCER-CONSUMER PROBLEM.
AIM :
To write a program to implement array-based circular queue and use it simulate a producer-consumer problem.
PROGRAM :
#include
#include
#include
int frnt=-1,rear=-1,buffer[5];
void consume()
{
if(frnt==-1)
printf(“\ncannot consume till producer produces it:”);
else
{
printf(“the consumed item is:%d”,buffer[frnt]);
if(frnt==rear)
frnt=rear=-1;
else
frnt=((frnt+1)%5);
}
getch();
}
void producer(int x)
{
if(frnt==(rear+1)%5)
{
printf(“\ncannot produce till consumerhaves it”);
}
else
{
if(frnt==-1)
frnt=rear=0;
else
rear=((rear+1)%5);
buffer[rear]=x;
printf(“\nthe producet element is:%d”,buffer[rear]);
}
getch();
}
void disp()
{
int i;
printf(“\nthe buffer contains:”);
if(rear>=frnt)
{
for(i=frnt;i<=rear;++i)
printf("%d\t",buffer[i]);
}
else
{
#include
#include
int frnt=-1,rear=-1,buffer[5];
void consume()
{
if(frnt==-1)
printf(“\ncannot consume till producer produces it:”);
else
{
printf(“the consumed item is:%d”,buffer[frnt]);
if(frnt==rear)
frnt=rear=-1;
else
frnt=((frnt+1)%5);
}
getch();
}
void producer(int x)
{
if(frnt==(rear+1)%5)
{
printf(“\ncannot produce till consumerhaves it”);
}
else
{
if(frnt==-1)
frnt=rear=0;
else
rear=((rear+1)%5);
buffer[rear]=x;
printf(“\nthe producet element is:%d”,buffer[rear]);
}
getch();
}
void disp()
{
int i;
printf(“\nthe buffer contains:”);
if(rear>=frnt)
{
for(i=frnt;i<=rear;++i)
printf("%d\t",buffer[i]);
}
else
{
for(i=frnt;i<5;++i)
printf("%d\t",buffer[i]);
for(i=0;i<=rear;++i);
printf("%d\t",buffer[i]);
}
getch();
}
void main()
{
int ch,z;
do
{
clrscr();
printf("\nproducer and consumer");
printf("\n1.produce an iteam");
printf("\n2.consume an iteam");
printf("\n3.display iteams");
printf("\n4.exit");
printf("\nenter the choice:");
scanf("\t%d",&ch);
switch(ch)
{
case 1:
printf("\nenter item to be inserted in buffer");
scanf("%d",&z);
producer(z);
break;
case 2:
consume();
break;
case 3:
disp();
break;
case 4:
exit(0);
break;
}
} while(ch<=4);
}
printf("%d\t",buffer[i]);
for(i=0;i<=rear;++i);
printf("%d\t",buffer[i]);
}
getch();
}
void main()
{
int ch,z;
do
{
clrscr();
printf("\nproducer and consumer");
printf("\n1.produce an iteam");
printf("\n2.consume an iteam");
printf("\n3.display iteams");
printf("\n4.exit");
printf("\nenter the choice:");
scanf("\t%d",&ch);
switch(ch)
{
case 1:
printf("\nenter item to be inserted in buffer");
scanf("%d",&z);
producer(z);
break;
case 2:
consume();
break;
case 3:
disp();
break;
case 4:
exit(0);
break;
}
} while(ch<=4);
}
5. IMPLEMENT AN EXPRESSION TREE. PRODUCE ITS PRE- ORDER, IN-ORDER, ANDPOST- ORDER TRAVERSALS
AIM:
To develop a program to implement an expression tree, that produce its pre-order, in-order and post-order traversals.
ALGORITHM:
1. Start.
2. Create a binary tree with the nodes partitioned into three disjoint subsets. The first subset consists of a single elementcalled the root of the tree.the other two subsets are themselves binary trees called the left and right sub trees of the original tree.A left or right sub tree can be empty.Each element of a binary tree is called node of the tree.
3. A common operation in the binary tree is to traverse that is to pass through the tree enumerating each nodes once.Thetraversal of the binary tree can be done in three ways they are preorder,inorder,postorder traversal.
4. To traverse a nonempty binary tree preorder we perform the following three operations(as depth-first order)
o Visit the root
o Traverse the left subtree in preorder
o Traverse the right subtree in preorder
5. To traverse a nonempty binary tree inorder we perform the following three operations(as symmetric order)
o Traverse the left subtree in inorder
o Visit the root
o Traverse the right subtree in inorder
6. To traverse a nonempty binary tree postorder we perform the following three operations
o Traverse the left subtree in postorder
o Traverse the right subtree in postorder
o Visit the root
7. Stop.
PROGRAM:
#include<stdio.h>
#include<conio.h>
#include<ctype.h>
#include<alloc.h>
#define size 20 typedef struct node
{
char data;
struct node *left;
struct node *right;
}
btree;
/*stack stores the operand nodes of the tree*/
btree *stack[size];
int top;
void main()
{
btree *root;
char exp[80];/*exp stores postfix expression*/
btree *create(char exp[80]); void inorder(btree *root); voidpreorder(btree *root); void postorder(btree *root); clrscr();
printf("\n enter the postfix expression:\n");
scanf("%s",exp);
top=-1;/*Initialize the stack*/
root=create(exp);
printf("\n The tree is created.....\n"); printf("\n Inorder traversal: \n\n");inorder(root);
printf("\n Preorder traversal: \n\n");
preorder(root);
printf("\n Postorder traversal: \n\n");
postorder(root);
getch();
}
btree *create(char exp[])
{
btree *temp;
int pos;
char ch;
void push(btree*); btree *pop(); pos=0; ch=exp[pos]; while(ch!='\0')
{
/*create new node*/ temp=((btree*)malloc(sizeof(btree)));temp->left=temp->right=NULL;
temp->data=ch; if(isalpha(ch)) push(temp);
else if(ch=='+' ||ch=='-' || ch=='*' || ch=='/')
{
temp->right=pop(); temp->left=pop(); push(temp);
}
else
printf("\n Invalid char Expression\n");
pos++;
ch=exp[pos];
} temp=pop(); return(temp);
}
void push(btree *Node)
{
if(top+1 >=size) printf("Error:Stack is full\n"); top++;
stack[top]=Node;
}
btree* pop()
{
btree *Node;
if(top==-1)
printf("\nerror: stack is empty..\n"); Node =stack[top];
top--;
return(Node);
}
void inorder(btree *root)
{
btree *temp; temp=root; if(temp!=NULL)
{
inorder(temp->left); printf("%c",temp->data);inorder(temp->right);
}
}
void preorder(btree *root)
{
btree *temp; temp=root; if(temp!=NULL)
{
printf("%c",temp->data); preorder(temp->left); preorder(temp->right);
}
}
void postorder(btree *root)
{
btree *temp; temp=root; if(temp!=NULL)
{
postorder(temp->left); postorder(temp->right); printf("%c",temp->data);
}
}
6. IMPLEMENT BINARY SEARCH TREE
AIM :
To write a program to create binary search tree and perform insertion and search operations on it.
ALGORITHM:
1. Start
2. Create a binary tree using linked representation with nodes having the structure LEFTDATARIGHT. Build thetree in such a way that values at each left is less and values at each right is greater.
3. Insert: Get the value to be inserted. Create a new node and set the data field to X. then set the left and right links toNULL.
4. Compare X with root node data in X <root continue search in left subtree. If X=root, then display “Duplicatedata”, if X>root then search in right subtree. Then insert the node in its right position.
5. Display: Display all the data in the tree.
6. Stop.
PROGRAM:
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
#define NULL 0 struct search
{
int element;
struct search* left;
struct search *right;
};
struct search *t;
struct search *makeempty(struct search *); struct search *findmin(structsearch *); struct search *findmax(struct search *); void inorder(struct search *);
struct search *insert(int,struct search *); struct search *delet(int,structsearch *); int retrieve(struct search *);
void main()
{
int choice,element; clrscr(); printf(“\n\t\t tree”);
t=makeempty(NULL);
printf(“\n Operations on tree”);
printf("\n 1.Findmin \t 2.Findmax \t 3.Insert \t 4.Delete \t 5.Exit \n");
do
{
printf("\nEnter your choice:"); scanf("%d",&choice);switch(choice)
{
case 1:
printf("\n Minimum:%d",retrieve(findmin(t)));
break;
case 2:
printf("\n Maximum:%d",retrieve(findmax(t)));
break;
case 3:
printf("\n Enter an element to insert:"); scanf("%d",&element);t=insert(element,t);
inorder(t);
break;
case 4:
printf("\nEnter the element to delete:"); scanf("%d",&element);t=delet(element,t);
inorder(t);
break; case 5: exit(0);
}
}while(choice!=6);
getch();
}
struct search *makeempty(struct search *t)
{
if(t!=NULL)
{
makeempty(t->left); makeempty(t->right); free(t);
}
return(0);
}
struct search *findmin(struct search *t)
{ if(t==NULL) return(NULL);
else if(t->left==NULL)
return(t);
else
return(findmin(t->left));
}
struct search *findmax(struct search *t)
{
if(t!=NULL)
while(t->right!=NULL)
t=t->right;
return(t);
}
struct search *insert(int x,struct search *t)
{
if(t==NULL)
{
t=(struct search *)malloc(sizeof(struct search));
if(t==NULL)
{
exit(1);
}
else
{
t->element=x;
t->left=t->right=NULL;
}
}
else
{
if(x<t->element)
t->left=insert(x,t->left);
else if(x>t->element)
t->right=insert(x,t->right);
}
return(t);
}
struct search *delete(int x, struct search *t)
{
if(t==NULL) printf("\nElement not found"); elseif(x<t->element)
t->left=delet(x,t->left);
else if(x>t->element)
t->right=delet(x,t->right);
else if(t->left && t->right)
{
tmp=findmin(t->right);
t->element=tmp->element;
t->right=delet(t->element,t->right);
}
else
{
tmp=t;
if(t->left==NULL)
t=t->right;
else if(t->right==NULL)
t=t->left;
free(tmp);
}
int retrieve(struct search *p)
{
return(p->element);
}
void inorder(struct search *t)
{
if(t!=NULL)
{
inorder(t->left);
printf("\t %d\t",t->element);
inorder(t->right);
}
}
7. IMPLEMENT INSERTION IN AVL TREES
AIM:
To develop a program to implement the insertion on AVL Trees.
ALGORITHM:
1. Start.
2. Declare the node with leftlink, rightlink, data and height of node.
3. Enter the number of elements to be inserted.
4. While inserting each element the height of each node will be checked.
5. If the height difference of left and right node is equal to 2 for an node then the height is unbalanced at the node.
6. The present node while inserting a new node at left sub tree then perform rotation with left child otherwise rotation withright chile.
7. Height is unbalanced at Grand Parent node while inserting a new node at right subtree of parent node then performdouble rotation with left.
8. Height is unbalanced at grandparent node while inserting a new node then perform double rotation with right.
9. To view the tree perform traversal on tree.
10. Stop.
PROGRAM:
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define FALSE 0
#define TRUE 1
typedef struct Node
{
int data;
int BF;
struct Node *left;
struct Node *right;
}node;
node *root;
node *create(node *root,int data,int *current);
node *remove(node *root,int data,int *current);
node *find_succ(node *temp,node *root,int *current);
node *right_rotation(node *root,int *current); node *left_rotation(node*root,int *current); void display(node *root);
node *insert(int data,int *current)
{ root=create(root,data,current); return root;
}
node *create(struct Node *root,int data,int *current)
{
node *temp1,*temp2;
if(root==NULL)
{
root= new node; root->data=data; root->left=NULL; root->right=NULL; root->BF=0;
*current=TRUE;
return(root);
}
if(data<root->data)
{
root->left=create(root->left,data,current);
if(*current)
{
switch(root->BF)
{
case 1 :
temp1=root->left;
if(temp1->BF==1)
{
printf("\n\n Single Rotation : R Rotation");
root->left=temp1->right;
temp1->right=root; root->BF=0; root=temp1;
}
else
{
printf("\n Double rotation : LR rotation");
temp2=temp1->right; temp1->right=temp2->left;temp2->left=temp1;
root->left=temp2->right; temp2->right=root;if(temp2->BF==1)
root->BF=-1;
else
root->BF=0; if(temp2->BF==-1) temp1->BF=1;
else
temp1->BF=0;
root=temp2;
}
root->BF=0;
*current=FALSE;
break;
case 0:
root->BF=1;
break;
case -1:
root->BF=0;
*current=FALSE;
}}}
if(data > root->data)
{
root->right=create(root->right,data,current);
if(*current!=NULL)
{
switch(root->BF)
{
case 1:
root->BF=0;
*current=FALSE;
break;
case 0:
root->BF=-1;
break;
case -1:
temp1=root->right;
if(temp1->BF==-1)
{
printf("\n\n\n single rotation : L Rotation");
root->right=temp1->left;
temp1->left=root; root->BF=0; root=temp1;
}
else
{
printf("\n Double rotation : RL rotation");
temp2=temp1->left;
temp1->left=temp2->right;
temp2->right=temp1; root->right=temp2->left;temp2->left=root; if(temp2->BF==-1)
root->BF=1;
else
root->BF=0; if(temp2->BF==1) temp1->BF=-1; else
temp1->BF=0;
root=temp2;
}
root->BF=0;
*current=FALSE;
}
}
}
return(root);
}
void display(node *root)
{
if(root!=NULL)
{
display(root->left); printf(" %d",root->data); display(root->right);
}
}
node *remove(node *root,int data,int *current)
{
node *temp;
if(root->data==13) printf(" %d",root->data);if(root==NULL)
{
printf("\n No Such data");
return (root);
}
else
{
if(data<root->data)
{
root->left=remove(root->left,data,current); if(*current) root=right_rotation(root,current);
}
else
{
if(data>root->data)
{
root->right=remove(root->right,data,current);
if(*current)
root=left_rotation(root,current);
}
else
{
temp=root;
if(temp->right==NULL)
{
root=temp->left;
*current=TRUE;
delete(temp);
}
else
{
if(temp->left==NULL)
{
root=temp->right;
*current=TRUE;
delete(temp);
}
else
{
temp->right=find_succ(temp->right,temp,current);
if(*current)
root=left_rotation(root,current);
}
}
}
}
}
return(root);
}
node *find_succ(node *succ,node *temp,int *current)
{
node *temp1=succ;
if(succ->left!=NULL)
{
succ->left=find_succ(succ->left,temp,current);
if(*current)
succ=right_rotation(succ,current);
}
else
{
temp1=succ;
temp->data=succ->data; succ=succ->right; delete(temp1);
*current = TRUE;
}
return(succ);
}
node *right_rotation(node *root,int *current)
{
node *temp1,*temp2;
switch(root->BF)
{
case 1:
root->BF=0;
break;
case 0:
root->BF=-1;
*current=FALSE;
break;
case -1:
temp1=root->right;
if(temp1->BF<=0)
{
printf("\n Single Rotation : L rotation");
root->right=temp1->left; temp1->left=root;if(temp1->BF==0)
{
root->BF=-1;
temp1->BF=1;
*current=FALSE;
}
else
{
root->BF=temp1->BF=0;
}
root=temp1;
}
else
{
printf("\n Double Rotation : RL Rotation");
temp2=temp1->left;
temp1->left=temp2->right;
temp2->right=temp1; root->right=temp2->left;temp2->left=root; if(temp2->BF==-1)
root->BF=1;
else
root->BF=0; if(temp2->BF==-1) root->BF=1;
else
root->BF=0; if(temp2->BF==1) temp1->BF=-1; else
temp1->BF=0; root=temp2; temp2->BF=0;
}
}
return (root);
}
node *left_rotation(node *root,int *current)
{
node *temp1,*temp2;
switch(root->BF)
{
case -1:
root->BF=0;
break;
case 0:
root->BF=1;
*current=FALSE;
break; case 1: temp1=root->left;
if(temp1->BF>=0)
{
printf("\n Single Rotation R Rotation");
root->left=temp1->right; temp1->right=root;if(temp1->BF==0)
{
root->BF=1;
temp1->BF=-1;
*current=FALSE;
}
else
{
root->BF=temp1->BF=0;
}
root=temp1;
}
else
{
printf("\n Double Rotatuion : LR Rotation");
temp2=temp1->right; temp1->right=temp2->left;temp2->left=temp1;
root->left=temp2->right; temp2->right=root;if(temp2->BF==1)
root->BF=-1;
else
root->BF=0;
if(temp2->BF==-1)
temp1->BF=1;
else
temp1->BF=0; root=temp2; temp2->BF=0;
}
}
return root;
}
void main()
{
node *root=NULL;
int current; clrscr(); root=insert(40,¤t); printf("\n\t\t"); display(root); root=insert(50,¤t); printf("\n\t\t"); display(root); root=insert(70,¤t); printf("\n\t\t"); display(root); root=insert(30,¤t); printf("\n\t\t"); display(root); root=insert(20,¤t); printf("\n\t\t"); display(root); root=insert(45,¤t); printf("\n\t\t"); display(root); root=insert(25,¤t); printf("\n\t\t"); display(root); root=insert(10,¤t); printf("\n\t\t"); display(root); root=insert(5,¤t); printf("\n\t\t"); display(root);
printf("\n\n\n Final AVL tree is : \n");
display(root);
}
8. IMPLEMENT PRIORITY QUEUE USING BINARY HEAPS
AIM:
To develop a program to implement the priority queue using Binary Heaps.
ALGORITHM:
1. Start.
2. Definition: An abstract data type to efficiently support finding the item with the highest priority across a seriesof operations. The basic operations are: insert, find-minimum (or maximum), and delete-minimum (or maximum). Someimplementations also efficiently support join two priority queues (meld), delete an arbitrary item, and increase thepriority of a item (decrease-key).
3. Formal Definition: The operations new(), insert(v, PQ), find-minimum or min(PQ), and delete-minimum or dm(PQ) may be defined with axiomatic semantics as follows.
4. new() returns a priority queue
5. min(insert(v, new())) = v
6. dm(insert(v, new())) = new()
7. min(insert(v, insert(w, PQ))) = if priority(v) < priority(min(insert(w, PQ)))
then v else min(insert(w, PQ))
8. dm(insert(v, insert(w, PQ))) = if priority(v) < priority(min(insert(w, PQ))) then insert(w, PQ) else insert(v,dm(insert(w, PQ))) where PQ is a priority queue, v and w are items, and priority(v) is the priority of item v.
9. Stop.
PROGRAM
#include<stdio.h>
#include<conio.h>
#define SIZE 5
void main(void)
{
int rear,front,que[SIZE],choice;int Qfull(int rear),Qempty(int rear,int front);
int insert(int que[SIZE],int rear,int front);
int delet(int que[SIZE],int front);
void display(int que[SIZE],int rear,int front);
char ans; clrscr(); front=0; rear=-1; do
{
clrscr();
printf("\n\t\t Priority Queue \n");
printf("\n Main Menu");
printf("\n 1.Insert\n2.Delete\n3.Display"); printf("\n Enter Your Choice : ");scanf("%d",&choice);
switch(choice)
{
case 1 : if(Qfull(rear)) printf("\n Queue if FUll"); else rear=insert(que,rear,front); break;
case 2:
if(Qempty(rear,front))
printf("\n Cannot delete elements");
else front=delet(que,front); break;
case 3:if(Qempty(rear,front)) printf("\n eue is empty"); else
display(que,rear,front);
break;
default:printf("\n Wrong Choice");
break;
}
printf("\n Do you Want to continue?");
ans=getche();
} while(ans=='Y'||ans=='y'); getch();
}
int insert(int que[SIZE],int rear,int front)
{
int item,j;
printf("\n Enter the Elements : ");
scanf("%d",&item); if(front == -1) front++;
j=rear;
while(j>=0 && item<que[j])
{ que[j+1]=que[j]; j--;
} que[j+1]=item; rear=rear+1; return rear;
}
int Qfull(int rear)
{
if(rear==SIZE-1)
return 1; else return 0;
}
int delet(int que[SIZE],int front)
{
int item;
item=que[front];
printf("\n The item deleted is %d",item);
front++;
return front;
}
Qempty(int rear,int front)
{
if((front==-1) || (front>rear))
return 1; else return 0;
}
void display(int que[SIZE],int rear,int front)
{
int i;
printf("\n The Queue is : "); for(i=front;i<=rear;i++) printf(" %d",que[i]);
}
9. IMPLEMENT HASHING WITH OPEN ADDRESSING
AIM :
To develop a program to implement Hashing with open addressing.
ALGORITHM:
Open addressing hashing works on the same principle as other types of hashing; that is, it uses a hashing function h andthe key of a datum x to map x to h[key(x)], and the values are s tored in a table. The difference is in what is stored in thetable. Instead of maintaining a pointer to a linked list, the table contains the actual values of key(x). Implementation
The table is T[0..m-1] where m is the table size, and the input is x_1,...,x_n. The has function h is given.
INSERT:
We apply our hash function to the first value: the last digit is 9, so 19 goes in slot 9. Next is 33: this goes in slot 3. Nowwe come to a problem: the next number, 43 should also go into slot 3. We have no linked lists, so where does it go? Inopen addressing, a value that is slated for an occupied slot goes into the next empty slot. 43 then goes into slot 4. 53: slot 3is filled, go to slot 4. Slot 4 is filled, go to slot 5. Slot 5 is empty, so 53 goes into slot 5.
The table is usually made circular, so that a value meant to be inserted into the last slot (which is occupied) is sentaround to the front of the list. So if we were to insert
99 into the table, we see that slot 9 is occupied, and 99 is sent to slot 0, which is empty. Note that if we have more valuesentered than slots, we can run out of room in the table, and be unable to make any more insertions. For this reason, the loadfactor a in open addressing can never exceed 1.0 .
DELETE:
Say we want to delete 43. First we go to slot 3: It's occupied, but not by 43. So we go on to the next occupied slot. Wecontinue to do this until we find either the number we're looking for (success), an empty slot or we arrive back where westarted. In this case, the very next slot is occupied by 43, so we remove it and mark the slot as deleted. (We'll see why in amoment.)
Probing and the Probe Sequence
Probing is simply another word for the sequence we used for our search and insert routines. We "probe" the table until we find an available slot. Due to the (usually) circular nature of the table we have to limit the number of slots the algorithm willexamine. Since there are only m slots in the table, we limit the algorithm to m comparisons.
The probe sequence is the permutation of 0,1,...,m-1 used for searching for an available slot when inserting an element. For a key k the sequence is denoted by:
h(k,0), h(k,1), ..., h(k,m-1)
Thus, h(k,0) is what we used to call h(k). The probe sequence used in the simple introductory example is simply
h(k), h(k) + 1, ..., h(k) + m - 1
all mod m (to force the circular inspection of the array). Clearly, this is a permutation, but not a very good one (we'll see why ina moment).
Linear Probing:
This is more or less self-explanatory. In linear probing, the slots in the has table are probed in a linear fashion, in order (ie.check slot 4, then slot 5, then 6, then 7,...etc). We express linear probing as
h(k,i)=[h(k) + c*i] mod m
where c is an integer. While the slots are probed in a linear fashion, they are not necessarily probed in exact order.Note that we use mod m to account for the (usually) circular nature of the table. One of the problems with linear probing iscalled primary clustering. In this, "blocks" of occupied slots tend to accumulate; the larger a block is, the faster it grows, by theprinciples of probability. This increases the average search time in the table.
PROGRAM
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define MAX 10
void main()
{
int a[MAX],num,key,i;
char ans;
int create(int);
void linear_prob(int [],int,int),display(int []);
clrscr();
printf("\n Collision Handling By Linaer Probling");
for(i=0;i<MAX;i++)
a[i]=-1;
do
{
printf("\n Enter the Number "); scanf("%d",&num); key=create(num); linear_prob(a,key,num);
printf("\n Do U Wish to Contiue?(Y/N");
ans=getch();
} while(ans=='y'); display(a); getch();
}
int create(int num)
{
int key; key=num%10; return key;
}
void linear_prob(int a[MAX],int key,int num)
{
int flag,i,count=0; void display(int a[]); flag=0;
if(a[key]==-1) a[key]=num; else
{ i=0; while(i<MAX)
{
if(a[i]!=-1) count++; i++;
}
if(count==MAX)
{
printf("\n\n Hash Table is Fu;;");
display(a); getch(); exit(1);
} for(i=key+1;i<MAX;i++) if(a[i]==-1)
{ a[i]=num; flag=1; break;
} for(i=0;i<key&&flag==0;i++) if(a[i]==-1)
{ a[i]=num; flag=1; break;
}
}
}
void display(int a[MAX])
{
int i;
printf("\n\n The HAsh Table is....\n");
for(i=0;i<MAX;i++)
printf("\n %d %d",i,a[i]);
}
10.TOPOLOGICAL SORTING
AIM :
To develop a program to perform topological sort on a directed graph to decide if it is acyclic.
ALGORITHM :
PROGRAM
#include
#include
#defineMAX20
int n,adj[MAX][MAX];
int front=-1,rear=-1,queue[MAX];
void main()
{
int i,j=0,k;
int topsort[MAX],indeg[MAX];
create_graph();
printf(“The adjacency matrix is:\n”);
display();
for(i=1;i<+n;i++)
{
indeg[i]=indegree(i);
if(indeg[i]==0)
insert_queue(i);
}
while(front<=rear)
{
k=delete_queue();
topsort[j++]=k;
for(i=1;i<=n;i++)
{
if(adj[k][i]==1)
{
adj[k][i]=0;
indeg[i]=indeg[i]-1;
if(indeg[i]==0)
insert_queue(i);
}
}
}
printf("Nodes after topological sorting are:\n");
for(i=0;i<=n;i++)
printf("%d",topsort[i]);
printf("\n");
}
create_graph()
{
int i,max_edges,origin,destin;
printf("\n Enter number of vertices:");
scamf("%d",&n);
max_edges=n*(n-1);
for(i=1;i<=max_edges;i++)
{
printf("\n Enter edge %d (00 to quit):",i);
scanf("%d%d",&origin,&destin);
if((origin==0)&&(destin==0))
{
printf("Invalid edge!!\n");
i–;
}
else
adj[origin][destin]=1;
}return;
}
display()
{
int i,j;
for(i=0;i<=n;i++)
{
for(j=1;jrear)
{
printf(“Queue Underflow”);
return;
}
else
{
del_item=queue[front];
front=front+1;
return del_item;
}
}
int indegree(int node)
{
int i,in_deg=0;
for(i=1;i<=n;i++)
if(adj[i][node]==1)
in_deg++;
returnin_deg;
}
OUTPUT:
Enter number of vertices:7
Enter edge 1(0 0 to quit): 1 2
Enter edge 2(0 0 to quit): 1 3
Enter edge 3(0 0 to quit): 1 4
Enter edge 4(0 0 to quit): 4 3
Enter edge 5(0 0 to quit): 2 4
Enter edge 6(0 0 to quit): 2 5
Enter edge 7(0 0 to quit): 3 6
Enter edge 8(0 0 to quit): 4 6
Enter edge 9(0 0 to quit): 4 7
Enter edge 10(0 0 to quit): 5 4
Enter edge 11(0 0 to quit): 5 7
Enter edge 12(0 0 to quit): 7 6
Enter edge 13(0 0 to quit): 0 0
Enter edge 2(0 0 to quit): 1 3
Enter edge 3(0 0 to quit): 1 4
Enter edge 4(0 0 to quit): 4 3
Enter edge 5(0 0 to quit): 2 4
Enter edge 6(0 0 to quit): 2 5
Enter edge 7(0 0 to quit): 3 6
Enter edge 8(0 0 to quit): 4 6
Enter edge 9(0 0 to quit): 4 7
Enter edge 10(0 0 to quit): 5 4
Enter edge 11(0 0 to quit): 5 7
Enter edge 12(0 0 to quit): 7 6
Enter edge 13(0 0 to quit): 0 0
The adjanecy matrix is:
0 1 1 1 0 0 0
0 0 0 1 1 0 0
0 0 0 0 0 1 0
0 0 1 0 0 1 1
0 0 0 1 0 0 1
0 0 0 0 0 0 0
0 0 0 0 0 1 0
0 0 0 1 1 0 0
0 0 0 0 0 1 0
0 0 1 0 0 1 1
0 0 0 1 0 0 1
0 0 0 0 0 0 0
0 0 0 0 0 1 0
Nodes after topological sorting are:
1 2 5 4 37 6
11.Implement Dijkstra’s algorithm using priority queues
Aim:
Algorithm:
Program :
#include<stdio.h>
#include<conio.h>
#define infinity 999
#define max 10
int G[max][max],Q[max];
int n,path[max],p[max];
int dest,scr,y,z;
void display(int,int);
void main()
{
void buildgraph();
void dijkstra(int,int);
void insert(int,int);
void insertq(int);
int front,rear;
clrscr();
printf(“\nProgram for the shortest path algorithm using priority queue”);
printf(“\nEnter the number of the vertices:”);
scanf(“%d”,&n);
buildgraph();
printf(“\nEnter the source”);
scanf(“%d”,&scr);
printf(“\nEnter the destination”);
scanf(“%d”,&dest);
dijkstra(scr,dest);
for(y=1;y<=max;y++)
p[y]=infinity;
printf(“\nThe shortest path is:\n\t”);
display(dest,scr);
printf(“%d”,dest);
getch();
}
void display(int dest,int scr)
{
int z=1;
while(dest>scr)
{
int a;
a=path[dest];
if(a!=scr)
{
p[z]=a;
}
else
{
p[z]=a;
}
++z;
dest=a;
}
for(y=max;y>0;y–)
{
if(p[y]!=infinity)
{
printf(“%d”,p[y]);
}
}
}
void buildgraph()
{
int i,j,v1,v2;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf(“\nEnter the edge of v%d to v%d:”,i,j);
scanf(“%d”,&G[i][j]);
}
printf(“\n”);
}
}
void insertq(int index)
{
Q[index]=1;
}
void insert(int index,int vertex)
{
path[index]=vertex;
}
void dijkstra(int scr,int dest)
{
int small,dist[10],current,start,new1;
int temp,i,a[10];
void insertq(int);
for(i=0;i<=n;i++)
{
a[i]=0;
dist[i]=infinity;
}
Q[scr]=1;
dist[scr]=0;
current=scr;
while(current!=dest)
{
small=infinity;
start=dist[current];
for(i=1;i<=n;i++)
{
if(Q[i]==0)
{
new1=start+G[current][i];
if(new1<dist[i])
{
dist[i]=new1;
insert(i,current);
}
if(dist[i]<small)
{
small=dist[i];
temp=i;
}
}
}
current=temp;
insertq(current);
}
//printf(“\nThe minimum cost is:%d”,new1);
}
#include<conio.h>
#define infinity 999
#define max 10
int G[max][max],Q[max];
int n,path[max],p[max];
int dest,scr,y,z;
void display(int,int);
void main()
{
void buildgraph();
void dijkstra(int,int);
void insert(int,int);
void insertq(int);
int front,rear;
clrscr();
printf(“\nProgram for the shortest path algorithm using priority queue”);
printf(“\nEnter the number of the vertices:”);
scanf(“%d”,&n);
buildgraph();
printf(“\nEnter the source”);
scanf(“%d”,&scr);
printf(“\nEnter the destination”);
scanf(“%d”,&dest);
dijkstra(scr,dest);
for(y=1;y<=max;y++)
p[y]=infinity;
printf(“\nThe shortest path is:\n\t”);
display(dest,scr);
printf(“%d”,dest);
getch();
}
void display(int dest,int scr)
{
int z=1;
while(dest>scr)
{
int a;
a=path[dest];
if(a!=scr)
{
p[z]=a;
}
else
{
p[z]=a;
}
++z;
dest=a;
}
for(y=max;y>0;y–)
{
if(p[y]!=infinity)
{
printf(“%d”,p[y]);
}
}
}
void buildgraph()
{
int i,j,v1,v2;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf(“\nEnter the edge of v%d to v%d:”,i,j);
scanf(“%d”,&G[i][j]);
}
printf(“\n”);
}
}
void insertq(int index)
{
Q[index]=1;
}
void insert(int index,int vertex)
{
path[index]=vertex;
}
void dijkstra(int scr,int dest)
{
int small,dist[10],current,start,new1;
int temp,i,a[10];
void insertq(int);
for(i=0;i<=n;i++)
{
a[i]=0;
dist[i]=infinity;
}
Q[scr]=1;
dist[scr]=0;
current=scr;
while(current!=dest)
{
small=infinity;
start=dist[current];
for(i=1;i<=n;i++)
{
if(Q[i]==0)
{
new1=start+G[current][i];
if(new1<dist[i])
{
dist[i]=new1;
insert(i,current);
}
if(dist[i]<small)
{
small=dist[i];
temp=i;
}
}
}
current=temp;
insertq(current);
}
//printf(“\nThe minimum cost is:%d”,new1);
}
12a. Implementation of Krusal's Algorithm
Program:
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
int i,j,k,a,b,u,v,n,ne=1;
int min,mincost=0,cost[9][9],parent[9];
int find(int);
int uni(int,int);
void main()
{
clrscr();
printf("\n\n\tImplementation of Kruskal's algorithm\n\n");
printf("\nEnter the no. of vertices\n");
scanf("%d",&n);
printf("\nEnter the cost adjacency matrix\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d",&cost[i][j]);
if(cost[i][j]==0)
cost[i][j]=999;
}
}
printf("\nThe edges of Minimum Cost Spanning Tree are\n\n");
while(ne<n)
{
for(i=1,min=999;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(cost[i][j]<min)
{
min=cost[i][j];
a=u=i;
b=v=j;
}
}
}
u=find(u);
v=find(v);
if(uni(u,v))
{
printf("\n%d edge (%d,%d) =%d\n",ne++,a,b,min);
mincost +=min;
}
cost[a][b]=cost[b][a]=999;
}
printf("\n\tMinimum cost = %d\n",mincost);
getch();
}
int find(int i)
{
while(parent[i])
i=parent[i];
return i;
}
int uni(int i,int j)
{
if(i!=j)
{
parent[j]=i;
return 1;
}
return 0;
}
13.KNAPSACK PROBLEM USING BACKTRACKING ALGORITHM
PROGRAM:
#include
#include
float final_profit=-1.0;
int p[100],w[100];
int m,n;
int temp[100],x[100];
float final_wt=-1.0;
float bound_calculation(int cp,int cw,int k)
{ int ub,c,i;
ub=cp;
c=cw;
for(i=k+1;i<=n;i++)
{ c=c+w[i];
if(c<m)
ub=ub+p[i];
else
return (ub+(1-(c-m)/w[i]*p[i]));
} return ub;
}
void bk(int k,int cp,int cw)
{
int new_k,new_cp,new_cw,j;
if(cw+w[k]<=m)
{
temp[k]=1;
if(kfinal_profit)&&(k==n))
{
final_profit=new_cp;
final_wt=new_cw;
for(j=1;j=final_profit)
{ temp[k]=0;
if(kfinal_profit)&&(k==n))
{ final_profit=cp;
final_wt=cw;
for(j=1;j<=n;j++ )
x[j]=temp[j];
} } }
void main()
{ int i;
clrscr();
printf(“\n\t Knapsack Problem using Backtracking algorithm\n”);
printf(“\n Enter the Capacity of knapsack:”);
scanf(“%d”,&m);
printf(“\n Enter the Total number of Items :”);
scanf(“%d”,&n);
printf(“\n Enter the Profits one by one :”);
for(i=0;i<n;i++)
scanf(“%d”,&p[i]);
printf(“\n Enter the Weights one by one :”);
for(i=0;i<n;i++)
scanf(“%d”,&w[i]);
printf(“\n\nProfit\tWeight”);
printf(“\n____________________________”);
for(i=0;i<n;i++)
printf(“\n%d\t%d”,p[i],w[i]);
printf(“\n______________________________\n”);
bk(1,0,0);
printf(“\n Following Items are selected from Knapsack…”);
for(i=0;i<n;i++)
{ if(x[i]==1)
printf(“\n\t\tItem %d”,i);
}
printf(“\n\n Finalweight =%0.2f”,final_wt);
printf(“\nFinal Profit=%0.2f”,final_profit);
getch();
}
#include
#include
float final_profit=-1.0;
int p[100],w[100];
int m,n;
int temp[100],x[100];
float final_wt=-1.0;
float bound_calculation(int cp,int cw,int k)
{ int ub,c,i;
ub=cp;
c=cw;
for(i=k+1;i<=n;i++)
{ c=c+w[i];
if(c<m)
ub=ub+p[i];
else
return (ub+(1-(c-m)/w[i]*p[i]));
} return ub;
}
void bk(int k,int cp,int cw)
{
int new_k,new_cp,new_cw,j;
if(cw+w[k]<=m)
{
temp[k]=1;
if(kfinal_profit)&&(k==n))
{
final_profit=new_cp;
final_wt=new_cw;
for(j=1;j=final_profit)
{ temp[k]=0;
if(kfinal_profit)&&(k==n))
{ final_profit=cp;
final_wt=cw;
for(j=1;j<=n;j++ )
x[j]=temp[j];
} } }
void main()
{ int i;
clrscr();
printf(“\n\t Knapsack Problem using Backtracking algorithm\n”);
printf(“\n Enter the Capacity of knapsack:”);
scanf(“%d”,&m);
printf(“\n Enter the Total number of Items :”);
scanf(“%d”,&n);
printf(“\n Enter the Profits one by one :”);
for(i=0;i<n;i++)
scanf(“%d”,&p[i]);
printf(“\n Enter the Weights one by one :”);
for(i=0;i<n;i++)
scanf(“%d”,&w[i]);
printf(“\n\nProfit\tWeight”);
printf(“\n____________________________”);
for(i=0;i<n;i++)
printf(“\n%d\t%d”,p[i],w[i]);
printf(“\n______________________________\n”);
bk(1,0,0);
printf(“\n Following Items are selected from Knapsack…”);
for(i=0;i<n;i++)
{ if(x[i]==1)
printf(“\n\t\tItem %d”,i);
}
printf(“\n\n Finalweight =%0.2f”,final_wt);
printf(“\nFinal Profit=%0.2f”,final_profit);
getch();
}
OUTPUT:
Knapsack Problem using Backtracking algorithm
Enter the Capacity of knapsack:167
Enter the Total number of Items :6
Enter the Profits one by one :
56 23 89 14 65 23
Enter the Weights one by one :
89 23 54 76 82 91
Profit Weight
____________________________
56 89
23 23
89 54
14 76
65 82
23 91
______________________________
Following Items are selected from Knapsack…
Item 1
Item 2
Item 4
Final weight =159.00
Final Profit=177.00
Enter the Capacity of knapsack:167
Enter the Total number of Items :6
Enter the Profits one by one :
56 23 89 14 65 23
Enter the Weights one by one :
89 23 54 76 82 91
Profit Weight
____________________________
56 89
23 23
89 54
14 76
65 82
23 91
______________________________
Following Items are selected from Knapsack…
Item 1
Item 2
Item 4
Final weight =159.00
Final Profit=177.00
0 comments:
Post a Comment
Thanks For Coming The Page.