précédent suivant haut Contents Index

LES TABLEAUX DYNAMIQUES


tableaux unidimensionnels en C

Les tableaux statiques nécessitent de maximiser lors de l'écriture du programme la dimension des tableaux. En cas de tableaux nombreux, il serait plus utile de ne réserver, pour chaque exécution, que la taille nécessaire à l'application en cours. En C, cette transformation est triviale grâce à la fonction malloc et à l'équivalence d'écriture entre les tableaux unidimensionnel et les pointeurs. Il suffira donc, pour utiliser les fonctions décrites pour les tableaux unidimensionnels statiques, de ne remplacer que la déclaration des tableaux :
#define composante float
typedef composante *type_tus; /* ou typedef composante type_tus[] */
reste identique, mais la déclaration composante tab[dim] sera remplacée par :
tab=(type_tus)malloc(taille*sizeof(composante));
à partir du moment où l'on a besoin du tableau, puis free(tab); quand il redevient inutile. Le problème des tableaux dynamiques en C est que l'on doit connaître la dimension d'un tableau avant sa première utilisation, ce qui empêchera par exemple une introduction de données du type "entrez vos données, tapez FIN pour terminer" mais nécessitera de demander en premier le nombre de données. L'autre problème provient du fait de la gestion de la mémoire inaccessible au programmeur : des créations et suppressions successives de tableaux vont créer une mémoire morcelée, et donc l'impossibilité de réserver un gros tableau, alors que la mémoire était disponible mais non continue. On est alors obligé de passer par la méthode du super-tableau pour pouvoir effectuer des retassages de mémoire.

la méthode du super-tableau

Dans les langages ne disposant pas de fonctions spécifiques à l'allocation dynamique de mémoire, on crée un grand tableau, appelé super-tableau, dimensionné au maximum de mémoire disponible. On crée ensuite les fonctions utilitaires nécessaires : réservation de mémoire (bloc) d'une taille donnée en argument (la fonction rend l'indice dans le super-tableau du début du sous-tableau alloué), libération d'un bloc préalablement alloué,... L'utilisation d'un bloc alloué est alors très simple : on remplace l'écriture bloc[i] par super_tableau[indice_debut_bloc+i]. Les parties du super-tableau utilisées n'ont pas absolument besoin d'une gestion poussée, mais on préfère en général prévoir un tableau annexe contenant les adresses et tailles des blocs actuellement réservés. Par contre il faut gérer les parties libres. Une solution est d'utiliser une pile (voir plus loin), mais la libération d'un bloc autre que le dernier soit nécessite un décalage des blocs suivants (attention, les indices de début de blocs sont modifiés), soit un marquage spécifique de cette zone (la place ne sera effectivement libérée que lorsque tous les blocs suivants seront libérés). Cette méthode est utilisable dans beaucoup de cas, il suffit de réserver en premier les blocs qui seront utilisés tout au long du programme, les blocs à durée de vie plus faible par la suite. L'autre solution consiste à gérer les blocs libres sous forme d'une liste chaînée (voir plus loin), chaque bloc libéré contenant l'indication de sa taille et l'adresse du bloc libre suivant (la place utilisée par ces informations est "masquée" puisque n'utilisant que des zones libres). L'allocation d'un bloc consiste alors en la recherche du premier bloc libre de taille suffisante. Un retassage (et donc modification des indices de débuts de blocs) n'est nécessaire qu'en cas de mémoire trop morcelée.

Cette méthode du super-tableau permet de manière très simple d'accéder à toutes les possibilités des pointeurs, dans tout langage. C'est la raison pour laquelle des programmes très efficaces continuent à être développés dans ces langages (pratiquement tous les gros programmes scientifiques (C.A.O., éléments finis,...) de plusieurs centaines de milliers de lignes sont écrits en FORTRAN, et utilisent cette méthode). De plus la gestion par le programmeur de l'allocation de mémoire peut permettre d'être plus efficace que la gestion par le compilateur, puisque pouvant être spécifique au problème traité.

les tableaux multidimensionnels

Il n'y a pas en C d'équivalence d'écriture permettant une utilisation directe de l'allocation dynamique pour les tableaux multidimensionnels. On utilise donc la même méthode pour l'allocation dynamique en C (la mémoire est en fait un tableau unidimensionnel d'octets) qu'avec un super-tableau. Nous n'allons traiter que les tableaux à deux dimensions, l'extension à N dimensions ne posant aucun problème.

matrices pleines (matrices rectangulaires dynamiques : mrd)

Pour allouer dynamiquement une matrice de taille (nbl,nbc), on réserve un tableau unidimensionnel de taille nbl*nbc :
typedef composante * mat_dyn;
mat_dyn alloc_mrd(int nbl;int nbc)
 {return((mat_dyn)malloc(nbl*nbc*sizeof(composante)));}
