C++，优先队列的链表

Question

我正在处理一项任务，目标是制作一个模块，该模块将协助表示显示每个 'item' 的优先级队列，并且它是合适的 'priority value'。我并没有要求任何人像我之前的 post 中所说的那样为我做我的 "homework"，我只是寻求帮助以了解我的 insert 和 insertCell 函数给我错误。任何 advice/tips 都会对解决我的问题很有帮助。

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

我遇到的主要问题就像我说的，insert 和 insertCell 函数。我不断收到错误消息：

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)

再一次，任何帮助都会很棒，谢谢。

Answer 1

主要问题（导致 invalid initialization 错误的问题）是您将 PriorityQueue& 传递给期望 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);
}

我也注意到你的isEmpty逻辑似乎是倒退的：

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

如果 q.cells == NULL，您将返回 false，而在这种情况下您可能打算返回 true，否则 false。

C++，优先队列的链表

C++, Linked Lists for Priority Queues

c++

linked-list

priority-queue