Pouvoir n'utiliser qu'une valeur à la fois peut très souvent s'avérer inefficace, voire, purement et simplement impossible.
Imaginez simplement que vous ayiez besoin d'une chaine de 20 caractères et que vous soyiez obligé de gérer 20 variables de type caractère de manière indépendante (car, finalement une chaîne de 20 caractères n'est rien d'autre que… 20 caractère mis bout à bout), vous ne pourriez déjà pas les gérer de manière globale, mais en plus, votre programmation se transformerait vite en casse-tête.
Par chance, tous les langages de programmations permettent d'utiliser des tableaux, qui ont pour seul et unique but de fournir un certain nombre d'éléments d'un type déterminé disposés l'un à la suite de l'autre dans la mémoire à disposition de l'utilisateur.
On pourra alors disposer de toutes les valeurs en appelant simplement le nom choisi pour désigner le tableau, ou, de manière séparée, chaque élément du tableau en indiquant l'indice de l'élément auquel on souhaite accéder.
Il est bien évidemment possible de créer des tableaux pour tous les types de base de valeurs existant.
Vous pourriez très bien choisir de créer un tableau de 12 entiers pour contenir le nombre de jours que l'on trouve dans chaque mois.
Le schéma que voici présente la manière dont la mémoire est allouée à un tableau.
Ce schéma est important à plus d'un titre:
D'abord, il représente bien le fait que l'on ne sait jamais ni ce qui précède l'espace alloué au tableau, ni ce qui le suit.
Avec un peu de chance, les espaces mémoires suivants n'auront pas été utilisés, mais il n'est pas exclu qu'ils contiennent, dans le meilleur des cas, des valeurs propres à votre application, dans le pire des cas, des valeurs nécessaires à une autre application en cours d'exécution, voire, quarrément, des instructions nécessaires à votre système d'exploitation.
Ensuite, parce qu'il indique clairement que l'adresse mémoire qui est réservée au premier élément du tableau est l'adresse mémoire du début même du tableau.
C'est la raison pour laquelle certains langages de programmations, dont font partie le C et le C++, nécessitent pour accéder au N ième élément d'un tableau d'utiliser l'indice N-1.
Pour accéder à la valeur d'un élément précis d'un tableau, il s'agira de donner l'indice de l'élément du tableau auquel on souhaite avoir accès.
La plupart des langages de programmations demanderont que l'on indique le nom du tableau, suivi de l'indice de l'élément auquel on souhaite accéder entre crochets, soit, par exemple tab[5] demanderait l'accès au cinquième élément d'un tableau nommé tab.
Les langages de programmation qui n'utiliseraient pas les crochets pour indiquer les indices utiliserons sans doute les parenthèses (ce qui est le cas, par exemple du COBOL qui accède au cinquième élément de tab par tab(5))
De la même manière, rien ne vous empêche (hormis peut être la quantité de mémoire disponible sur l'ordinateur) de créer des tableaux à plusieurs dimentions.
Vous pourriez, par exemple, souhaiter disposer d'une chaine de vingt caractères pour chacune des 24 heures de la journées, ce pour chacun des (maximum)31 jours du mois mais pour les douze mois de l'année.
Vous demanderiez donc la création d'un tableau à quatre dimentions:
La dernière dimention disposant de douze éléments (pour le mois de l'année), chacun étant composé de 31 élément (pour les 31 jours disponible les mois les plus longs), qui seraient eux meme composés de 24 éléments (pour chaque heure de chaque jour du mois de l'année), qui seraient enfin composé de 20 caractères (pour la chaine de caractères dont vous voulez disposer pour chaque heure de chaque jour de chaque mois de l'année).
Pour accéder à une chaine précise, vous indiqueriez alors l'indice du mois concerné, suivi de l'indice du jour, suivi enfin de l'indice de l'heure précise qui vous intéresse.
En pratique, il devient très difficile de gérer plus de trois à quatre dimentions, sans compter le fait que, plus le nombre d'éléements de chaque dimention est important, plus le système risque d'avoir du mal à trouver un endroit en mémoire dans lequel il lui sera possible de mettre l'ensemble du tableau.
On se limitera donc, dans la mesure du possible à des tableaux à trois ou à quatre dimentions.
Quand on parle de dimention aux gens, ils voyent de manière systématique les trois dimentions classiques: longueur, hauteur et profondeur, et il est déjà très difficile de s'imaginer où peut se situer une quatrième dimention.
L'ordinateur ne dispose lui-même que d'une dimention pour gérer sa mémoire.
Après tout, il n'a qu'une liste d'adresses mémoires allant de 1 à... sa limite de mémoire.
Si, sans aller jusqu'à quatre dimention, on lui demande simplement de réserver l'espace pour cinq chaines de caractères composées chacune de 20 caractères, il réservera tout simplement 20 espaces pour la première chaine, à la suite de quoi il en réservera 20 autre pour la seconde et ainsi de suite j'usquà avoir réservé le nombre suffisant d'espaces mémoire.
Il y aura donc une différence fondamentale entre le fait de lui demander de réserver 5 fois 20 caractères et le fait de lui demander de réserver 20 fois 5 caractères, bien que le nombre total d'espaces mémoires réservés restera identique.
en effet, L'ordinateur se souviendra de l'adresse de départ de chaque éléments.
Dans le premier cas, il se souviendra que le premier élément commence à Depart+0, le deuxième à Depart+20, le troisième à Depart+40 et ainsi de suite pour arriver au cinquième qui commence à Depart+80, alors que dans le second cas, il se souviendra que le premier commencera à Depart+0, le deuxieme à Depart+5, le troisième à Depart+10…et le vingtieme à Depart+95…
Depart représentant ici l'adresse de départ de la mémoire qui est réservée au tableau.
Il sera donc important de veiller, lors de la création de tableaux à plusieurs dimentions, à ce que les dimentions soient gérées dans le bon ordre.
Quand on utilise des tableaux multi-dimentionnels, on accède aux différents éléments exactement de la même manière que dans le cas d'un tableau simple, à ceci près que nous devrons indiquer un indice pour chaque dimention envisagée.
De cette manière, en nommant "mat" le tableau à quatre dimentions pris en exemple au chapitre précédent, nous serons en mesure d'accéder:
Il est bien souvent utile, voire nécessaire, d'envisager de trier les données dont on dispose…
Que le but soit simplement de permettre d'accéder aux données dans un certain ordre, ou d'en faciliter la recherche, le fait de disposer de données triées présente en effet de nombreux avantages…
Quel que soit le type de données que l'on introduit dans le tableau, le principe restera de toutes façon le même: placer les données selon la valeur (triée de manière ascendante ou descendante) que prend l'élément.
De manière générale, il y a deux possiblités d'envisager le tri:
Il me semble important de préciser qu'aucune des possibilités n'est à la base meilleure, ni plus mauvaise que l'autre… Tout au plus, l'une d'elles peut sembler plus simple à mettre en oeuvre que l'autre, mais les deux seront particulièrement gourmandes en temps d'exécution dés le moment où la taille du tableau sera importante.
Simplement, quand la taille du tableau est importante, le tri "à la volée" *risque* de ralentir l'acquisition des données au moment même, alors que le tri "en bloc" *risque* de demander beaucoup de temps entre l'aquisition des données et le moment où celles-ci seront effectivement triées…
Et le terme "important" dans ce contexte est encore à pondérer très largement: un tableau prenant 20,50 voire même 100 éléments peut encore, surtout au vu des capacités des ordinateurs actuels, ne pas être vraiment considéré comme un "grand" tableau…
Imaginons que nous voulions créer une application toute simple qui demande à l'utilisateur d'introduire dix nombres entiers différents compris entre 0 et 100 puis qui les réaffiche tous dans l'ordre croissant de leurs valeurs.
Tout étant dit, et l'étape d'acquisition des nombres ne nous intéressant pas forcément, il n'est peut être pas *forcément* nécessaire de passer par l'étape de l'énoncé du problème…
Par contre, il est intéressant de savoir si l'on souhaîte créer cette application de manière à ce qu'elle trie les nombres donnés directement lors de l'introduction
Si l'on souhaîte effectuer le tri à la volée, on peut dire que deux grandes étapes sont nécessaires:
Pour arriver à placer le nombre qui vient juste d'être introduit, il "suffira" de déplacer tous les nombre qui sont plus grands que celui introduit d'un cran vers la fin du tableau, en prenant juste la précaution de ne pas risquer de perdre les valeurs lors des recopies…
Pour y arriver, il s'agira donc de partir du dernier élément défini du tableau, et de vérifier s'il est plus grand ou plus petit que l'élément introduit.
S'il est plus grand, on le décale d'une place vers la fin du tableau, et on recommence avec l'élément qui le précède.
Le nasichneiderman correspondant pourrait ressembler à ceci, sur base d'une routine qui prendrait comme paramètre deux valeurs entières: combien (nombre d'éléments déjà introduits), et introduit (valeur que l'utilisateur vient d'introduire) et se basant sur un tableau nommé tab défini en tant que variable globale.
Bien sûr, il ne s'agit ici que d'une des solutions envisageables, et, pour être honnête, l'utilisation d'un tableau défnit comme variable globale n'est pas réellement la solution la meilleure…
Cependant, dans l'état des connaissances acquises à la lecture de ce tutorial, est a le mérite de ne pas brûler les étapes et de tenir parfaitement la route…
Si on préfère attendre que tous les nombres soient introduits avant de les trier, il faudra utiliser un deuxième tableau pour les transférer sans risque de les perdre…
Deux optiques inverses sont possibles:
Soit on cherche l'élément restant le plus petit, pour le retranscrire dans le tableau temporaire, soit on cherche l'élément restant le plus grand. La seule différence qui apparaitra dans la gestion de la copie des valeur, c'est que dans le premier cas on remplira le tableau par le début, alors que dans le second on le remplira par la fin…
Une troisième optique envisageable sera, lorsque l'on parcourre le tableau à la recherche des éléments, on prenne le nombre restant le plus petit et le nombre restant le plus grand. Cette optique qui combine les deux autres aurait pour principal avantage de ne devoir parcourrir le tableau de base que la moitié des foish… en ajoutant néanmoins de la complexité à logique.
Cependant, vu la petite taille du tableau que nous nous apprêtons à trier, le gain de temps occasionné par cette troisième optique est à ce point négligeable qu'il rend son recours inutile, autrement qu'à titre purement didactique…
Comme nous avons décidé des principales caractéristiques de l'application (nombre de valeur à introduire, valeurs minimales et maximale) de manière purement arbitraire, nous pouvons très bien nous contenter de coder ces valeurs en dur dans notre routine de tri, sans avoir à nous occuper de transmettre de paramètres.
La seule disposition qu'il nous reste à prendre, est tout simplement de déclarer notre tableau de base (que nous nommerons de nouveau tab) en tant que variable globale…
Voici à quoi pourrait ressembler le nassichneiderman de tri sur base du choix du nombre le plus petit:
Bon, rien qu'à voir votre mine dubitative, j'ai l'impression que certains d'entre vous s'apprêtent à demander la camisole de force pour moi… Je vais donc me dépêcher de vous donner les explications pour vous convaincre du bien-fondé de cet algoritme.
Nous devons copier dix valeurs dans un tableau temporaire … Il faudra donc effectuer dix fois le traitement complet de recherche, et introduire les valeurs aux indices 0 à 9.
C'est pour cela que le tout se trouve dans la boucle pour copie=0 à 9.
Nous avons déterminé arbitrairement que la plus grande valeur admise à l'acquisition (et donc que nous risquons de trouver dans le tableau) est 100…
En utilisant sciemment une valeur plus élevée comme valeur de référence, on s'assure du fait que, même si il ne reste qu'un nombre dans le tableau, et ce nombre est 100, qu'il sera effectivement considéré comme étant le plus petit trouvé.
Il est maintenant temps de parcourrir le tableau à trier à la recherche du nombre restant le plus petit, c'est la raison d'être de la deuxième boucle (qui parcourrera les indices 0 à 9 du tableau de référence)
Si on trouve une valeur plus petite que notre valeur de référence (qui est notre nombre "potentiellement le plus petit"), on l'utilise comme nouvelle valeur de référence.
Pour éviter que ce nombre soit réutilisé lors du prochain parcours du tableau, on lui donne une valeur expressément supérieure à la valeur maximale qu'on s'attend à trouver (donc supérieure à 100)
A la fin de la seconde boucle, min vaut donc le plus petit nombre restant que l'on a trouvé dans le tableau, on peut donc le placer dans notre tableau temporaire…
Une fois que l'on est sorti de la première boucle (celle qui s'occupait de remplir le tableau temporaire) on indique que notre tableau de référence n'est plus l'ancien tableau, mais bel et bien le nouveau.
A la sortie de la routine, nous nous retrouvons donc avec un tableau parfaitement trié.
Revenons maintenant, si vous le voulez bien à au fameux tableau mat à quatredimentions dont je parlais quelques chapitres plus haut…
Il faut bien se rendre compte qu'un tel tableau monopolisera une quantité incroyable de mémoire…
En effet, vous aurez en définitive besoin de 12*31*24*20=167 560 octets contigus pour contenir toutes les informations.
Une chance, finalement, que nous ne voulions que des caractères dans ce cas, car, s'il s'était agit de réels double précision, nous aurions eu encore besoin de dix fois plus de mémoire contigue…
De plus, pour s'assurer que chaque mois soit en mesure de disposer du bon nombre de jour, nous sommes obligé d'utiliser le nombre de jours le plus élevé que l'on trouve dans les mois, à savoir 31…
Or, il n'y a que 7 mois de 31 jours... et il y en a même un qui n'en a que 27 ou 28 selon que l'année soit bissextile ou non…
Nous gaspillerons donc dans cet exemple d'office (7*24*20)= 3 360 octets minimum (pour les années bisextiles, 3 840 pour les autres) de mémoire, ce qui est sans doute peu en regard de la capacité des mémoires actuelles, mais énorme pour les petits systèmes.
Et je ne vous parle pas du gaspillage occasionné par le fait que l'on décide de n'utiliser de manière systématique que quatre caractères sur les vingt initialement prévus…
Cette manière de travailler risque donc fort, sur les systèmes limités en mémoire, non seulement d'utiliser énormément de ressources par rapport au ressources disponibles, mais aussi, pour tous les systèmes, de provoquer un gaspillage des ressources, la mémoire réservée devenant fatalement indisponible pour d'autres nécessités.
Le gros risque, avec les tableaux de caractères, est d'utiliser ce que l'on appelle l'acquisition bufferisée du clavier.
Il s'agit en fait de laisser l'utilisateur enfoncer autant de touches qu'il le désire, et d'attendre qu'il enfonce la touche <Enter> pour placer ce qu'il aura écrit dans le tableau auquel c'est destiné.
Tant que l'utilisateur veillera à ne pas dépasser le nombre de caractères qui a été prévu, tout ira très bien, mais les choses dégénèreront rapidement si l'utilisateur essaye d'en introduire d'avantage.
En effet, la plupart des langages commenceront à remplir le tableau à l'adresse exacte, mais ne tiendront pas compte de la taille maximale définie pour ce tableau.
Il s'en suit que si on prévoit une taille de tableaux de 20 caractères, mais que l'utilisateurs essaye d'en introduire 25, les 5 caractères surnuméraires iront… à des adresses mémoires qui risquent d'être utilisées pour autre chose.
Si les adresses mémoires surnuméraires contiennent des valeurs, elles seront irrémédiablement remplacées par les valeurs des caractères correspondants.
Dans le meilleur des cas, on risque alors d'obtenir un résultat haberrant, mais ca risque, dans le prie, de mener au plantage pur et simple du système.
Le terme tableaux est utilisé à tord, parce que l'on se réfère à la visualisation en tableau que l'on s'en fait.
En effet, on visualiserait plutot une chaine de caractère sous cette forme
| Chaine | v | a | l | e | u | r | d | e | l | a | c | h | a | i | n | e | \0 |
|---|
De même, on visualiserait plutôt un tableau à deux dimention sous la forme de
| chaine1 | V | a | l | e | u | r | 1 | \0 | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| chaine2 | V | a | l | e | u | r | 2 | \0 | ||||||||||||
| … | ||||||||||||||||||||
| chaineX | C | o | n | t | e | n | u | d | e | l | a | c | h | a | i | n | e |
Seulement, il s'agit d'un abus de langage.
En effet, un tableau à une dimention devrait être applelé par le terme qui permet la représentation d'un certain nombre de valeurs sur une ligne: un vecteur.
Les tableaux à plusieurs dimentions devraient idéalement être appelés par le terme qui permet la représentation de plusieurs vecteurs: une matrice, surtout si le tableau est destiné à contenir des valeurs numériques.
Les règles de calcul à appliquer sur ces tableaux à plusieurs dimentions sont d'ailleurs les règles du calcul matriciel, avec tout ce que cela comporte.
Copyright (©) 2005 (Philippe Dunski)
Ce cours est libre, vous pouvez le redistribuer et/ou le modifier selon les termes de la Licence Publique Générale GNU publiée par la Free Software Foundation (version 2 ou bien toute autre version ultérieure choisie par vous).
Ce cours est distribué car potentiellement utile, mais SANS AUCUNE GARANTIE, ni explicite ni implicite, y compris les garanties de commercialisation ou d'adaptation dans un but spécifique. Reportez-vous à la Licence Publique Générale GNU pour plus de détails.
Cependant, l'auteur apprécierait grandement que vous lui fassiez part de toute modification apportée à son contnu
Vous pouvez le contacter par mail à l'adresse koala01@free.fr
Vous pouvez trouver une adaptation française de la licence GNU/GPL à l'URL http://www.linux-france.org/article/these/gpl.html
