Allocation dynamique sur tableau 2D

Bonjour, j'aimerais faire une fonction qui alloue dynamiquement un tableau 2D mais en seulement 2 malloc et la même fonction en seulement 1 malloc. J'ai déjà tenté ça mais le programme crash et je ne sais pas pourquoi. Merci d'avance.

En 1 malloc

Code:

---

1 2 3 4 5 6

int** initTab(int N, int M){   int** tab = (int**) malloc( (sizeof(int*)*N*M );   return tab; }

---

En 2 malloc

Code:

---

1 2 3 4 5 6 7 8

int** initTab(int N, int M){   int** tab = (int**) malloc(sizeof(int*)*N);   int** tab2 = (int*) malloc(sizeof(int)*M);   return tab; }

---

Bonjour,

Déjà, il est difficile de savoir pourquoi cela crashe, car le seul code que vous donnez, c'est celui de l'allocation (qui d'après moi, ne va pas crasher, sauf cas très improbable).

Dans le premier cas, vous alliez N * M int*, alors qu'il faudrait plutôt allouer N * M intDans le second cas, il me semble qu'il faille une boucle for. Du coup, il faut écrire deux malloc, toutefois, à l'exécution, ce sont plus de deux mallocs qui vont être réalisés.

C'est des exercices que je dois faire en cours donc je n'ai pas accès au reste du code, je ne dois écrire que la fonction demandé. Voici l'intitulé de l'exercice :

Complétez la fonction pour qu'elle alloue et retourne un tableau de NxM cases.

Chaque case (i,j), telle que 0<=i<N, et 0<=j<M, sera accessible via tab[i][j] si tab est le nom donné au tableau retourné, et sera initialisée à i+j.

L'allocation devra se faire en 2 mallocs.

Et j'ai fait que tu m'as conseillé, mais ce n'est pas ce qui est demandé

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

int** initMatrix(int N, int M){   int** tab = (int**) malloc(sizeof(int*)*N);   for(int i=0; i<N; i++){   tab[i] = (int*) malloc(sizeof(int)*M);   for(int j=0; j<M; j++){ tab[i][j]=i+j; } }   return tab; }

---

Résultat :
Pièce jointe 520677

Au vu de l'indication, je comprend bien qu'il faut enlever la boucle et faire qu'un malloc de N*M, mais je ne sais pas où la faire pointer. J'ai tenté ça mais ça crash :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

int** initMatrix(int N, int M){   int** tab = (int**) malloc(sizeof(int*)*N);   *tab = (int*) malloc(N*M);   for(int i=0; i<N; i++){ for(int j=0; j<M; j++){ tab[i][j]=i+j; } }       return tab; }

---

Bonjour

Citation:

---

Envoyé par Adiren

Complétez la fonction pour qu'elle alloue et retourne un tableau de NxM cases.

Chaque case (i,j), telle que 0<=i<N, et 0<=j<M, sera accessible via tab[i][j] si tab est le nom donné au tableau retourné, et sera initialisée à i+j.

L'allocation devra se faire en 2 mallocs.

Et j'ai fait que tu m'as conseillé, mais ce n'est pas ce qui est demandé

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

int** initMatrix(int N, int M){   int** tab = (int**) malloc(sizeof(int*)*N);   for(int i=0; i<N; i++){   tab[i] = (int*) malloc(sizeof(int)*M);   for(int j=0; j<M; j++){ tab[i][j]=i+j; } }   return tab; }

---

---

Mais si. Il y a bien 2 malloc dans cette fonction !!!

Citation:

---

Envoyé par Adiren

Au vu de l'indication, je comprend bien qu'il faut enlever la boucle et faire qu'un malloc de N*M, mais je ne sais pas où la faire pointer. J'ai tenté ça mais ça crash :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

int** initMatrix(int N, int M){   int** tab = (int**) malloc(sizeof(int*)*N);   *tab = (int*) malloc(N*M);   for(int i=0; i<N; i++){ for(int j=0; j<M; j++){ tab[i][j]=i+j; } }       return tab; }

---

---

Normal. Il ne faut pas perdre de vue que tu dois obtenir en final des cases. La première méthode te fait allouer N pointeurs puis chaque pointeur te fait allouer M cases. Donc tu as bien des cases au final (et en 2 malloc comme demandé)
La seconde méthode doit te faire allouer aussi des cases mais en une seule opération. Comme un jeu d'échecs de N*M cases (et non N*M pointeurs). Bref dans cette seconde méthode, tu n'as droit qu'à un malloc donc tu dois partr d'un int * et non d'un int **. Ton tout premier essai sur cet exo était presque ça.

Je ne montrais que la fonction avec 2 malloc, et comme un malloc est dans une boucle, ce n'est pas 2 malloc mais en N+1.

Et merci, pour les indications avec qu'1 malloc, je vais retenter

Bonjour,

Alors, pour la version avec un seul malloc, il faut que tu utilises un tableau 1D comme un tableau 2D.

Code:

---

1 2 3 4 5 6 7

#define WIDTH 10 #define HEIGHT 10 int* matrix = malloc(WIDTH * HEIGHT * sizeof(int)); // [...] // Exemple mise a 42 de l'élément matrix[i][j] matrix[i*WIDTH +j] = 42;

---

Tu peux éventuellement utiliser des defines pour simplifier les écritures/lectures.


Pour la version a 2 mallocs c'est un peu plus subtil. Tu alloues tout en une fois comme un tableau contigu et tu fais pointer sur les bons éléments.

Code:

---

1 2 3 4 5 6 7

int** matrix= malloc(WIDTH *sizeof(int*)); int* tmpptr = malloc(WIDTH * HEIGHT *sizeof(int)) for(int i=0;i<WIDTH ;++i) { matrix[i] = tmpptr; tmpptr += HEIGHT; }

---

(On peut faire beaucoup plus cours que ce code, mais cette version me semble pédagogique. Attention je n'ai pas testé ces codes).


En réutilisant la deuxième approche tu peux passer très simplement à un seul malloc tout en gardant un int**. Si tu as compris le principe tu dois être capable de l'adapter tout seul! :)

Merci beaucoup, je comprend pour tu fais ça comme ça mais a quoi sert le tmpptr += HEIGHT;, il sert à décaler l'endroit où l'ont pointe sur tmpptr pour qu'on soit sur la bonne "partition" ?

Citation:

---

Envoyé par emixam16

Alors, pour la version avec un seul malloc, il faut que tu utilises un tableau 1D comme un tableau 2D.

---

Ca tu aurais pu le lui laisser trouver tout seul...

Citation:

---

Envoyé par emixam16

Pour la version a 2 mallocs c'est un peu plus subtil. Tu alloues tout en une fois comme un tableau contigu et tu fais pointer sur les bons éléments.

Code:

---

1 2 3 4 5 6 7

int** matrix= malloc(WIDTH *sizeof(int*)); int* tmpptr = malloc(WIDTH * HEIGHT *sizeof(int)) for(int i=0;i<WIDTH ;++i) { matrix[i] = tmpptr; tmpptr += HEIGHT; }

---

---

Joli :applo:

Citation:

---

Envoyé par Adiren

Je ne montrais que la fonction avec 2 malloc, et comme un malloc est dans une boucle, ce n'est pas 2 malloc mais en N+1.

---

Comme j'avais pas pensé à la solution de emixam16, je me disais qu'on pouvait jouer sur les mots avec l'énoncé en parlant du code source (qui effectivement contient 2 malloc) et non de son exécution (qui effectivement en comporte N). D'autant plus que sa solution est loin d'un niveau débutant.

Citation:

---

Envoyé par Adiren

Merci beaucoup, je comprend pour tu fais ça comme ça mais a quoi sert le tmpptr += HEIGHT;, il sert à décaler l'endroit où l'ont pointe sur tmpptr pour qu'on soit sur la bonne "partition" ?

---

Exact. C'est un peu le un mélange de ton tout premier exemple (avec les malloc dans la boucle) et de celui de l'échiquier. Il définit d'abord l'échiquier en un coup puis il place différents pointeurs (dont le tableau a été lui-aussi alloué) aux endroits clefs dudit échiquier (les têtes de ligne). Et donc quand tu es sur un échiquier numéroté de 0 à 63 et que tu te trouves en début de ligne "l", il faut ajouter "8" pour te retrouver au début de la ligne "l+1".

Bravo pour la version en deux malloc, je n'arrivais pas à la trouver. Toutefois, je me demande l'utilité d'un tel exercice. Est-ce qu'en pratique vous avez déjà rencontré un tel besoin ? Après, on peut toujours dire que c'est pour forcer à manipuler les pointeurs, mais... quand même, ça me semble faire du code tordu pour rien :aie:.

Effectivement c'est pour me forcer à utiliser les pointeurs. Et oui c'est du code tordu :roll:

Pour la version du tableau 2D en 1 malloc j'ai tenté cela, en me basant sur la méthode avec 2 malloc

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

int** initMatrix(int N, int M){   int** tab= malloc(N * N * M * sizeof(int*));   for(int i=0;i<N ;++i) {   tab[i] = tab[(M*i) +N];   for(int j=0; j<M; j++){ tab[(i*M) + N + j]= i+j; } tab += M; } return tab; }

---

ça n'abouti pas à quelque chose de concluant, j'ai mal compris un truc ?

Citation:

---

Envoyé par LittleWhite

Bravo pour la version en deux malloc, je n'arrivais pas à la trouver. Toutefois, je me demande l'utilité d'un tel exercice. Est-ce qu'en pratique vous avez déjà rencontré un tel besoin ? Après, on peut toujours dire que c'est pour forcer à manipuler les pointeurs, mais... quand même, ça me semble faire du code tordu pour rien :aie:.

---

Effectivement c'est un peu overkill comme approche mais oui, j'ai déjà vu ce type de code utilisé en pratique sur des systèmes Temps Réels (propriétaires) où les allocations étaient longues dans le pire des cas donc ils faisaient toutes leurs allocations d'un "bloc de traitement" en une fois pour être sur que le pire cas reste dans l'enveloppe temporelle. Y compris quand ils avaient des matrices.

Après clairement pour le cas général ça reste de l'optimisation de bout de chandelle... Mais pour un étudiant ça fait quand même travailler les pointeurs à la dure!

Citation:

---

Envoyé par adiren

ça n'abouti pas à quelque chose de concluant, j'ai mal compris un truc ?

---

Oui, tu as plusieurs erreurs. Certaines de ces erreurs pourraient corrigées facilement en regardant ton compilateur!

Citation:

---

Envoyé par adiren

Code:

---

int** tab= malloc(N * N * M * sizeof(int));

---

---

D'ou sort ce N * N * M * sizeof(int)? Que veut tu allouer ici?

Citation:

---

Envoyé par adiren

Code:

---

tab[i] = tab[(M*i) +N];

---

---

Là c'est encore plus faux. tab est un int** pas un int* sers t'en comme tel.

--

Ce schéma devrait t'aider à comprendre l'allocation à 2 mallocs, et comment l'adapter pour passer à 1.

http://c-faq.com/aryptr/array2.gif

Citation:

---

Envoyé par Adiren

ça n'abouti pas à quelque chose de concluant, j'ai mal compris un truc ?

---

Oui. Avec un malloc faut voir ton tableau juste comme une longue suite de cases. Donc un "int *". Tout comme un échiquier que tu découperais lignes à lignes et que tu alignerais ensuite bout à bout. Et c'est quoi ce "N * N * N" ??? Tu veux allouer un cube ??? (remarque, même pour un cube, bien écrit ça fonctionnera aussi).

Après avoir un peu (beaucoup) cherché, j'ai fait cela. ça ne crash, je n'arrive juste plus à le remplir.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

int** initMatrix(int N, int M){   int** tab = (int**) malloc(N*sizeof(int*) + N*M*sizeof(int));   for(int i=0;i<N ;++i){ tab[i] = tab +M;   for(int j=0; j<M; j++){ tab[i][j] = i+j; } } return tab; }

---

Et voila ma sortie :

Je sens que j'y suis presque !!

Pour l'allocation, c'est bien!

par contre pour l'initialisation des pointeurs sur les colonnes tu ne sembles pas avoir compris...

Code:

---

1 2 3

for(int i=0;i<N ;++i) tab[i] = tab +M;

---

??? Pourquoi tab+M? Ici toutes les cases pointent vers le même endroit (puisque M est constant). Cela ne peut pas fonctionner. Indice: tab[i] doit dépendre de i, comme dans mon schéma!

De base j'avais mis tab[i] = tab + N + M*i;
Mais ça me sortait des choses bizarres.

Pièce jointe 523261

Ok j'ai fait cela et ça a marché : tab[i] = tab +N + M*(i+N);

Je comprend pas pourquoi on doit faire i+N à la fin

Ton compilateur te donne des warnings, ce n'est pas pour rien. Essaie de les comprendre et les interpréter. Un warning c'est rarement anodin.

Code:

---

1 2 3

warning: assignment from incompatible pointer type [-Wincompatible-pointer-types] tab[i] = tab + N + M*i;

---

Allez, je vais t'aider car ton problème est légèrement piégeux.

En gros tu initialise un int* à partir d'un int**. Et ça, ben c'est pas bon.

Donc soit tu te dis, je vais calculer les tailles manuellement

Code:

---

tab[i] = ((void*)tab) + N*sizeof(int**) + M*i*sizeof(int);

---

Soit tu te force tab+N à être traité comme un int*

Code:

---

tab[i] = ((int*)(tab + N)) + M*i;

---

Et voilà, tu as un code qui marche avec un seul malloc!
--
Note: Tu es assez débutant et cette méthode est assez bourrine avancée. Ne t'en sers pas comme exemple général, les autres méthodes sont plus simples, plus intuitives et peu ou prou aussi rapides. Donc, sauf quand tu sais ce que tu fais, évite ce genre "d'optimisations", surtout si tu codes en groupe, tu vas rapidement te faire détester!

J'ai réussi en faisant cela :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

int** initMatrix(int N, int M){   int** tab = (int**) malloc(N*sizeof(int*) + N*M*sizeof(int));   for(int i=0;i<N ;i++){ tab[i] = (tab +N) +M*(i+N); for(int j=0; j<M; j++){ tab[i][j] = i+j; } } return tab; }

---

C'était un peu en bidouillant en fonction des erreurs retournées mais je ne comprend vraiment pas cette solution. Tu peux m'expliquer s'il te plait ? C'est le M*(i+N).

Citation:

---

Envoyé par Adiren

Tu peux m'expliquer s'il te plait ? C'est le M*(i+N).

---

Je pense que c'est pour placer les différents pointeurs de ligne tab[i] après la zone de datas. Tu peux t'en rendre compte si tu isoles le calcul dans une variable que tu affiches

Accessoirement je te conseillerais de mettre des variables plus explicites que ce "N" et "M". Par exemple "nLig" et "nCol" comme j'ai fait chez-moi ce qui donne

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14

int** initMatrix(int nLig, int nCol) { int** tab=malloc(nLig * sizeof(*tab) + nLig * nCol * sizeof(**tab)); printf("tab=%p\n", tab); size_t off;   for(int i=0; i<nLig; i++) { off=nLig + nCol * (i + nLig); tab[i]=(int*)(tab + off); printf("off=%lu, tab[%d]=%p\n", off, i, tab[i]); for(int j=0; j<nCol; j++) tab[i][j]=i + j; } return tab; }

---

Bonsoir,

Citation:

---

Envoyé par Sve@r

Citation:

---

Envoyé par Adiren

Tu peux m'expliquer s'il te plait ? C'est le M*(i+N).

---

Je pense que c'est pour placer les différents pointeurs de ligne tab[i] après la zone de datas. Tu peux t'en rendre compte si tu isoles le calcul dans une variable que tu affiches

---

C'est le but disons… mais ce n'est pas correct. Ça ne fait que tomber en marche.
Rien que la première adresse pour i=0 : (tab + nLig) + nCol * (0 + nLig) = (tab + nLig) + nCol * nLig va déjà taper au dela de la zone allouée (en 64 bits où généralement sizeof(int*) = 2 * sizeof(int) = 8. En 32 bits où on aura généralement sizeof(int*) = sizeof(int) = 4, elle arrive pile à la toute fin).

tab étant de type int**, avec tab + off on va se déplacer par unités de sizeof(*tab) = sizeof(int*) = 8 (64 bits) / 4 (32 bits).

La première partie nLig qui constitue le calcul de off est correcte : on passe la première zone de taille nLig * sizeof(*tab). Mais ensuite il faut se déplacer par unités de sizeof(int). Et pour cela il faut revenir à un int * :

Code:

---

int *debut_tableau = (int*)(tab + nLig);

---

Puis chaque ligne contenant nCol valeurs, aller sur la i^e ligne revient à se déplacer de i * nCol cases :

Code:

---

tab[i] = debut_tableau + i * nCol;

---

Le but final étant de faire pointer chaque pointeur tab[i] (cases bleus à gauche) vers l'adresse de la première case de chaque ligne correspondante (cases rouges tab[i][0]).

Citation:

---

Envoyé par Winjerome

tab étant de type int**, avec tab + off on va se déplacer par unités de sizeof(*tab) = sizeof(int*) = 8 (64 bits) / 4 (32 bits).

---

Exact, effectivement j'ai raté ce détail. Mais (à ma décharge :oops:) j'ai juste repris le code initial en isolant le calcul dans "off". Le code initial ajoute ce calcul à tab, j'ajoute off à tab.

Citation:

---

Envoyé par Winjerome

Le but final étant de faire pointer chaque pointeur tab[i] (cases bleus à gauche) vers l'adresse de la première case de chaque ligne correspondante (cases rouges tab[i][0]).

---

Oui mais pour moi c'est dans l'autre sens. Les pointeurs sont à la fin de la zone des ints, qui, elle, commence au début de tab. Ceci pour permettre par exemple à un itérateur qui partirait de tab de pouvoir lui-aussi accéder aux ints par simple incrément sans avoir à le faire partir d'un offset à la c..
Et ces pointeurs continuent évidemment à pointer vers les différents "tab[x]" qui identifient chaque début de ligne.
Sinon très belle image. Tu l'as faite avec quoi ?

[edit] Ok, j'ai affiché les adresse

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 32 33

#include <stdio.h> #include <stdlib.h>   int** initMatrix(int nLig, int nCol) { printf("sizeof(int)=%lu\n", sizeof(int)); printf("sizeof(int*)=%lu\n", sizeof(int*)); printf("sizeof(int**)=%lu\n", sizeof(int**)); printf("lig=%d, col=%d\n", nLig, nCol); int** tab; size_t t=nLig * sizeof(*tab) + nLig * nCol * sizeof(**tab); printf("alloc=%lu\n", t); tab=malloc(t); printf("tab=%lu\n", tab); size_t off;   for(int i=0; i<nLig; i++) { off=nLig + nCol * (i + nLig); tab[i]=(int*)(tab + off); printf("off=%lu, tab[%d]=%lu\n", off, i, tab[i]); for(int j=0; j<nCol; j++) tab[i][j]=i + j; } return tab; }   int main() { int l=3, c=5; int **tab=initMatrix(l, c); for (int i=0; i < l; i++) { for (int j=0; j < c; j++) printf("%lu tab[%d][%d]=%d\n", &tab[i][j], i, j, tab[i][j]); } }

---

Et voici ce que ça donne (je supprime les grands chiffres des millions)

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

sizeof(int)=4 sizeof(int*)=8 sizeof(int**)=8 lig=3, col=5 alloc=84 tab=616880 off=18, tab[0]=617024 off=23, tab[1]=617064 off=28, tab[2]=617104 617024 tab[0][0]=0 617028 tab[0][1]=1 617032 tab[0][2]=2 617036 tab[0][3]=3 617040 tab[0][4]=4 617064 tab[1][0]=1 617068 tab[1][1]=2 617072 tab[1][2]=3 617076 tab[1][3]=4 617080 tab[1][4]=5 617104 tab[2][0]=2 617108 tab[2][1]=3 617112 tab[2][2]=4 617116 tab[2][3]=5 617120 tab[2][4]=6

---

Effectivement, avec tab qui commence à 616880 et qui alloue 84 octets, les adresses ne peuvent aller que de 616880 à 616964 et ne peuvent pas atteindre ces 617xxx. Pourtant les 84 octets c'est bon (15 int de 4 + 3 int* de 8). C'est donc le calcul qu'il faut revoir. Et déjà une chose est sûre, avec un off qui compte en octets, il faut se déplacer dans tab en octets donc le caster en char* chaque fois qu'on y fait des opérations dessus.

Mais si on rectifie le calcul (ie tab[i]=(int*)((char*)tab + off), alors au résultat

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

sizeof(int)=4 sizeof(int*)=8 sizeof(int**)=8 lig=3, col=5 alloc=84 tab=25808 off=18, tab[0]=25826 off=23, tab[1]=25831 off=28, tab[2]=25836 25826 tab[0][0]=1436508729 25830 tab[0][1]=0 25834 tab[0][2]=131584 25838 tab[0][3]=196608 25842 tab[0][4]=262144 25831 tab[1][0]=0 25835 tab[1][1]=514 25839 tab[1][2]=768 25843 tab[1][3]=1024 25847 tab[1][4]=1280 25836 tab[2][0]=2 25840 tab[2][1]=3 25844 tab[2][2]=4 25848 tab[2][3]=5 25852 tab[2][4]=6

---

Donc là les différents "tab[x]" ont les bonnes valeurs d'adresse, mais ça cafouille aux valeurs...