Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Algorithme, Tableaux, Structures, fichiers et bdd Note préliminaire : le formal

Algorithme, Tableaux, Structures, fichiers et bdd Note préliminaire : le formalisme des instructions utilisé ici approche le formalisme utilisé dans l'interpréteur Alg'Exec. Mais il ne lui correspond pas exactement car Alg'Exec est contraignant sur certains points où son formalisme est inadapté à l'algorithmique. Dans certains cas, il sera fait référence à d'autre formalismes, ce sera alors explicitement indiqué. 1 Introduction Les variables que nous avons vues sont jusqu'à présent élémentaires. Elles ne contiennent qu'une seule valeur d'un type simple. Cependant, il arrive que nous soyons obligés de traiter des données groupées en table et des données différentes appartenant à un même groupe. Dans le premier cas, nous observerons les tableaux de données, dans le second, de donnée de type structuré vus conjointement aux fichiers et tables de BDD. Vous trouverez, enfin, des exemples mixé de données structurées, de tableaux, de fichiers ou tables de bases de données. 2 Tableaux Les tableaux sont une suite de cases de type élémentaire, assemblées en un seul bloc (comme des cubes collées les uns aux autres, ou une rangée d'alvéoles) Nous allons voir comment lire, modifier, modifier, rechercher, intervertir des éléments. 2.1 Déclaration d'un tableau Lors de la déclaration, on indique le nombre total d'éléments du tableau (que ceux-ci soient affectés ou non). Ce nombre sera le nombre d'éléments maximum que l'on pourra mettre dans le tableau. Dans la partie déclaration on écrit : monTableau[1 : 10] : tableau de entier 'Déclaration de mon tableau Décortiquons : monTableau : nom de la variable [] : indication d'intervalle d'indices 1 : indice minimum (facultatif, 1 par défaut) 10 : indice maximum (obligatoire ; les indices min et max sont séparés par un : ) Tableau : type tableau de : mot de séparation du type tableau et du type des éléments entier : type de chaque élément. Remarques : L'indice maximum indique le nombre maximum d'éléments. Dépasser ce nombre provoque une erreur. Un tableau déclaré de cette façon sera homogène. Tous les éléments ont toujours le même type. 2.2 Accès aux éléments Pour repérer un élément parmi les autre, on utilise un index, nombre entier qui permet d'accéder à un élément (imaginez un ascenseur et ne n° des étages). Pour lire un élément ou le modifier, on indiquera la valeur de l'indice : a <- monTableau[1] // a prend la valeur de l'élément n°1 monTableau[5] <- 3456 // l'élément n°5 prend la valeur 3456 monTableau[3] <- [123, 456] // les éléments n°3 et n°4 prennent respectivement les valeurs 234 et 456 b <- 3 a <- monTableau[b] // a prend la valeur de la cellule n° 3 2.3 Lecture séquentielle d'un tableau Pour lire tout un tableau, on utilisera alors une boucle 'pour' et non un 'TantQue' ou 'Répéter' : pour indice de 1 à 10 faire Traitements finPour exemple : fonction somme(tabEntier[] : tableau de entier, iMax : entier) : entier /* faire la somme du tableau d'entiers donné, le nombre d'éléments est aussi donné. */ var // Déclarations i : entier ' indice de travail somme : entier ' résultat de la somme début // Corps somme <- 0 pour i de 1 à iMax somme <- somme+tabEntier[i] finPour retourner somme // attention, retourner n'existe pas dans Alg'Exec Fin Remarque : pas besoin d'indiquer indiceMin et indiceMax dans la définition du tableau transmis en paramètre. Note : dans Alg'Exec, à la place de "retourner", il faut utiliser une variable prédéfinie "valret" qui permet de retourner une valeur dans les fonctions. /ex, à la place de "retourner somme" il faudrait écrire "valret <-somme". C'est ce qui me fait dire qu'Alg'Exec n'est pas la panacée et en DOIT PAS être la référence en terme de formalisation algorithmique. 2.4 Rechercher dans un tableau Pour rechercher un élément dans un tableau, on ne peut plus utiliser de boucle pour car on ne sait pas à quel moment on s'arrêtera. Exemple : rechercher le plus grand élément d'un tableau 2.5 Effacement dans un tableau Pour effacer un élément du tableau, on a le choix entre différentes solutions : 1. On attend que l'élément soit écrasé par une nouvelle valeur. 2. On met l'élément à une valeur signifiant "élément vide" par convention. 3. On compresse les éléments et on note le nombre d'élément "valides" dans une variable associée au tableau. 4. Autres solutions … La solution 1 est facile à mettre en œuvre, mais on ne sait pas, à priori quelles sont les éléments que l'on peut écraser. Eventuellement, la variable indice peut y être liée. La seconde solution est déjà un peu meilleure mais on se prive d'une valeur possible et on est obligé de rechercher les éléments vides avant de pouvoir mettre un nouvel élément. La troisième solution nécessite un traitement à chaque suppression mais, connaissant l'indice du dernier élément (ou du premier disponible) il est facile d'ajouter un élément. A noter que si les éléments d'un tableau doivent être triés, cela complique le problème car il faut rechercher la juste place de l'élément à ajouter et l'insérer dans le tableau, ce qui nécessite de lui faire de la place en décalant tous les éléments avant de l'ajouter ou le mettre à la fin et re-trier le tableau. Les autres solutions sont d'utiliser autre chose qu'un tableau pour faire une liste d'éléments. Nous n'étudierons pas cette autre chose dans ce cours. Exemple : Faire un extrait des algorithmes permettant d'illustrer chacune des trois solutions 2.6 Compresser les éléments d'un tableau Les élément du tableau sont tous des entiers naturels (positifs). La valeur –1 marque un trou dans le tableau. a) faire l'algorithme d'initialisation du tableau b) Faire l'algorithme pour combler tous les trous dans le tableau. 2.7 Intervertir des éléments Avec le tableau de caractères suivant : bonjour[7] qui contiendra {'B', 'O', 'N', 'J', 'O', 'U', 'R'}. On utilisera la procédure iniBonjour(es bonjour[] : tableau de caractère) pour initialiser le tableau et afficherBonjour(bonjour[] : tableau de caractère) pour afficher le contenu du tableau. a) faire l'algorithme pour intervertir les éléments deux à deux, observez le résultat. b) faire l'algorithme qui inverse le sens des éléments (ruojnob). 2.8 Tableaux et fonctions ou procédures On peut transmettre un tableau aux fonctions ou procédures dans les paramètres. Illustration : Fonction sommeTableau(tableauEntier[1..10] : tableau de entier) : entier /* Fonction qui renvoie la somme des éléments d'un tableau */ var // Déclarations i, somme : entier ' respectivement indice et somme du tableau début // Corps pour i de 1 à 10 faire somme <- somme+tableauEntier[i] finPour retourner somme fin // fin de l'algorithme De même, il est possible de retourner un tableau : Procédure insérerElément(es ancienTab[1..10] tableau de caractère; élément : caractère) /* Procédure qui insère un élément dans un tableau trié. Attention, le tableau est modifié ! Si le tableau original est plein, soit le dernier élément est perdu : (['a', 'c', 'd'], 'b') => ['a', 'b', 'c'] soit l'élément à insérer est ignoré : (['a', 'c', 'd'], 'e') => ['a', 'b', 'd'] */ var // Déclarations i, j : entier ' respectivement indices du nouveau et de l'ancien tableau nouvTab : tab[1..10] de caractère début // Corps j<-1 pour i de 1 à 10 si (élémentInséré = 'OUI' ou tableau[j] < élément) alors nouvTab[i] <- ancienTab[j] i <- i+1 // passer à l'élément suivant de l'ancien tableau sinon nouvTab[i] <- élément élémentInséré <- 'OUI' // l'élément a été inséré finSi finPour ancienTab <- nouvTab fin Notez la présence de l'indicateur "es" avant le paramètre modifiable dans la procédure. Le cas le plus fréquent de modification du contenu d'un paramètre concerne les tableaux. 3 Variables structurées Si on manipule des personnes, rien n'est plus gênant de devoir toujours utiliser plusieurs variables pour la même personne. Exemple : Saisir les nom, prénom et âge de 10 personnes Solution 1 : on utilise un tableau pour chaque donnée enregistrerPers() var // Déclarations i : entier ' indice commun aux tableaux tNom, tPrénom[1..10] : tableau de chaîne ' noms & prénoms des personnes tAge[1..10] : tableau de entier ' âges des personnes début // Corps pour i de 1 à 10 faire afficher("personne n° ", i) saisir("nom =? ", tNom[i]) saisir("prénom =? ", tPrenom[i]) saisir ("âge =? ", tAge[i]) finPour fin Quels problèmes pose cet algorithme ? • il faut traiter autant de tableaux que de données, • chaque tableau est traité séparément pour une même personne • les indices doivent correspondre, sinon risque de traiter une donnée d'une personne et une autre d'une autre personne simultanément • il n'est pas possible de retourner le tableau car on ne peut retourner qu'une seule donnée à la fois une fausse solution serait d'utiliser un tableau à deux dimensions, mais toutes les données seraient alors du même type et l'algorithme deviendrai difficile à lire. Solution 2, utiliser un tableau d'éléments structurés : enregistrerPers() var // Déclarations i : entier ' indice commun aux tableaux tPers[1..10] : tableau de structure personne nom : chaîne ' nom de personne prénom : chaîne ' prénom de personne âge : entier ' âge de personne FinStructure début // uploads/Litterature/ 02i-algo02.pdf