Le tableau : des cases côte à côteChapitre 2/12
Les places numérotées d'un cinéma
Dans une salle de cinéma, les places d'un rang sont côte à côte et numérotées. Avec le billet « rang F, place 12 », tu vas directement à ta place : pas besoin de demander à chaque spectateur du rang où est la tienne.
Un tableau, c'est ça : des cases qui se suivent dans la mémoire, numérotées à partir de 0. Le numéro d'une case s'appelle son indice. On a déjà vu l'animation au chapitre 1, la revoici :
Mémoire vive (RAM)
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
Zoomons sur 32 cases de la RAM, des adresses 100 à 131. Les cases grises sont déjà utilisées par d'autres programmes ou d'autres données.
VitesseÉtape 1/6
D'autres tableaux de la vraie vie : les casiers numérotés de la piscine, les boîtes aux lettres d'un immeuble, les cases d'un calendrier de l'Avent, les sièges d'un avion.
DéfinitionUn tableau
Programme complet du cours structures de données (12 chapitres, gratuit)
- 1. Ranger des données dans la mémoire : La RAM est un gros tableau de cases numérotées de 0 à N - 1 : 8 milliards pour 8 Go. Impossible de tout relire pour trouver une donnée, d'où les structures de données : un ordre connu à l'avance et des règles pour y accéder. Interface et implémentation.
- 2. Le tableau : des cases côte à côte : Des cases contiguës numérotées : accès direct par l'indice en une seule étape, mais insérer ou supprimer au début oblige à tout décaler.
- 3. La liste chaînée : des maillons reliés : Des maillons éparpillés dans la mémoire, chacun connaît l'adresse du suivant : insérer ou supprimer revient à raccrocher une flèche, mais lire le 100e oblige à passer par les 99 premiers.
- 4. La pile : dernier arrivé, premier sorti : La pile d'assiettes : on pose en haut, on prend en haut. Empiler, dépiler, sommet, LIFO, et une pile en Python avec append et pop.
- 5. La file : premier arrivé, premier servi : La file d'attente : on arrive à la fin, on sort par le début. Enfiler, défiler, FIFO, la différence avec la pile, et une file en Python.
- 6. Devine la structure : Le retour d'Insta, Ctrl+Z, la file d'impression, la playlist « à suivre », le distributeur de Pez, la pile d'appels : reconnaître la structure cachée derrière des situations réelles.
- 7. Les arbres : ranger en hiérarchie : Arborescence de fichiers, arbre généalogique, tournoi : une racine, des nœuds, des feuilles. Vocabulaire, hauteur, taille et arbre binaire.
- 8. Parcourir un arbre : Visiter tous les nœuds d'un arbre, chacun une fois : le parcours en largeur (avec une file), et les parcours en profondeur préfixe, infixe et suffixe.
- 9. L'arbre binaire de recherche : Plus petit à gauche, plus grand à droite : chercher une valeur en éliminant la moitié de l'arbre à chaque comparaison, insérer, et pourquoi l'arbre doit rester équilibré.
- 10. Pile et file en programmation objet : Écrire les classes Pile et File, puis une file fabriquée avec deux piles : même interface, autre implémentation.
- 11. La liste chaînée en programmation objet : Les classes Maillon et ListeChainee : ajouter en tête, parcourir, compter, lire le k-ième, ajouter en queue, supprimer. Puis une pile implémentée par une liste chaînée.
- 12. Les arbres en programmation objet : La classe Noeud, la récursivité pour la taille et la hauteur, les parcours préfixe, infixe, suffixe et en largeur, puis l'insertion et la recherche dans un ABR.