C 通用堆排序

Question

好吧，我需要在 c 中创建一个“通用”堆排序，这就是我到目前为止所拥有的 （我可能在代码中丢失了一些右括号，但当我将代码移到此处时，它们就丢失了）

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 *)) {
  void *p1, *p2;
  void *last = base + (size*(nelem-1));
  for (size_t curpos = nelem-1; curpos>0; curpos-2){
    p1 = base + ((curpos-1)/2)*size;
    if(compar(last, (last-size)) >= 0){ 
      if(compar(last, p1) > 0){
        swap(last, p1, size);
        heapify(base, nelem, curpos, size, compar); 
      }
    }
    else { //LEFT>RIGHT
      if(compar(last-size, p1) > 0){
         swap(last-size, p1, size);
         heapify(base, 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 = base + (size*(nelem-1)); 
    swap(base, last, size);
    nelem=nelem-1;
    heapify(base, 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

调试器通常可用于诊断内存错误源。让我们知道当您从调试器运行代码时会发生什么。

Answer 2

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

curpos-2 没有任何效果。您是指 -- 还是 -=2 ？

另外，严格来说，您不能对 void * 指针进行指针算术，即使您的编译器允许，也不要依赖它。相反，请将其转换为 char *，以便保证 ptr + x 只会添加 x 字节，而不是 的某个倍数>x。

您可能还会发现创建一个宏来索引元素数组很有用。这将使您的代码更具可读性：

#define ELEM(base, i) ((char *)(base) + (i)*size)

Answer 3

您可以使用 gdb 来帮助调试。首先，使用 -g 编译程序以启用调试符号。然后运行：gdb heapsort 其中 heapsort 是程序的名称。然后输入run，按回车键，然后等待直到崩溃。有用的命令包括用于回溯的 bt 和用于打印变量中的值的 p。