LES TABLEAUX DYNAMIQUES
Les
tableaux statiques necessitent de maximiser lors de l'ecriture du
programme la dimension des tableaux. En cas de tableaux nombreux, il serait
plus utile de ne reserver, pour chaque execution, que la taille
necessaire a l'application en cours. En C, cette transformation
est triviale grace a la fonction malloc et a
l'equivalence d'ecriture entre les tableaux unidimensionnel et
les pointeurs. Il suffira donc, pour utiliser les fonctions decrites
pour les tableaux unidimensionnels statiques, de ne remplacer que la
declaration des tableaux :#define composante float
typedef composante *type_tus; /* ou typedef composante type_tus[] */
reste identique, mais la declaration composante
tab[dim] sera remplacee par :tab=(type_tus)malloc(taille*sizeof(composante));
a partir du moment ou l'on a besoin du tableau, puis
free(tab); quand il redevient inutile. Le probleme des tableaux
dynamiques en C est que l'on doit connaitre la dimension d'un tableau
avant sa premiere utilisation, ce qui empechera par exemple une
introduction de donnees du type "entrez vos donnees, tapez FIN
pour terminer" mais necessitera de demander en premier le nombre de
donnees. L'autre probleme provient du fait de la gestion de la
memoire inaccessible au programmeur : des creations et
suppressions successives de tableaux vont creer une memoire
morcelee, et donc l'impossibilite de reserver un gros
tableau, alors que la memoire etait disponible mais non continue.
On est alors oblige de passer par la methode du super-tableau
pour pouvoir effectuer des retassages de memoire.
Dans les langages ne disposant pas de fonctions specifiques
a l'allocation dynamique
de memoire, on cree un grand tableau, appele super-tableau,
dimensionne
au maximum de memoire disponible. On cree ensuite les fonctions
utilitaires necessaires : reservation de memoire (bloc)
d'une taille donnee en argument (la fonction rend l'indice dans le
super-tableau du debut du sous-tableau alloue), liberation
d'un bloc prealablement alloue,... L'utilisation d'un bloc
alloue est alors tres simple : on remplace l'ecriture
bloc[i] par super_tableau[indice_debut_bloc+i]. Les parties
du super-tableau utilisees n'ont pas absolument besoin d'une gestion
poussee, mais on prefere en general
prevoir un tableau annexe contenant les adresses et tailles des blocs
actuellement reserves. Par contre il faut gerer les
parties libres. Une solution est d'utiliser une pile
(voir plus loin), mais la liberation d'un bloc autre que le dernier soit
necessite un decalage
des blocs suivants (attention, les indices de debut de blocs sont
modifies), soit un marquage specifique de cette zone (la place ne
sera effectivement liberee que lorsque tous les blocs suivants
seront liberes). Cette methode est utilisable dans
beaucoup de cas, il suffit de reserver en premier les blocs qui seront
utilises tout au long du programme, les blocs a duree de
vie plus faible par la suite. L'autre solution consiste a gerer
les blocs libres sous forme d'une liste chainee (voir plus loin),
chaque bloc libere contenant l'indication de sa taille et
l'adresse du bloc libre suivant (la place utilisee par ces informations
est "masquee" 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 debuts de blocs) n'est
necessaire qu'en cas de memoire trop morcelee.
Cette methode du super-tableau permet de maniere tres
simple d'acceder a toutes les possibilites des pointeurs,
dans tout langage. C'est la raison pour laquelle des programmes tres
efficaces continuent a etre developpes dans ces
langages (pratiquement tous les gros programmes scientifiques (C.A.O.,
elements finis,...) de plusieurs centaines de milliers de lignes
sont ecrits en FORTRAN, et utilisent cette methode). De plus la
gestion par le programmeur de l'allocation de memoire peut permettre
d'etre plus efficace que la gestion par le compilateur, puisque pouvant
etre specifique au probleme traite.
Il n'y a pas en C d'equivalence d'ecriture permettant une
utilisation directe de l'allocation dynamique pour les tableaux
multidimensionnels.
On utilise donc la meme methode pour l'allocation dynamique en C
(la memoire est en fait un tableau unidimensionnel d'octets) qu'avec un
super-tableau. Nous n'allons traiter que les tableaux a deux dimensions,
l'extension a N dimensions ne posant aucun probleme.
Pour allouer dynamiquement une matrice
de taille (nbl,nbc), on reserve 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 accede a l'element en ligne l et
colonne c par m[l*nbc+c] (pour l et c commencant a 0, comme en
C). On peut prevoir une fonction (ou meme une macro, plus rapide)
pour effectuer ce calcul :#define adr_mrd(l,c,nbc) ((l)*(nbc)+(c))
Les algorithmes pour les matrices statiques doivent etre
reecrits, en remplacant 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 eviter sa transmission en argument (par exemple si l'on utilise des
matrices carrees toutes de meme taille), mais ce n'est pas
conseille (dans le cas d'une macro, ce ne sont pas de vrais passages
d'arguments et donc ne prend pas de temps supplementaire).
Exercice (gauss_mrd) : ecrire une version de la methode de
Gauss
pour des matrices dynamiques. La solution donnee 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 resultat tres efficace. On gere en fait un ensemble de
lignes de longueur differente (donc des tableaux dynamiques). Dans
quelques cas, la longueur et la position de chaque ligne se trouve par calcul :
matrices triangulees, matrices bandes
(reorganisees pour que tous les elements non nuls
soient au maximum a la distance B (largeur de bande)
de la diagonale),... Un utilise alors la meme methode que pour les
matrices pleines, en changeant simplement le calcul pour acceder
a une composante (adr_mrd). Dans tous les autres cas, chaque ligne est
allouee dynamiquement, l'adresse et la longueur de chaque ligne
etant stockee dans un tableau statique ou dynamique, voire liste
chainee... La longueur peut etre omise si la ligne est
terminee par un signe particulier (chaines de caracteres 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
exageree, alors que les manipulations de lignes (plus
volumineuses) se font par manipulation d'adresses (par exemple pour
echanger deux lignes, il suffit d'echanger les deux adresses de
lignes, les lignes elles-memes n'etant physiquement pas
deplacees). Ce type de donnees 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 (frequent en mecanique) de matrices
symetriques contenant beaucoup de 0, on peut avoir du mal a
reorganiser la matrice efficacement pour qu'elle soit sous forme de
bande, par contre il est plus facile de la reorganiser pour qu'un
maximum de lignes soient regroupees pres de la diagonale,
quelques lignes restant a grande largeur. On stocke alors uniquement,
pour chaque ligne, les elements de la diagonale au dernier non
nul. Ce type de stockage est egalement appele quelquefois
"a largeur de bande variable".
Ces tableaux de tableaux dynamiques permettent toujours un acces presque
direct a un element l,c : tab[adresse_ligne[l]][c]. Mais
ils gardent les problemes des tableaux dynamiques, en particulier de ne
pas etre totalement dynamiques puisqu'une fois une ligne
creee, on ne peut pas directement l'agrandir (en fait il suffit
de reserver une nouvelle ligne plus grande, y recopier la
precedente, changer l'adresse de la ligne dans le tableau
d'adresses de lignes puis supprimer l'ancienne ligne). Souvent dans ce cas on
prefere directement creer un ligne un peu plus longue que
necessaire, pour ne pas repeter l'operation trop
souvent.
Exercice (inse_ttd) : ecrire un programme pour trier des lignes
de texte, utilisant les tableaux de tableaux dynamiques. On choisira un tri par
insertion, puisque les echanges de lignes ne sont que des
echanges d'adresses, le texte en lui-meme ne sera jamais
deplace.
Les tableaux dynamiques ne sont pas totalement dynamiques, c'est
a dire que leur taille, bien que definie en cours
d'execution du programme, ne peut pas facilement etre
modifiee (c'est neanmoins presque toujours possible mais
relativement couteux en temps et memoire). Mais ils gardent la
principale qualite des tableaux statiques : l'acces
immediat a une composante dont on connait la position. Ils
en gardent egalement la faible efficacite en cas d'insertions et
suppressions. Les tableaux dynamiques sont neanmoins la solution
minimisant la place occupee en memoire pour de gros ensembles de
donnees : Seule la place necessaire est reservee
(excepte une memoire pour l'adresse du debut du tableau),
aucune memoire n'est utilisee pour indiquer ou se trouve
la composante suivante, puisqu'elle est placee directement apres
la precedente (contrairement aux listes par exemple).