erreur de segmentation lors de l’hémification

J’étais simplement en train d’heapifier un tableau en C. Mais en cours d’exécution, cela me donne une erreur de segmentation (kernel vidé) … Je ne sais pas du tout où j’essaie d’accéder à de la mémoire non allouée !!

#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; } 

Vous appelez min_heap(a,i) lorsque i == n/2 .

Dans ce cas, à l’intérieur de min_heap() l’appel de right() retournera en vigueur:

 (2 * (n/2) + 1) 

Quand n est pair, cela donne un index de droite de n+1 et l’access à a[r] (avec r == n+1 ) dépasse la fin du tableau que vous avez alloué.

Je ne sais pas si c’est la raison de votre erreur de segmentation; Je suppose qu’il peut y avoir d’autres problèmes.

Vous devriez probablement simplement passer à travers une exécution avec un débogueur.

Voici du code provenant de More Programming Pearls de Jon Bentley, écrit sous forme de commentaires dans un fichier C. Le code complet ne vous concerne pas; c’est une interface générique comme l’interface vers bsearch() et qsort() , mais cela est écrit 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) ** } ** } */ 

Dans le code, le tableau en cours de sorting est x , indexé de 1 à N