Discussion :

[Adiren]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[LittleWhite]

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.

[Adiren]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :


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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[Sve@r]

Bonjour

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 !!!

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[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.

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

[emixam16]

Bonjour,

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

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

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 c :

Sélectionner tout - Visualiser dans une fenêtre à part

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!

[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" ?

[Sve@r]

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...

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 c :

Sélectionner tout - Visualiser dans une fenêtre à part

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

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.

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".

[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 .

[Adiren]

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

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 ?

[emixam16]

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 .

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!

ç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!

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[Sve@r]

ç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).

[Adiren]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 !!

[emixam16]

Pour l'allocation, c'est bien!

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

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

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!

[Adiren]

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



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

[emixam16]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 c :

Sélectionner tout - Visualiser dans une fenêtre à part

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

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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!

[Adiren]

J'ai réussi en faisant cela :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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).

[Sve@r]

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 c :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[Winjerome]

Bonsoir,

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 size(int). Et pour cela il faut revenir à un int * :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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]).