LES TABLEAUX DYNAMIQUES
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.
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é.
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.
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.
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é.
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).