Allocation dynamique d'une matrice inconnue en C

Ma recommandation est de considérer votre matrice comme ayant un type de données abstrait que vous souhaitez implémenter.

Une méthode courante consiste à utiliser un tableau de pointeurs (des tableaux représentant les lignes de votre matrice). Mais je pense que c'est déroutant et inefficace.

Alors, quelles sont les opérations que vous voulez sur vos matrices?

• créer une matrice de dimensions données

• détruire une matrice créée précédemment

• accéder à un élément d'une matrice donnée avec des index de lignes et de colonnes donnés

• changer la valeur d'un élément dans une matrice donnée avec des index de lignes et de colonnes donnés

• etc....

BTW, vous pouvez en avoir plusieurs variantes. Par exemple, vous pouvez vérifier les erreurs (par exemple, rejeter un index négatif) ou disposer de fonctions dangereuses (mais légèrement plus rapides) capables d' un comportement indéfini (ce qui est très scary ). Bien sûr, vous pouvez définir plus d'opérations (en utilisant d'autres), par exemple la multiplication de matrice, etc.

^{Vous devez répertorier - sur papier ou sur tableau - toutes les opérations souhaitées sur vos matrices et les expliquer dans votre documentation (ou vos commentaires). En pratique, vous pouvez effectuer plusieurs dizaines, voire des centaines d'opérations sur votre type de données abstrait. Documentez également ce qui se passe dans les cas d'erreur.}

Je recommande généralement de conserver les dimensions avec la matrice (sauf si vous savez qu'une partie de la dimension est une constante). Un moyen courant d'implémenter des types de données abstraits en C consiste à les encapsuler dans une struct et à utiliser des pointeurs sur celles-ci.

Je suggère donc d'utiliser un membre de tableau flexible (en tant que dernier élément de votre struct ). Voici ma structure matrix_st :

  struct matrix_st {
    unsigned m_h, m_w; // height and width of matrix
    double m_v[]; // values inside the matrixes, there are m_h*m_w of them
  };

donc mon type de données abstrait est juste des pointeurs vers

  typedef struct matrix_st Matrix;

Voici les déclarations des fonctions implémentant mon type de données abstrait:

  Matrix* matrix_create(unsigned height, unsigned width);
  void matrix_destroy(Matrix*mat);
  double matrix_access(Matrix*mat, unsigned i, unsigned j);
  void matrix_change_element(Matrix*mat, unsigned i, unsigned j,double v);

Voici quelques implémentations (puisque je ne veux pas traiter de matrices pathologiquement énormes, je définis une dimension maximale; les ressources informatiques sont toujours finies!):

  #define MATRIX_MAXDIM 10000000 /* ten millions */
  Matrix* matrix_create(unsigned height, unsigned width) {
     if (height>MATRIX_MAXDIM || width>MATRIX_MAXDIM) {
        fprintf(stderr, "too huge matrix height=%u width=%u\n",
                height, width);
        exit(EXIT_FAILURE);
     };
     Matrix* res = 
        calloc(1, sizeof(Matrix) + height*width*sizeof(double));
     if (!res) {
         perror("matrix calloc");
         exit(EXIT_FAILURE);
     };
     res->m_h = height;
     res->m_w = width;
     return res; 
  } // end matrix_create

J'utilise calloc pas malloc parce que je veux vraiment de la mémoire zéro-ed. Donc, la matrice retournée contient tous les zéros. BTW sur certains ordinateurs (pas le mien, un bureau PC / Linux / Debian / x86-64), la height*width*sizeof(double) pourrait déborder.

Voici la fonction pour accéder à certains éléments. Il vérifie quelques erreurs.

double matrix_access(Matrix*mat, unsigned i, unsigned j) 
{ 
   if (!mat) 
      { fprintf(stderr, "no matrix to access\n"); exit(EXIT_FAILURE; };
   unsigned h = mat->m_h;
   unsigned w = mat->m_w;
   if (i >= h || j >= w)
      { fprintf(stderr, "out-of-bound matrix access\n"); 
        exit(EXIT_FAILURE); };
   return mat->m_v [i*h + j];
}

Comme je n’ai fait qu’un seul calloc la destruction est simple à coder:

  void matrix_destroy(Matrix*mat) {
    if (!mat) { fprintf(stderr, "no matrix to destroy\n"); exit(EXIT_FAILURE); };
    assert (mat->m_h < MATRIX_MAXDIM);
    assert (mat->m_w < MATRIX_MAXDIM);
    free (mat);
  }

Les déclarations d'affirmation sont en principe inutiles (elles vérifient quelque chose qui devrait toujours être vrai). Mais j’adore la programmation défensive (cela m’aiderait à détecter des bugs dans d’ autres endroits qui abusent de ma Matrix ). Ils pourraient être désactivés (lire assert(3) ) au moment de la compilation.

En passant, vous pouvez déclarer ces fonctions en inline ou en static inline (et les définir dans un fichier d’en-tête inclus). Un compilateur optimiseur est susceptible de produire un code efficace (par exemple, compiler with gcc -O2 -Wall -march=native lors d’une analyse comparative).

Puisque vous lisez une matrice à partir d’un fichier, vous devez définir votre format de fichier (utiliser dans votre documentation une notation EBNF pour décrire la syntaxe de ce fichier est utile) et vous pouvez définir et implémenter une fonction lisant et créant une matrice à partir de. une poignée de fichier ouverte.

Le codage des autres fonctions est laissé comme exercice au lecteur.

N'oubliez pas de compiler with tous les avertissements et informations de débogage, donc gcc -Wall -Wextra -g avec GCC . Utilisez le débogueur gdb (et aussi valgrind pour chasser les fuites de mémoire ). Lisez la documentation de chaque fonction utilisée (par exemple, votre code ne vérifie pas le nombre de retours de scanf mais il devrait le faire). Exécutez plusieurs cas de test . Essayez de vous convaincre que votre code est bon (en en prouvant des parties). Peut-être utiliser un analyseur de code source statique (par exemple, Frama-C , qui souhaite des annotations supplémentaires dans ACSL ). Si vous devez benchmark votre programme, activez les optimisations au moment de la compilation (par exemple, en passant -O2 -march=native à gcc ....).

Dans un commentaire de code, vous demandez:

 // I need to now dynamically allocate the input files

Vous n'allouez pas de files entrée (le système d'exploitation les gère), vous allouez une zone de mémoire . Lisez à propos de l'allocation de mémoire dynamique en C. Notez que l'allocation de mémoire peut échouer (par exemple, comme malloc(3) dans malloc(3) ), car votre espace d'adressage virtuel ne peut pas croître indéfiniment.

En passant, la pile d’appels est limitée (typiquement à un mégaoctet ou à quelques-uns d’entre eux sur des ordinateurs de bureau), vous voulez donc généralement éviter les grandes variables automatiques . C’est une autre bonne raison d’éviter de placer des matrices dans votre cadre d’appel et de préférer les allocation de mémoire pour eux.