Les tableaux et structures

a. Simplifier les variables

Jusqu’à présent, les types de données que vous avez rencontrés sont des scalaires, sauf pour les chaînes de caractères. Pour rappel un scalaire est un type de donnée qui ne représente qu’une seule variable à la fois : la variable ne représente qu’une seule et unique donnée. Un entier, un caractère, un réel, un booléen, etc., sont des scalaires. Une chaîne de caractères n’est pas un scalaire : il s’agit d’une suite, ou liste, de caractères, les uns après les autres. Une chaîne est donc une liste ordonnée par vos soins de scalaires. Les langages proposent souvent un type spécifique aux chaînes de caractères, mais c’est une facilité offerte par ceux-ci. Un langage comme le C n’en propose pas : le langage ne fait que réserver de la mémoire qui accueillera chaque caractère un à un et rien n’empêche d’y mettre autre chose. En algorithmique, vous utilisez le type alphanumérique, il vous faudra alors faire attention lors de la conversion en C. Bien heureusement, C# propose un type de ce genre, même si, comme souvent, derrière les apparences se cache une bien trompeuse réalité…

Mais alors comment se représenter une chaîne de caractères avec un type scalaire ? Il faut pour cela se rappeler comment sont placées les informations en mémoire. La mémoire de l’ordinateur est composée de cases pouvant contenir certaines informations. Ces cases sont numérotées (on parle d’adresse de la case, ou d’adresse mémoire tout simplement) et contiennent des données. Ces données représentent ce que vous voulez selon le contexte de leur utilisation. Vous pouvez par exemple partir du principe qu’elles contiennent des scalaires. Si une case mémoire contient le nombre 65, ce peut être la valeur entière 65 ou encore le code ASCII du caractère "A". Une case mémoire peut parfaitement contenir l’adresse d’une autre case mémoire : c’est un peu plus compliqué que ça en a l’air, et ce sera l’objet...

a. Principe

Vous avez pu voir dans les exemples précédents l’intérêt des tableaux pour le stockage de valeurs multiples. Mais suivant le cas, il peut être utile d’avoir besoin d’obtenir une liste ordonnée de valeurs par ordre croissant ou décroissant. Autrement dit vous voulez trier le contenu du tableau. Prenez le cas d’un professeur souhaitant trier les notes de ses élèves de la plus basse à la plus haute, ou des résultats d’un tirage du loto pour le rendre plus lisible.

Imaginez un tirage du loto de cinq numéros, évidemment tous différents, dont les valeurs s’étalent entre 1 et 49. Voici l’état initial du tableau suite au tirage au sort :

Il existe plusieurs méthodes permettant de trier ces différentes valeurs. Elles ont toutes leurs qualités et leurs défauts. Ainsi une méthode sera lente, l’autre sera plus gourmande en mémoire, et ainsi de suite. C’est leur complexité qui détermine leur usage notamment pour de grandes plages de valeurs.

Dans les algorithmes suivants, la variable Cpt contient le nombre d’éléments du tableau initial et t[] est le tableau.

Il est intéressant de prendre en compte la complexité de ces divers algorithmes, bien que cette notion présentée au premier chapitre, ne soit généralement pas (ou peu) abordée dans les premières années d’études en informatique. Les algorithmes ont souvent une complexité proche. Pourtant à l’usage, un tri shell est plus rapide qu’un tri par sélection, tout dépend du nombre d’éléments et l’éventuel ordre de ceux-ci au départ.

b. Le tri par création

Le tri par création ne sera abordé que du point de vue théorique. En effet, si cette méthode semble simple, elle est en fait lourde et compliquée. Si on demande à un débutant en programmation comment trier un tableau, il vous proposera très certainement de créer un deuxième tableau dans lequel on placera au fur et à mesure les éléments du premier tableau dans l’ordre croissant.

C’est une très...

a. Type structuré

Le type structuré est opposable aux types dit primitifs vus jusqu’à présent. Un type structuré peut contenir des éléments de types primitifs (entiers, réels...