Erreur lors de l'ajout de plusieurs éléments à une file d'attente prioritaire avec un tableau de taille fixe

Question

avant de commencer, oui c'est le devoir.

J'espère pouvoir obtenir quelques éclaircissements ici. J'implémente une file d'attente prioritaire avec un tableau de taille fixe et ai toutes les fonctions écrites et tout compile mais j'ai un problème avec l'option M dans le fichier de test. Toutes les autres fonctions fonctionnent très bien mais quand j'essaye de add_multiple_items j'obtiens une erreur d'expression dans l'affirmation de la fonction swap_with_parent. Voici mes fichiers de programme. Le fichier pqtest2.cpp:

// FILE: pqtest2.cpp 
// An interactive test program for the Priority Queue class 
#include <cctype>  // Provides toupper 
#include <iostream> // Provides cout and cin 
#include <cstdlib> // Provides EXIT_SUCCESS and size_t 
#include "pqueue2.h" // Implemented using a heap 
using namespace std; 

// PROTOTYPES for functions used by this test program: 
void print_menu(); 
char get_user_command(); 
int get_number(const char message[ ]); 
void add_multiple_entries(PriorityQueue &q); 

int main() 
{ 
    PriorityQueue test; 
    char choice; 
    cout << "CSC-161 Lesson Ten Test Program" << endl << endl; 
    do 
{ 
    print_menu(); 
    choice = toupper(get_user_command()); 
    switch (choice) 
    { 
     case 'E': 
      if (test.is_empty()) 
       cout << "The Priority Queue is empty." << endl; 
      else 
       cout << "The Priority Queue is not empty." << endl; 
      break; 
     case 'G': 
      if (!test.is_empty()) 
       cout << "Front item is: " << test.get_front() << endl; 
      else 
       cout << "There is no current item." << endl; 
      break; 
     case 'I': 
      test.insert(get_number("Please enter the next item: "), 
       (unsigned int) get_number("The item's priority: ")); 
      break; 
     case 'M': 
      add_multiple_entries(test); 
      break; 
     case 'P': 
      test.print_tree("Contents of heap:"); 
      break; 
     case 'S': 
      cout << "The size is " << test.size() << endl; 
      break; 
     case 'X': 
      if (test.is_empty()) 
       cout << "The Priority Queue is empty." << endl; 
      else 
       while(!test.is_empty()) 
        cout << "Value: " << test.get_front() << endl; 
      break; 
     case 'Q': 
      break; 
     default: 
      cout << choice << " is an invalid choice." << endl; 
    } 
} 
while ((choice != 'Q')); 
return EXIT_SUCCESS; 
} 

void print_menu() 
{ 
    cout << endl; 
cout << "The following choices are available: " << endl; 
cout << " E Print the result from the is_empty() function" << endl; 
cout << " G Print the result from the get_front() function" << endl; 
cout << " I Insert a new item with the insert(...) function" << endl; 
cout << " M Add multiple items with varying priorities " << endl; 
cout << " P Print the internal heap using the print_tree(...) function" << endl; 
cout << " S Print the result from the size() function" << endl; 
cout << " X Extract and print values in priority order" << endl; 
cout << " Q Quit this test program" << endl; 
} 

char get_user_command() 
{ 
char command; 
cout << "\nEnter choice: "; 
cin >> command; 
return command; 
} 

int get_number(const char message[ ]) 
{ 
int result; 
cout << message; 
cin >> result; 
return result; 
} 
void add_multiple_entries(PriorityQueue &thisQueue) 
{ 
thisQueue.insert(100, 10); 
thisQueue.insert(200, 10); 
thisQueue.insert(300, 5); 
thisQueue.insert(400, 5); 
thisQueue.insert(500, 20); 
thisQueue.insert(600, 20); 
thisQueue.insert(700, 20); 
thisQueue.insert(800, 10); 
thisQueue.insert(900, 10); 
return; 
} 

Le fichier pqueue.h:

