试图写heapify算法 - 分段错误

我最终试图使用heapsort按字母顺序排序已读入的单词。我从来没有堆积过，所以我试图跟随我的书。我使用cin将单词存储到动态分配的数组中，因为单词数量未知。从单独的代码我知道它正在被读入，并且数组正在变大。然后我试图堆积这个数组，但是由于我是编程新手，所以我一直处于分段错误的位置，我无法确定如何追溯到我做错了什么。这是我的heapify代码：试图写heapify算法 - 分段错误

void Heap::make(){ 
    //make a heap from wordArray 
    //r = last non-leaf 
    for(int r = size/2; r > 1; r--){ 
     int c = 2 * r; //location of left child 
     while(r <= size){ //size is a data member of Heap 
//if r has 2 children and right is larger, make c the right child 
      if((c < size) && (wordArray[c] < wordArray[c+1])){ 
       c++; 
      } 
//fix if parent failed heap-order condition 
      if(wordArray[r] < wordArray[c]){ 

       swap(wordArray[r], wordArray[c]); 
       r = c; //check that it didn't get messed up at c 
       c = 2 * c; 
      } 
      else{ 
       break; //heap-order condition holds so stop 
      } 
     }  
    } 
}

从玩弄COUTS我能确定的是，程序工作，直到if(wordArray[r] < wordArray[c])部分。 wordArray的元素是stings，并且比较器从外部测试正常工作。这是否与动态数组有关？我很困惑，我在这里做错了什么。

来源

2014-11-21 Tommy K

您是否尝试过调试代码以找到问题的根源？ – 2014-11-21 21:11:53

不知道你的数据类型，数组的最大值等。如果r ==大小然后c == 2 *大小大于大小。 wordarray [c]然后是未定义的。 – LeppyR64 2014-11-21 21:12:25

我的猜测是你读过一个数组的末尾。第一次点击wordArray [c]，c = 2 * r = 2 * size/2，所以您可能正在读wordArray [size]，但由于它是零索引，所以这已经过去了。 – TravisJ 2014-11-21 21:13:28

您正在阅读的是越界。当您检查：

if((c < size)

其中c是最后一个元素，你在这里读出界：

if((c < size) && (wordArray[c] < wordArray[c+1])){ 
              ^

的检查应该是：

if((c+1 < size)

而另一个问题在这里：

while(r <= size)

其中r在代码中使用时，如果它明显超出范围r == size。

对于大小，n的阵列，它们的元素从0 to n-1去，所以访问n个元件是未定义的行为。

来源

2014-11-21 21:13:36 2501

您可以访问一个数组的第n个元素通过它的它的N-1线arr[n-1];//this is the nth element

分割故障发生在你这里的代码

(wordArray[c] < wordArray[c+1]) // try to modify this.

让我们假设size = 6

Whwn for()环将首次运行，c = 2 * 6意味着6，并且您正在访问arr[6] and arr[6+1]两者均无效。数组索引从零开始而不是一个。

来源

2014-11-21 21:12:09 Shravan40

试图写heapify算法 - 分段错误

回答

相关问题