J'ai écrit une simple fonction récursive pour la recherche binaire qui prend trois arguments: un tableau d'entiers, la longueur du tableau et une valeur à trouver. L'idée est qu'à chaque appel récursif, il divise par deux la longueur et maintient le tableau [0] en place ou déplace l'index de départ vers le milieu (troisième ligne à partir du bas dans mon exemple). C'est jusqu'à ce que la valeur soit trouvée ou que la longueur soit égale à 0.

Ensuite, j'ai vu cette discussion: Comment faire vous décalez l'index de départ d'un tableau en C?

Il est dit ici qu'un nom de tableau est une constante et ne peut pas être réaffecté en C. Donc ma question est pourquoi ce code fonctionne?

int rsearch( int needle, int haystack[], int size ) {

if (size == 0) {
    printf("%i not found\n", needle);
    return 0;
}

int mid = size / 2;

if (haystack[mid] == needle) {
    printf( "found %i in the array\n", needle );
    return 1;

} else if (haystack[mid] > needle) {
    return rsearch( needle, haystack, size / 2 );

} else {
    haystack = &haystack[mid + 1];
    return rsearch( needle, haystack, (size - 1) / 2 );
}

J'étudie simplement et ma connaissance des pointeurs est très limitée. Et il n'y a pas d'application pratique ici. Juste curieux.

P.S. L'autre question est ce qui arrive à la mémoire allouée au tableau d'origine lorsqu'elle est réduite de cette façon? Est-il à nouveau disponible ou s'agit-il d'une fuite de mémoire?

0
fokuspokus 20 avril 2017 à 23:43

3 réponses

Meilleure réponse

Les tableaux lorsqu'ils sont utilisés comme arguments de fonction signifient en fait un pointeur vers un tableau, mais pas le tableau comme valeur. Les signatures de fonction suivantes sont donc équivalentes: void test(int xptr[10]), void test(int xptr[]) et void test(int *xptr).

Au point où un tableau est défini, cependant, vous ne pouvez initialiser que sa valeur, mais vous ne pouvez pas attribuer une autre valeur ultérieurement.

Lorsque vous passez un tableau, disons int x[10] à une fonction en utilisant simplement x comme paramètre, comme dans test(x), alors le tableau x se désintègre automatiquement en un pointeur vers le premier élément de x.

Voir le code suivant montrant la différence:

#include <stdio.h>

void test(int xptr[10]) {

    printf("value of xptr[0]: %d\n", xptr[0]); // -> 0

    xptr = &xptr[2];  // OK; xptr will point to element 2

    printf("value of xptr[0]: %d\n", xptr[0]); // -> 2
}

int main(){

    int x[10] = { 0,1,2,3,4,5,6,7,8,9 };

    // x = &x[2];  // Error: Array type 'int [10]' is not assignable

    // but:
    test(x);  // OK; and is eqivalent to...
    test (&x[0]); // OK;

    return 0; 
}
0
Stephan Lechner 20 avril 2017 à 21:03

Selon la norme C (6.7.6.3 Déclarateurs de fonction (y compris les prototypes))

7 Une déclaration d'un paramètre en tant que «tableau de type» doit être ajustée en «« pointeur qualifié vers le type »» ...

Et (6.3.2.1 Lvalues, tableaux et désignateurs de fonction)

3 Sauf s'il s'agit de l'opérande de l'opérateur sizeof ou de l'opérateur unaire &, ou d'un littéral de chaîne utilisé pour initialiser un tableau, une expression de type `` tableau de type '' est convertie en une expression avec un pointeur de type '' pour taper '' qui pointe vers l'élément initial de l'objet tableau et n'est pas une lvalue. Si l'objet tableau a une classe de stockage de registre, le comportement n'est pas défini.

Ainsi dans cette déclaration de fonction

int rsearch( int needle, int haystack[], int size );

Le paramètre int haystack[] est ajusté à int *haystack. Donc ces déclarations de fonction

int rsearch( int needle, int haystack[100], int size );
int rsearch( int needle, int haystack[10], int size );
int rsearch( int needle, int haystack[], int size );
int rsearch( int needle, int *haystack, int size );

Déclarer la même fonction. Vous pouvez inclure toutes ces déclarations dans votre programme car une déclaration de fonction peut apparaître plusieurs fois. Cependant, la fonction ne doit être définie qu'une seule fois (s'il ne s'agit pas d'une fonction en ligne).

En conséquence, le tableau passé à la fonction en tant qu'argument est implicitement converti en pointeur vers son premier élément.

Tenez compte du fait qu'il serait préférable de déclarer la fonction comme

int rsearch( int needle, const int *haystack, int size );
                         ^^^^^

Dans ce cas, la fonction peut également être utilisée avec des tableaux de constantes.

On dit ici qu'un nom de tableau est une constante et ne peut pas être réaffecté en C.

Il serait juste de dire que array n'est pas une lvalue modifiable.

À partir de la norme C (6.5.16 opérateurs d'affectation)

2 Un opérateur d'assignation doit avoir une lvaleur modifiable à sa gauche opérande.

Et (6.3.2.1 Lvalues, tableaux et désignateurs de fonction)

  1. ... Une lvalue modifiable est une lvalue qui n'a pas de type tableau , ...
0
Vlad from Moscow 20 avril 2017 à 21:31

En tant qu'argument de fonction, ceci:

int haystack[]

Est équivalent à:

int *haystack

Ceci est principalement dû au fait qu'un tableau se désintègre en un pointeur vers le premier élément lorsqu'il est passé à une fonction.

Donc, ce que vous avez n'est pas un tableau mais un pointeur. Contrairement à un tableau, un pointeur est une lvaleur modifiable, il est donc autorisé à lui affecter.

0
dbush 20 avril 2017 à 20:45