uint comme indices

Question

EDIT: Au départ, je l'avais transcrit i++ pas i--

Le code est maintenant comme il était, et le code dans les blocs compilable de code et des œuvres.

Pourquoi, si unsigned int i; est utilisé à la place de int i; dans l'extrait de code ci-dessous, en utilisant le résultat ne fonction dans un segfault?

void insertion_sort_int_array(int * const Ints, unsigned int const len) { 
    unsigned int pos; 
    int key; 
    int i; 

    for (pos = 1; pos < len; ++pos) { 
     key = Ints[pos]; 
     for (i = (pos - 1); (i >= 0) && Ints[i] > key; i--) { 
      Ints[i + 1] = Ints[i]; 
     } 
     Ints[i + 1] = key; 
    } 
} 

Answer 1

insertionSort(array A) 
begin 
    for x := 1 to length[A]-1 do 
    begin 
     value := A[x]; 
     i := x - 1; 
     while i >= 0 and A[i] > value do 
     begin 
      A[i + 1] := A[i]; 
      i := i - 1; 
     end; 
     A[i + 1] := value; 
    end; 
end; 

La seule différence entre l'algorithme de tri d'insertion standard et votre code est que vous incrémenter i au lieu de décrémentation. C'est ton problème. Je parie que dans le code que vous êtes en train de compiler et de lancer, vous avez i-- au lieu de i ++ dans la boucle interne. C'est pourquoi les non signés font une différence - ils ne peuvent pas être négatifs, donc la boucle interne ne finira jamais. Avez-vous copié le code incorrect lors de votre publication?

EDIT:

Eh bien, maintenant que vous avez modifié le code affiché, tout cela est logique, non? Un non signé va simplement déborder à INT_MAX lorsque vous le décrémentez au-delà de 0, ce qui vous amènera à accéder à la mémoire en dehors des limites du tableau.

Answer 2

Qu'est-ce qui maintient i + 1 dans les limites de votre tableau 'ints'? Il semblerait que des données mal formées dans votre tableau vous amèneront à indexer des zones de mémoire auxquelles vous ne devriez pas avoir accès.

Answer 3

Le code affiché échouera dans les deux cas (avec éventuellement une faute de seg- ment, éventuellement une corruption de mémoire).

La boucle interne à partir de pos-1 et scans vers le haut en mémoire jusqu'à ce qu'une condition aléatoire est remplie - il ne vérifie pas si elle a dépassé l'extrémité de la matrice, de sorte que se déroulera gaiement jusqu'à ce qu'il se bloque ou la La condition de fin arrive à être satisfaite par le contenu (indéfini) de la mémoire qu'il corrompt.

Vous avez probablement voulu numériser vers le bas en mémoire (en utilisant i-- dans la boucle), auquel cas il échouerait parce que la boucle atteindra 0. Soustraire 1 de 0 vous donne un très grand nombre positif dans un non signé, donc la boucle ne se terminera jamais (i> = 0 est toujours vrai) et il accédera à de la mémoire quelque part dans la région de Pluton.

Answer 4

i [provoquera] un accès au-delà des limites du tableau.

Importation limites et la comparaison à UINT_MAX au lieu des (i >= 0) précédentes résout le problème:

#include <limits.h> 

void insertion_sort_int_array(int * const Integers, unsigned int const N) 
{ 
    unsigned int o; 
    int target; 
    unsigned int i; 

    for (o = 1; o < N; o++) { 
     target = Integers[o]; 
     for (i = (o - 1); (i != UINT_MAX) && (Ints[i] > target); i--) { 
      Integers[i + 1] = Integers[i]; 
     } 
     Integers[i + 1] = key; 
    } 
} 

Answer 5

Pourquoi, si non signé int i; est utilisé au lieu de int i; dans l'extrait de code ci-dessous, utilise-t-il le résultat de la fonction dans une erreur de segmentation?

Parce que pour unsigned int i, i >= 0 est toujours vrai, de sorte que votre boucle est peu probable de mettre fin quand vous voulez.

Vous devez toujours être extrêmement prudent lorsque vous faites une boucle vers l'arrière (de haut en bas) si votre compteur n'est pas signé.