// FILE: pqueue2.h 
// CLASS PROVIDED: PriorityQueue (a priority queue of items) 
// 
// TYPEDEF and MEMBER CONSTANT for the PriorityQueue class: 
// static const size_t CAPACITY = ______ 
//  PriorityQueue::CAPACITY is the maximum number of entries that 
//  may be be in the priority queue at any one time. 
// 
// typedef _____ Item 
//  The type Item is the data type of the items in the Priority Queue. 
//  It may be any of the C++ built-in types (int, char, etc.), or a class 
//  with a default constructor, a copy constructor, and assignment operator. 
// 
// CONSTRUCTOR for the PriorityQueue class: 
// PriorityQueue() 
//  Postcondition: The PriorityQueue has been initialized with no Items. 
// 
// MODIFICATION MEMBER FUNCTIONS for the PriorityQueue class: 
// void insert(const Item& entry, unsigned int priority) 
//  Postcondition: A new copy of entry has been inserted with the specified 
//  priority. 
// 
// Item get_front() 
//  Precondition: size() > 0. 
//  Postcondition: The highest priority item has been returned and has been 
//  removed from the PriorityQueue. (If several items have equal priority, 
//  then there is no guarantee about which one will come out first! 
//  This differs from our first priority queue.) 
// 
// CONSTANT MEMBER FUNCTIONS for the PriorityQueue class: 
// size_t size() const 
//  Postcondition: Return value is the total number of items in the 
//  PriorityQueue. 
// 
// bool is_empty() const 
//  Postcondition: Return value is true if the PriorityQueue is empty. 
// 
// VALUE SEMANTICS for the PriorityQueue class: 
// Assignments and the copy constructor may be used with 
// PriorityQueue objects 

#ifndef PQUEUE_H 
#define PQUEUE_H 
#include <cstdlib> // Provides size_t 

    class PriorityQueue 
    { 
    public: 
     // TYPEDEF and MEMBER CONSTANT 
     typedef double Item; 
     static const size_t CAPACITY = 5000; 
     // CONSTRUCTOR 
     PriorityQueue(); 
     // MODIFICATION MEMBER FUNCTIONS 
     void insert(const Item& entry, unsigned int priority); 
     Item get_front(); 
     // CONSTANT MEMBER FUNCTIONS 
     size_t size() const { return many_items; } 
     bool is_empty() const { return (many_items == 0); } 
     // MEMBER FUNCTION FOR DEBUGGING 
     void print_tree(const char message[ ] = "", size_t i = 0) const; 
    private: 
     // STRUCT DEFINITION to store information about one item in the pqueue 
     struct OneItemInfo 
     { 
      Item data; 
      unsigned int priority; 
     }; 
     // PRIVATE MEMBER VARIABLES 
     OneItemInfo heap[CAPACITY]; 
     size_t many_items; 
     // PRIVATE HELPER FUNCTIONS -- see pqueue2.cxx for documentation 
     bool is_leaf(size_t i) const; 
     size_t parent_index(size_t i) const; 
     unsigned int parent_priority(size_t i) const; 
     size_t big_child_index(size_t i) const; 
     unsigned int big_child_priority(size_t i) const; 
     void swap_with_parent(size_t i); 
    }; 

#endif 

Le fichier pqueue2.cpp:

// FILE: pqueue2.cpp 
// IMPLEMENTS: PriorityQueue (See pqueue2.h for documentation.) 
// IMPLEMENTED BY: Michael Main (main@colorado.edu) 
// 
// Alex Chapman ID: S02084651 
// 
// 
// INVARIANT for the PriorityQueue Class: 
// 1. The member variable many_items is the number of items in the 
//  PriorityQueue. 
// 2. The items themselves are stored in the member variable heap, 
//  which is a partially filled array organized to follow the usual 
//  heap storage rules from Chapter 11 of the class notes. 
// NOTE: Private helper functions are implemented at the bottom of this 
// file along with their precondition/postcondition contracts. 

#include <cassert> // Provides assert function 
#include <iostream> // Provides cin, cout 
#include <iomanip> // Provides setw 
#include <cmath>  // Provides log2 
#include "pqueue2.h" 
using namespace std; 

PriorityQueue::PriorityQueue() 
{ 
    heap[CAPACITY]; 
    many_items = 0; 
} 

void PriorityQueue::insert(const Item& entry, unsigned int priority) 
{ 
    if (many_items == 0) 
    { 
     heap[many_items].data = entry; 
     heap[many_items].priority = priority; 
     many_items++; 
    } 
    else 
    { 
     heap[many_items].data = entry; 
     heap[many_items].priority = priority; 
     unsigned int i = many_items; 
     many_items++; 

     while(parent_priority(i) < priority) 
     { 
      swap_with_parent(i); 
      i = parent_index(i); 
     } 
    } 
} 

