Accueil
 COURS INFORMATIQUE
 Cours Algorithmique
 Cours ASP
 Cours CSS
 Cours HTML
 Cours PHP / MySQL
 Cours Réseaux
 Cours SQL
 Cours Visual Basic
 ARTICLES
  Conception de sites
  Droit & Internet
  e-commerce
  Société
  Strategies du web
  Technologies Web
  Marketing Web
 LIVRES
  ASP/ASP.Net
  C/C++/C#
  Conception de sites
  DHTML/CSS
  Gestion de Projet
  HTML/Internet
  Java/JSP/J2EE
  JavaScript/VbScript
  Juridique
  Marketing/Stratégie
  PHP/Linux/Unix
  Réseaux
  XML/XHTML/XSL
 NETALYA RECOMMANDE
Reussir un projet de site web

Cours d'algorithmiqueCours d'algorithmique N°5 : les tableaux

Auteur : Christophe Darmangeat

Infinite Menus, Copyright 2006, OpenCube Inc. All Rights Reserved.

Bonne nouvelle, on a vu toutes les structures logiques de la programmation.

Mauvaise nouvelle, il vous reste tout de même quelques petites choses à apprendre.

1. Utilité des tableaux

Imaginons que dans un programme, nous ayons besoin simultanément de 12 valeurs (par exemple, des notes pour calculer une moyenne). Evidemment, la seule solution dont nous disposons à l’heure actuelle consiste à déclarer quinze variables, appelées par exemple Notea, Noteb, Notec, etc. Bien sûr, on peut opter pour une notation un peu simplifiée, par exemple N1, N2, N3, etc. Mais cela ne change pas fondamentalement notre problème, car arrivé au calcul, cela donnera obligatoirement une atrocité du genre :

Moy = (N1 + N2 + N3 + N4 + N5 + N6 + N7 + N8 + N9 + N10 + N11 + N12 ) / 12

Ouf ! C’est tout de même bigrement laborieux. Et pour un peu que nous soyons dans un programme de gestion avec quelques centaines ou quelques milliers de valeurs à traiter, alors là c’est direct le suicide.

Cerise sur le gâteau, pour peu que l’on ne puisse savoir d’avance combien il y aura de valeurs à traiter, là on est carrément cuits.

C’est pourquoi la programmation nous permet de rassembler toutes ces variables en une seule, au sein de laquelle chaque valeur sera désignée par un numéro. En bon français, cela donnerait donc quelque chose du genre " la note numéro 1 ", " la note numéro 2 ", " la note numéro 8 ". C’est largement plus pratique, vous vous en doutez.

Un ensemble de valeurs portant ainsi le même nom de variable et repérées par un nombre, s’appelle un tableau, ou encore une variable indicée. Et le nombre qui sert à repérer chaque valeur s’appelle – ô surprise – un indice.

2. Notation et utilisation algorithmique.

Dans notre exemple, nous créerons donc un tableau appelé Note (ou N, si on veut aller plus vite). Et chaque note individuelle sera désignée Note(1), Note(2), etc.

Un tableau doit être déclaré comme tel, en précisant le nombre et le type de valeurs qu’il contiendra.

Tableau Note(12) en Entier

On peut créer des tableaux contenant des variables de tous types : tableaux de numériques, bien sûr, mais aussi tableaux de caractères, de booléens, de tout ce qui existe dans un langage donné comme type de variables. Par contre, hormis dans quelques rares langages, on ne peut pas faire un mixage de types différents de valeurs au sein d’un même tableau.

L’énorme avantage des tableaux, c’est qu’on va pouvoir les traiter en faisant des boucles. Par exemple, pour effectuer notre calcul de moyenne, cela donnera :

Tableau Note(12) en Entier
Variables
i, Som en Entier
Variable
Moy en Réel
...

Som ï 0
Pour i ï 1 à 12
Som = Som + Note(i)
i Suivant
Moy = Som / 12

NB : Cet exemple ne peut être qu’un extrait, dans la mesure où on n’a pas programmé comment s’effectue le remplissage des valeurs du tableau.

L’indice qui sert à repérer les éléments du tableau peut être exprimé directement comme un nombre en clair, mais il peut être aussi une variable, ou une expression calculée.

La valeur d’un indice doit toujours :

  • être égale au moins à 0 ou à 1 (dans certains langages, le premier élément d’un tableau porte l’indice zéro, dans d’autres l’indice 1)
  • être un nombre entier. Quel que soit le langage, l’élément Truc(3,1416) n’existe jamais
  • être inférieure ou égale au nombre d’éléments du tableau. Si le tableau Bidule a été déclaré comme ayant 25 éléments, la présence dans une ligne, sous une forme ou sous une autre, de Bidule(26) déclenchera automatiquement une erreur.

