tableaux mono et multidimension

Version imprimable

Voir 40 message(s) de cette discussion en une page

01/02/2010, 17h36
lazakal

tableaux mono et multidimension

Bonsoir tout le monde 8O,
J'ai des pbs avec les tableaux;
en fait, maintenant c une question: est ce que, sémantiquement parlant, un tableau 2D , par ex tab[N][N], est équivalent à toto[N*N]; bien sur en prenant les changement d'indices.

Je veux savoir si on peut se passer de la syntaxe tab[N][N], et travailler avec
le monodimentionnel; ou bien il existe des cas où il faut passer par les [][].
01/02/2010, 17h53
ok.Idriss

Salut.

Citation:

Envoyé par lazakal

tableau 2D , par ex tab[N][N], est équivalent à toto[N*N]; bien sur en prenant les changement d'indices.

Non tab[N][N] est un tableau bidimensionnel de dimensions N et N (par analogie, c'est comme si tu avais un tableau de N lignes composées chacune de N cases) alors que tab [N*N] est un tableau mono dimensionnel de dimension N*N (cette fois, N*N cases sur une seule ligne).

Citation:

Envoyé par lazakal

Je veux savoir si on peut se passer de la syntaxe tab[N][N], et travailler avec le monodimentionnel.

Tout dépend du problème algorithmique posé mais il n'y a pas d'équivalence entre les deux syntaxes (sauf si tu as un tableau de dimensions [1][k] ou [k][1] avec k quelconque bien entendu, là tu pourra te rapporter à un tableau mono dimensionnel de dimension [k], mais bon tu ne tomberas jamais sur un tableau avec de telles dimensions je pense).

P.S : il peut y avoir une infinité de dimensions possible, algorithmiquement parlant.

Cordialement,
Idriss
01/02/2010, 18h42
orfix
Ces deux tableaux :
Code:

1 2 int tab1[N][N]; int tab2[N*N];
auront la même représentation en mémoire, mais la syntaxe d'accès est différente.
01/02/2010, 21h46
lazakal

pointeur et tableau
Corrigez moi si j'ai bien vu,
en tapant:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 #include <stdio.h> #include <stdlib.h> int main() { int *pt; int A[5][5]; pt = A; A[0][0] = 1; printf("%i", pt[0]); return 0; }
j'en déduit qu'on se plaçant sur un pointeur que le tab 2D A[][] parait monodimensionnel.
Car en affichant A[0][0] et A[0] on tombe sur les bizarreries.
01/02/2010, 22h03
ok.Idriss

Salut.

Pour ton code, avec un compilo bien réglé tu aurais ce Warning :
assignment from incompatible pointer type

Le comportement de ton pointeur est indéterminé ... il faut lui allouer la mémoire nécessaire dynamiquement. Il semble néanmoins, d'après des tests que pt[k] = A[0][k] (pour k quelconque), mais ce n'est pas propre et ça n'a aucun intérêt sur le plan algorithmique : autant utiliser un tableau à 1D, sans compter que les valeurs stockées dans les cases des lignes suivantes (A[1][k], A[2][k], etc) ne pourrons pas être lues.

Sinon, tu peut afficher A[0][0] mais il est normal que tu ne puisses pas afficher A[0] ... on vient de t'expliquer en quoi les tableau à 1 dimension et les tableau à deux dimensions sont différents, pourquoi cherches-tu à remplacer l'un par l'autre ?

Sinon, bon ce n'est pas trop important (mais c'est plus rigoureux), quand main () ne prend pas de paramètres, penses à écrire int main (void).
01/02/2010, 22h17
Sve@r

Citation:

Envoyé par lazakal

Corrigez moi si j'ai bien vu,
en tapant:
#include <stdio.h>
#include <stdlib.h>
int main()
{
int *pt;
int A[5][5];
pt = A;
A[0][0] = 1;
printf("%i", pt[0]);
return 0;

}
j'en déduit qu'on se plaçant sur un pointeur que le tab 2D A[][] parait monodimensionnel.
Car en affichant A[0][0] et A[0] on tombe sur les bizarreries.

En fait, un tableau bidimensionnel sera traduit en mémoire par un simple tableau et c'est normal car la mémoire n'est qu'une suite d'octets.
Et donc aller sur la case A[x][y] sera traduit, en final, par A[x * largeur_en_y + y]. Et ce mécanisme sera étendu quelles que soient le nombre de dimensions.