On accède à l'élément en ligne l et colonne c par m[l*nbc+c] (pour l et c commençant à 0, comme en C). On peut prévoir une fonction (ou même une macro, plus rapide) pour effectuer ce calcul :
#define adr_mrd(l,c,nbc) ((l)*(nbc)+(c))
Les algorithmes pour les matrices statiques doivent être réécrits, en remplaçant chaque mat[l][c] par mat[adr_mrd(l,c,nbc)]. Souvent, on choisira un nom plus court pour adr_mrd. Dans les cas simples uniquement, on peut choisir nbc comme variable globale pour éviter sa transmission en argument (par exemple si l'on utilise des matrices carrées toutes de même taille), mais ce n'est pas conseillé (dans le cas d'une macro, ce ne sont pas de vrais passages d'arguments et donc ne prend pas de temps supplémentaire).

Exercice (gauss_mrd) : écrire une version de la méthode de Gauss pour des matrices dynamiques. La solution donnée en annexe 2 (du document papier) est un exemple de matrices dynamiques.

tableaux de tableaux dynamiques

Dans le cas de matrices non pleines, la gestion sera plus complexe mais le résultat très efficace. On gère en fait un ensemble de lignes de longueur différente (donc des tableaux dynamiques). Dans quelques cas, la longueur et la position de chaque ligne se trouve par calcul : matrices triangulées, matrices bandes (réorganisées pour que tous les éléments non nuls soient au maximum à la distance B (largeur de bande) de la diagonale),... Un utilise alors la même méthode que pour les matrices pleines, en changeant simplement le calcul pour accéder à une composante (adr_mrd). Dans tous les autres cas, chaque ligne est allouée dynamiquement, l'adresse et la longueur de chaque ligne étant stockée dans un tableau statique ou dynamique, voire liste chaînée... La longueur peut être omise si la ligne est terminée par un signe particulier (chaînes de caractères en particulier). Les manipulations deviennent alors plus efficaces : les manipulations de composantes (dans les lignes) restent des manipulations de type tableaux, donc efficaces tant que les lignes ne sont pas de taille exagérée, alors que les manipulations de lignes (plus volumineuses) se font par manipulation d'adresses (par exemple pour échanger deux lignes, il suffit d'échanger les deux adresses de lignes, les lignes elles-mêmes n'étant physiquement pas déplacées). Ce type de données est certainement le plus efficace pour du traitement de textes. Mais il permet aussi de traiter les matrices en "ligne de ciel:" dans le cas (fréquent en mécanique) de matrices symétriques contenant beaucoup de 0, on peut avoir du mal à réorganiser la matrice efficacement pour qu'elle soit sous forme de bande, par contre il est plus facile de la réorganiser pour qu'un maximum de lignes soient regroupées près de la diagonale, quelques lignes restant à grande largeur. On stocke alors uniquement, pour chaque ligne, les éléments de la diagonale au dernier non nul. Ce type de stockage est également appelé quelquefois "à largeur de bande variable".

Ces tableaux de tableaux dynamiques permettent toujours un accès presque direct à un élément l,c : tab[adresse_ligne[l]][c]. Mais ils gardent les problèmes des tableaux dynamiques, en particulier de ne pas être totalement dynamiques puisqu'une fois une ligne créée, on ne peut pas directement l'agrandir (en fait il suffit de réserver une nouvelle ligne plus grande, y recopier la précédente, changer l'adresse de la ligne dans le tableau d'adresses de lignes puis supprimer l'ancienne ligne). Souvent dans ce cas on préfère directement créer un ligne un peu plus longue que nécessaire, pour ne pas répéter l'opération trop souvent.

Exercice (inse_ttd) : écrire un programme pour trier des lignes de texte, utilisant les tableaux de tableaux dynamiques. On choisira un tri par insertion, puisque les échanges de lignes ne sont que des échanges d'adresses, le texte en lui-même ne sera jamais déplacé.

conclusions

Les tableaux dynamiques ne sont pas totalement dynamiques, c'est à dire que leur taille, bien que définie en cours d'exécution du programme, ne peut pas facilement être modifiée (c'est néanmoins presque toujours possible mais relativement coûteux en temps et mémoire). Mais ils gardent la principale qualité des tableaux statiques : l'accès immédiat à une composante dont on connaît la position. Ils en gardent également la faible efficacité en cas d'insertions et suppressions. Les tableaux dynamiques sont néanmoins la solution minimisant la place occupée en mémoire pour de gros ensembles de données : Seule la place nécessaire est réservée (excepté une mémoire pour l'adresse du début du tableau), aucune mémoire n'est utilisée pour indiquer où se trouve la composante suivante, puisqu'elle est placée directement après la précédente (contrairement aux listes par exemple).


précédent suivant haut Contents Index