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?

How exactly do structs in structs work? Do you need to do anything special with them?

What do you mean by 'special'? What you would do woith them would depend on what you intentions are. I know that sounds evasive, but it really is as much of an answer as I can give to such a vague question.

I think what you really want to know is, does the inner structure have to be a pointer?The answer to that again depends. In the general case, no, it doesn't - you can have a struct variable as an element of another struct:

struct POINT 
{
    int x, y;
};

struct VECTOR
{
    struct POINT start, end;
};

However, you'll note that these are individual elements, which are (relative to the structure) statically declared; if you want an element that is dynamically allocated, like a variable-length array or a linked list, the element would need to be a pointer to that data structure.

Also, any time a struct references its own type, it has to be via a pointer. Otherwise, the structure definition would be infinitely recursive.

Is this a form of a linked list?

Well, a linked data structure of some sort, yes. In this case, it does seem to be a list, but usually priority queues are more elaborate tree structures called heaps.

Which part of this is set to NULL? A lot of the comparisons later on are to NULL.

Well, ideally they would all be initialized to NULL before use, as a precaution, but that would take place in the functions, not here.

Were the node names made as pointers to make them easier to pass to functions later on?

No, they were declared as pointers because they are intended to reference dynamically allocated memory.

Do you really need to make them pointers?

Yes.

Do you really need that many names?

Yes and no; most of them are temporary variables used by several functions. They didn't all need to be globals, though, and really shouldn't have been strictly speaking; the coder who wrote this was just saving some typing by not re-declaring the temporary variables in each function.

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;

That's exactly why it is being typedefed, if I am not mistaken; the coder simply didn't want to repeat struct node * all over the place, so he aliased it to N to abstract it.

Is new being initialized to NULL?

   new = ( N* ) malloc( sizeof( N ) );

Quite the contrary, it is being set to a newly allocated space in memory which it can now use as a variable of type N (which is the same as struct node *, remember). However, the original programmer made a mistake here, I think; because N is an alias for a pointer type, it would allocate the space needed for a pointer, not for a struct node structure (which is much larger). I would expect that to cause memory problems with this code.

Edited 2 Years Ago by Schol-R-LEA

To continue...

    new->info = item;
    new->priority = itprio;

The arrow is being used because new is a pointer right?

Yes. The 'arrow' is the member indirection operator; it allows you to access structure member elements from a pointer to that structure.

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?

This question doesn't make much sense to me. N isn't a pointer variable, it is a pointer type. Furthermore, since new was declared as type struct node * directly, not type N (even if they are in fact the same thing), the question of what N is isn't relevant.

    if ( start == NULL || itprio < start->priority )  

Was start set to NULL when it was declared at the top?

No, in fact as far as I can tell, none of the variables are being initialized to NULL explicitly. This is a Bad Thing, as the original programmer seems to be assuming that the compiler will zero out all the memory before it is used, which usually isn't the case. This is not the only place that bad practices are used; for example, the call to malloc() is incorrect, as I said earlier. also, the header file shouldn't be <malloc.h>; according to the standard, the dynamic memory functions are in <stdlib.h>. All in all, this isn't a great example to learn from.

    new->next = start;

Is this where the linking of the linked list happens?

Sort of. What is happening here is that the new node has a higher priority than the existing highest priority node, so it is setting the new node to point to the old head of the list. the next line then makes the new node the new head of the list:

    start = new;

Whats happening here? Setting a new start because the lower the priority number, the higher the priority it has?

Basically, yes, at least that seems to be the intention.

    else
    {
        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");
    }

I don't understand this else block of code at all.

OK, in the first part of the if() statement, it checked to see if the list was empty (start == NULL) or if the new node had a higher priority than the current head node (itprio < start->priority), and if either of those were the case, then it replaced the head node with the new node. Following so far?

In the else clause, it handles the case where it isn't changing the head node. What it is doing is looping through the list until it finds either a node whose successor has a lower priority than the new node (q->next->priority <= itprio) or it finds the end of the list (q->next != NULL). Keep in mind here that a while() loop goes on as long as the statement is true, which is why it is checked to see if it hasn't reached those conditions. If it hasn't reached one of those conditions, it resets q, which is a pointer to a node in the list, to the next node in the list, moving it forward by one. This way, the test keeps moving forward through the list.

The next two lines are what it does when it finds what it is looking for: a node that is lower priority than the new node. It then inserts the new node in front of the lower priority node. Finally, and rather unnecessarily, it prints out that it inserted the node.

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");

    }
}

The original coder really screwed up here. It is apparent that it ought to be free(new), not free(start). This is a major mistake, and if it works at all it's by accident. It's clear this code wasn't properly tested.

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?

No, you can't, and yes, it would risk messing up start. Except when changing its value, you should never alter the value of the head of the list, otherwise the list as a whole could be lost and the memory leaked. You need at least one handle for the head of the list at all times.

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

Yeah, the coder made another mistake here; it seems they forgot that N was a pointer type already, and cast the returned value to a pointer to N rather than just N. This made its type struct node ** rather than struct node *, which is the type of new. It would have been better to foregoe the typedef entirely (since it is only used in one place) and simply used

new = (struct node *) malloc( sizeof(struct node) );

which would have been the correct allocation. Of course, there's a debate over casting the value of malloc() at all, but I'll leave that issue alone for now.

Thank you for your patience in giving your very detailed explanation :).

I changed the malloc part, added the initialization part, fixed the del() function.

This article has been dead for over six months. Start a new discussion instead.