Home > Data Structure EE2204 > Data Structure Lab Program

Data Structure Lab Program

1. Implement singly and doubly linked lists.
1.1 singly linked list

#include
#include
#include
typedef struct list
{
int data;
struct list*next;
}node;
node *newnode,*temp,*head;
node* getnode()
{
node *n;
n=(node*)malloc(sizeof(node));
n->next=NULL;
return(n);
}
void create()
{
char ch=’y’;
head->next=NULL;
do
{
newnode =getnode();
printf(“\n enter the element:”);
scanf(“%d”,&newnode->data);
if(head->next==NULL)
head->next=newnode;
else
temp->next=newnode;
temp=newnode;
printf(“do u wnt to cont?:”);
ch=getch();
}
while(ch==’y’||ch==’Y’);
}
void display()
{
printf(“\n\nthe list is:”);
for(temp=head->next;temp!=NULL;temp=temp->next)
{
printf(“\t%d”,temp->data);
}
getch();
}
void insert()
{
int pos;
temp=head->next;
newnode=getnode();
printf(“\n\nenter the new element & pos element aft to be inserted:”);
scanf(“%d%d”,&newnode->data,&pos);
while(temp->data!=pos&&temp->next!=NULL)
{
temp=temp->next;
}
newnode->next=temp->next;
temp->next=newnode;
printf(“\nnew node inserted…”);
display();
}
void first()
{
newnode=getnode();
printf(“\nenter the new element:”);
scanf(“%d”,&newnode->data);
newnode->next=head->next;
head->next=newnode;
printf(“\nnew node inserted at first…”);
display();
}
void del()
{
int pos;
node *temp1;
temp=head->next;
printf(“\n enter the pos element:”);
scanf(“%d”,&pos);
temp1=head;
while(temp->data!=pos&&temp->next!=NULL)
{
temp1=temp;
temp=temp->next;
}
temp1->next=temp->next;
free(temp);
printf(“\n\nnode deleted…”);
display();
}
void search()
{
int pos,i=1;temp=head->next;
printf(“enter the element to be search”);
scanf(“%d”,&pos);
while(temp->next!=NULL&&temp->data!=i)
{
if(temp->data==pos)
{
printf(“\n element at pos %d in the list”,i);
;
break;
}
else
{
i+=1;
temp=temp->next;
}
}
display();
}
void main()
{
int op;
do
{
clrscr();
printf(“\n\n\t\tlinked list implementation of list”);
printf(“\n1.create\n2.display\n3.insert\n4.insert first\n5.search\n6.delete\n7.exit”);
printf(“\n enter the option:”);
scanf(“%d”,&op);
switch(op)
{
case 1:
create();
break;
case 2:
display();
break;
case 3:
insert();
break;
case 4:
first();
break;
case 5:
search();
break;
case 6:
del();
break;
}
}
while(op<=6);
}

1.2 doubly linked lists

