0

下面给出的是我为使用我自己的堆实现而编写的驱动程序。

#include<iostream>
#include"Heap.h"

int main(){
        Heap h(30);
        h.insert(1);
        h.insert(3);
        h.insert(5);
        h.insert(6);
        h.insert(5);
        h.insert(8);

        h.display();
        std::cout<<h.extractMin();    // Statement 1
        h.display();
        }

这给出了所需的结果：

========= Heap Contents =========
1   3   5   6   5   8   
1
========= Heap Contents =========
3   6   5   8   5

但是，如果我将其更改statement 1为：

   std::cout<<"Min: "<<h.extractMin();

代码开始给出分段错误。同样，如果我statement 1将

int z = h.extractMin();

该代码仍然给出分段错误。这诱使我看看我是否在extractMin(). 以下是我的定义extractMin()：

int Heap::extractMin()
{
    int min = this -> arr[0];
    this -> arr[0] = this -> arr[heapSize];

    heapSize -= 1;
    heapify(0);

    return min;
}

为了完整起见，下面是我的定义heapify()：

void Heap::heapify(int index){
        if(index > this -> heapSize)
                return;

        int smallest = index;
        int l = leftChild(index);
        int r = rightChild(index);

        if(l <= heapSize && arr[l] < arr[index])
                smallest = l;
        if(r <= heapSize && arr[r] < smallest)
                smallest = r;

        if(smallest != index){
                arr[smallest] = arr[smallest] ^ arr[index];
                arr[index] = arr[smallest] ^ arr[index];
                arr[smallest] = arr[smallest] ^ arr[index];
                heapify(smallest);
                }
        }

知道发生了什么吗？我无法理解分段错误背后的原因。我有什么明显的遗漏吗？

谢谢！

加法1：

这也发生了h.getHeapSize()，h.getArrSize()这让我认为问题出在其他东西上，而不是功能上。

补充2：

整个代码如下：

#include<iostream>
#include<cmath>

class Heap{
    private:
        int* arr;
        int size;
        int heapSize;
    public:
        Heap(int = 8); 
        Heap(int*, int size);
        int* initArr(int size);
        void setSize(int);
        int getSize();
        int getHeapSize();
        void setHeapSize(int);
        int leftChild(int);
        int rightChild(int);
        int parent(int);
        void heapify(int);
        void buildHeap();
        void insert(int);
        int extractMin();
        void display() const;
    };

Heap::Heap(int size){
    initArr(size);
    this -> size = size;
    this -> heapSize = -1;
    }

Heap::Heap(int* arr, int size){
    this -> arr = arr;
    this -> size = size;
    this -> heapSize = size - 1;
    buildHeap();
    }

int* Heap::initArr(int size){
    int* arr = new int[size];
    return arr;
    }

void Heap::setSize(int size){
    if(size > this -> heapSize)
        this -> size = size;
    }

int Heap::getSize(){
    return this -> size;
    }

void Heap::setHeapSize(int heapSize){
    this -> heapSize = heapSize;
    }

int Heap::getHeapSize(){
    return this -> heapSize;
    }

int Heap::leftChild(int index){
    return 2*index + 1;
    }

int Heap::rightChild(int index){
    return 2*index + 2;
    }

int Heap::parent(int index){
    return ceil(index >> 1) - 1;
    }

void Heap::heapify(int index){
    if(index > this -> heapSize)
        return;

    int smallest = index;
    int l = leftChild(index);
    int r = rightChild(index);

    if(l <= heapSize && arr[l] < arr[index])
        smallest = l;
    if(r <= heapSize && arr[r] < smallest)
        smallest = r;

    if(smallest != index){
        arr[smallest] = arr[smallest] ^ arr[index];
        arr[index] = arr[smallest] ^ arr[index];
        arr[smallest] = arr[smallest] ^ arr[index];
        heapify(smallest);
        }
    }

void Heap::buildHeap(){
    for(int i = heapSize/2 - 1; i >= 0; i-- )
        heapify(i);
    }

void Heap::insert(int val){
    heapSize += 1;
    int loc = heapSize;

    arr[heapSize] = val;
    int p;

    while((p = arr[parent(heapSize)]) > val){   
        arr[loc] = arr[p] ^ arr[loc];
        arr[p] = arr[p] ^ arr[loc];
        arr[loc] = arr[p] ^ arr[loc];
        }
    }

int Heap::extractMin(){
    //int temp = arr[0];
    //arr[0] = arr[heapSize];
    //arr[heapSize] = temp;

    int min = arr[0];
    arr[0] = arr[heapSize];

    heapSize -= 1;
    heapify(0);

    //return arr[heapSize + 1];
    return min;
    }

void Heap::display() const{
    std::cout<<"\n========= Heap Contents =========\n";
    for(int i = 0; i <= heapSize; i++)
        std::cout<<arr[i]<<'\t';
    std::cout<<'\n';
    }
4

2 回答 2

0

有很多问题。

首先，接受int参数的构造函数不会初始化arr成员，它会分配内存并将其分配给本地指针变量，它会返回但您只是忽略返回值。
您必须将其存储在成员变量中（将局部变量命名为与成员相同的名称通常是一个非常糟糕的主意。）

一旦你解决了这个问题：在第一次插入期间，h.insert(1);,parent(heapSize)是-1。
由于您使用它在数组中进行索引，因此程序具有未定义的行为并且所有赌注都已关闭；该程序不是有效的 C++ 程序。

可能还有其他问题，但这些是最明显的。

于 2013-08-25T21:56:13.460 回答
0

从您在此处发布的内容来看，堆大小处理不当是罪魁祸首。所有涉及的测试heapSize似乎都没有考虑基于零的访问。你真的应该改变它，因为它会导致很多不合逻辑的后果： heapSize 是否被初始化为-1?

至于调试：

  • 悠闲地添加更多的空值和边界检查（不仅heapSize对 0，对 0 也一样）
  • 尝试减少测试集（它是否因一项而崩溃？）并尝试手动或使用 gdb 跟踪控制流

编辑

错误在parent(). 尝试调试提示。

于 2013-08-25T21:24:22.100 回答