Comment atsortingbuer un tableau 2D à l’aide d’une instruction malloc

On m’a demandé lors d’une entrevue comment allouer un tableau à deux dimensions. Voici ma solution.

#include  int **array; array = malloc(nrows * sizeof(int *)); for(i = 0; i < nrows; i++) { array[i] = malloc(ncolumns * sizeof(int)); if(array[i] == NULL) { fprintf(stderr, "out of memory\n"); exit or return } } 

Je pensais avoir fait du bon travail, mais ensuite il m’a demandé de le faire en utilisant une instruction malloc() et non deux. Je ne sais pas comment y arriver.

Quelqu’un peut-il me suggérer une idée de le faire dans un seul malloc() ?

Il vous suffit de calculer la quantité totale de mémoire nécessaire pour les deux nrows lignes et les données réelles de nrows , de l’additionner et de faire un seul appel:

 int **array = malloc(nrows * sizeof *array + (nrows * (ncolumns * sizeof **array)); 

Si vous pensez que cela semble trop complexe, vous pouvez le scinder et le rendre un peu auto-documenté en nommant les différents termes de l’expression de taille:

 int **array; /* Declare this first so we can use it with sizeof. */ const size_t row_pointers_bytes = nrows * sizeof *array; const size_t row_elements_bytes = ncolumns * sizeof **array; array = malloc(row_pointers_bytes + nrows * row_elements_bytes); 

Vous devez ensuite parcourir et initialiser les pointeurs de ligne pour que le pointeur de chaque ligne pointe vers le premier élément de cette ligne particulière:

 size_t i; int * const data = array + nrows; for(i = 0; i < nrows; i++) array[i] = data + i * ncolumns; 

Notez que la structure résultante est légèrement différente de ce que vous obtenez si vous le faites, par exemple, int array[nrows][ncolumns] , car nous avons des pointeurs de ligne explicites, ce qui signifie que pour un tableau alloué comme ceci, il n’est pas nécessaire que toutes les lignes aient le même nombre de colonnes.

Cela signifie également qu'un access comme array[2][3] fait quelque chose de différent d'un access similaire dans un tableau 2D réel. Dans ce cas, l'access le plus à l'intérieur se produit en premier et array[2] lit un pointeur à partir du 3ème élément de array . Ce pointeur est alors traité comme la base d'un tableau (colonne), dans lequel nous indexons pour obtenir le quasortingème élément.

En revanche, pour quelque chose comme

 int array2[4][3]; 

qui est un tableau 2D proprement dit "emballé" ne prenant que 12 entiers, un access comme array[3][2] consiste simplement à append un décalage à l'adresse de base pour accéder à l'élément.

 int **array = malloc (nrows * sizeof(int *) + (nrows * (ncolumns * sizeof(int))); 

Cela fonctionne parce qu’en C, les tableaux ne sont que tous les éléments les uns après les autres sous forme de tas d’octets. Il n’y a pas de métadonnées ou quoi que ce soit. malloc () ne sait pas s’il est alloué pour être utilisé comme caractères, entiers ou lignes dans un tableau.

Ensuite, vous devez initialiser:

 int *offs = &array[nrows]; /* same as int *offs = array + nrows; */ for (i = 0; i < nrows; i++, offs += ncolumns) { array[i] = offs; } 

Voici une autre approche.

Si vous connaissez le nombre de colonnes au moment de la compilation, vous pouvez faire quelque chose comme ceci:

 #define COLS ... // integer value > 0 ... size_t rows; int (*arr)[COLS]; ... // get number of rows arr = malloc(sizeof *arr * rows); if (arr) { size_t i, j; for (i = 0; i < rows; i++) for (j = 0; j < COLS; j++) arr[i][j] = ...; } 

Si vous travaillez dans C99, vous pouvez utiliser un pointeur sur un VLA:

 size_t rows, cols; ... // get rows and cols int (*arr)[cols] = malloc(sizeof *arr * rows); if (arr) { size_t i, j; for (i = 0; i < rows; i++) for (j = 0; j < cols; j++) arr[i][j] = ...; } 

Vous devriez pouvoir faire cela avec (un peu moche avec tout le casting cependant):

 int** array; size_t pitch, ptrs, i; char* base; pitch = rows * sizeof(int); ptrs = sizeof(int*) * rows; array = (int**)malloc((columns * pitch) + ptrs); base = (char*)array + ptrs; for(i = 0; i < rows; i++) { array[i] = (int*)(base + (pitch * i)); } 

Je ne suis pas un fan de ce “tableau de pointeurs vers tableau” pour résoudre le paradigme de tableau à plusieurs dimensions. Toujours privilégié un tableau de dimension unique, lors de l’access à l’élément avec array [row * cols + col]? Aucun problème pour tout encapsuler dans une classe et implémenter une méthode ‘at’.

Si vous insistez pour accéder aux membres du tableau avec cette notation: Masortingx [i] [j], vous pouvez faire un peu de magie C ++. La solution de John essaie de le faire de cette façon, mais il a besoin que le nombre de colonnes soit connu au moment de la compilation. Avec certains C ++ et en surchargeant l’opérateur [], vous pouvez obtenir ceci complètement:

 class Row { private: int* _p; public: Row( int* p ) { _p = p; } int& operator[](int col) { return _p[col]; } }; class Masortingx { private: int* _p; int _cols; public: Masortingx( int rows, int cols ) { _cols=cols; _p = (int*)malloc(rows*cols ); } Row operator[](int row) { return _p + row*_cols; } }; 

Alors maintenant, vous pouvez utiliser l’object Masortingx, par exemple pour créer une table de multiplication:

 Masortingx mtrx(rows, cols); for( i=0; i 

Vous devriez maintenant que l'optimiseur fait ce qu'il faut et qu'il n'y a pas de fonction d'appel ni aucun autre type de surcharge. Aucun constructeur n'est appelé. Tant que vous ne déplacez pas la masortingce entre les fonctions, même la variable _cols n'est pas créée. L'instruction mtrx [i] [j] fait essentiellement mtrx [i * cols + j].

Comment allouer un tableau 2D à l’aide d’une instruction malloc (?)

Aucune réponse, jusqu’à présent, allouez de la mémoire pour un véritable tableau 2D.

int **array est un pointeur sur lequel pointer vers int . array n’est pas un pointeur sur un tableau 2D.

int a[2][3] est un exemple de tableau 2D réel ou de tableau 2 du tableau 3 d’int


Pour allouer de la mémoire à un vrai tableau 2D, avec C99, utilisez malloc() et enregistrez-le dans un pointeur sur un tableau de longueur variable (VLA)

 // Simply allocate and initialize in one line of code int (*c)[nrows][ncolumns] = malloc(sizeof *c); if (c == NULL) { fprintf(stderr, "out of memory\n"); return; } // Use c (*c)[1][2] = rand(); ... free(c); 

Sans la prise en charge de VLA, si les dimensions sont des constantes, le code peut utiliser

 #define NROW 4 #define NCOL 5 int (*d)[NROW][NCOL] = malloc(sizeof *d); 

Vous pouvez allouer (row*column) * sizeof(int) octets de mémoire en utilisant malloc. Voici un extrait de code à démontrer.

 int row = 3, col = 4; int *arr = (int *)malloc(row * col * sizeof(int)); int i, j, count = 0; for (i = 0; i < r; i++) for (j = 0; j < c; j++) *(arr + i*col + j) = ++count; //row major memory layout for (i = 0; i < r; i++) for (j = 0; j < c; j++) printf("%d ", *(arr + i*col + j));