PriorityQueue::Item PriorityQueue::get_front() 
{ 
    assert(many_items > 0); 
    if (many_items == 1) 
    { 
     Item front_value = heap[0].data; 
     many_items--; 
     return front_value; 
    } 
    else 
    { 
     Item front_value = heap[0].data; 
     heap[0] = heap[many_items - 1]; 
     unsigned int priority = heap[many_items - 1].priority; 
     unsigned int k = 0; 

     while((k < many_items) && !is_leaf(k) && big_child_priority(k) > priority) 
     { 
      unsigned int j = big_child_index(k); 
      swap_with_parent(big_child_index(k)); 
      k = j; 
     } 
     many_items--; 
     return front_value; 
    } 
} 

bool PriorityQueue::is_leaf(size_t i) const 
// Precondition: (i < many_items) 
// Postcondition: If heap[i] has no children in the heap, then the function 
// returns true. Otherwise the function returns false. 
{ 
    if (2 * i + 1 >= many_items) 
    { 
     return 1; 
    } 
    else 
    { 
     return 0; 
    } 
} 

size_t PriorityQueue::parent_index(size_t i) const 
// Precondition: (i > 0) && (i < many_items) 
// Postcondition: The return value is the index of the parent of heap[i]. 
{ 
    return (i - 1)/2; 
} 

unsigned int PriorityQueue::parent_priority(size_t i) const 
// Precondition: (i > 0) && (i < many_items) 
// Postcondition: The return value is the priority of the parent of heap[i]. 
{ 
    return heap[(i - 1)/2].priority; 
} 

size_t PriorityQueue::big_child_index(size_t i) const 
// Precondition: !is_leaf(i) 
// Postcondition: The return value is the index of one of heap[i]'s children. 
// This is the child with the larger priority. 
{ 
    assert(!is_leaf(i)); 

    if ((2 * i) + 2 < many_items) 
    { 
     if (heap[(2 * i) + 1].priority > heap[(2 * i) + 2].priority) 
     { 
      return (2 * i) + 1; 
     } 
     else 
     { 
      return (2 * i) + 2; 
     } 
    } 
    else 
    { 
     return (2 * i) + 1; 
    } 
} 

unsigned int PriorityQueue::big_child_priority(size_t i) const 
// Precondition: !is_leaf(i) 
// Postcondition: The return value heap[big_child_index(i)].priority 
{ 
    return heap[big_child_index(i)].priority; 
} 

void PriorityQueue::swap_with_parent(size_t i) 
// Precondition: (i > 0) && (i < many_items) 
// Postcondition: heap[i] has been swapped with heap[parent_index(i)] 
{ 
    assert (i>0 && i< many_items); 
    OneItemInfo temp_parent = heap[parent_index(i)]; 
    OneItemInfo temp_child = heap[i]; 
    heap[i] = temp_parent; 
    heap[parent_index(i)] = temp_child; 
} 

void PriorityQueue::print_tree(const char message[ ], size_t i) const 
// Postcondition: If the message is non-empty, then that has been written 
// to cout. After the message, the portion of the heap with root at node 
// node i has been written to the screen. Each node's data is indented 
// 4*d, where d is the depth of the node. 
// NOTE: The default argument for message is the empty string, and the 
// default argument for i is zero. For example, to print the entire 
// tree of a PriorityQueue p, with a message of "The tree:", you can call: 
//  p.print_tree("The tree:"); 
// This call uses i=0, which prints the whole tree. 
{ 
    const char NO_MESSAGE[] = ""; 
    size_t depth; 

    if (message[0] != '\0') 
    { 
     cout << message << endl; 
    } 
    if (i > many_items) 
    { 
     cout << "No Nodes" << endl; 
    } 
    else 
    { 
     depth = int(log(double(i + 1))/log(2.0)); 
     cout << setw(depth * 4) << ""; 
     cout << heap[i].data; 
     cout << " (priority " << heap[i].priority << ")" << endl; 

     if (2 * i + 1 < many_items) 
     { 
      print_tree(NO_MESSAGE, 2 * i + 1); 
     } 
     if (2 * i + 2 < many_items) 
     { 
      print_tree(NO_MESSAGE, 2 * i + 2); 
     } 
    } 
} 

Aussi je joins la photo d'erreur.

Answer 1

while(parent_priority(i) < priority) 

Vous avez gardé la recherche de parents, même quand i == 0. Changez-le en while (i > 0 && parent_priority(i) < priority).