#include
#include
#include
typedef struct list
{
int data;
struct list*next,*pre;
}node;
node *newnode,*temp,*head=NULL;
node* getnode()
{
node *n;
n=(node*)malloc(sizeof(node));
n->next=NULL;
n->pre=NULL;
return(n);
}
void create()
{
char ch=’y’;
do
{
newnode =getnode();
printf(“\n Enter the element:”);
scanf(“%d”,&newnode->data);
if(head->next==NULL)
{
head->next=newnode;
newnode->pre=head;
}

else
{
temp->next=newnode;
newnode->pre=temp;
}
temp=newnode;
printf(“do u wnt to cont?:”);
ch=getch();
}
while(ch==’y’||ch==’Y’);
}
void display()
{
printf(“\n\nthe list is:”);
for(temp=head->next;temp!=NULL;temp=temp->next)
{
printf(“\t%d”,temp->data);
}
getch();
}
void insert()
{
int pos;
temp=head->next;
newnode=getnode();
printf(“\n\nenter the new element & pos element aft to be inserted:”);
scanf(“%d%d”,&newnode->data,&pos);
while(temp->data!=pos&&temp->next!=NULL)
{
temp=temp->next;
}
newnode->next=temp->next;
newnode->pre=temp;
temp->pre=newnode;
newnode->pre->next=newnode;
printf(“\nnew node inserted…”);
display();
}
void first()
{
temp=getnode();
printf(“\nenter the new element:”);
scanf(“%d”,&temp->data);
temp->next=head->next;
head->next->pre=temp;
head->next=temp;
temp->pre=head;
printf(“\nnew node inserted at first…”);
display();
}
void del()
{
int pos;
node *temp1;
temp=head;
printf(“\n enter the pos element:”);
scanf(“%d”,&pos);
while(temp->data!=pos&&temp->next!=NULL)
{
temp1=temp;
temp=temp->next;
}
temp1->next=temp->next;
free(temp);
printf(“\n\nnode deleted…”);
display();
}
void search()
{
int pos,i=1;temp=head;
printf(“enter the element to be search”);
scanf(“%d”,&pos);
while(temp->next!=NULL)
{
if(temp->next->data==pos)
{
printf(“\n element at pos %d in the list”,i);
break;
}
else
{
i=i+1;
temp=temp->next;
}
}
display();
}
void main()
{
int op;
head=(node*)malloc(sizeof(node));
do
{
clrscr();
printf(“\n\n\t\tlinked list implementation of list”);
printf(“\n1.create\n2.display\n3.insert\n4.insert first\n5.search\n6.delete\n7.exit”);
printf(“\n enter the option:”);
scanf(“%d”,&op);
switch(op)
{
case 1:
create();
break;
case 2:
display();
break;
case 3:
insert();
break;
case 4:
first();
break;
case 5:
search();
break;
case 6:
del();
break;
}
}
while(op<=6);
}

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

#include
#include
typedef struct pnode
{
float coef;
int exp;
struct pnode *next;
}p;
p *getnode();
void main()
{
p *p1,*p2,*p3;

p *getpoly(),*add(p*,p*);

void display(p*);
clrscr();
printf(“\n enter first polynomial”);
p1=getpoly();
printf(“\n enter second polynomial”);
p2=getpoly();
printf(“\nthe first polynomial is”);
display(p1);
printf(“\nthe second polynomial is”);
display(p2);
p3=add(p1,p2);
printf(“\naddition of two polynomial is :\n”);
display(p3);

}
p *getpoly()
{
p *temp,*New,*last;
int flag,exp;
char ans;
float coef;
temp=NULL;
flag=1;
printf(“\nenter the polynomial in descending order of exponent”);
do
{
printf(“\nenter the coef & exponent of a term”);
scanf(“%f%d”,&coef,&exp);
New=getnode();
if(New==NULL)
printf(“\nmemory cannot be allocated”);
New->coef=coef;
New->exp=exp;
if(flag==1)
{
temp=New;
last=temp;
flag=0;
}
else
{
last->next=New;
last=New;
}
printf(“\ndou want to more terms”);
ans=getch();
}
while(ans==’y’);
return(temp);
}
p *getnode()
{
p *temp;
temp=(p*) malloc (sizeof(p));
temp->next=NULL;
return(temp);
}
void display(p*head)
{
p*temp;
temp=head;
if(temp==NULL)
printf(“\npolynomial empty”);
while(temp->next!=NULL)
{
printf(“%0.1fx^%d+”,temp->coef,temp->exp);
temp=temp->next;
}
printf(“\n%0.1fx^%d”,temp->coef,temp->exp);
getch();
}
p*add(p*first,p*second)
{
p *p1,*p2,*temp,*dummy;
char ch;
float coef;
p *append(int,float,p*);
p1=first;
p2=second;
temp=(p*)malloc(sizeof(p));
if(temp==NULL)
printf(“\nmemory cannot be allocated”);
dummy=temp;
while(p1!=NULL&&p2!=NULL)
{
if(p1->exp==p2->exp)
{
coef=p1->coef+p2->coef;
temp=append(p1->exp,coef,temp);
p1=p1->next;
p2=p2->next;
}
else
if(p1->expexp)
{
coef=p2->coef;
temp=append(p2->exp,coef,temp);
p2=p2->next;
}
else
if(p1->exp>p2->exp)
{
coef=p1->coef;
temp=append(p1->exp,coef,temp);
p1=p1->next;
}
}
while(p1!=NULL)
{
temp=append(p1->exp,p1->coef,temp);
p1=p1->next;
}
while(p2!=NULL)
{
temp=append(p2->exp,p2->coef,temp);
p2=p2->next;
}
temp->next=NULL;
temp=dummy->next;
free(dummy);
return(temp);
}
p*append(int Exp,float Coef,p*temp)
{
p*New,*dum;
New=(p*)malloc(sizeof(p));
if(New==NULL)
printf(“\ncannot be allocated”);
New->exp=Exp;
New->coef=Coef;
New->next=NULL;
dum=temp;
dum->next=New;
dum=New;
return(dum);
}
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.

