Une structure de données est une manière d’organiser les données pour faciliter les traitements. On distingue plusieurs types de structure de données:
-Les structures linéaires: les tableaux, les enregistrements, les listes, les piles et les files.
-Les structures non linéaires: les arbres et les graphes
Exemple de l’algorithme de calcul de la moyenne de 12 notes.
Algorithme Moyenne
var n1,n2,n3,n4,n5,n6, n7,n8,n9,n10,n11,n12: réels;
Début
Ecrire («Entrer la première note»), Lire (n1);
Ecrire («Entrer la deuxième note»), Lire (n2);
Ecrire («Entrer la troisième note»), Lire (n3);
Ecrire («Entrer laurée note»), Lire (n4);
Ecrire («Entrer la cinquième note»), Lire (n5);
Ecrire («Entrer la sixième note»), Lire (n6);
Ecrire («Entrer la septième note»), Lire (n7);
Ecrire («Entrer la huitième note»), Lire (n8);
Ecrire («Entrer la neuvième note»), Lire (n9);
Ecrire («Entrer la dixième note»), Lire (n10);
Ecrire («Entrer la onzième note»), Lire (n11);
Ecrire («Entrer la douzième note»), Lire (n12);
Moy ← (n1+n2+n3+n4+n5+n6+n7+n8+n9+n10+N11+n12)/12;
Ecrire («La moyenne des douze notes est:», Moy);
Fin
On comprend que si on a beaucoup de notes à calculer, le travail deviendra très fastidieux. C’est pourquoi il faut rassembler toutes les variables en une seule, au sein de laquelle chaque valeur sera désignée par un numéro d’où la nécessité d’un tableau.
Définition
Un tableau est un regroupement de valeurs portant le même nom de variable qui sont repérées par un numéro. Il permet de ranger un nombre fini d’éléments de même type et selon une disposition bien définie.
Tableau NOTES
|
Indice |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
Valeur |
8 |
12 |
11 |
5 |
16 |
13 |
7 |
14 |
12 |
4 |
17 |
Le numéro qui permet de repérer chaque valeur s’appelle l’indice (ici les indices vont de 0 à 10).
Chaque fois que l’on veut désigner un élément du tableau, on fait figurer le nom du tableau, suivi de l’indice de l’élément, entre crochets.
On accède ainsi à la ième valeur d’un tableau en utilisant la syntaxe suivante:
Syntaxe:
Nom_du_tableau [indice]
Exemple: NOTES [6] /* donne la valeur 7 */
L’accès à un élément du tableau se fait par l’intermédiaire de son indice qui représente l’emplacement de l’élément dans le tableau: c’est l’accès direct. Elle se fait par adressage de chaque cellule. L’ordinateur se positionne directement sur une valeur connaissant son adresse.
Pour parcourir les éléments d’un tableau, il faut utiliser une boucle.
La formulation simple de la déclaration d’un tableau est la suivante:
Syntaxe:
nomTableau: Tableau [indice inférieure…indice supérieure] de type_de_données
Exemple:
Pour un tableau de 30 notes des élèves d’une classe, on note:
Tableau [1…30] de réel
Si tab est le nom du tableau, on écrit:
tab: Tableau [1…30] de réel
Si tab est un tableau de 10 entiers
tab [2] ←5 met la valeur 5 dans la deuxième case du tableau
En considérant le cas où a est une variable de type entier, a←tab[2] met la valeur de la deuxième case du tableau dans a c.-à-d. 5.
Pour saisir les variables d’un tableau données par un utilisateur, on utilise la syntaxe suivante
Syntaxe:
Lire (tab[i]);
On peut utiliser une boucle
Exemple:
|
Algorithme SaisieNotes var tab: Tableau [1…N] de réels var N, i: entiers; Début Pour i de 1 à N Faire Lire (tab[i]) ; FinPour FinSaisieNotes
|
Syntaxe:
Afficher(T[i]);
Exemple:
|
Algorithme AfficherNotes var tab: Tableau [1…N] de réels; var N, i: entiers; Début Pour i de 1 à N Faire Afficher (tab[i]) ; FinPour FinAfficherNotes
|
La recherche séquentielle ou recherche linéaire est un algorithme pour trouver une valeur dans une liste. L’accès dans une liste est dit séquentiel lorsqu’on passe en revue tous les éléments de la liste pour avoir accès à l’élément recherché.
On suppose que le tableau est déjà saisi.
Exemple:
|
Algorithme RechercheMinTableau const n=10; tab: Tableau [1…N] de réels var N, i: entier; var Min: entier; Début Pour i de 1 à N Faire Min ← tab[i]; Si tab[i] < Min alors Min ← tab[i]; FinSi FinPour Afficher (Min); FinRechercheMinTableau FinPour Retourner (Min); FinRechercheMin
|
Soit le tableau:
|
12 |
20 |
40 |
6 |
8 |
10 |
|
N°ligne |
Var |
Instruction |
Ecran |
|
|
|
|
Min=12 |
|
|
i=0 |
Tab[0]<12 FAUX |
Min=12 |
|
|
i=1 |
Tab[1]<12 FAUX |
Min=12 |
|
|
i=2 |
Tab[2]<12 FAUX |
Min=12 |
|
|
i=3 |
Tab[3]<12 VRAI |
Min=6 |
|
|
i=4 |
Tab[4]<6 FAUX |
Min=6 |
|
|
i=5 |
Tab[5]<6 FAUX |
Min=6 |
Un enregistrement est un type de données défini par l’utilisateur qui permet de regrouper un nombre fini d’éléments de types éventuellement différents sous un nom commun.
Les éléments qui composent un enregistrement sont appelés champs. A la différence des tableaux, qui ne permettent que les éléments du même type, les enregistrements permettent de combiner différents types de données.
Pour créer des enregistrements, il faut déclarer un nouveau type dit type structuré, basé sur d’autres types existants. Ce nouveau type peut être utilisé comme un type normal en déclarant une ou plusieurs variables de ce type.
Avant de déclarer une variable enregistrement, il faut avoir au préalable définir son type, c-à-d le nom et le type de champs qui le composent.
Syntaxe:
Type
Nom_Type=Enregistrement
Champ1: Type 1
Champ2: Type 2
….
Champ N: Type N
FinNom_type
Exemple:
|
Type Personne: Enregistrement Nom: chaine Prenom: chaine Age: Entier FinPersonne
|
Une fois qu’on a défini un type structuré, on peut déclarer des variables enregistrements exactement de la même façon que l’on déclare des variables d’un type primitif:
Syntaxe:
Varnom_variable: nom_enregistrement;
Exemple: Déclaration de deux variables pers1 et pers2 de type Personne
pers1, pers2: Personne
Alors que les éléments d’un tableau sont accessibles à travers leur indice, les champs d’un enregistrement sont accessibles à travers l’opérateur de champ qui est un simple point«.»
Syntaxe:
Nom_variable.Nom_champ
Exemple:
Pour accéder à l’âge de la variable pers2, on écrit tout simplementpers2.age
Affectation
L’affectation de valeurs aux différents champs d’une variable enregistrement se fait comme suit:
Syntaxe: variable.champ ←valeur;
Exemple: pers1.Nom←«Fati»
Lecture
Syntaxe:Lire(variable.champ);
Ecriture
Syntaxe: Ecrire (variable.champ);
Exemple: Soit un algorithme qui saisit des données des élèves E1 et E2 et calcule la différence de leurs notes.
Remarques:
1- Il n’existe pas de constante type enregistrement.
2-Les seules opérations sur les enregistrements sont l’affectation et le passage comme paramètre.
3-Les seules expressions d’un type enregistrement sont les variables de ce type.
4-Il n’y a pas de fonction (même prédéfinie) à résultat d’un type enregistrement.
1: Définir: structure de données, tableau.
2: Quelles sont les limites d’un tableau?
3: Cite 04 structures de données linéaires.
4: Cite 04 structures de données non linéaires.
5: Citer 03 structures de contrôle.
EXERCICE I: On donne l’algorithme suivant:
1. Algorithme
3. Variable i, S: entiers;
4. Notes: Tableau [1…5] d’entiers;
5. Début
6. S ← 0;
7. Pour i de 1 à 5 Faire
8. Ecrire«Entrer la note n°»;
9. Lire (Notes[i]);
10. S ← S +Notes[i];
11. FinPour
12. Ecrire(«Moyenne:», S/5);
13. Fin
Questions
1. Que fait cet algorithme?
2. Dire ce que fait la ligne N°4 de cet algorithme.
3. Relève 02 instructions d’affection.
4. Donner la trace d’exécution de cet algorithme pour le tableau: 12-8-14-6-10.
EXERCICE II:
1. Algorithme
2. var tab: Tableau [1…N] de réels
3. var N, i, Min: entiers;
4.
5. Début
6. Pour i de 1 à N Faire
7. Lire (tab[i]) ;
10. FinPour
11.
12. Pour i de 1 à N Faire
13. Min ← tab[1];
14. Si tab[i] < Min alors
15 Min ← tab[i];
16. FinSi
17. FinPour
18. Afficher (Min);
19.
20. Pour i de 1 à N Faire
21. Afficher (tab[i])
22. FinPour
23. Fin
Questions:
1. Identifier le module de saisie du tableau tab.
2. Identifier le module d’affichage tableau tab.
3. Identifier une structure alternative.
4. Que fait la ligne N° 13?
5. Que fait cet algorithme?
EXERCICE III: Dire ce que font les algorithmes suivants:
1.Algorithme
Tableau [1…5] des entiers;
var i entier;
Début
Pour i de 1 à 5 Faire
T[i] ← 0;
FinPour
Fin
2.Algorithme
T: Tableau [1….5] de caractères;
Début
T [0] ← «a»;
T [1] ← «e»;
T [2] ← «i »;
T [3] ← «o»;
T [4] ← «u»;
T [5] ← «y »;
Fin
3.Algorithme
Notes: Tableau [1…9] en numérique;
i: entier;
Début
Pour i allant de 1 à 9 Faire
Ecrire «Entrer la note numéro», i+1;
Lire Notes[i];
FinPour
Pour i allant de1 à 9 Faire
Ecrire Notes[i];
FinPour
Fin
4.Algorithme
Nb: Tableau [5] d’entiers;
Var i: entier;
Début
Pour i de 1 à 5 Faire
Nb [i] ← i*i;
FinPour
Fin
Merci de votre visite
Laissez un commentaire