UFR MI

Support de cours
INITIATION A L’ALGORITHME
➢ CHI – Généralités et structures de contrôle
➢ CHII – Types énumérés, Tableaux et enregistrements
➢ CHIII – Algorithme procédural
➢ CHV- Fichiers
Dans ce cours, nous allons:
➢ Décrire les structure de données de type enuméré, tableaux
et enregistrements.
➢ Ecrire des algorithme pour les opérations de base sur ce
type de structure
➢ Utiliser ces structures de données pour resoudre des
problèmes concrets
I- Types énumérés
I-1- Motivation : Parfois, dans un programme on est obligé de prendre des
conventions (des codages) pour représenter certaines informations. Par exemple, pour
représenter un mois de l’année on peut décider de prendre des entiers avec 1 pour
janvier, 2 pour février, etc.
Le principe d’un type énuméré est de donner un nom symbolique pour chacune des
valeur que peut prendre une variable.
I-2- Définitions
Les types énumérés permettent à l’utilisateur de définir son propre type en indiquant
explicitement l’ensemble de ses valeurs..
I-3- syntaxe
Type
nom_type_enumere = (val1, val2, ..., valn)
❑ Exemple :
Type
Mois = (janvier, février, ..., décembre)
Jour = (lundi, mardi, mercredi, jeudi, vendredi, samedi, dimanche)
Couleur = (rouge, jaune, vert, bleu, violet)
Remarque: le programmeur utilisera le nom symbolique pour désigner une valeur
particulière du type
I-3- syntaxe (suite)
❑ Exemple :
Var
m: Mois
c: Couleur
DEBUT
m <- ‘’MAI ‘’
c <- ‘’VIOLET’’
m <- ‘c’ - - interdit car de types différents !
...
FIN
I-3- syntaxe (suite)
❑ Exemple : ❑ Remarque :
Var Les booléens sont un exemple de type
énuméré avec deux valeurs FAUX et VRAI.
m: Mois
c: Couleur Type
DEBUT Booléen = (FAUX, VRAI)
m <- MAI
c <- VIOLET
m <- c -- interdit car de types
différents !
...
FIN
II- Les tableaux
II-1- Contexte et justification
Jusqu’à présent, nous avons uniquement utilisé des variables simples qui
correspondaient à un unique emplacement en mémoire d’un type
particulier. Cependant, il est fréquent de devoir manipuler un grand nombre
(par forcément très grand d’ailleurs) de données du même type auxquelles
on applique les mêmes traitements.
II-2- Définition
Un tableau est une variable qui permet de rassembler sous un même nom
(celui de la variable) un nombre fini d’éléments ayant tous le même type.
II- Les tableaux
II-2- Définition (suite)
Un élément particulier d’un tableau est désigné en précisant son indice. On
parle alors de tableau à une dimension.
Il est peut être nécessaire de préciser plusieurs indices pour accéder à une
donnée. On parle alors de tableau à plusieurs dimensions.
Lorsqu’un tableau est défini, le nombre d’éléments qu’il peut contenir doit
être précisé (en général au travers de la spécification des valeurs possibles
des indices) et il ne pourra pas être changé par la suite. Ce nombre
d’éléments est appelé la capacité du tableau.
II- Tableaux de dimension 1
II-1- Définition
Un tableau à une dimension unidimensionnel ou est un tableau dont on
accède aux éléments (pour « lire » ou modifier leur valeur) en utilisant un
seul indice (ou index).
Ex :
II-2- Syntaxe
TABLEAU Nom_du_tableau [nombre de composants] : Type_des_composants
Ex : TABLEAU Notes [10] : Réel
II- Tableaux de dimension 1
II-3- Accès aux composants d’un tableau
Dans un tableau à une dimension un composant est repéré par un indice
Ex :

i : Entier
Notes [3] ← 14 - Notes [10] ← 3
Notes[i] représente la composante d’indice i .
II- Tableaux de dimension 1
II-4- Saisie des composants d’un tableau à une dimension

II-5- Saisie des composants d’un tableau à une dimension

Application : Ecrire un programme qui permet de saisir 5 notes dans un tableau et de les afficher.
II- Tableaux de dimension 1
II-6- Opérations sur tableau de dimension 1
II-6-1- Recherche séquentielle
La recherche séquentielle encore appelée méthode du drapeau utilise un drapeau pour initier la
recherche
❑ Méthode:
Etape1 : baisser le drapeau
Etape2 : parcourir le tableau pour rechercher un élément
Etape3 : lever le drapeau des que élément recherché est trouvé
Etape 4 : à la fin du parcours tester l’etat du drapeau. S’il est levé l’élément recherché est dans le
tableau sinon la recherche est considéré comme infructueuse
II-6- Opérations sur tableau de dimension 1
II-6-1- Recherche séquentielle (Suite)

