我在为学校作业编写的C ++程序中遇到了一个非常奇怪的错误（末尾粘贴了代码），但我不知道它为什么这样做。特别是，它有时会随机输出错误的信息，有时会给出正确的输出，每次都在相同的输入上运行。如果有人对为什么有见识，我将不胜感激：
我已经制作了一个C ++程序，该程序实现了一个简单的MaxHeap数据结构，该结构支持使用HeapInsert从一个空堆开始将元素逐个插入堆中，或者从一个元素数组开始并使用在元素的前半部分上执行bubbledown以便将其转换为堆-程序采用一个命令行参数，要么是HeapInsert将使用第一种方法来构建堆，要么是BubbleDown它将使用第二种方法来构建堆。
该程序从cin中获取用户输入：首先将提供使堆变出的元素数量，然后是要放入堆中的元素。完成后，它输出在bubbleup / bubbledown中执行的交换次数，然后输出堆中的元素，以便它们位于存储堆的数组中。
我们已经得到了一个示例输入（100个随机数）和一个示例输出，我的代码应该产生这些示例才能知道我们的实现是正确的。我在命令行上执行以下操作：
g++ HeapTest.cpp
./a.out BubbleDown < 100.txt > out
diff out s100b.txt
100.txt是样本输入，s100b.txt是正确的样本输出。
执行线
./a.out BubbleDown < 100.txt > out
diff out s100b.txt
反复，我得到不一致的结果。看来我得到输出的一半时间完全与示例文件匹配，但有一半时间却不匹配，尤其是当我查看输出文件时，似乎随机大数已插入到堆中而没有原因，使我的输出错误。
对我来说，在完全相同的输入下重复运行代码时，结果将不一致，这对我来说绝对没有意义。这仅在我在命令行上使用“ BubbleDown”选项时发生。下面是我的代码：
#include <cstdlib>
#include <stdint.h>
#include <iostream>
#include <string>
#include <cstring>
#include <cassert>
#include <cmath>
using namespace std;
struct MaxHeap { //MaxHeap data structure
int n; //size of the heap
int numex; //number of exchanges in building the heap
int* A; //Array storing the actual heap
MaxHeap(int a){ //First Constructor: initializes an empty heap of size 0 in an array of size a
n=0; //initialize size to 0
numex=0;//initialize numex to 0
A = new int[a]; //allocate space for array of size A on heap
}
MaxHeap(int * data, int a){ //Second Constructor: consumes array of a elements and creates a heap
//out of thoses elements using bubbledown
n = a;
A = data;
numex = 0;
for(int k = (int)(floor((n-1)/2)); k > -1 ; k-=1){
bubbledown(k);
}
}
~MaxHeap(){} //necessary since MaxHeaps made with first constructor are non-contiguous
void bubbleup(int v){//bubble-up algorithm as described in class
int j;
while( (v != 0) && (A[(int)(floor((v-1)/2))] < A[v]) ){
numex +=1;
j = A[v];
A[v] = A[(int)(floor((v-1)/2))];
A[(int)(floor((v-1)/2))] = j;
v = (int)(floor((v-1)/2));
}
}
void bubbledown(int v){//bubbledown algorithm as described in calss
int j;
int k;
int L;
int temp;
while(true){
j = 2*v+1;
k = 2*v+2;
if((j <= n) && (A[j] > A[v])){L = j;}
else{L = v;}
if((k <= n) && (A[k] > A[L])){L = k;}
if(L == v){break;}
else{numex +=1; temp = A[v]; A[v] = A[L]; A[L] = temp; v=L;}
}
}
void HeapInsert(int i, int k){//heapinsert algorithm as described in class
n=k+1;
A[n-1] = i;
bubbleup(n-1);
}
};
void error(){
cerr << "Usage: " << endl;
exit(-1);
}
int main(int argc, char * argv[]){
int flag;
char hins[] = "HeapInsert";
char bdwn[] = "BubbleDown";
switch(argc){
case 2:
if(strcmp(argv[1], hins) == 0){flag=0; break;}
else if(strcmp(argv[1], bdwn) == 0){flag=1; break;}
else{error();}
default: error();
}
if(flag==0){//If HeapInsert option selected, the below creates a heap via HeapInsert
int nelem;
cin >> nelem; //read in number of elements that are going to be given
struct MaxHeap H = MaxHeap(nelem); //call first constructor
for(int k=0; k < nelem; k+=1){ //insert elements into the heap one by one as they are read in
int i;
cin >> i;
H.HeapInsert(i,k);
}
cout << H.numex << endl; //print number of exchanges
for(int k =0;k < nelem; k+=1){ //print elements of heap 1 by 1
cout << H.A[k] << endl;
}
}
else{ //if BubbleDown option chosen by user
int nelem;
cin >> nelem; //read in number of elements
int data[nelem]; //initialize array to store that number of elements
for(int k=0; k < nelem; k+=1){ //build array of elements in order given
int i;
cin >> i;
data[k] = i;
}
struct MaxHeap H = MaxHeap(data, nelem); //use second constructor to create a heap out of the array
cout << H.numex << endl; //print number of exchanges
for(int k =0;k < nelem; k+=1){ //print out elements 1 by 1
cout << H.A[k] << endl;
}
}
}
如果有人对我的代码在不依赖任何随机性或内存分配（给出BubbleDown选项时不使用内存分配）的情况下如何产生不一致的结果有任何想法，将不胜感激！
最佳答案
我用调试符号编译了程序...gcc -g -O0 -o stuff stuff.cpp
然后在Valgrind中运行它...echo '4 2 3 4 5 6' | valgrind ./stuff BubbleDown
它说的是：
==28605== Conditional jump or move depends on uninitialised value(s)
==28605== at 0x401186: MaxHeap::bubbledown(int) (stuff.cpp:52)
==28605== by 0x400FCD: MaxHeap::MaxHeap(int*, int) (stuff.cpp:26)
==28605== by 0x400E08: main (stuff.cpp:125)
这似乎对应于此：
if((j <= n) && (A[j] > A[v])){L = j;}
问题似乎在于您正在读取数组的末尾。如果
j == n，则它是数组末尾的一个元素。与k == n相同。如果将bubbledown更改为此，则问题将消失：void bubbledown(int v){//bubbledown algorithm as described in calss
while(true){
const int j = 2*v+1;
const int k = 2*v+2;
int L;
// notice < instead of <=
if((j < n) && (A[j] > A[v])){
L = j;
}
else{
L = v;
}
// notice < instead of <=
if((k < n) && (A[k] > A[L])){
L = k;
}
if(L == v){
break;
}
else{
numex +=1;
const int temp = A[v];
A[v] = A[L];
A[L] = temp;
v = L;
}
}
}
注意：我使用了一些Linux命令来执行此操作（最重要的是Valgrind）。无论您使用的是哪种编译器工具链/ IDE，都应该有自己的调试器，大概可以为您提供类似的输出。有一个Stack Overflow question about Valgrind substitutes in Windows。我建议找到一个喜欢的工具-这将使C ++调试容易得多。