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);
}
}
}
또한 내가 첨부 오류 그림.
삽입시이 어설 션이 실패합니까? 거기에 printfs를 넣거나 디버거를 따라 가라. –