Could any expert explain to me how this priority queue works?
Hi could any expert explain to me how this works? especially those in red, bold.
Been figuring for a couple of hours & hope to understand how this code works.
Thanks.
Code:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX_STR_LEN 81
#define MAX_NODE 255
typedef struct
{
int priority;
char string[MAX_STR_LEN];
}element;
typedef struct pqueue{
element item[MAX_NODE];
int size;
}pqueue;
// Adds a new word with given priority
int enqueuepriority(pqueue *pq, char* str, int priority)
{
int i ;
if (pq->size==MAX_NODE) {
fprintf(stderr,"The heap is full!\n");
exit(1);
}
i=++pq->size;
while (i-1&&priority<pq->item[i/2].priority)
{
pq->item[i]=pq->item[i/2];
i/=2;
}
pq->item[i].priority=priority;
strcpy(pq->item[i].string,str);
return priority;
}
// Returns the string stored in the first node
char* dequeue(pqueue *pq)
{
element ele,tmp;
static char rtstr[MAX_STR_LEN];
int parent,child;
if (pq->size==0) {
fprintf(stderr,"The heap is empty!\n");
exit(1);
}
ele=pq->item[1];
tmp=pq->item[pq->size--];
parent=1;
child=2;
while (child<=pq->size)
{
if (child<pq->size && pq->item[child].priority>pq->item[child+1].priority)
child++;
if (tmp.priority<=pq->item[child].priority) break;
pq->item[parent]=pq->item[child];
parent=child;
child*=2;
}
pq->item[parent]=tmp;
strcpy(rtstr,ele.string);
return rtstr;
}
void init_prt(void)
{
printf("(1) Enqueue (single)\n(2) Enqueue (multiple)\n(3) Dequeue (single)\n(4) Dequeue (all)\n(5) Quit");
printf("\nChoose an action: ");
}
void proc(pqueue *pq,const int c)
{
char str[MAX_STR_LEN];
int priority;
switch (c) {
case 1:
printf("Enter a name to save and its priority : \n");
scanf("%s%d",str,&priority);
enqueuepriority(pq,str,priority);
break;
case 2:
printf("Enter names to save and their priority. Enter “done” to quit\n");
do
{
scanf("%s",str);
if (strcmp(str,"done")) {
scanf("%d",&priority);
enqueuepriority(pq,str,priority);
}
else break;
}while (1);
break;
case 3:
printf("%s\n",dequeue(pq));
break;
case 4:
while (pq->size)
printf("%s\n",dequeue(pq));
break;
case 5: break;
default:fprintf(stderr,"input error,re-input please!\n");break;
}
}
int main(void)
{
pqueue pq={0};
int chp;
do
{
init_prt();
fflush(stdin);
scanf("%d",&chp);
proc(&pq,chp);
printf("\n++++++++++++++++++++++++++++++++\n\n");
}while (chp!=5);
return 0;
}
|
