1. We have moved from vBulletin to XenForo and you are viewing the site in the middle of the move. Though the functional aspect of everything is working fine, we are still working on other changes including the new design on Xenforo.
    Dismiss Notice

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

    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