C++, Linked Lists for Priority Queues

Question

I'm working on an assignment and the goal is to make a module that will assist in representing a priority queue displaying each 'item' and it's appropriate 'priority value'. I'm not asking anybody to do my "homework" for me as stated in my previous post, I'm simply asking for help understanding where I am going wrong with my insert and insertCell functions that gives me errors. Any advice/tips would be very helpful in solving my problem.

//Beginning of Code
//File: pqueue.cpp


//Module pqueue.cpp provides priority queues that include items and their 
//priority types. It tests for empty queues, can insert priority queues that
//include a new item with a new priority, can remove priority queues and/or
//items with their priorities, and can print each item along with its priority
//to the standard output.
//
//

#include <cstdio>
#include "pqueue.h"
#include <cstdlib>

using namespace std;

//An object of type PQCell represents a cell in a linked list.
//
//PQCell has three field.
//
//item- the particular item that is entered
//priority- the priority that an item has
//nextList- a pointer to the next cell in the list
struct PQCell
{ 
    ItemType item;
    PriorityType priority;
    PQCell *nextItem;

    PQCell(ItemType a, PriorityType b, PQCell* nextCell)
    {
        item = a;
        priority = b;
        nextItem = nextCell;
    }   
};

//Function isEmpty returns true if the queue is empty and false if it is not.
bool isEmpty(const PriorityQueue& q)
{
    if(q.cells == NULL)
    {
            return false;
    }

    return true;
}   

//Function insertCell inserts item x with priority p into a linked list 'L'.
void insertCell(PQCell*& L, ItemType x, PriorityType p)
{
    if(L==NULL || L -> priority > p)
    {
        L = new PQCell(x, p, L);
    }

    else
    {
        insertCell(L -> nextItem, x,p);
    }
}

//Function insert inserts item x with priority p into a priority queue 'q'.
void insert(PriorityQueue& q, ItemType x, PriorityType p)
{
    insertCell(q, x, p);
}

//Function printPriorityQueue prints a representation of the priority queue 
//including each value, x, and it's priority type, y, respectively.
void printPriorityQueue(const PriorityQueue& q, ItemPrinter printItem, 
        PriorityPrinter printPriority)
{
    PQCell* pointer = q.cells;
    while(pointer != NULL)
    {
        printf("Item = ");
        (printItem)(pointer->item);

        printf("     Priority = ");
        (printPriority)(pointer->priority);

        printf("\n");

        pointer = pointer -> nextItem;
    }
}

//Function remove removes the item with the smallest priority. It also stores
//the item and it's priority into x and p, respectively.
void remove(PriorityQueue& q, ItemType& x, PriorityType& p)
{
    if(q.cells != NULL)
    {
        PQCell *pointer = q.cells;
        q.cells = q.cells -> nextItem;
        x = pointer -> item;
        p = pointer -> priority;
        delete [] pointer;
    }

    else
    {
        printf("Q is empty");
        exit(1);
    }
}

---

//File: pqueue.h



typedef const char* ItemType;
typedef double      PriorityType;
struct PQCell;
typedef void (*ItemPrinter)(ItemType);
typedef void (*PriorityPrinter)(PriorityType);



struct PriorityQueue
{
    PQCell* cells;

    PriorityQueue()
    {
        cells = NULL;
    }
};

bool isEmpty(const PriorityQueue& q);

void insert(PriorityQueue& q, ItemType x, PriorityType p);

void printPriorityQueue(const PriorityQueue& q, ItemPrinter printItem, 
        PriorityPrinter printPriority);

void remove(PriorityQueue& q, ItemType& x, PriorityType& p);

The main problem I'm having is like I said, the insert and insertCell functions. I keep receiving the errors:

pqueue.cpp: In function void insert(PriorityQueue*&, ItemType, PriorityType):

pqueue.cpp:70:20: error: invalid initialization of reference of type PQCell*& from expression of type PriorityQueue*
  insertCell(q, x, p);

pqueue.cpp:54:6: error: in passing argument 1 of void insertCell(PQCell*&, ItemType, PriorityType)
 void insertCell(PQCell*& L, ItemType x, PriorityType p)

Again, any help would be great, thanks.

Answer 1

The main problem (the one that's causing the invalid initialization error) is that you're passing a PriorityQueue& into a function that's expecting a PQCell*&:

//Function insert inserts item x with priority p into a priority queue 'q'.
void insert(PriorityQueue& q, ItemType x, PriorityType p)
{
   // Wrong.
   //insertCell(q, x, p);

   // You probably meant to do this:
   insertCell(q.cells, x, p);
}

I also noticed that your isEmpty logic seems to be backwards:

//Function isEmpty returns true if the queue is empty and false if it is not.
bool isEmpty(const PriorityQueue& q)
{
   if(q.cells == NULL)
   {
       return false;
   }

   return true;
}     

You're returning false if q.cells == NULL, when you probably meant to be returning true in that case, and false otherwise.