Voici quelques pages, j'ai tenté de vous initier à l'utilisation de tableaux.
Bien que je présume que tout le monde a dores et déjà bien pris conscience des limites qu'imposent l'utilisation d'un tableau, j'estime (peut être à tord, à vous de me le dire) qu'il n'est sans doute pas inutile d'«enfoncer un peu le clou» en les rappelant:
Sans doute vous apprêtez-vous à vous écrier «Mais alors comment s'y prendre », fort de l'impression (fausse au demeurant) que j'ai pu vous laisser mûrir qu'un tableau ne pouvait être géré que de manière statique…
Si je n'ai pas parlé en son temps de la gestion dynamique de tableaux, c'est simplement parce qu'il manquait certains concepts (celui de pointeur, en l'occurence) pour permettre une compréhension aisée du principe…
Alors, autant tordre directement le cou à cette idée fausse: oui, la gestion dynamique des tableaux est tout à fait possible…
Par contre, il faut bien l'avouer, elle a beau être possible, elle risque de ne pas se faire tout à fait sans mal…:
Le tout, bien évidemment, sans oublier de libérer la mémoire allouée au tableau avant de quitter définitivement l'application…
Vous comprendrez donc que je dise que, oui, une gestion dynamique de tableau est parfaitement possible, mais elle risque vraiment d'être malaisée…
Et pourtant, soyons un peu fou, voyons le raisonnement qu'il faudrait prévoir pour le faire.
De manière à travailler "dans les règles de l'art", nous allons donc mettre en oeuvre une petit programme en suivant les principes que j'ai énoncés jusqu'à présent…
- Que doit faire l'application? Cette application devra simplement proposer à l'utilisateur d'introduire un nombre, ou d'arrêter l'introduction.
- Une fois que l'utilisateur décide de ne plus en introduire, elle devra présenter les nombres qu'il aura donnés.
- De quelles informations l'application a-t-elle besoin? Afin de fonctionner de manière correcte, l'application a besoin de:
- un caractère singifiant si l'utilisateur souhaite introduire un nouveau nombre ou non,
- une valeur de type "entier" qui corresponde au nombres d'éléments déjà introduits,
- un tableau reprenant les différents nombres introduits.
- Où l'application va-t-elle se procurer ces informations?
- Le choix d'introduire un nouveau nombre et le nombre lui-même seront fournis par l'utilisateur.
- Le nombre d'éléments déjà introduits sera incrémenté automatiquement à chaque fois que l'utilisateur décidera de rajouter un nombre.
- Le tableau reprenant les nombres introduits sera géré dynamiquement.
nota: Pour cet exemple, nous pourrons nous contenter d'une introduction des nombres non sécurisée… Cependant, il serait pour ainsi dire indispensable de veiller à la sécurisation des introductions clavier dans le cas d'une application qui dépasserait le cadre purement théorique de ce tutorial.
- Comment l'application doit-elle gérer ces informations?
- La valeur de choix détermine s'il faut retourner dans la boucle générale ou non. Si le choix est d'introduire un nouveau nombre, le nombre d'éléments est incrémenté et le tableau est réalloué dynamiquement.
- Le nombre introduit prend systématiquement la place du dernier élément du tableau.
- Après que l'utilisateur ait décidé d'arrêter l'introduction de nombres, tous les nombres introduits sont réaffichés.
Je vais profiter de cet exemple pour vous faire part d'une manière de concevoir les nassichneiderman qui, bien qu'étant de prime abord relativement surprenante, peut présenter un intérêt certain lors de la mise au point d'applications.
Quand on y regarde bien, la plupart des applications suivront exactement le même schéma de base lors de leur exécution, qui passera par trois à quatre grandes étapes:
L'idée que je vous suggère (et dont vous vous rendrez sans doute compte à l'usage que, dès qu'elle est applicable, elle permet de fournir un code dans lequel il est bien plus facile de s'y retrouver) est tout simplement de créer une routine spécifique pour chacune de ces étapes.
Il suffira alors, dans la routine principale, simplement d'appeler chacune de ces "sous routines" (le terme est peut être mal choisi, je vous l'accorde) l'une après l'autre, éventuellement en prenant la précaution de s'assurer qu'elle s'est bien déroulée.
Pour cet exemple, j'ai préféré vous présenter chaque nassichneiderman séparément, simplement pour être en mesure de tous vous les expliquer sans risquer de m'emmeler les pinceaux (ce qui aurait risqué de rendre votre propre compréhension plus dure)…
Dans le cadre de l'application que nous tentons de mettre au point, voilà à quoi pourrait ressemler le nassichneiderman de la routine principale
Pour ceux qui ne l'auraient peut être pas compris à la vue du nassichneiderman, la fonction AquisNombre() se chargera de la boucle d'introductions des différents nombres, AffichNombre() se chargera de l'affichage des nombres qui ont été introduits, et finalisation se chargera de la libération de la mémoire avant de quitter l'application
Dans le cas qui nous intéresse, j'ai jugé opportun (mais c'est un état qui doit être réévalué pour chaque cas) d'utiliser des variables globales tant pour le pointeur qui récupérera les entiers introduits que pour la variable qui gardera en mémoire le nombre d'éléments introduits… Le seul but de la manoeuvre étant de ne pas se trouver dans une situation dans laquelle il faudra, en définitive, gérer un pointeur et un pointeur de pointeur qui devraient être transmis en paramètres.
Dans le but d'éviter les valeurs «parasites» qui pourraient se trouver aux adresses mémoires des différents variables (en considérant par abus de langage le pointeur comme étant une variable), on les définit toutes à 0 par défaut.
Cette routine n'est qu'une boucle qui s'occupe de l'acquisition des nombres, et de la gestion du choix de l'utilisateur d'en introduire un suivant ou non.
L'acquisition du nombre en elle même n'est finalement rien d'autre que la définition de la valeur d'un élément donné du tableau d'entier dont on dispose.
Comme on considère comme acquis le fait que l'utilisateur introduira au minimum un nombre, c'est en toute logique que je me suis dirigé vers une boucle de type "jusque".
La gestion du pointeur en elle-même sera effectuée grâce à l'appel de la routine GestTab().
S'il peut parraître surprenant que la première instruction d'une boucle soit l'appel à une routine, cela se justifie pleinement par le fait que pour le premier élément que l'utilisateur va introduire, il s'agira bel et bien de disposer d'un tableau (même si ce n'est un tableau d'un élément) dans lequel placer la valeur donnée…
De la même manière, il peut parraitre surprenant que l'affichage fasse appel à la valeur de Nombre, alors que l'introduction dans le tableau utilise l'indice Nombre-1…
Plusieurs raisons sont à la base de cet état de fait:
Vous pourriez également vous étonner du fait que j'ai explicitement dit que, pour cet exemple, la sécurisation de l'acquisition n'était pas nécessaire, et que je fasse pourtant un test (dans une boucle imbriquée) sur la valeur du choix de l'utilisateur de continuer ou non…
A vrai dire, il ne faut pas confondre le fait de «travailler de manière non sécurisée» et celui de «laisser l'utilisateur faire n'importe quelle idiotie (pour rester poli)»
Il ne serait en effet pas logique de proposer à l'utilisateur d'introduire un nouveau nombre s'il répond Z à la question de continuer…
Les deux seules réponses qui aient un sens sont O (oui, laissez moi introduire un nouveau nombre) et N (non, j'ai fini mon introduction)… Il s'agit donc de limiter les possibilités à ces deux choix.
Enfin, vous pourriez vous étonner de voir une instruction du genre de choix =majuscule choix…
Il faut savoir que quand on travaille avec les caractères, un o est différent du O et un n est différent du N (ils ont des valeurs ASCII différentes, et ne sont donc pas égaux)
Cependant, tous les langages disposent d'instructions permettant de transformer un caractere (ou une chaine de caractères) en majuscule ou en minuscule, pour autant qu'il s'agisse d'une lettre, bien s&ucicr;…
Comme il est moins "lisible" de demander de transformer en majuscule le résultat d'une introduction clavier que de demander de transformer une valeur en majuscule, j'ai préféré utiliser carrément une ligne supplémentaire.
Mais ce n'est pas un simple caprice: le but est que cela fonctionne aussi bien si l'utilisateur utilise une majuscule ou une minuscule.
Cette simple instruction me permet donc de simplifier considérablement les tests à effectuer, car, je ne dois plus m'inquiéter que des valeurs majuscules (une pour O et une pour N) alors que j'aurais du prévoir la gestion des majuscules ET des minuscules (non seulement O et N, mais aussi o et n), ce qui aurait créé un test deux fois plus long…
Pour que notre routine de gestion des introductions de nombre puisse fonctionner correctement, il ne nous manque plus qu'un élément (qui est d'ailleurs le but réel de cet exemple):
Heuu…A voir vos têtes, il n'est pas impossible que quelques explications soient les bienvenues, les voici donc:
Au moment où la routine est appelée, Nombre vaut toujours… le nombre de valeurs qui ont déjà été définies par l'utilisateur. Or, il s'agit bien d'utiliser un pointeur de travail qui puisse contenir ce nombre d'éléments + 1 (de manière à pouvoir y mettre la valeur que l'utilisateur introduira dés que la routine sera terminée)
Il est donc tout à fait logique d'incrémenter Nombre dés le départ.
La deuxième instruction demande d'allouer un tableau qui soit en mesure de contenir Nombre éléments à un pointeur de travail.
Comme la suite des événements dépend entièrement de la réussite de cette allocation, il est logique que tout le reste se trouve dans la partie qui sera effectuée si l'allocation de mémoire a réussi (et dont le principal signe est que travail n'est pas égal à 0)
Le deuxième test a simplement pour but de s'assurer qu'il existe déjà des valeurs introduites, et donc à recopier (car, si c'est la première valeur qu'on introduit, à ce stade-ci, Tab vaut toujours 0)… Une alternative tout à fait valable aurait été de tester si Nombre-1 valait 0 ou non… J'ai suivi ici l'inspiration du moment qui m'incitait plutot à vérifier le pointeur (je l'avoue honnêtement, il n'y a aucune raison strictement logique à choisir une des possiblité plutôt qu'une autre)
Par expérience personnelle, les applications supportent mal de devoir recopier la valeur de l'adresse mémoire 0 (NULL) ailleurs, c'est la raison pour laquelle on s'évite les ennuis potentiels en ne demandant la recopie des valeurs… que s'il y a des valeurs à recopier.
S'il y a des valeurs à recopier, nous entrons dans une boucle qui recopiera les différentes valeurs, en prenant bien soin de ne pas essayer de copier la valeur de Tab[Nombre](qui est en dehors de la fourchette mémoire qui est actuellement attribuée à Tab).
Les trois lignes suivantes sont sûrement la cause de la ligne que je vois traverser le front de plusieurs d'entre vous (si, si, j'vous jure, juste entre les deux sourcils) … Et pourtant, ce sont sans doute les trois lignes les plus importantes de la routine, celles qui permettront d'éviter la fuite de mémoire.
A ce stade, Tab pointe toujours vers le tableau qui a été créé de manière dynamique lors de l'appel précédent de GestTab()…
Une fois que nous lui aurons donné l'adresse du nouveau tableau, il n'y aura plus moyen de la récupérer l'adresse de départ de l'ancien.
Comme nous avons recopié les valeurs de l'ancien tableau dans le nouveau, (et que le seul qui nous intéresse actuellement est justement le nouveau tableau) il n'y a pas de raison de monopoliser encore la mémoire de l'ancien. Comme, en plus, par la suite, il sera impossible de libérer cette mémoire, il faut le faire maintenant ou jamais… C'est donc maintenant.
Ensuite, il faut s'assurer que tab pointe bien vers l'adresse à laquelle commence le tableau qui contient les valeurs (le seul dont l'espace soit encore alloué), c'est à dire qu'il faut lui donner la valeur de l'adresse de notre tableau de travail, autrement dit, la valeur de notre pointeur Travail.
Il ne nous reste plus, par sécurité, à faire pointer Travail vers une zone mémoire "voie de garage" (c'est à dire vers l'adresse 0(NULL))
Cette sécurité n'est pas à proprement parler indispensable dans ce cas, vu que Travail cessera d'exister une fois que la routine sera quittée (ce qui est bel et bien le cas), mais l'un dans l'autre, il vaut mieux prendre l'habitude de le faire de manière systématique (quitte à le faire une fois de trop) que de prendre le risque d'oublier de le faire quand c'est nécessaire 
.
Voilà donc tout ce qui sera nécessaire pour mener à bien l'acquisition d'un nombre inconnu à l'avance de valeurs entières dans un tableau géré dynamiquement.
Il ne nous reste plus qu'à nous attaquer aux routines
Si j'ai un aveu à vous faire, c'est que j'ai longtemps hésité à présenter le nassichneiderman de ces deux routines, au vu de leur simplicité extrème.
Cependant, au risque de passer encore une fois pour un enfonceur de portes ouvertes, le soucis d'être complet a une fois de plus pris le dessus, dans le but avoué de ne pas risquer de passer à côté d'une explication qui pourrait justement vous faire défaut.
Si je vous les livre ensemble, c'est uniquement parce que vous vous rendrez sans doute tout de suite compte qu'il ne valait peut être même pas la peine d'en faire deux routines tellement elles sont simples (soyons cependant clair et précis: dans l'exemple qui nous occupe, l'utilisation de deux routines ne se justifiait peut être pas… mais il peut parfaitement se justifier dans le cadre de programmes plus volumineux que celui-ci)
Que dire? Finalement pas grand chose… Si ce n'est rappeler le fait que le Nième élément d'un tableau se trouve à l'indice N-1, que, dans AfficheNombre(), la valeur qui nous sert de référence est celle de l'indice et qu'il est donc logique d'indiquer la valeur "pour le commun des mortels" sous la forme de notre compteur +1 (histoire que le premier élément soit bien le numéro 1) …
Eventuellement, rappeler que, si on ne prend pas le pli d'attendre une introduction non bufferisée (représentée ici par "attendre touche clavier"), l'application va continuer (et sans doute finir) sans rien attendre (avec le résultat que l'utilisateur ne verra rien de ce qui est affiché)
Et bien sûr, rappeler encore une fois que Tab est un tableau dont la mémoire a été allouée de manière dynamique, et qu'il nous appartient donc de veiller nous même à ce qu'elle soit libérée (et que le pointeur qui la représente soit renvoyé sur une adresse "sans risque") avant de quitter l'application pour de bon.
La preuve est donc faite, il est parfaitement possible d'envisager l'allocation dynamique de la mémoire pour des tableaux…
Mais le fait que ce soit faisable ne signifie nullement que ce soit la manière la plus efficace d'envisager une gestion dynamique des données.
Dans l'exemple que je viens d'utiliser, selon l'optique du concepteur, cette méthode pourrait être l'une de celle qui pourrait présenter le moins d'inconvénients (à savoir nécessiter une quantité de mémoire moindre sans trop ralentir l'exécution) MAIS, et c'est là que cela se corse, uniquement s'il faut s'appuyer sur un utilisateur pour introduire les données…
Il serait en effet étonnant qu'un utilisateur s'amuse à introduire plus de quelques dizaines (allez, au pire quelques centaines) de données manuellement…En tout cas, personnellement, cela me taperait sur le système de le faire bien avant d'atteindre un tel nombre d'introductions .
Dans de telles conditions, il est peu vraissemblable que l'application présente un réel ralentissement à l'exécution (ou du moins que ce ralentissement ne soit du qu'à notre "géniale" application)
Tout risque de se compliquer singulièrement si l'application va chercher ses données dans un fichier contenant quelques (dizaines de) milliers d'éléments…
Peut être estimez-vous que vous ne créerez jamais un fichier contenant une telle quantité d'informations à lire? Détrompez-vous bien…
Un exemple tout bête pour vous le prouver:
Je me suis amusé à "modéliser" un château tou simple en 3D.
Quand je dis tout simple, c'est vraiment tout simple (une enceinte en hexagone, une tour ronde avec un toit conique à chaque coin, rien autour du chateau, rien dans la cour du chateau, et pas meme une porte dans les murs)…
Ce château à lui seul comporte près de 1000 points (984, pour être précis). D'accord, nous sommes loin de 10000 points, mais, rajoutons l'un ou l'autre détail (une porte pour entrer dans la cour du chateau, quelques collines en 3D, un sol avec un relief qui ne soit pas en "table de billard", quelques cahuttes, quelques arbres), et il y a de fortes chances que les 10000 points soient très largement dépassés…
Peut être vous demandez vous ce qui dans, mon beau nassichneiderman (dans lequel j'ai visiblement pensé à tout) risque de faire baisser les performances de l'application si elle doit gérer l'introduction (de quelque manière que ce soit) d'un grand nombre de données… Non? Vous savez ce qui fera baisser les performances? Vraiment? Bravo…
Pour ceux qui n'ont pas trouvé la faille, il est inutile de faire durer le suspense plus longtemps.
Le problème, c'est qu'à chaque fois qu'on décidera de rajouter un élément au tableau, il y a une boucle (qui sera répétée un nombre correspondant au nombre de données déjà mises en mémoire) qui sera effectuée sytématiquement.
Je sais, il n'y a pas beaucoup d'instructions, et elles devraient être effectuées en un temps relativement restreint (au pire, l'exécution complete de la boucle ne devrait prendre qu'une septentaine de boucle d'horloge processeur… Avec une fréquence d'horloge se chiffrant en gigahertz, le temps pris pour une exécution de la boucle est négligeable), mais ne dit on pas que ce sont les petits ruisseaux qui font les grands fleuves?
Après tout, l'océan n'est rempli que d'une multitude de petites gouttes… Et tout le problème est bien là…
En effet, quand votre application décidera d'allouer un tableau suffisemment grand pour la dix millième donnée, cette "malheureuse petite séquence d'instruction qui ne dure que 70 boucles d'horloge processeur" aura visiblement été effectuée… un nombre correspondant à la factorielle de 9999 de fois…
Le pire, dans tout cela, c'est que, d'une certaine manière, ce nombre faramineux de fois que ces instructions auront été effectuées ne sert à rien, vu que c'est pour recommencer tout de suite après (pour le dix mille unième élément)
Et encore, c'est sans compter sur le fait que pour définir un point dans un environnement à trois dimention, il s'agit de lui donner trois coordonnées (une pour chaque dimention)…
Cependant, je peux vous rassurer, il existe des solutions qui permettent de
L'idée de base pour se passer des tableaux est relativement simple, et se base sur les pointeurs:
«Si nous utilisions une structure apte à contenir non seulement les informations que l'on souhaite garder en mémoire, mais aussi un pointeur vers l'adresse où se trouve l'élément suivant?»
En gros, il suffirait de garder l'endroit où se trouve le premier élément accessible sous la main, pour pouvoir accéder à tous les autres… Un peu à la manière de ce qui se passe quand on tire sur un fil qui dépasse d'un tricot: on récupère la laine de toutes les mailles les unes après les autres(et ca peut aller carrément jusqu'à récupérer la laine de tout le tricot).
Fort de cette idée, il y a plusieurs moyens d'en envisager la mise en oeuvre selon l'élément auquel on accède en premier lieu:
.Je vous rassure, toutes ces méthodes sont expliquées en long, en large et en travers dans les pages qui suivent.
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
