您好，我正在学习斯坦福大学的CS106b编程抽象，这是一门用c ++讲授的编程课程，并且在PQueue分配（优先级队列）（基于堆的实现）中，当将东西从一个队列中取出时，我遇到了这种分段错误核心转储行为。已查询了大量随机性质的条目，每次运行所需的确切数量各不相同，并且可以是10000至70000个条目之间的任何值，如果我将排序后的输入排队（例如lupe计数器），则不会出现此问题，它甚至可以是10000000个条目。我已经花了几个小时试图查找错误，但是我找不到它，我的猜测是我必须对内存管理做一些事情，但是我使用的PQueue :: doubleCapacity（）方法基于工作向量类中的一个，我认为入队和出队方法都很好，因为入队仍然可以为很大的条目（小于10000）工作。这不是一个可以轻松搜索的问题，因此请帮助下面的代码。该代码使用了CS106库中的一些类，可以在http://sourceforge.net/projects/progabstrlib/中找到这些类，但是我希望它足够简单，因此您无需进行编译就可以告诉我我做错了什么。
我正在使用g ++在Ubuntu 12.04上工作，如果那很重要
/*
* File: pqueue.h
*/
#ifndef _pqueue_h
#define _pqueue_h
#include "genlib.h"
#include "vector.h"
#include "disallowcopy.h"
class PQueue
{
public:
PQueue();
~PQueue();
bool isEmpty();
int size();
void enqueue(int newElem);
int dequeueMax();
/*
* needed for assigment puprposses there are three more PQueue implementation
* so it is needed to compare memory speed trade of.
*/
int bytesUsed();
string implementationName();
void printDebuggingInfo();
bool printDebugToFile(string fileName);
private:
template <typename Type>
void PrintArry(Type arr[], int size);
DISALLOW_COPYING(PQueue)
static const int START_SIZE = 2;
int* entries;
int _capacity_, _size_;
void doubleCapacity();
void halfCapacity();
void swap(int& one, int &two);
};
#endif
// ---------------------------------------------------------------------------------------------
/*
* File: pqheap.cpp
* -- ----------------
*/
//#include "pqueue.h" // commented out so i can compile this whole file at once
#include "genlib.h"
#include <iostream>
#include <sstream>
#include <fstream>
PQueue::PQueue()
{
entries = new int[START_SIZE];
_capacity_ = START_SIZE;
_size_ = 0;
/*
* i am not using first cell so i want to know what should be in it this is because of
* the fact that in the way in which i have implemented heap based PQueue the acuall values
* are stored form number 1 and not 0; so child of value x can be reach by multiplying
* the index of it by two adding 1 for the second child;
*/
entries[_size_] = -888;
}
PQueue::~PQueue()
{
if (entries != NULL) delete[] entries;
}
bool PQueue::isEmpty()
{
return (_size_ == 0);
}
int PQueue::size()
{
return _size_;
}
/*
* the heap enqueuing works by adding new value to the end of the array and bubrling it up to the
* wright position by compare with its parent and swap if necesery.
*/
void PQueue::enqueue(int newValue)
{
int curValPos = ++_size_;
if(_size_ == _capacity_)
doubleCapacity();
entries[curValPos] = newValue;
// bubbling value up to its proper position;
while(curValPos > 1)
{
int parentPos = curValPos/2;
if(newValue < entries[parentPos])
break;
else
{
swap(entries[curValPos], entries[parentPos]);
curValPos = parentPos;
}
}
}
/*
* dequeuing is done by taking the highest value ( value from index 1 ) and then to repare the
* queue last value is copied to the first position and then buubled down till it reaches
* its proper position, it is done by comparison with children of the current position and
* swaping while nesessery.
*/
int PQueue::dequeueMax()
{
if (isEmpty())
Error("Tried to dequeue max from an empty pqueue!");
if(_capacity_ > (_size_*2)+10)
halfCapacity();
int curPos = 1;
int maxValue = entries[curPos];
//cout << maxValue << "|" ;
entries[curPos] = entries[_size_];
_size_ -= 1;
int biggerChild = 0;
while(biggerChild < _size_)
{
biggerChild = curPos*2;
if(entries[biggerChild] < entries[biggerChild+1])
biggerChild += 1; // the second child is bigger than the first
// if the bigger child is smaller than newVal or if the current
// position does not have children
if(entries[curPos] >= entries[biggerChild] || biggerChild > _size_)
break;
else
{
swap(entries[curPos], entries[biggerChild]);
curPos = biggerChild;
}
}
return maxValue;
}
int PQueue::bytesUsed()
{
cout << endl << "______________________ " << endl;
cout << "SIZE OF THIS = " << sizeof(*this) << endl;
cout << "SIZE OF ENTRIES = " << sizeof(*entries) << endl;
cout << "______________________ " << endl;
return sizeof(*this) + sizeof(int)*_size_;
}
string PQueue::implementationName()
{
return "( heap )";
}
void PQueue::printDebuggingInfo()
{
cout << "------------------ START DEBUG INFO ------------------" << endl;
cout << "Pqueue contains " << _size_ << " entries" << endl;
for (int i = 1; i <= _size_; i++)
cout << entries[i] << " ";
cout << endl << endl;
/*
* the print out is helpful only for the top few nodes and children.
*/
int numInCurRow = 1 , numInPrewRow = 1;
for (int i = 1; i <= _size_; i++)
{
cout << entries[i] << "|";
numInCurRow--;
if(numInCurRow == 0)
{
cout << endl;
numInPrewRow *= 2;
numInCurRow = numInPrewRow;
}
}
cout << endl;
cout << "------------------ END DEBUG INFO ------------------" << endl;
}
bool PQueue::printDebugToFile(string fileName)
{
ofstream outFile;
string str = fileName;
outFile.open(str.c_str());
if(outFile.fail())
{
cout << "WriteVectorToFile could not open file " + fileName << endl;
return false;
}
outFile << "------------------ START DEBUG INFO ------------------" << endl;
outFile << "Pqueue contains " << _size_ << " entries" << endl;
for (int i = 1; i <= _size_; i++)
outFile << entries[i] << " ";
outFile << endl << endl;
int numInCurRow = 1 , numInPrewRow = 1;
for (int i = 1; i <= _size_; i++)
{
outFile << entries[i] << "|";
numInCurRow--;
if(numInCurRow == 0)
{
outFile << endl;
numInPrewRow *= 2;
numInCurRow = numInPrewRow;
}
}
outFile << endl;
outFile << "------------------ END DEBUG INFO ------------------" << endl;
outFile.close();
return true;
}
void PQueue::doubleCapacity()
{
_capacity_ *= 2;
int* biggerArry = new int[_capacity_];
cout << "resizing capacity from " << _capacity_/2 << " new capacity = " << _capacity_ << endl;
for(int i = 0; i <= _size_; i++)
biggerArry[i] = entries[i];
delete[] entries;
entries = biggerArry;
}
/*
*
*/
void PQueue::halfCapacity()
{
_capacity_ /= 2;
int* halfArry = new int[_capacity_];
cout << endl <<" downsizing capacity from " << _capacity_*2 << " new capacity = " << _capacity_ << endl;
for(int i = 0; i < _capacity_; i++)
halfArry[i] = entries[i];
delete[] entries;
entries = halfArry;
}
void PQueue::swap(int &one, int &two)
{
int tmp = one;
one = two;
two = tmp;
}
//---------------------------------------------------------------------------------------------
/*
* main.cpp the driver
*/
/* File: main.cpp
* --------------
* Simple main module for PQueue assignment.
*/
//#include "pqheap.cpp" // commented out so i can compile this whole file at once
#include <iostream>
#include "genlib.h"
#include "simpio.h"
#include "random.h"
#include <ctime>
#include <fstream>
#include "vector.h"
using namespace std;
/*
* auxiliary functions
*/
string iToS(int x);
int sToI(string str);
bool ReadVectorFromFile(Vector<int> &v, string fileName);
template <typename Type>
bool WriteVectorToFile(Vector<Type> v, string fileName);
int main()
{
Randomize();
PQueue pq;
while(true)
{
cout << "how big queue do we want to work with ? "+pq.implementationName() << endl;
int y, x = GetInteger();
Vector <int> v;
/*
* "1000000.vec" file contains 1000000 unsorted integers with no repetitions,
* use of it produces the same segmentation fault core dumped it is cometed out for now
*/
//ReadVectorFromFile(v,"1000000.vec");
double start = double(clock())/1000000;
for(int i = 0; i < x; i++)
{
pq.enqueue(RandomInteger(0,i));
}
double stop = double(clock())/1000000;
cout << "time needed for enqueue of size "<< x << " = " << stop-start << endl;
//v.clear();
pq.printDebugToFile("debug."+ iToS(x)+ ".debug");
/*
* it seems that even dequeung a few values from the top produces the error
*/
cout << "how much to dequeue ?" << endl;
y = GetInteger();
start = double(clock())/1000000;
for(int i = 0; i < y; i++)
{
//pq.printDebuggingInfo();
v.add(pq.dequeueMax());
}
stop = double(clock())/1000000;
cout << "time needed for dequeue "+iToS(y)+" elements from PQ of size "<< x << " = " << stop-start << endl;
WriteVectorToFile(v, "QUEUE_" + iToS(x) + ".test");
}
return (0);
}
//---------------------------------------------------------------------------------
string iToS(int x)
{
ostringstream convert;
convert << x;
return convert.str();
}
int sToI(string str)
{
istringstream converter(str);
int n;
converter >> n;
return n;
}
bool ReadVectorFromFile(Vector<int> &v, string fileName)
{
ifstream inFile;
inFile.open(fileName.c_str());
if(inFile.fail())
{
cout << " ReadVectorFromFile could not read from the file " + fileName << endl;
return false;
}
string line;
while(true)
{
getline(inFile, line);
if(inFile.fail())
break;
v.add(sToI(line));
}
inFile.close();
return true;
}
template <typename Longboard>
bool WriteVectorToFile(Vector<Longboard> v, string fileName)
{
ofstream outFile;
string str = fileName;
outFile.open(str.c_str());
if(outFile.fail())
{
cout << "WriteVectorToFile could not open file " + fileName << endl;
return false;
}
for(int i = 0; i < v.size(); i++)
{
outFile << v[i];
outFile << endl;
}
outFile.close();
return true;
}
最佳答案
乍一看，您对<= _size_的使用似乎很可疑。看来_size_代表队列中的元素数[0，_capacity]。因此，最后一个元素的索引应为_size_ - 1
不过请记住，在为isEmpty()编制索引之前，必须确保已选中[_size_-1]，以防万一_size_为0。
关于c++ - 分段故障核心仅在非常大的随机输入导致的出队前基于pqueue堆转储，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/16818745/