Le gag de la journée : consiste à confondre, dans sa tête et / ou dans un algorithme, l’indice d’un élément d’un tableau avec son contenu. La troisième maison de la rue n’a pas forcément trois habitants, et la vingtième vingt habitants. En notation algorithmique, il n’y a aucun rapport entre i et truc(i).

3. Tableaux dynamiques

Il arrive fréquemment que l’on ne connaisse pas à l’avance le nombre d’éléments que devra comporter le tableau. Bien sûr, une solution consisterait à déclarer un tableau gigantesque (10 000 éléments, pourquoi pas, au diable les varices) pour être sûr que " ça rentre ". Mais d’une part, on n’en sera jamais parfaitement sûr, d’autre part, en raison de l’immensité de la place mémoire réservée – et la plupart du temps non utilisée, c’est un gâchis préjudiciable à la rapidité de notre algorithme.

Aussi, pour parer à ce genre de situation, a-t-on la possibilité de déclarer le tableau sans préciser son nombre d’éléments, puis au cours du programme, à préciser ce nombre via l’instruction Redim. Notez que tant qu’on n’a pas précisé le nombre d’éléments d’un tableau, d’une manière ou d’une autre, ce tableau est inutilisable.

Exemple : on veut faire saisir des notes pour un calcul de moyenne, mais on ne sait pas combien il y aura de notes à saisir. Le début de l’algorithme sera quelque chose du genre :

Tableau Notes() en Entier
Variable
nb en Entier
Début
Ecrire
"Combien y a-t-il de notes à saisir ?"
Lire nb
Redim Notes(nb)
...

4. Tri d’un tableau

Ce qui suit est incontournable. Combien de fois au cours d’une carrière (brillante) de développeur a-t-on besoin de ranger des valeurs dans un ordre donné ? C’est incalculable. Aussi, plutôt qu’avoir à réinventer à chaque fois la roue, le fusil à tirer dans les coins, le fil à couper le roquefort et la poudre à maquiller, vaut-il mieux avoir assimiler quelques techniques solidement éprouvées, même si elles paraissent un peu ardues au départ.

Il existe plusieurs stratégies possibles pour trier les éléments d’un tableau ; nous en verrons une : le tri par sélection.

Admettons que le but de la manœuvre soit de trier un tableau de 12 éléments dans l’ordre croissant.

45 122 12 3 21 78 64 53 89 28 84 46

On commence par rechercher le plus petit élément. On l’identifie en quatrième position, et on l’échange alors avec l’élément numéro 1.

3 122 12 45 21 78 64 53 89 28 84 46

On recommence à rechercher le plus petit élément, mais cette fois à partir du deuxième élément. On le trouve en 3e position, on échange donc le deuxième avec le troisième :

3 12 122 45 21 78 64 53 89 28 84 46

On recommence à partir du troisième, ce qui donnera in fine :

3 12 21 45 122 78 64 53 89 28 84 46

Et cetera, et cetera , jusqu’à l’avant dernier.

L’algorithme permettant d’effectuer cette tâche est le suivant :

Pour i ï 1 à 11
mini = t(i)
posmini = i
Pour j ï i + 1 à 12
Si t(j) < mini alors
mini ï t(j)
posmini ï j
Finsi
j suivant
t(posmini) ï t(i)
t(i) ï mini
i suivant


Nous vous informons que ce cours constitue une œuvre protégée en France par le Code de la Propriété Intellectuelle, et à l’étranger par les conventions internationales en vigueur sur le droit d’auteur. La violation de l’un des droits d’auteur de l’œuvre est un délit de contrefaçon. Il est donc interdit, à titre privé ou public, de reproduire, copier, vendre, revendre ou exploiter, que ce soit dans un but commercial ou purement gratuit, ce cours, sauf accord exprès et préalable de son auteur.


Google
 
 RESSOURCES GRATUITES
 Caractères spéciaux
 Code Couleurs HTML
 Générateur Méta Tags
 Références HTML
 Scripts : ASP
 Scripts : Java Scripts
 PRATIQUE / OUTILS
 Salons Informatiques
 Astuces Windows
 TÉLÉCHARGEMENTS
 Utilitaires système
 Logiciels pratiques
 Jeux & démos
 INFOS SITE
 Contacts
 Mentions légales
 Qui sommes-nous ?
 PARTENAIRES
 Jeux et Jouets
 Murielle Cahen
 Cours d'anglais
 Droit NTIC
 Directeur Internet
 Australie
 Création site Internet
 VOD News
 Web Hostings