Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/forums/c/)
-   -   Could any expert explain to me how this priority queue works? (http://www.go4expert.com/forums/expert-explain-priority-queue-t28138/)

won212 5Apr2012 12:42

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



All times are GMT +5.5. The time now is 08:40.