#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
{

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);
}

5. Implement an expression tree. Produce its pre-order, in-order, and post-order traversals.
#include
#include
#include
typedef struct tree
{
char data;
struct tree *left;
struct tree *right;
}*pos;
pos stack[30];
int top=-1;
pos newnode(char b)
{
pos temp;
temp=(struct tree*)malloc(sizeof(struct tree));
temp->data=b;
temp->left=NULL;
temp->right=NULL;
return(temp);
}
void push(pos temp)
{
stack[++top]=temp;
}
pos pop()
{
pos p;
p=stack[top--];
return(p);
}
void inorder(pos t)
{
if(t!=NULL)
{
inorder(t->left);
printf(“%s”,t->data);
inorder(t->right);
}
}
void preorder(pos t)
{
if(t!=NULL)
{
printf(“%s”,t->data);
preorder(t->left);
inorder(t->right);
}
}
void postorder(pos t)
{
if(t!=NULL)
{
postorder(t->left);
postorder(t->right);
printf(“%s”,t->data);
}
}
void main()
{
char a[20];pos temp,t;int j,i;
clrscr();
printf(“\nEnter the postfix expression”);
gets(a);
for(i=0;a[i]!=NULL;i++)
{
if(a[i]==’*’ || a[i]==’/’ || a[i]==’+’ || a[i]==’-’)
{
temp=newnode(a[i]);
temp->right=pop();
temp->left=pop();
push(temp);
}
else
{
temp=newnode(a[i]);
push(temp);
}
}
inorder(temp);
printf(“\n”);
preorder(temp);
printf(“\n”);
postorder(temp);
getch();
}
BST program

#include
#include
typedef struct btree
{
int data;
struct btree *left;
struct btree *right;
}*node;
node findmin(node t)
{
if(t->left==NULL)
{
return(t);
}
else
{
return(findmin(t->left));
}
}
node insert(node t,int x)
{
if(t==NULL)
{
t=(struct btree*)malloc(sizeof(struct btree));
if(t!=NULL)
{
t->data=x;
t->left=NULL;
t->right=NULL;
}
}
else if(t->data>x)
{
t->left=insert(t->left,x);
}
else if(t->dataright=insert(t->right,x);
}
return t;
}
node deletion(node t,int x)
{
if(t==NULL)
{
printf(“\nEmpty”);
}
else if(x>t->data)
{
t->right=deletion(t->right,x);
}
else if(xdata)
{
t->left=deletion(t->left,x);
}
else if(t->right!=NULL && t->left!=NULL)
{
node temp;
temp=findmin(t->right);
t->data=temp->data;
t->right=deletion(t->right,t->data);
}
else
{
node temp;
temp=t;
if(t->left==NULL)
{
t=t->right;
}
else if(t->right==NULL)
{
t=t->left;
}
free(temp);
}
return t;
}
node findmax(node t)
{
if(t->right==NULL)
{
return t;
}
else
{
return(findmax(t->right));
}
}
void inorder(node t)
{
if(t!=NULL)
{
inorder(t->left);
printf(“%d \t”,t->data);
inorder(t->right);
}
}
void main()
{
int ch,a;node t,t1,t2;
t=NULL;
clrscr();
menu:
printf(“\nBinary Search Tree”);
printf(“\n1.Insert\n2.Delete\n3.Find Minimum\n4.Find Maximum\n5.Display tree\n6.Exit”);
printf(“\nEnter the choice :”);
scanf(“%d”,&ch);
switch(ch)
{
case 1:printf(“\nEnter the data to be inserted”);
scanf(“%d”,&a);
t=insert(t,a);
break;
case 2:printf(“\nEnter the data to be deleted”);
scanf(“%d”,&a);
t=deletion(t,a);
break;
case 3:t1=findmin(t);
printf(“\n%d is the minimun element”,t1->data);
break;
case 4:t2=findmax(t);
printf(“\n%d is the maximum element”,t2->data);
break;
case 5:inorder(t);
break;
case 6:exit(0);
default:printf(“\nWrong input”);
}goto menu;
}

