before we get started, yes this is homework.
在我们开始之前,是的,这是功课。
hopefully I can get some clarification here. I am implementing a priority queue with a fixed size array and have all the functions written and everything compiles but I am having a problem with the option M in the test file. All the other functions work just fine but when I try to add_multiple_items I get an expression error in the assert of the swap_with_parent function. here is my program files. The pqtest2.cpp file:
希望我能在这里得到一些澄清。我正在实现一个具有固定大小数组的优先级队列,并且已编写所有函数并编译所有内容,但我在测试文件中遇到选项M的问题。所有其他函数都工作得很好但是当我尝试add_multiple_items时,我在swap_with_parent函数的断言中得到一个表达式错误。这是我的程序文件。 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;
}
The pqueue.h file:
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
The pqueue2.cpp file:
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);
}
}
}
Also I have attached the error pic.
我也附上了错误图片。
1 个解决方案
#1
0
while(parent_priority(i) < priority)
You kept looking for parent even when i == 0. Change it into while (i > 0 && parent_priority(i) < priority).
即使i == 0,你仍然在寻找父母。将其改为while(i> 0 && parent_priority(i)
#1
0
while(parent_priority(i) < priority)
You kept looking for parent even when i == 0. Change it into while (i > 0 && parent_priority(i) < priority).
即使i == 0,你仍然在寻找父母。将其改为while(i> 0 && parent_priority(i)