Description
T[5] : tableau de 5 composants
i : indice de parcours du table
val: la valeur recherché
Pos : position de l’élément recherché
Drapeau: le drapeau
II- Tableaux de dimension 1
II-6- Opérations sur tableau de dimension 1
II-6-2- Recherche Dichotomique
La recherche Dichotomique se base sur le principe de la recherche dans un dictionnaire. Il est utiliser
pour rechercher un élément dans un tableau ordonné.
❑ Méthode:
Etape 1 : déterminer l’élément médian (au milieu du tableau). Puis le comparer à l’élément recherché.
Etape 2 : s’il est égale à l’élément recherché c’est fini
Etape 3 : si est plus petit, reprendre les étapes précédente sur la partie à droite de l’élément médian
Etape 4 : si est plus grand, reprendre les étapes précédente sur la partie à gauche de l’élément
médian
II-6- Opérations sur tableau de dimension 1
II-6-2 Recherche Dichotomique
Recherche manuelle
Application au tableau ci-contre (T) -1 8 12 20 32
II-6- Opérations sur tableau de dimension 1
II-6-2 Recherche Dichotomique (Algorithme)
II- Tableaux de dimension 1
II-6- Opérations sur tableau de dimension 1
II-6-3- Tri par sélection (du minimum)
La tri par sélection du minimum parcours le tableau pour rechercher l’indice du minimum. dès qu’il
l’a trouvé il le permute avec l’élément en fin de tableau. La taille du tableau est décrémenté puis le
même principe est exécuté sur ce nouveau tableau
❑ Méthode:
Etape 1 : supposer que le premier élément est le maximum.
Etape 2 : parcourir le tableau pour récupérer l’indice du maximum réel
Etape 3 : permuter le maximum réel avec l’élément en dernière position
Etape 4 : réduire la taille du tableau de 1
Etape 4 : reprendre le même principe
II- Tableaux de dimension 1
II-6- Opérations sur tableau de dimension 1
II-6-3- Tri par sélection (du maximum)
❑ Exemple :
II- Tableaux de dimension 1
II-6- Opérations sur tableau de dimension 1
II-6-3- Tri par sélection (algorithme)
II- Tableaux de dimension 1
II-6- Opérations sur tableau de dimension 1
II-6-4- Tri bulle (voir TD)
II- Tableaux de dimension 2
II-1- définition

Un tableau à 2 dimensions est interpréter comme un tableau à une dimension de L composants

dont chaque composant correspond lui-même à un tableau à une dimension de C composants. On
appelle L le nombre de lignes et C le nombre de colonnes du tableau. Un tableau à 2 dimension
contient donc L*C composants.
III- Tableaux de dimension 2
III-1- définition (suite)

III-2- Déclaration
TABLEAU Nom_du_tableau[Nombre_de_lignes,Nombre_de_colonnes] : Type_des_composants
Ex : TABLEAU A[10,5] : Entier
III- Tableaux de dimension 2
III-3- Saisie des éléments d’un tableau à 2 dimensions
III- Tableaux de dimension 2
III-3- Affichage des éléments d’un tableau à 2 dimensions
IV- Enregistrements
IV-1- Motivation
Un type enregistrement permet de définir des types structurés (ou complexes) qui ne peuvent pas être représentés par
les types élémentaires que nous avons déjà vus (Entier, Booléen, Réel, etc.), ni par un tableau.

EXEMPLES : Voici quelques exemples d’enregistrements :

– Un complexe est défini par une partie réelle et une partie imaginaire.
– Une date est composée d’un numéro de jour (1..31), d’un numéro de mois (1..12) et d’une année (strictement
positive).
– Un stage peut être défini comme un intitulé (une chaîne de caractères), une date de début et une date de fin (deux
dates), un nombre de places (entier).
– Une fiche bibliographique est définie par le titre du livre (Chaîne), les auteurs (noms et prénoms), la date de
parution, l’éditeur, le numéro ISBN (Chaîne), etc.
IV- Enregistrements
IV-2- Définition d’un type enregistrement
Un enregistrement est un type T qui est le produit cartésien de plusieurs types T1, T2, ..., Tn. À chaque composante de
type Ti est associé un identificateur choisi par le programmeur. Il permet de sélectionner la composante. Le couple
(identificateur, Type) est appelé un champ de l’enregistrement

Par exemple, le type correspondant à une date peut être décrit ainsi :
IV- Enregistrements
IV-2- Définition d’un type enregistrement (suite)
Intuitivement, un enregistrement permet donc de regrouper dans une même structure un ensemble d’informations
ayant entre elles un lien logique.

Intérêt : Les enregistrements permettent de manipuler simultanément un ensemble de données logiquement reliées.
Par exemple, pour avoir deux dates, il suffit de déclarer deux variables d1 et d2 du type Date plutôt que j1, m1, a1 et j2,
m2, a2 de type Entier.
IV-3- Déclaration d’une variable de type enregistrement
Un type enregistrement est avant tout un type. Il permet donc de déclarer des variables de ce type.
IV- Enregistrements
IV-4- Manipulation d’une variable de type enregistrement
Sur les variables de type enregistrement, un seul opérateur existe l’affectation. Il consiste à copier toutes les
composantes de l’enregistrement.
Tous les autres traitements doivent être explicitement réalisés par le programmeur. Pour ce faire, il peut accéder
individuellement à chaque composante grâce à son identifiant. La composante (le champ) se comporte alors
exactement comme tout autre variable du même type que cette composante.
Remarque : Il est conseillé d’écrire des sous-programmes réalisant les opérations usuelles sur le type enregistrement :
voir sous-programmes et types abstraits de données.
Par exemple, si d est une variable de type Date, on peut accéder au jour de cette date en écrivant d.jour. On peut alors
l’écrire, le lire, le comparer... et plus généralement lui appliquer toutes les opérations définies sur le type.
Attention : Lorsqu’on utilise « . », il est nécessaire que l’expression à gauche soit d’un type Enregistrement et qu’à
droite se trouve un identificateur correspondant à un nom de champ du dit enregistrement. Ces vérifications sont
réalisées par le compilateur.
IV- Enregistrements
IV-4- Manipulation d’une variable de type enregistrement (algorithme)
UFR MI