Tableaux
Tableaux de variables
Le tableau de variables, c'est sans doute la première chose que l'on apprend quand on découvre la programmation. C'est le bête tableau. Si on a un type entier, on crée un tableau de 10 éléments en faisant :
| C | Pascal |
|---|---|
int tableau[10]; |
Var tableau:Array[0..9] Of Integer; |
En mémoire, tableau se présente comme ceci :
On accède à un élément par la syntaxe bien connue :
| C | Pascal |
|---|---|
int element = tableau[5]; |
Var element:Integer;
element := tableau[5]; |
Rigolons un peu et essayons de voir ce que donne le code suivant :
| C | Pascal |
|---|---|
int* pntr &tableau[1]; |
Type pntr:Pointer;
pntr:=@tableau[1]; |
Sur un dessin, ça va donner :
On peut également voir que, numériquement, l'adresse du premier élément d'un tableau, ou bien l'adresse dun tableau, c'est la même chose. En pratique, en C, un tableau est toujours représenté par l'adresse du premier élément, mais ça c'est un détail propre au C : en C, les tableaux n'existent en réalité pas (il n'existe pas de type array) [2] .
Tableaux de pointeurs
Le défaut du tableau de variables, c'est qu'il doit être continu en mémoire. Alors pour un petit tableau d'entiers,, ça n'est pas un problème, mais ça devient rapidement pénible avec des tableaux plus grands, ou avec des types plus gros. C'est ainsi qu'en général, on préfère utiliser des tableaux de pointeurs, ce qui revient à peu près au même. Sur un schémas, ça se traduit par :
J'ai volontairement mis les éléments dans le désordre pour bien montrer qu'à présent, les éléments peuvent se trouver n'importe où dans la mémoire. Le tableau en lui-même doit toujours être continu, bien sûr, mais en général un pointeur, c'est moins gros qu'un autre type.
Le code correspondant à ce tableau sera :
| C | Pascal |
|---|---|
LeType** tableauDeType[10]; |
Var tableauDeType:Array[0..9] Of ^LeType; |
Pour accéder à un élément, on fera :
| C | Pascal |
|---|---|
*(tableauDeType[5]) = LaValeur; |
tableauDeType[5]^ := LaValeur; |
Buffers circulaires
Le système du buffer circulaire s'applique aux tableaux de variables ou aux tableaux de pointeurs, mais j'utiliserai le second exemple pour illustrer le bidule.
En général, le problème posé est le suivant : on veut avoir un « truc » dans lequel on veut rajouter des éléments à la fin, et les retirer par le début. Une file d'attente fonctionne comme ça.
Imaginons que nous voulions résoudre le problème avec un tableau. Une approche normale serait de dire : « ben je rajoute les éléments au bout du tableau, et quand on me demande d'en retirer un, je me contente de retirer l'élément 0 en décalant tous les autres éléments vers le bas ». Il faut donc avoir quelque part un compteur qui indique le dernier élément, et donc indirectement le nombre d'éléments qui se trouve dans la structure. Il faudra toujours veiller à ce qu'on ne « déborde » pas du tableau, qui a en général une taille fixe.
Donc sur un dessin ça donne, si on imagine qu'il y a trois éléments dans notre file d'attente :
La variable (le rectangle) qui contient un 3, c'est la variable qui « retient » le nombre d'éléments qui se trouvent dans la structure. Rajouter un élément à la fin est facile, il suffit de mettre la valeur du pointeur du quatrième élément du tableau vers le nouvel élément à rajouter. Retirer un élément est assez simple aussi : il faut tout déplacer vers la gauche :
Le défaut de cette méthode est clair : si il y a 4000 éléments dans ce tableau, il va falloir se taper la copie de 4000 valeurs de pointeurs... Plutôt inefficace, surtout quand on sait qu'il existe un meilleur système.
Au lieu de se dire « le premier élément, c'est celui qui se trouve à l'indice 0 », on se disait « je retiens quel indice correspond au premier élément ». Hop, je rajoute une variable qui est cet indice. Dans l'exemple, le premier élément est l'élément 0 :
C'est quand même plus rapide d'incrémenter une valeur que de faire toute la copie d'un tableau, élément par élément... Si je veux rajouter un nouvel élément, je modifierai le pointeur de l'élément 3 (le quatrième, donc), comme si je n'avais en réalité rien supprimé (ce qui est le cas, finalement). Le problème qui arrive c'est : si j'ai dix places libres dans mon tableaux, et que je rajoute puis supprime dix fois de suite un élément, à la fin il ne reste plus de place dans le tableau, même si aucun élément ne s'y trouve, car le « premier élément » vaudra 10.
Le problème, en réalité, c'est que je gaspille ma place : ici dans l'exemple, la première case du tableau devient inutilisable après la première suppression. Comment faire pour la récupérer ? On pourrait évidemment penser à décaler tous les éléments d'un cran vers la gauche pour « boucher le trou », mais ça revient à la méthode lente vue en premier, il faut donc trouver autre chose.
L'astuce revient à ceci : considérer la case 0 du tableau comme étant une case 10 virtuelle. Mettons-nous dans la situation suivante :
Le premier élément se trouve donc à l'indice 7, et il y a 3 éléments. Si je veux rajouter un quatrième élément, je vais le mettre où ? Eh bien à l'indice 0, pardis ! Je considère tout « modulo 10 » : 0 peut se lire 0, 10, 20, etc... Si on me dit « ça commence à l'élément 17, et il y a 3 éléments », ça revient au même que de me dire « ça commence à l'élément 7, et il y a 3 éléments », ou 27, 37, ...
Donc si je rajoute un élément 3, ça va donner :
Un élément 4 irait se mettre à l'indice 1, etc... remarquez que 1=(4+7) modulo 10, c'est la formule pour trouver l'indice du nouvel élément : (premier+longueur) modulo 10. En fait, c'est la généralisation du premier système, où premier valait toujours 0. Il faut évidement s'assurer qu'on ne met pas plus de 10 élément dans le tableau, sinon on irait écraser les premiers éléments...
Si on vous demande le k-ème élément, au lieu du premier, il vous sera également très facile de répondre : c'est l'élément qui se trouve à l'indice (premier+i) modulo 10, avec i allant de 0 à 9 (0 pour le premier, 1 pour le second, etc...).