Maintenant, ton code comporte une erreur car pt étant un int *, il ne peut pas recevoir la valeur de A qui se rapproche plutôt d'un int **. Alors c'est vrai qu'il n'y a, à la base, pas grande différence entre un int * ou int ** (tous deux reçoivent une adresse) mais si tu travailles avec un int **, ça veut dire que (*pt) est connu (int*) et (**pt) est lui-aussi connu (int). Alors que si tu utilises "int *pt", le compilo croira que "*pt" est un int alors que c'est pas le cas.

Toutefois, méfiance. Même si A peut ressembler à un int **, ce n'en est pas tout à fait un. En effet, le compilo connaissant la dimension de A saura faire le calcul qui va bien pour aller sur A[x][y] alors qu'il ne saura pas aller sur pt[x][y].

Pour simplifier: seule la dernière dimension d'un tableau peut être remplacée par une étoile. Ainsi A[10] peut être stocké sans soucis dans un int *pt (et les accès à A[x] pourront être remplacés par pt[x]) mais un A[10][100] ne pourra être stocké que dans un int *pt[100] et ainsi de suite.
01/02/2010, 22h52
lazakal

pointeur **

Merci homo-sapiens-numerus (1111..) ; quoique ça parait enchevêtré mais je tiens le bout : **pt n'est pas un int, je vais cherché un "contre ou pour" exemple pour me convaincre.
01/02/2010, 22h55
diogene
Citation:

Envoyé par Sve@r

...
Toutefois, méfiance. Même si A peut ressembler à un int **, ce n'en est pas tout à fait un...

Ce n'en est pas un du tout. C'est un int (*)[5] : adresse d'un tableau de 5 int (les éléments du tableau A sont des tableaux de 5 int)

Le code suivant est légal :
Code:

1 2 3 4 5 6 7 8 9 10 #include <stdio.h> #include <stdlib.h> int main() { int *pt; int A[5][5]; pt = A[0]; .... return 0; }

Citation:

Envoyé par lazakal

Merci homo-sapiens-numerus (1111..) ; quoique ça parait enchevêtré mais je tiens le bout : **pt n'est pas un int, je vais cherché un "contre ou pour" exemple pour me convaincre.

Ah si !!! Si pt est un int **, alors **pt est un int. Le problème n'est pas la nature de "**pt" mais son emplacement

Voici différents exemples qui te montreront comment peut être considéré un tableau et la façon dont le C fait ses accès

Tableau 1D
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 int main() { static int tab[5]={10, 20, 30, 40, 50}; fct1(tab); fct2(tab); } void fct1(int pt[5]) { int i; for (i=0; i < 5; i++) printf("pt[%d]=%d\n", i, pt[i]); } void fct2(int *pt) { int i; for (i=0; i < 5; i++) printf("pt[%d]=%d\n", i, pt[i]); }
Tableau 2D
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 int main() { static int tab[2][5]={ {10, 20, 30, 40, 50}, {100, 200, 300, 400, 500} }; fct1(tab); fct2(tab); } void fct1(int pt[2][5]) { int i, j; for (i=0; i< 2; i++) { for (j=0; j < 5; j++) printf("pt[%d][%d]=%d\n", i, j, pt[i][j]); printf("\n"); } } void fct2(int *pt[5]) { int i, j; for (i=0; i< 2; i++) { for (j=0; j < 5; j++) printf("pt[%d][%d]=%d\n", i, j, pt[i][j]); printf("\n"); } }
Exemple de tableau 2D qui ne fonctionne pas
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 int main() { static int tab[2][5]={ {10, 20, 30, 40, 50}, {100, 200, 300, 400, 500} }; fct3(tab); } void fct3(int **pt) { int i, j; for (i=0; i< 2; i++) { for (j=0; j < 5; j++) printf("pt[%d][%d]=%d\n", i, j, pt[i][j]); printf("\n"); } }
Les deux premiers exemples fonctionnent car
- dans un tableau 1D, le compilo n'a pas besoin de connaitre la taille du tableau pour se déplacer sur la case "i". Il fait simplement "décalage de i * taille d'un int"
- dans le tableau 2D, chaque fonction stocke le paramètre reçu dans une variable où la largeur est indiquée. Et donc quand on demande pt[i][j], le compilo va taper sur la zone correspondant à "(i * 5 + j) * taille d'un int"

Dans le 3° exemple, l'adresse "tab" (car tab n'est qu'une adresse) est stockée dans un pointeur qui pourrait sembler adapté mais auquel il manque la notion de "largeur". Et donc quand on demande "pt[i][j]", le compilo ne sait pas de combien il doit décaler son "i" car il ne connait pas la largeur de ce "i" (qui vaut 5 mais qu'il ne sait pas).
Et ça, c'est à cause du fait que la mémoire n'est en fait qu'une longue suite de cases et qu'à un moment donné, il faut transformer une adresse [x][y] en position simple.

