2

Cで「ジェネリック」ヒープソートを作成する必要があります。

比較機能を含むメインファイルがあります。基本的に、配列のベースアドレス、要素の数、各要素のサイズ、および比較関数は、ヒープソート関数に渡されます。私は2つの問題に直面しています。1つはプログラムがそれをソートしていないので、誰かがコードに何か問題があるのではないかと思っていました。2 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;
    }
  }
}
4

1 に答える 1

2

あなたのコードと質問は2010年のこの質問と驚くほど似ているように思われるので、これは宿題だと思います。

クラッシュに関して、問題は次の行にありsrtheapます：

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

ループの更新式curpos=-2が間違っています。あなたはおそらく欲しいですcurpos-=2。その場合でも、まだ問題があります。size_tは符号なし型であるため、元の配列に偶数の要素がある場合、プログラムは最終的に。curposに等しいポイントに到達し1ます。減算しようとすると2、結果は非常に大きな正の数になり、-1予想どおりではありません。したがって、ループ条件はcurpos>0trueと評価され、ループは配列の終わりをはるかに超えて配列要素にアクセスしようとし、クラッシュをトリガーします。

コードが不必要に複雑に見えるため、コードが正しくソートされない理由を理解するのは気が進まない。これは、この実装に基づいた実用的な汎用ヒープソートです。

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);
}

このバージョンは再帰を使用しますが、ループに変換するのは簡単です。それは読者にお任せします。

于 2012-12-06T07:08:29.137 に答える