CHAPITRE II
STRUCTURE DE DONNEES STATIQUES
UTS/UFR-ST/MPCI-1/Algorithmique/2023-24/B. ZERBO
1
STRUCTURE DE DONNEES STATIQUES
Objectif
Connaître les structures de données statiques
UTS/UFR-ST/MPCI-1/Algorithmique/2023-24/B. ZERBO 2
Plan
Introduction
I- Les tableaux
II- Les types énumérés
III- Les structures
IV- Autres types
UTS/UFR-ST/MPCI-1/Algorithmique/2023-24/B. ZERBO 3
INTRODUCTION
UTS/UFR-ST/MPCI-1/Algorithmique/2023-24/B. ZERBO 4
Structures de données statiques
Introduction
Une structure de données est une manière particulière de stocker et
d’organiser des données dans un ordinateur de façon à pouvoir être
utilisées efficacement
Différents types de structures de données existent pour répondre à
des problèmes très précis
Une structure de données statique est une structure de données dont
la taille ne change pas au cours de l’exécution du programme
UTS/UFR-ST/MPCI-1/Algorithmique/2023-24/B. ZERBO 5
Structures de données statiques
Introduction
Elément essentiel pour l’efficacité des algorithmes
Permettent d’organiser la gestion des données
Une structure de données ne regroupe pas
nécessairement des objets du même type
UTS/UFR-ST/MPCI-1/Algorithmique/2023-24/B. ZERBO 6
I- LES TABLEAUX
UTS/UFR-ST/MPCI-1/Algorithmique/2023-24/B. ZERBO 7
Structures de données statiques
I- Les tableaux
Les tableaux
Pour des données nombreuses et de même nature, il est plus
pratique de les ranger dans un tableau.
Un tableau peut avoir une dimension, on parle alors de vecteur
Un tableau peut avoir plusieurs dimensions, on dit qu’il est
multidimensionnel
La taille d’un tableau doit être définie avant son utilisation et ne
peut plus être changée.
Les seules opérations possibles sont:
affecter un élément à un indice
lire un élément à un indice
UTS/UFR-ST/MPCI-1/Algorithmique/2023-24/B. ZERBO 8
Structures de données statiques
I- Les tableaux
Notion intuitive
Les tableaux
Un tableau à une dimension est formé d’éléments tous
de même nature et repérés par un index
Représentation graphique
Un tableau à une dimension est souvent représenté
comme une suite de cases avec un index pointant sur
une case.
UTS/UFR-ST/MPCI-1/Algorithmique/2023-24/B. ZERBO 9
Structures de données statiques
I- Les tableaux
Déclaration d’un tableaux
Syntaxe:
- Nom[Entier]: type
- Nom un identificateur, Entier une expression constante entière
positive et type un type prédéfini
Sémantique:
- type est le type des éléments du tableau,
- Nom le nom du tableau et
- Entier le nombre (maximum) d’éléments du tableau.
Exemple: On déclare un tableau tab de cinq réels de la façon
suivante :
tab[5]: réel
UTS/UFR-ST/MPCI-1/Algorithmique/2023-24/B. ZERBO 10
Structures de données statiques
I- Les tableaux
Déclaration d’un tableaux
Exemple: On déclare un tableau tab de cinq réels de la façon
suivante :
- tab[5]: réel
UTS/UFR-ST/MPCI-1/Algorithmique/2023-24/B. ZERBO 11
Structures de données statiques
I- Les tableaux
Accès à un élément d’un tableaux
Syntaxe:
L’accès un élément du tableau de d’identificateur Nom
se fait en désignant cet élément de la
façon suivante : Nom[index] où index est une
expression entière positive
Sémantique:
Ceci permet de désigner l’élément du tableau dont
l’index est celui désigné.
UTS/UFR-ST/MPCI-1/Algorithmique/2023-24/B. ZERBO 12
Structures de données statiques
I- Les tableaux
Tableaux: Exemple
Problème:
Les étudiants d’une classe ont obtenu chacun une note à un
certain examen. Nous voulons déterminer combien d’entre
eux ont une note supérieure à la moyenne de la classe.
UTS/UFR-ST/MPCI-1/Algorithmique/2023-24/B. ZERBO 13
Structures de données statiques
I- Les tableaux
Algorithme sans tableaux: Exemple
Demander le nombre n d’étudiant
– saisir les n notes tout en calculant la somme de ces notes
– diviser la somme par n pour obtenir la moyenne de la
classe
UTS/UFR-ST/MPCI-1/Algorithmique/2023-24/B. ZERBO 14
Structures de données statiques
I- Les tableaux
Algorithme sans tableaux: Exemple
– initialiser à zéro le le compteur des notes supérieures à la
moyenne de la classe
– redemander les n notes et comparer chacune d’elles à la
moyenne de la classe afin d’incrémenter le compteur des
notes supérieures à la moyenne de la classe
– afficher le résultat
UTS/UFR-ST/MPCI-1/Algorithmique/2023-24/B. ZERBO 15
Structures de données statiques
I- Les tableaux
Algorithme avec tableaux: Exemple
– saisir les n notes et les conserver
– calculer la moyenne de ces n notes
– déterminer combien, parmi ces n notes, sont
supérieures à la moyenne ainsi obtenue
UTS/UFR-ST/MPCI-1/Algorithmique/2023-24/B. ZERBO 16
Structures de données statiques
I- Les tableaux
Tableaux à deux dimensions
Un tableau à deux dimensions est formé d’éléments tous
de même nature et repérés par deux index (et non plus
un seul)
Un tableau à deux dimensions est souvent représenté
par un certain nombre de lignes et de colonnes. Un
élément est repéré par son numéro de ligne et son
numéro de colonne.
UTS/UFR-ST/MPCI-1/Algorithmique/2023-24/B. ZERBO 17
Structures de données statiques
I- Les tableaux
Tableaux à deux dimensions
Un tableau à deux dimensions est ce qu’on appelle une
matrice en mathématiques : un élément d’un tel tableau
est repéré par deux indices et se note souvent aij, les
indices étant i et j.
Exemple: On déclare un tableau tab de cinq lignes et
trois colonnes de réels de la façon suivante :
tab[5][3]: réel
UTS/UFR-ST/MPCI-1/Algorithmique/2023-24/B. ZERBO 18
Structures de données statiques
I- Les tableaux
Tableaux à deux dimensions: représentation graphique
Tableau à 3 lignes et 4 colonnes
Traditionnellement les lignes sont indexées par l’indice i et les colonnes
par l’indice j
tableau[1][2] = 2
tableau[3][2] = 8
3 2 5 7
9 4 1 4
7 8 5 9
UTS/UFR-ST/MPCI-1/Algorithmique/2023-24/B. ZERBO 19
Structures de données statiques
I- Les tableaux
Tableaux à deux dimensions: Algorithme de base
constante (nbligne:enier)8
(nbcolonne:enier)10
tableau
tableau[nbligne][nbcolonne]: réel
variable
ligne, colonne: entier
pour ligne allant de 1 à nbligne faire
pour colonne allant de 1 à nbcolonne faire
saisir(tableau[ligne][colonne])
fpour
fpour
UTS/UFR-ST/MPCI-1/Algorithmique/2023-24/B. ZERBO 20
II- TYPES ENUMERE
UTS/UFR-ST/MPCI-1/Algorithmique/2023-24/B. ZERBO 21
Structures de données statiques
II- Types énumérés
Le type énumération
Définition d’un type
- mot réservé: type
- Identificateur: commence par une majuscule
Type énumération : spécifie la liste des valeurs du type
- Définition du type :
type Jour{LUNDI, MARDI, MERCREDI, JEUDI, VENDREDI,
SAMEDI, DIMANCHE }
UTS/UFR-ST/MPCI-1/Algorithmique/2023-24/B. ZERBO 22
Structures de données statiques
II- Types énumérés
Le type énumération
Utilisation
variable
jour : Jour {Définition d’une variable de type Jour}
si jour = VENDREDI alors
afficher ( "Ce soir, c’est le week-end" )
fsi
Intérêt :
- lisibilité
UTS/UFR-ST/MPCI-1/Algorithmique/2023-24/B. ZERBO 23
III- ENREGISTREMENT
UTS/UFR-ST/MPCI-1/Algorithmique/2023-24/B. ZERBO 24
Structures de données statiques
III- Les enregistrements
LES ENREGISTREMENTS
Présentation:
Un enregistrement est un type de donnée permettant
d’avoir dans une même variable plusieurs informations
pouvant être de type différent. On parle d’enregistrement
ou de structure
Exemple traité
On veut définir un type de donnée correspondant à un
élève. Un élève a un nom, un prénom et une note.
UTS/UFR-ST/MPCI-1/Algorithmique/2023-24/B. ZERBO 25
Structures de données statiques
III- Les enregistrements
LES ENREGISTREMENTS
Définition du type
enregistrement typEleve
nom : chaîne
prénom : chaîne
note : entier
finenregistrement
On utilise le mot-clé « structure » pour déclarer le nouveau
type. On peut aussi utiliser le mot clé « enregistrement ».
typEleve est le nom du type créé. Il pourra s’utiliser comme
n’importe quel type simple.
« nom », « prénom » et « note » sont trois champs typés.
UTS/UFR-ST/MPCI-1/Algorithmique/2023-24/B. ZERBO 26
Structures de données statiques
III- Les enregistrements
Déclaration de variables
LES ENREGISTREMENTS
vareleve1, vareleve2, vareleve3 : typEleve
Utilisation des variables
[Link] "toto"
[Link] "olivier"
[Link] 12
[Link] [Link] {affectation d’un champs}
vareleve3 vareleve1 {affectation globale de l’enregistrement} é.
UTS/UFR-ST/MPCI-1/Algorithmique/2023-24/B. ZERBO 27
IV- AUTRES TYPES
UTS/UFR-ST/MPCI-1/Algorithmique/2023-24/B. ZERBO 28
Structures de données statiques
IV- Autres types
Types numériques classique
Lorsqu’on déclare une variable, il ne suffit pas de créer
une boîte (réserver un emplacement mémoire) ;
taille de la boîte (de l’emplacement mémoire) ;
type de codage utilisé.
UTS/UFR-ST/MPCI-1/Algorithmique/2023-24/B. ZERBO 29
Structures de données statiques
IV- Autres types
Types numériques classique
Si l’on réserve un octet pour coder un nombre
28 = 256 valeurs différentes.
- Cela peut signifier par exemple les nombres entiers de 1 à
256, ou de 0 à 255, ou de –127 à +128…
UTS/UFR-ST/MPCI-1/Algorithmique/2023-24/B. ZERBO 30
Structures de données statiques
IV- Autres types
Types numériques classique
Si l’on réserve deux octets,
- on a droit à 65 536 valeurs ; avec trois octets, 16 777 216,
etc.
Et là se pose un autre problème : ce codage doit-il
représenter des nombres décimaux ? des nombres
négatifs ?
UTS/UFR-ST/MPCI-1/Algorithmique/2023-24/B. ZERBO 31
Structures de données statiques
IV- Autres types
Types numériques classique
Le type de codage (autrement dit, le type de variable)
choisi pour un nombre va déterminer :
- Les valeurs maximales et minimales des nombres
pouvant être stockés dans la variable
- la précision de ces nombres (dans le cas de nombres
décimaux).
UTS/UFR-ST/MPCI-1/Algorithmique/2023-24/B. ZERBO 32
Structures de données statiques
IV- Autres types
Types numériques classique
UTS/UFR-ST/MPCI-1/Algorithmique/2023-24/B. ZERBO 33
Structures de données statiques
IV- Autres types
Autres Types numériques
Certains langages autorisent d’autres types
numériques, notamment :
Le type monétaire (avec strictement deux chiffres
après la virgule)
Le type date (jour/mois/année).
UTS/UFR-ST/MPCI-1/Algorithmique/2023-24/B. ZERBO 34
Structures de données statiques
IV- Autres types
Type alphanumérique
Type alphanumérique (également appelé type
caractère, type chaîne ou en anglais, le type string)
Dans une variable de ce type, on stocke des
caractères,
lettres,
signes de ponctuation,
espaces, ou même de
chiffres.
UTS/UFR-ST/MPCI-1/Algorithmique/2023-24/B. ZERBO 35
Structures de données statiques
IV- Autres types
Type alphanumérique
Le nombre maximal de caractères pouvant être
stockés dans une seule variable string dépend du
langage utilisé.
UTS/UFR-ST/MPCI-1/Algorithmique/2023-24/B. ZERBO 36
Structures de données statiques
IV- Autres types
Type booléen
Le dernier type de variables est le type booléen : on y
stocke uniquement les valeurs logiques VRAI et FAUX.
On peut représenter ces notions abstraites de VRAI et
de FAUX par tout ce qu'on veut : de l'anglais (TRUE et
FALSE) ou des nombres (0 et 1).
UTS/UFR-ST/MPCI-1/Algorithmique/2023-24/B. ZERBO 37
Structures de données statiques
IV- Autres types
Type booléen
Le type booléen est très économique en termes de
place mémoire occupée, puisque pour stocker une telle
information binaire, un seul bit suffit.
UTS/UFR-ST/MPCI-1/Algorithmique/2023-24/B. ZERBO 38
Bibliographie
- Cécile Balkanski, Nelly Bensimon, Gérard Ligozat, Algorithmique : Volume 1,
UniversitéParis XI I.U.T. d'Orsay Département Informatique 2003-2004
- Classe de TIG, Lycée B. de Laffemas, ALGORITHMIQUE : STRUCTURE DES
DONNEES ET DES TRAITEMENTS
- Cours C, Semaine 1, INPT–PAD, Algorithmique et programmation
- JC Régin - ASD - L2I – 2010, Algorithmique et Structures de Données
- Capocchi Laurent, Université de Corse - IUP NTIC2 2005/2006 . Algorithme et
Structure de Données
UTS/UFR-ST/MPCI-1/Algorithmique/2023-24/B. ZERBO 39