Bonsoir,
Je résume, A[] et A[][] correspondent respectivement à int* et int**, qui sont
distincts; et pour le A[][] il faut l'accompagner avec la 2ème dim.

Alors une dernière question pour boucler la boucle:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 #include <stdio.h> #include <stdlib.h> #define N 3 int main() { int A[N][N]; fnc(A,N); return 0; } int fnc( int *U, int n) { int i,j; for(i=0; i<n; i++) { U[i*n+j]=1; } return 0; }
Pourquoi ce programme fonctionne alors que la fonction admet un int*, et on
lui donne un int**.

Citation:

Je résume, A[] et A[][] correspondent respectivement à int* et int**,

Non, c'est faux (comme déjà expliqué plus haut).
Il n'y a aucun rapport entre le nombre d'étoiles et le nombre de dimensions du tableau.
int** correspondrait à int * A[N].

Citation:

Pourquoi ce programme fonctionne alors que la fonction admet un int*, et on
lui donne un int**.

On ne lui donne PAS un int** en argument mais un int (*)[3].

- Le compilateur devrait signaler l'utilisation d'une fonction sans prototype fnc(). En l'absence du prototype, il ne peut pas vérifier l'accord entre le type des paramètres et le type des arguments.

- Si on ajoute le prototype, le compilateur devrait signaler un désaccord entre le type du paramètre (int *) et celui de l'argument int (*)[3]

Le programme devrait être construit ainsi :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 #include <stdio.h> #include <stdlib.h> #define N 3 int fnc( int *U, int n); int main() { int A[N][N]; fnc(A[0],N); //(A[0] comme déjà signalé plus haut) return 0; } int fnc( int *U, int n) { int i,j; for(i=0; i<n; i++) { U[i*n+j]=1; } return 0; }

02/02/2010, 19h27
Sve@r
Citation:

Envoyé par lazakal

Bonsoir,
Je résume, A[] et A[][] correspondent respectivement à int* et int**, qui sont
distincts; et pour le A[][] il faut l'accompagner avec la 2ème dim.

Argh !!! Le résumé qui tue !!! On ne peut parler (et encore avec grande prudence) d'équivalence entre [] et "*" que pour la dernière dimension d'un tableau
- int A[N] => A pourra être stocké dans un int pt[] ou int *pt et pt[x] fonctionnera
- int A[N][M] => A pourra être stocké dans un int pt[][M] ou int *pt[M] et pt[x][y] fonctionnera
- int A[N][M][L] => A pourra être stocké dans un int pt[][M][L] ou int *pt[M][L] et pt[x][y][z] fonctionnera
etc etc

Citation:

Envoyé par lazakal

Pourquoi ce programme fonctionne alors que la fonction admet un int*, et on lui donne un int**.

Parce que dans l'absolu toute adresse n'est qu'un nombre. Tu peux même stocker A dans un int si tu le désires (et si tu forces un peu le compilo). Toutefois, même s'il "fonctionne", c'est pas certain qu'il fonctionne correctement

Si tu déclares un simple tableau => int tab[N] et que tu stockes tab dans un "int *pt", le compilo connait "pt" (variable de type "int étoile") et il connait aussi "étoile pt" (variable de type "int") => tu remarques qu'il a donc deux variables de types distincts.
Et donc il sait manipuler "pt" et "*pt" et aussi pt[x] qui correspond à *(pt + x)

Si tu stockes tab dans un "int pt" tu te supprimes tout seul la variable "*pt" qui n'existe plus. Et maintenant si tu veux manipuler *(pt + x) ou pt[x], le compilo ne sait pas ce qu'il faut aller chercher à l'adresse "pt + x" qui se trouve elle-même au milieu de toute la mémoire. Certaines valeurs sont stockées sur un octet, d'autres sur 2, d'autres sur 4. Et donc ne connaissant pas le type "*pt", il ne saura pas ce qu'il faut récupérer.
03/02/2010, 18h53
lazakal

les pointeurs

Bonsoir,
Excusez mon acharnement et mes bêtises, et merci pour vos patiences, mais je vous promet au bout d'y arriver.
Je résume encore au risque d'ébranler ma boucle locale:

en regardant un int A[N][M], je me dis:

tu as en face: A qui est un pointeur vers (int*)[N];

