Fallo de segmentación al heapificar.

Simplemente estaba acumulando una matriz en C. Pero mientras se ejecuta, me está dando una falla de segmentación (núcleo volcado) … ¡No tengo idea de dónde estoy tratando de acceder a la memoria no asignada!

#include int n; int left(i) { return (2*i); } int right(i) { return (2*i + 1); } void min_heap(int a[],int i) { int l=left(i); int r=right(i); int min; if((l<=n)&&(a[l]<=a[i])&&(a[l]<=a[r])) { min=a[l]; a[i]=a[i]+a[l]; a[l]=a[i]-a[l]; a[i]=a[i]-a[l]; } else if((r<=n)&&(a[r]<=a[i])&&(a[r]<=a[l])) { min=a[r]; a[i]=a[i]+a[r]; a[r]=a[i]-a[r]; a[i]=a[i]-a[r]; } min_heap(a,min); } int main() { printf("The no is : "); scanf("%d",&n); int i,a[n+1]; for(i=1;i=1;i--) { min_heap(a,i); } for(i=1;i<=n;i++) { printf("%d",a[i]); } return 0; } 

min_heap(a,i) a min_heap(a,i) cuando i == n/2 .

En este caso, dentro de min_heap() la llamada a la right() regresará en efecto:

 (2 * (n/2) + 1) 

Cuando n es par, se obtendrá un índice correcto de n+1 y el acceso a[r] (con r == n+1 ) está más allá del final de la matriz que ha asignado.

No estoy seguro de si esta es la razón de tu falta de seguridad; Supongo que puede haber otros problemas.

Probablemente debería pasar por una ejecución con un depurador.

Aquí hay un código de More Programming Pearls escrito por Jon Bentley, escrito como comentarios en un archivo C. El código completo no es relevante para usted; es una interfaz genérica como la interfaz de bsearch() y qsort() , pero esto está escrito en awk .

 /* ** See Appendix 2 of Jon Bentley "More Programming Pearls". ** See also Column 14 of Jon Bentley "Programming Pearls, 2nd Edn". ** Note that MPP algorithms are in terms of an array indexed from 1. ** C, of course, indexes arrays from zero. ** ** 1-based identities. ** root = 1 ** value(i) = x(i) ** leftchild(i) = 2*i ** rightchild(i) = 2*i+1 ** parent(i) = i/2 ** null(i) = (i < 1) or (i > n) ** ** 0-based identities. ** root = 0 ** value(i) = x(i) ** leftchild(i) = 2*(i+1)-1 = 2*i+1 ** rightchild(i) = 2*(i+1)+1-1 = leftchild(i)+1 ** parent(i) = (i+1)/2-1 ** null(i) = (i < 0) or (i >= n) # NB: i < 0 irrelevant for unsigned numbers */ /* ** function swap(i, jt) { ** # x[i] :=: x[j] ** t = x[i] ** x[i] = x[j] ** x[j] = t ** } ** ** function siftup(l, u, i, p) { ** # pre maxheap(l, u-1) ** # post maxheap(l, u) ** i = u ** while (1) { ** # maxheap(l, u) except between i and its parent ** if (i <= l) break ** p = int(i/2) # p = parent(i) ** if (x[p] >= x[i]) break ** swap(p, i) ** i = p ** } ** } ** ** function siftdown(l, u, i, c) { ** # pre maxheap(l+1, u) ** # post maxheap(l,u) ** i = l ** while (1) { ** # maxheap(l, u) except between i and its children ** c = 2*i # c = leftchild(i) ** if (c > u) break; ** if (c + 1 <= u && x[c+1] > x[c]) c++ ** if (x[i] >= x[c]) break ** swap(c, i) ** i = c ** } ** } ** ** function hsort( i) { ** # post sorted(1, n) ** for (i = int(n/2); i >= 1; i--) ** siftdown(i, n) ** for (i = n; i >= 2; i--) { ** swap(1, i) ** siftdown(1, i-1) ** } ** } */ 

En el código, la matriz que se clasifica es x , indexada de 1 a N