c универсальный порт - PullRequest
Новая
       2

c универсальный порт

1 голос
/ 23 ноября 2010

Хорошо, мне нужно создать «универсальный» heapsort в 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;
    }
  }
}

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

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

Спасибо!

Ответы [ 3 ]

2 голосов
/ 23 ноября 2010

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

1 голос
/ 23 ноября 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)
0 голосов
/ 23 ноября 2010

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

...