(int*)[N] est un tableau de pointeurs (int*); c à d A[0], A[1]...A[N] sont
des pointeurs vers les tableaux de int ,respectivement, A[0][M], A[1][M],...A[N][M].

Et donc pour boucler la boucle: on peut considérer A[N][M]
comme un tab 1D : *(A[0]+i), i allant de 0 à N*M.
03/02/2010, 21h08
Sve@r

Citation:

Envoyé par lazakal

Bonsoir,
Excusez mon acharnement et mes bêtises, et merci pour vos patiences, mais je vous promet au bout d'y arriver.
Je résume encore au risque d'ébranler ma boucle locale:

en regardant un int A[N][M], je me dis:

tu as en face: A qui est un pointeur vers (int*)[N];

(int*)[N] est un tableau de pointeurs (int*); c à d A[0], A[1]...A[N] sont
des pointeurs vers les tableaux de int ,respectivement, A[0][M], A[1][M],...A[N][M].

Et donc pour boucler la boucle: on peut considérer A[N][M]
comme un tab 1D : *(A[0]+i), i allant de 0 à N*M.

Oui... et non.

Oui parce que t'as parfaitement compris le mécanisme de transformation d'indice en "D" dimensions en indice en 1 dimension. Et effectivement, *(A[0] + i) avec un i correctement calculé t'amènera sur la case référncée aussi par A[x][y]

Non parce qu'au niveau de la machine, les choses sont pas équivalentes. C'est comme si je te parle de "5.0" et "5". N'importe quel mathématicien dira "c'est la même chose". Oui, d'un point de vue humain. Mais au niveau de la machine, l'un est un entier et l'autre un nombre à virgule flottante.

Ainsi, au niveau machine, un tableau est un tableau et un pointeur est un pointeur. Et ce n'est pas parce que l'un peut, dans une certaine mesure, se comporter comme l'autre que les deux éléments sont la même chose.
03/02/2010, 21h57
lazakal

Encore merci HSSN, j'ai oublié qu'un tableau est une structure fondamentale et
élémentaire et donc pouvait recevoir une certaine attention de la part du compi
Merci à tout le monde.
Et à toi auusi IDRISS, ok?. :ccool:
03/02/2010, 22h48
diogene

Il faut faire attention :

Citation:

en regardant un int A[N][M], je me dis:

tu as en face: A qui est un pointeur vers (int*)[N];

Non, A est un int(*)[M] (attention aux parenthèses) ce qui n'est pas la même chose.

Citation:

(int*)[N] est un tableau de pointeurs (int*); c à d A[0], A[1]...A[N] sont des pointeurs vers les tableaux de int ,

Si on écrit int*A[], (on ne peut pas mettre les parenthèses comme dans (int*)[], ça ferait un opérateur de cast) on a bien un tableau de pointeurs sur int. Mais alors, A[i] est du type pointeur sur int : int * , pas pointeur vers un tableau de int.

Le raisonnement est le suivant :

- Règle : Sauf employé avec les opérateurs unaires sizeof et &, l'identificateur d'un tableau est une valeur égale à l'adresse du premier élément du tableau et est donc du type "adresse d'un élément du tableau".

Conséquence :

- Si on a int A[N], les éléments du tableau sont des int et le type de A est donc pointeur sur int : int *

- Si on a int A[N][M], les éléments du tableau sont des tableaux de M int et le type est pointeur sur des tableaux de M int : int (*)[M]
Dans ce cas A[i] est un tableau de M éléments de type int et donc son type est int *
04/02/2010, 21h49
c-candide
Citation:

Envoyé par diogene

- Règle : Sauf employé avec les opérateurs unaires sizeof et &,

Tu oublies un cas.

Citation:

Envoyé par diogene

l'identificateur d'un tableau est une valeur égale à l'adresse du premier élément du tableau et est donc du type "adresse d'un élément du tableau".

