Tuesday, October 1, 2013

priority queue using linked list

//priority queue using linked list

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

typedef struct node
{
int info,pr;
struct node *next;
}node;
node *start=NULL;

void insert_at_end(int x,int p);
void insert_at_beg(int x,int p);
void insert_at_specific(int ,int, int);
void del_at_beg();
void insert(int x,int p);

int main()
{
int n,po,ch,p;
while(1)
{
printf("\n\t\t\tMenu");
printf("\n\t\t\t1 : Insertion");
printf("\n\t\t\t2 : Deletion");
printf("\n\t\t\t3 : Exit");
printf("\n\t\t\tEnter ur choice : ");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("\nEnter the info :");
scanf("%d",&n);
printf("\nEnter the priority :");
scanf("%d",&p);
insert(n,p);
break;
case 2:
del_at_beg();
break;
case 3:
exit(0);
default:
printf("\nInvalid choice");
}
}
return 0;
}

void insert_at_end(int x, int p)
{
node *temp,*new_node;
new_node=(node*)malloc(sizeof(node));
new_node->info=x;
new_node->pr=p;
new_node->next=NULL;
if(start==NULL)
start=new_node;
else
{
temp=start;
while(temp->next!=NULL)
temp=temp->next;
temp->next=new_node;
}
}

void insert_at_beg(int x,int p)
{
node *new_node;
new_node=(node*)malloc(sizeof(node));
new_node->info=x;
new_node->pr=p;
new_node->next=start;
start=new_node;
}

void insert_at_specific(int x,int p,int po)
{
int i;
node *new_node,*temp;
if(po<1 || po>count()+1)
{
printf("\nInvalid position");
return;
}
if(po==1)
insert_at_beg(x,p);
else
{
if(po==count()+1)
insert_at_end(x,p);
else
{
new_node=(node*)malloc(sizeof(node));
new_node->info=x;
new_node->pr=p;
new_node->next=NULL;
temp=start;
for(i=1;i<po-1;i++)
temp=temp->next;
new_node->next=temp->next;
temp->next=new_node;
}
}
}


int count()
{
node *temp;
int c=0;
for(temp=start;temp!=NULL;temp=temp->next)
c++;
return c;
}

void del_at_beg()
{
node *temp;
if(start==NULL)
{
printf("\nList Empty");
return;
}
temp=start;
start=start->next;
printf("\nDeleted node : %d",temp->info);
printf("\nDeleted priority : %d",temp->pr);
free(temp);
}

void insert(int x,int p)
{
node *temp;
int po=0;
if(start==NULL)
{
insert_at_beg(x,p);
return;
}
temp=start;
while(temp!=NULL)
{
if(temp->pr >= p)
{
po++;
temp=temp->next;
}
else
break;
}
insert_at_specific(x,p,po+1);
}

No comments: