c - 通用堆排序 : not sorting + segmentation fault

Question

我需要在 C 中创建一个“通用”堆排序。

我有一个包含比较功能的主文件。本质上，数组的基地址、元素的数量、每个元素的大小以及比较函数都被传递到堆排序函数中。我遇到了两个问题，一个是程序没有对它进行排序，所以我想知道是否有人可以看到代码有什么问题。二我在 1710 个元素后遇到段错误。

#include <stdio.h>  
#include <string.h>
#include "srt.h"


void srtheap(void *, size_t, size_t, int (*)(const void *, const void *));
void heapify(void *, size_t, size_t, size_t, int (*)(const void *, const void *)); 

void srtheap(void *base, size_t nelem, size_t size, int (*compar)(const void *, const void *)) {
  char *p1, *p2;
  char *qb=base;
  void *last = qb + (size*(nelem-1));
  for (size_t curpos = nelem-1; curpos>0; curpos=-2){
    p1 = qb + ((curpos-1)/2)*size;
    if(compar(last, (last-size)) >= 0){ 
      if(compar(last, p1) > 0){
        swap(last, p1, size);
        heapify(qb, nelem, curpos, size, compar); 
      }
    }
    else { //LEFT>RIGHT
      if(compar(last-size, p1) > 0){
         swap(last-size, p1, size);
         heapify(qb, nelem, curpos-1, size, compar);
      }
           //otherwise, parent is greater than LEFT & RIGHT,
           //or parent has swapped with child, iteration done, repeat through loop
    }      //end else, children have been compared to parent
           //end check for two children, only left child if this loop is skipped
    last = last-(2*size);
  }

/*
  **Now heapify and sort array
  */
  while(nelem > 0){
    last = qb + (size*(nelem-1)); 
    swap(qb, last, size);
    nelem=nelem-1;
    heapify(qb, nelem, 0, size, compar); //pass in array, #elements, starting pos, compare
  }

}

void heapify(void *root, size_t numel, size_t pos, size_t sz, int (*compar)(const void *, const void *)){
  void *rc, *lc, *p1;
  while(pos < numel){
    rc = root+((pos+1)*2)*sz; //right child
    lc = root+(((pos+1)*2)-1)*sz; //left child
    p1 = root+(pos*sz); //parent
    if((pos+1)*2 < numel){ //check if current element has RIGHT
      if (compar(rc, lc)>=0){
    if(compar(rc, p1)>0) {
      swap(rc, p1, sz);
      pos=(pos+1)*2; //move to RIGHT, heapify
        }
    else {
      pos = numel; //PARENT>LEFT&RIGHT, array is heapified for now 
        }
      } //end RIGHT>LEFT
      else { //LEFT>RIGHT
    if(compar(lc, p1) >0 ) {
      swap(lc, rc, sz);
      pos=((pos+1)*2)-1; // move to LEFT, heapify
    }
        else {
      pos = numel; //PARENT>LEFT&RIGHT, array is heapified for now
        } //end inner if, else
      }//end LEFT,RIGHT comparison
    }//end check for RIGHT
    else if (((pos+1)*2)-1 < numel){ //else, check if element has LEFT
      if(compar(lc, p1)>0){
    swap(lc, p1, sz);
    pos=((pos+1)*2)-1; //move to LEFT, continue heapify
      }
      else {
    pos = numel; //PARENT>LEFT, array is heapified for now
      }
    }//end check for LEFT
    else { //current element has no children, array is heapified for now
      pos = numel;
    }
  }
}

Answer 1

您的代码和问题似乎与 this question 惊人地相似从 2010 年开始，所以我怀疑这是一项家庭作业。

关于崩溃，问题出在 srtheap 的这一行:

for (size_t curpos = nelem-1; curpos>0; curpos=-2){

循环的更新表达式，curpos=-2 是错误的。您可能需要 curpos-=2。但是，如果是这样的话，仍然存在问题。 size_t 是无符号类型，因此如果原始数组中的元素数量为偶数，则程序最终将到达 curpos 等于 1 的点。当它尝试减去 2 时，结果将是一个非常大的正数，而不是您可能期望的 -1。因此，循环条件 curpos>0 的计算结果为真，并且循环将尝试访问远远超出数组末尾的数组元素，从而引发崩溃。

我不愿意弄清楚为什么您的代码没有正确排序，因为它看起来不必要地复杂。这是一个基于 this implementation 的工作通用堆排序.

void srtheap(void *base, size_t nelem, size_t size, int (*compar)(const void *, const void *))
{
    char *cb = (char *)base;

    size_t i = (nelem / 2);
    while (1) {
        heapify(cb, size, i, nelem-1, compar);
        if (i == 0) break;
        i--;
    }

    for (size_t i = nelem-1; i >= 1; i--) {
        swap(cb, cb+(size * i), size);
        heapify(cb, size, 0, i-1, compar);
    }
}

void heapify(char *base, const size_t size, size_t root, const size_t bottom, int (*compar)(const void *, const void *))
{
    size_t maxChild = root * 2 + 1;

    if (maxChild < bottom) {
        size_t otherChild = maxChild + 1;
        maxChild = (compar(base + (otherChild * size), base + (maxChild * size)) > 0) ? otherChild : maxChild;
    } else {
        if (maxChild > bottom) return;
    }

    if (compar(base + (root * size), base + (maxChild * size)) >= 0) return;

    swap(base + (root * size), base + (maxChild * size), size);

    heapify(base, size, maxChild, bottom, compar);
}

此版本使用递归，但将其转换为循环很容易。我会把它留给读者。