c generic 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입니다.