1. 首页
  2. 问答
  3. 错误将多个项目添加到具有固定大小数组的优先队列

错误将多个项目添加到具有固定大小数组的优先队列

2017-04-19 23 views
0

在我们开始之前，是的这是作业。错误将多个项目添加到具有固定大小数组的优先队列

希望我能在这里得到一些解释。我正在实现一个具有固定大小数组的优先级队列，并且已经编写了所有函数并编译了所有内容，但是我在测试文件中遇到了选项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; 
}

的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

的pqueue2.cpp文件：

// FILE: pqueue2.cpp 
// IMPLEMENTS: PriorityQueue (See pqueue2.h for documentation.) 
// IMPLEMENTED BY: Michael Main ([email protected]) 
// 
// 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); 
     } 
    } 
}

而且我附上了错误照片。

This is the original output when you first start the program

Here is the error I get when I try option M

来源

2017-04-19 Blankets_McGee

+0

这个断言在哪个插入失败？把一些printfs放在那里，或者在调试器中继续。 –

回答

0 
while(parent_priority(i) < priority)

您一直在寻找父母，即使i == 0。将其更改为while (i > 0 && parent_priority(i) < priority)。

来源

2017-04-19 23:58:34 timrau

+0

就是这样！谢谢@timrau –

相关问题

 相关问题