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

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

0 голосов
/ 21 марта 2019

Я работаю над заданием, и цель состоит в том, чтобы создать модуль, который будет помогать в представлении очереди приоритетов, отображающей каждый «элемент» и соответствующее ему «значение приоритета».Я не прошу никого делать мою «домашнюю работу» для меня, как указано в моем предыдущем посте, я просто прошу помощи, чтобы понять, где я ошибаюсь с моими 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)

Опять же, любая помощь будет отличной, спасибо.

1 Ответ

1 голос
/ 21 марта 2019

Основная проблема (которая вызывает ошибку 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 в противном случае.

...