1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Could any expert explain to me how this priority queue works?

Discussion in 'C' started by won212, Apr 5, 2012.

  1. won212

    won212 New Member

    Joined:
    Mar 3, 2012
    Messages:
    17
    Likes Received:
    2
    Trophy Points:
    0
    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);
            }
           [B][COLOR=red] i=++pq->size;
            while (i-1&&priority<pq->item[i/2].priority)
            {
                pq->item[i]=pq->item[i/2];
                i/=2;
    [/COLOR][/B]        }
            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)
    {
       [B][COLOR=red] 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;
    [/COLOR][/B]}
    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;
    }
    
    
     

Share This Page