I was reading this example of Priority queues and have several questions.
http://matrixsust.blogspot.com/2011/11/basic-priority-queue-in-c.html
#include<stdio.h>
#include<malloc.h>
void insert();
void del();
void display();
//How exactly do structs in structs work? Do you need to do anything special with them? Is this a //form of a linked list? Which part of this is set to NULL? A lot of the comparisons later on are // to NULL. Were the node names made as pointers to make them easier to pass to functions later on?
//Do you really need to make them pointers? Do you really need that many names?
struct node
{
int priority;
int info;
struct node *next;
}*start, *q, *temp, *new;
//Why was this declared as typedef? I thought you only use typedef if you want to reuse a type more //easily.
typedef struct node *N;
int main()
{
int ch;
do
{
printf( "\n[1] INSERTION\t[2] DELETION\t[3] DISPLAY [4] EXIT\t:" );
scanf( "%d", &ch );
while(ch > 4)
{
printf( "\n[1] INSERTION\t[2] DELETION\t[3] DISPLAY [4] EXIT\t:" );
scanf( "%d", &ch );
}
switch ( ch )
{
case 1:
insert();
break;
case 2:
del();
break;
case 3:
display();
break;
case 4:
break;
}
}
while ( ch < 4 );
return 0;
}
void insert()
{
int item, itprio;
//Is new being initialized to NULL?
new = ( N* ) malloc( sizeof( N ) );
printf( "ENTER THE ELT.TO BE INSERTED :\t" );
scanf( "%d", &item );
printf( "ENTER ITS PRIORITY :\t" );
scanf( "%d", &itprio );
//The arrow is being used because new is a pointer right? What if just new is a pointer and N
//wasn't a pointer? What about if N was a pointer and new wasn't a pointer? Would you still use
// a pointer in both cases?
new->info = item;
new->priority = itprio;
//Was start set to NULL when it was declared at the top?
if ( start == NULL || itprio < start->priority )
{
//Is this where the linking of the linked list happens?
new->next = start;
//whats happening here? Setting a new start because the lower the priority number, the
//higher the priority it has?
start = new;
printf("if in insert \n");
}
else
{
//I don't understand this else block of code at all.
q = start;
while ( q->next != NULL && q->next->priority <= itprio )
q = q->next;
new->next = q->next;
q->next = new;
printf("else in insert \n");
}
}
void del()
{
if ( start == NULL )
{
printf( "\nQUEUE UNDERFLOW\n" );
}
else
{
new = start;
printf( "\nDELETED ITEM IS %d\n", new->info );
//Are you moving start to the next link in the list?
start = start->next;
//How does free know which start to get rid of? The original start of the just moved to start?
free( start );
printf("else in del \n");
}
}
void display()
{
//Could you have gotten this display function to work without setting start equal to temp?
//Could you just replace all the temps with start? Are you risking messing up start by
//not doing this?
temp = start;
if ( start == NULL )
printf( "QUEUE IS EMPTY\n" );
else
{
printf( "QUEUE IS:\n" );
while ( temp != NULL )
{
printf( "\t%d[priority=%d]", temp->info, temp->priority );
temp = temp->next;
printf("else while in display \n");
}
}
}
My compiler also complained about this line? Is this important? Its usually a bad idea to ignore compiler warnings.
main.c: In function ‘insert’:
main.c:60: warning: assignment from incompatible pointer type
new = ( N* ) malloc( sizeof( N ) );
Does creating a priority queue like this have any advantages? What is the significance of of -1? They set there front and rear to that. It seems like you are creating more trouble for yourself by setting the size of your priority queue. Will you run into any issues with not using free()?
http://www.sanfoundry.com/c-program-priority-queue/
/*
* C Program to Implement Priority Queue to Add and Delete Elements
*/
#include <stdio.h>
#include <stdlib.h>
#define MAX 5
void insert_by_priority(int);
void delete_by_priority(int);
void create();
void check(int);
void display_pqueue();
int pri_que[MAX];
int front, rear;
void main()
{
int n, ch;
printf("\n1 - Insert an element into queue");
printf("\n2 - Delete an element from queue");
printf("\n3 - Display queue elements");
printf("\n4 - Exit");
create();
while (1)
{
printf("\nEnter your choice : ");
scanf("%d", &ch);
switch (ch)
{
case 1:
printf("\nEnter value to be inserted : ");
scanf("%d",&n);
insert_by_priority(n);
break;
case 2:
printf("\nEnter value to delete : ");
scanf("%d",&n);
delete_by_priority(n);
break;
case 3:
display_pqueue();
break;
case 4:
exit(0);
default:
printf("\nChoice is incorrect, Enter a correct choice");
}
}
}
/* Function to create an empty priority queue */
void create()
{
front = rear = -1;
}
/* Function to insert value into priority queue */
void insert_by_priority(int data)
{
if (rear >= MAX - 1)
{
printf("\nQueue overflow no more elements can be inserted");
return;
}
if ((front == -1) && (rear == -1))
{
front++;
rear++;
pri_que[rear] = data;
return;
}
else
check(data);
rear++;
}
/* Function to check priority and place element */
void check(int data)
{
int i,j;
for (i = 0; i <= rear; i++)
{
if (data >= pri_que[i])
{
for (j = rear + 1; j > i; j--)
{
pri_que[j] = pri_que[j - 1];
}
pri_que[i] = data;
return;
}
}
pri_que[i] = data;
}
/* Function to delete an element from queue */
void delete_by_priority(int data)
{
int i;
if ((front==-1) && (rear==-1))
{
printf("\nQueue is empty no elements to delete");
return;
}
for (i = 0; i <= rear; i++)
{
if (data == pri_que[i])
{
for (; i < rear; i++)
{
pri_que[i] = pri_que[i + 1];
}
pri_que[i] = -99;
rear--;
if (rear == -1)
front = -1;
return;
}
}
printf("\n%d not found in queue to delete", data);
}
/* Function to display queue elements */
void display_pqueue()
{
if ((front == -1) && (rear == -1))
{
printf("\nQueue is empty");
return;
}
for (; front <= rear; front++)
{
printf(" %d ", pri_que[front]);
}
front = 0;
}
How would you change from a lower the number the higher the priority to the higher the number the higher the priority? How would you access the second member of your priority queue or the fifth member of your priority queue?
