当运行 on Linux 时，二进制堆 Class 出现段错误，插入堆问题

Question

我已经用 C++ 为学校实现了二进制堆 class。我在学校 Linux 服务器上使用程序运行时遇到问题。我的代码在 Mac 上 100% 正确输出。在从 main.cpp 打印出第一行代码后，SegFault 就出现了。我试过使用 GDB，但无法查明问题所在。运行 GDB 给我以下问题：程序收到信号 SIGSEGV，分段错误。 std::string::assign(std::string const&) 中的 0x00007ffff7ae8d68。任何试图纠正此问题的帮助将不胜感激。

编辑：我发现这是导致问题的插入函数：我已将函数更新为：

已更新插入函数：

template <class typ>
void Heap<typ>::insert(typ k) {
    if (size == 0) {
        size = size + 1;
        heap[size] = k;
        return;
    }
    if (size == cap-1) {
        cap = cap * 2;
        typ *tempHeap = new typ [cap];
        for (int i = 1; i <= size; i++)
            tempHeap[i] = heap[i];
        delete [] heap;
        heap = tempHeap;
    }
    size = size + 1;
    heap[size] = k; // insert item at end of heap
    int i = size; // set i to size
    while (i != 1 && heap[parent(i)] > heap[i]) { // move up to parents until heap property is restored all the way to the root
        swapKeys(&heap[parent(i)], &heap[i]); // swap items
        i = parent(i); // set i to parent of i
    }
}

这修复了发生的段错误并正确输出堆。

Answer 1

插入第一个元素时，您将 cap 从 0 更改为 cap * 2，这仍然是 0，导致后续 heap[size] = k 具有未定义的行为.您还应该在此时也将 cap 更新为数组的新大小。

你的下一个错误是：

size = size + 1; // update size
heap[size] = k; // insert item at end of heap

在此之前 size 可能等于 cap - 1，在递增后 size 变为 cap 导致 heap[size] 具有未定义的行为。

这一行的注释与提示另一个错误的代码不匹配？

int i = size; // set i to one less than size

我不确定您的程序的预期行为，但以下代码至少不会再崩溃：

template <class typ>
void Heap<typ>::insert(typ k) {
    if (size == cap) { //resize the array when full
        cap = cap == 0 ? 2 : cap * 2;
        typ* tempHeap = new typ[cap];
        for (int i = 0; i < size; i++)
            tempHeap[i] = heap[i];
        delete[] heap;
        heap = tempHeap;
    }
    heap[size] = k; // insert item at end of heap
    int i = size; // set i to one less than size
    size = size + 1; // update size
    while (i != 1 && heap[parent(i)] > heap[i]) { // move up to parents until heap property is restored all the way to the root
        swapKeys(&heap[parent(i)], &heap[i]); // swap items
        i = parent(i); // set i to parent of i
    }
}

关于一个不相关的说明，避免 #includeing cpp 文件，应该只包含头文件。即使您将 Heap.cpp 重命名为 Heap.h，您也应该删除 using namespace std;，这会导致难以追踪编译器错误，请参阅 Why is "using namespace std;" considered bad practice?

Answer 2

程序的问题与插入和提取值时调整堆大小有关。更新 insert 和 extractMin 函数后程序已修复。

当运行 on Linux 时，二进制堆 Class 出现段错误，插入堆问题

Seg Fault with Binary Heap Class when running on Linux, Insert Heap problems

c++

segmentation-fault

当 运行 on Linux 时，二进制堆 Class 出现段错误，插入堆问题

Seg Fault with Binary Heap Class when running on Linux, Insert Heap problems

c++

segmentation-fault

当运行 on Linux 时，二进制堆 Class 出现段错误，插入堆问题