c общая пирамидальная сортировка

Хорошо, поэтому мне нужно создать «общую» пирамидальную сортировку в 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;
    }
  }
}

Кроме того, у меня есть основной файл, который включает функцию сравнения. По сути, базовый адрес массива, количество элементов, размер каждого элемента и функция сравнения передаются в мои функции пирамидальной сортировки.

Когда я запускаю программу, я получаю ошибку сегментации, которая, как я полагаю, означает, что я пытаюсь получить доступ к памяти, которая мне не выделена. Итак, я думаю, мне интересно, видит ли кто-нибудь какие-либо проблемы, когда я обращаюсь к незаконным адресам памяти, или может указать мне отладчик, который я могу использовать, чтобы понять это?

Спасибо!


person mike    schedule 23.11.2010    source источник
comment
Какую платформу вы используете? Поскольку вы говорите «ошибка сегментации», это обычно сообщение, которое вы получаете от Unix/Linux, поэтому я предполагаю, что вы используете одно из них. Если вы компилируете с помощью gcc, выполните сборку с флагом -g, чтобы включить символы отладки, а затем запустите свой код через gdb (это ссылка на простое руководство по gdb).   -  person wkl    schedule 23.11.2010
comment
Да, я использую SunOS. Я посмотрю в gdb и посмотрю, добьюсь ли я успеха. Спасибо   -  person mike    schedule 23.11.2010


Ответы (3)


Отладчики часто полезны при диагностике источников ошибок памяти. Сообщите нам, что происходит, когда вы запускаете свой код из отладчика.

person ssegvic    schedule 23.11.2010
comment
поэтому, когда я запускаю свою программу в gdb, я получаю ошибку SIGSEGV, обратная трассировка: программа получила сигнал SIGSEGV, ошибка сегментации. 0x1080c в ?? () (gdb) bt #0 0x1080c в ?? () #1 0x10ad8 в ?? () #2 0x10774 в ?? () Итак, моя программа дает сбой в первой строке кода? - person mike; 23.11.2010
comment
Скомпилируйте с -g, затем перезапустите программу. При сбое программы используйте список команд, обратную трассировку, вверх и вниз. Удачи! - person ssegvic; 26.11.2010

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)
person casablanca    schedule 23.11.2010
comment
Я бы предложил использовать встроенную функцию вместо макроса из-за большей безопасности. - person ssegvic; 23.11.2010
comment
@ssegvic: это на C, а не на C++. - person casablanca; 23.11.2010
comment
ха, спасибо за находку в моем цикле for, и поэтому, когда я первоначально объявляю свои указатели, они должны выглядеть больше как char *p1, *p2; и char *last = (char *) base + (nelem-1)*size? - person mike; 23.11.2010
comment
@casablanca: Я знаю, что вы собирались сказать это :-) Как вы думаете, почему макросы предпочтительнее встроенных функций в C? - person ssegvic; 23.11.2010
comment
@ssegvic: Неважно, я всегда застрял в древнем мире и не осознавал, что C99 поддерживает встроенные функции. :) - person casablanca; 23.11.2010
comment
@ssegvic: ммм, может быть, это потому, что inline был добавлен в C только в 1999 году :-) - person ninjalj; 23.11.2010
comment
я должен привести (char *) к каждой ссылке базы в моем коде? - person mike; 23.11.2010
comment
Вы действительно должны просто создать новую переменную-указатель типа unsigned char * и немедленно преобразовать void * в нее, а затем прекратить использование void *, поскольку она непригодна для арифметики. - person R.. GitHub STOP HELPING ICE; 24.11.2010

Вы можете использовать gdb для отладки этого. Сначала скомпилируйте свою программу с помощью -g, чтобы включить символы отладки. Затем запустите: gdb heapsort, где heapsort — это имя программы. Затем введите run, нажмите Enter и подождите, пока он не вылетит. Полезные команды включают bt для обратной трассировки и p для печати значений переменных.

person nmichaels    schedule 23.11.2010