STRUCTURE DES DONNEES

 

DEFINITION 

            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

 

A-LES TABLEAUX

Utilité des tableaux

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.

Déclaration d’un tableau

            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

Opérations sur les tableaux

Saisie des éléments d’un tableau

 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

 

 

Afficher les éléments d’un tableau

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

 

 

Recherche dans un tableau

            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é.

Recherche l’élément minimum d’un tableau.

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

 

 

Trace d’exécution :

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

 

 

B-ENREGISTREMENTS

Définitions

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.

 

Déclaration d’un type structuré

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

 

 

 

Définition d’une variable de type structuré

            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

Accès à un champ d’un enregistrement

            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.

 

EXERCICES

CONTROLE SE CONNAISSANCES

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

 

CORRIGES

 CONTROLE SE CONNAISSANCES

1- Une structure de données est une manière d’organiser les données pour faciliter les traitements.  

 -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.

2 -Limites des tableaux :

   -les données sont du même type, on ne peut pas utiliser les entiers et les caractères dans un même tableau.

   -Les données présentes dans un tableau sont contigües c.-à-d. côte-à-côte dans la mémoire, ce qui entraine que la taille du tableau est fixe.

    -On ne peut ni ajouter une case à la fin d’un tableau, ni insérer une case au milieu.

3 : Tableau, enregistrement, listes chainées, piles, files.

4 : Graphes, arbres

 

EXERCICE I :

1. Cet algorithmique calcule la somme de 05 notes et fait la moyenne.

2. La ligne N°4 déclare un tableau.

3. S←0 et S←S+ Notes[i]

4.

Ligne

i

Instructions

écran

10

1

0+12

 

10

2

12+8

 

10

3

20+14

 

10

4

34+6

 

10

5

40+10

12

 

 

Moyenne=10

 

EXERCICE II :

1. Lignes 6,7et10

2. Lignes 20,21 et 22.

3. Lignes 14,15 et 16.

4. La ligne initialise la variable Min.

5. C’est un algorithme recherche le minimum d’une liste.

 

EXERCICE III :

 

1. initialise un tableau

 

2. déclare les 6 voyelles de l’alphabet

 

3. déclare et affiche un tableau de neuf notes

 

4. calcule les carres des 5 premiers nombres entiers.