c一般的なheapsort

Question

これで、Cで 'generic' heapsortを作成する必要があります。これは私がこれまでに持っていたものです （コードでは閉じ括弧が欠落しているかもしれませんが、

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と入力してEnterキーを押し、クラッシュするまで待ちます。有用なコマンドには、バックトレースの場合はbt、変数の場合はpが出力されます。