Ce n'est pas du tout un identificateur de tableau qui est une valeur (d'ailleurs un identificateur n'EST pas une valeur) mais c'est une lvalue qui est CONVERTIE (c'est essentiel) en une expression de type etc. Avec ta formulation, on ne peut pas comprendre le très bon exemple que tu as donné précédemment :
Code:

1 2 3 4 5 6 7 8 9 10 #include <stdio.h> #include <stdlib.h> int main() { int *pt; int A[5][5]; pt = A[0]; .... return 0; }
puisque A[0] n'est pas un identificateur. Il faudrait plutôt dire que A[0] est une lvalue de type tableau d'entiers et donc, dans ce contexte, elle est convertie en pointeur vers son premier élément.

Quand on parle de tableaux vs pointeurs, il faut peser ses mots. Avec tes formulations, on penserait assez vite qu'un tableau EST un pointeur.
05/02/2010, 06h42
Melem

Citation:

Envoyé par c-candide

Tu oublies un cas.

Cette remarque aurait pu avoir de la valeur si tu avais rappelé le cas "oublié" (chaîne littérale initialisante). De plus, cet oubli n'est pas bien grâve. Pas parce que le moment de l'initialisation est déjà de toute façon le fourre-tout des exceptions et qu'il n'est plus vraiment utile de le rappeler à chaque fois, mais surtout parce que cette règle est déjà le plus souvent (mieux) formulée autrement (genre char s[] = {...} peut être simplifiée en char s[] = "...", etc.) pour en rester là. De plus, il n'était absolument pas nécessaire de le dire parce qu'on parle là d'identificateur de tableau (pas d'expression de type tableau en général, comme tu le développeras par la suite).

Citation:

Envoyé par c-candide

Ce n'est pas du tout un identificateur de tableau qui est une valeur (d'ailleurs un identificateur n'EST pas une valeur) mais c'est une lvalue qui est CONVERTIE (c'est essentiel) en une expression de type etc. Avec ta formulation, on ne peut pas comprendre le très bon exemple que tu as donné (...)

puisque A[0] n'est pas un identificateur. Il faudrait plutôt dire que A[0] est une lvalue de type tableau d'entiers et donc, dans ce contexte, elle est convertie en pointeur vers son premier élément.

En fait, la formulation de diogene était correcte. Seulement ça ne permet effectivement pas d'expliquer rigoureusement l'exemple qu'il avait donné, comme tu l'as fait remarqué. Mais la pédagogie était bonne, parfaite même, et permet de comprendre l'exemple.

Citation:

Envoyé par c-candide

Quand on parle de tableaux vs pointeurs, il faut peser ses mots. Avec tes formulations, on penserait assez vite qu'un tableau EST un pointeur.

Un tableau n'est pas un pointeur, jamais. Mais l'identificateur d'un tableau, en dehors de sizeof et de &, EST (après conversion si t'as vraiment besoin qu'on le précise) un pointeur sur le premier élément du tableau. Je répète que je suis entièrement d'accord que les règles énoncées en ayant recours à la notion d'identificateur ne constituent pas le cas général, mais elles ne sont pas fausses.
05/02/2010, 08h52
c-candide

Citation:

Envoyé par Melem

Mais l'identificateur d'un tableau, en dehors de sizeof et de &, EST (après conversion si t'as vraiment besoin qu'on le précise) un pointeur sur le premier élément du tableau.

C'est incorrect, tu mélanges deux niveaux. Un objet peut exister sans qu'il y ait d'identificateur pour le désigner.Un identificateur n'est pas un objet, un identificateur appartient au champ lexical du programme, la Norme en parle dans le § intitulé Lexical elements et dit:

Citation:

An identiﬁer is a sequence of nondigit characters

d'ailleurs quand on parle de la portée de l'identificateur toto, on se réfère à la présence dans le texte du code-source du "mot" toto.

Tu ne veux pas employer le terme approprié ("est converti"), c'est ton droit. Si je ne l'emploie pas, ta phrase ci-dessus devient :

Citation:

Mais l'identificateur d'un tableau, en dehors de sizeof et de &, EST un pointeur sur le premier élément du tableau.

donc, on lit bien un identificateur de tableau EST un pointeur.

Si tu te targues de pédagogie, ta formulation est imprudente voire dangereuse. La bonne formulation est dans la Norme et ici pour cette question de tableau vs pointeur, il est difficile de s'en éloigner un tant soit peu sans tomber dans la simplification abusive.
05/02/2010, 10h21
lazakal

débutant cherche à comprendre

Bonjour, 8O
Cher candide,
Je débute en C, et j'ai lancé cette discussion en espérant avoir des réponses
simples ou graduelles. :calim2:

Il se trouve que j'ai déjà enseigné, et j'ai pratiqué la pédagogie. Il existe des niveaux d'abstraction, dans chaque discipline, qu'on y recours selon les circonstances. ;)

En tout les cas l'évolution des messages (et des clics...) m'amena au tuto de patrick Gonord "Concepts en C"; je le trouve de "haut niveau d'abstraction" et surtout trés bien conçu, Grand Merci P.G. :ccool:

Alors si tu as des remarques commence par le tuto. :zoubi:

Candidement. ::D

Voir 40 message(s) de cette discussion en une page