8. Implement priority queue using heaps

#include
#include
struct heapstruct
{
int capacity;
int size;
int *a;
};
typedef struct heapstruct *pq;
pq initialize(int maxa,int mindata)
{
pq h;
h=(struct heapstruct*)malloc(sizeof(struct heapstruct));
if(h==NULL)
printf(“\nOut of Space”);
h->a=(int*)malloc((maxa+1)*sizeof(int));
h->capacity=maxa;
h->size=0;
h->a[0]=mindata;
return h;
}
void insert(int x,pq h)
{
int i;
if(h->size==h->capacity)
{
printf(“\nFull”);
}
else
{
for(i=++h->size;h->a[i/2]>x;i=i/2)
{
h->a[i]=h->a[i/2];
}
h->a[i]=x;
}
}
int delmin(pq h)
{
int i,mina,lasta,child;
if(h->size==0)
{
return(h->a[0]);
}
else
{
mina=h->a[1];
lasta=h->a[h->size--];
for(i=1;i*2size;i=child)
{
child=i*2;
if(child!=h->size && h->a[child+1]a[child])
child++;
if(lasta>h->a[child])
{
h->a[i]=h->a[child];
}
else
break;
}
h->a[i]=lasta;
return mina;
}
}
void display(pq h)
{
int i;
for(i=1;isize;i++)
{
printf(“\nThe data is: %d”,h->a[i]);
}
}
void main()
{
pq h;int x,y,z,u,v;char ch;
clrscr();
printf(“\nEnter the maximum number of elements for the Priority Queue:”);
scanf(“%d”,&x);
printf(“\nEnter the minimum element :”);
scanf(“%d”,&y);
h=initialize(x,y);
menu:
printf(“\nPriority Queue”);
printf(“\n1.Insert\n2.Delete\n3.Display\n4.Exit”);
scanf(“%d”,&u);
switch(u)
{
case 1:printf(“Enter the Data:”);
scanf(“%d”,&z);
insert(z,h);
break;
case 2:v=delmin(h);
printf(“\nThe deleted element is: %d”,v);
break;
case 3:display(h);
break;
case 4:exit(0);
}
goto menu;
}

HASHING IMPLEMENTATION USING OPEN ADDRESSING
#include
#include
void main()
{
int a[10]={0,0,0,0,0,0,0,0,0,0};
int n,value,temp,hashvalue;
clrscr();
printf(“\nEnter 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 other value”);
a[hashvalue]=value;
printf(“\n a[%d]the value %d is stored”,hashvalue,value);
goto menu;
}
}
hashvalue=0;
for(hashvalue;hashvalue<n;hashvalue++)
{
if(a[hashvalue]==0)
{
printf(“Space is allocated give other value”);
a[hashvalue]=value;
printf(“\n a[%d]the value %d is stored”,hashvalue,value);
goto menu;
}
}
printf(“ERROR”);
printf(“\nEnter ’0′ and press ‘Enter key’ twice to exit”);

}
menu:
printf(“\n Do u want enter more”);
scanf(“%d”,&temp);
}
while(temp==1);
getch();
}
OUTPUT:

Enter the value of n(table size):3

Enter the hash value:10

a[1]the value 10 is stored
Do u want enter more:1

Enter the hash value:20

a[2]the value 20 is stored
Do u want enter more:1

Enter the hash value:30

a[0]the value 30 is stored
Do u want enter more:1

Enter the hash value:40
ERROR
Enter ’0′ and press ‘Enter key’ twice to exit
Do u want enter more:0
TOPOLOGICAL SORTING
#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

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

Nodes after topological sorting are:

1 2 5 4 37 6

11. Implement Dijkstra’s algorithm using priority queues
#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);
}

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();
}
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

About these ads
  1. mohanapriyaa
    August 17, 2010 at 12:18 AM | #1

    really its nice.. so useful .. can u give ur id .. to contact u .

  2. mohanapriyaa
    August 17, 2010 at 2:19 AM | #2

    its really super.. no word to express my feeling know..

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: