C++, связанные списки для приоритетных очередей

Я работаю над заданием, и цель состоит в том, чтобы создать модуль, который поможет представить очередь приоритетов, отображающую каждый «элемент» и соответствующее «значение приоритета». Я не прошу никого делать за меня «домашнее задание», как указано в моем предыдущем посте, я просто прошу помочь понять, где я ошибаюсь с моими функциями insert и insertCell, которые дают мне ошибки. Любые советы/подсказки будут очень полезны в решении моей проблемы.

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

Опять же, любая помощь будет здорово, спасибо.


person Luke    schedule 20.03.2019    source источник
comment
PriorityQueue& не является PQCell*&. Это ясно объясняет все сообщения об ошибках. Насколько я вижу, этот вызов должен передавать q.cells в качестве первого аргумента.   -  person WhozCraig    schedule 21.03.2019
comment
Вместо того, чтобы передавать ссылку на указатель на insertCell(), почему бы вам просто не вернуть указатель на новый PQCell? Я нахожу сочетание ссылок и указателей сбивающим с толку, есть ли причина, по которой вы не используете указатель на указатель? Разве мы больше не учим указатели на указатели?   -  person Kingsley    schedule 21.03.2019
comment
Я изменил код на то, что вы предлагаете, и он исправил ошибки @WhozCraig, спасибо.   -  person Luke    schedule 21.03.2019
comment
@Kingsley, мы давали конкретные инструкции по использованию этих двух заголовков функций в том виде, в каком они есть, что, к сожалению, означает, что если я изменю его, чтобы упростить мне задачу, это снизит полученную оценку.   -  person Luke    schedule 21.03.2019
comment
Достаточно справедливо, но Param *& никогда бы не прошел код-ревью ни в одной компании, в которой я когда-либо работал.   -  person Kingsley    schedule 21.03.2019
comment
Вот почему я думаю, что больше не буду брать этого профессора. @Кингсли   -  person Luke    schedule 21.03.2019
comment
@Kingsley Вы говорите, что Param** пройдет проверку кода? Мне кажется еще хуже.   -  person john    schedule 21.03.2019
comment
@Джон, конечно, если это было подходящим использованием. Каждый argv есть ** !   -  person Kingsley    schedule 21.03.2019
comment
@Kingsley Мне любопытно; что конкретно заставит каждую компанию, в которой вы когда-либо работали, отклонить регистрацию с этой конструкцией, и, в частности, каковы связанные с этим причины, кроме чисто мнения рецензента о стиле. Не поймите неправильно; Я предпочитаю передавать параметры указателя входа/выхода по адресу (указатель на указатель; пережиток моего многолетнего опыта в C до возвращения домой на C++ 25 лет назад, так как он оставляет за собой возможность возвращать состояние успеха/ошибки в качестве результата), но Я хотел бы иметь общепринятое отраслевое руководство, на которое можно было бы опереться, когда советуют джуниорам просто не делать этого?   -  person WhozCraig    schedule 21.03.2019
comment
@WhozCraig - я не знаю ни одного общепринятого отраслевого руководства. Когда я был младшим, в обзоре кода мне сказали: ссылки C++ следует использовать только для перегрузки операторов (т. е. для возврата ссылки на объект для поддержки присваивания). У меня лично нет проблем с использованием ссылок для параметра var (хотя я тоже предпочитаю указатели), но не смешивание ссылок и указателей. Может быть, за эти годы я превратился в скрягу в программировании. Кажется, в наши дни, если вы используете ** в C/C++, вы, очевидно, тоже ненавидите котят. По крайней мере, так кажется на SO.   -  person Kingsley    schedule 21.03.2019


Ответы (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;
}     

Вы возвращаете false, если q.cells == NULL, когда вы, вероятно, хотели вернуть true в этом случае, и false в противном случае.

person Mike Holt    schedule 20.03.2019
comment
Спасибо, что указали на ошибку в isEmpty. И да, q.cells был правильным способом сделать это. - person Luke; 21.03.2019