Algorithmique II
Pr. Mohammed EL AMRANI
m-elamrani@[Link]
S2 : Informatique appliquée
Faculté des Sciences de Rabat
Table of contents
01 02 03
Rappel Récursivité Structures
Notion de base en Fonctions et procédures Gestion des enregstrements
Algorithmique récursives et de fichiers
04 05 06
Tri & Recherche Complexité Conclusion
Tri et recherche dans les Classes et calcul de la Exemples classiques
tableaux complexité algorithmique
03
Gestion d’Enregistrements et de
Fichiers
Les Enregistrements
Un enregistrement est un type de données défini par l’utilisateur et qui permet
de grouper un nombre fini d’éléments (ou champs) de types éventuellement
différents (alphabétique, numérique, logique,…) sous un nom commun.
A la différence des tableaux, qui ne permettent de grouper que des éléments du
même type, les enregistrements permettent de combiner différents types de
données.
Les éléments qui composent un enregistrement sont appelés champs.
Avant de déclarer une variable enregistrement, il faut avoir au préalable définit
son type, c’est à dire le nom et le type des champs qui le compose.
Le type d’un enregistrement est appelé type structuré
Les Enregistrements
Déclaration
Nom_Type : Enregistrement Exemple
Champ1 : Type1 Complexe : Enregistrement
Champ2 : Type2 Partie_reelle : réel
… Partie_imaginaire : réel
ChampN : TypeN fenreg
fenreg
x : Complexe
Déclaration
x {1, 2} { x=1+2i }
Nouvelle_variable : Nom_Type
Les Enregistrements
Remarques
Les types enregistrements font partie des types structurés. Concernant les champs,
il faut savoir que ceux-ci peuvent être de n’importe quel type (sauf un type fichier).
Mais :
Il n’existe pas de constante d’un type enregistrement.
Il n’existe pas d’opération (autre que l’affectation et le passage comme
paramètre) sur les enregistrements.
Les seules expressions d’un type enregistrement sont les variables de ce type.
Les Enregistrements
Pseudo code Langage C
struct point {
Point : Enregistrement float x;
x: réel float y;
}
y: réel struct point A; { déclarer une variable de type point}
fenreg
typedef struct point Point; { créer un alias appelé « Point » }
Point B; { utiliser l’alias « Point » pour déclarer la variable }
{déclaration de variables}
typedef struct point
A : Point { { On peut également créer un alias
float x; à la déclaration de la structure }
B : Point
float y;
} Point
Point C = { 1, 2 };
Les Enregistrements
Opération sur les structures
Point : Enregistrement
Accès à un champs :
x: décimal
<NOM_ENREGISTREMENT>.<NOM_CHAMPS>
y: décimal
fenreg
p1 : Point
p1.x ← 1 p1 ← {1, 2}
p1.y ← 2 écrire("L’abscisse est", p1.x, " et l’ordonnée est ", p1.y)
Affectation :
<variable_type_structure> ← <variable_type_structure>
p2 ← p1
p2.x ← 3
p2.y ← 4
écrire("L’abscisse est " , p2.x, " et l’ordonnée est ", p2.y)
Les Enregistrements
Exemple
Écrire une fonction permettant d’additionner deux nombres complexes
Complexe : Enregistrement Fonction add(x: Complexe, y: Comlexe): Complexe
Variable
real : réel z: Complexe
imag : réel début
[Link] ← [Link] + [Link]
fenreg [Link] ← [Link] + [Link]
Retourner ( z )
fin
Les Unions
Une union permet de désigner un seul espace mémoire, et de permettre d'y
accéder de plusieurs moyens différents. En somme, une union est un
regroupement de plusieurs types de données, qui permettent tous d’accéder
au même emplacement mémoire.
Déclaration
Nom_Type : Union
Champ1 : Type1
Champ2 : Type2
…
ChampN : TypeN
funion
Les Unions
Pseudo code Langage C
Exemple : Union union Decimal {
a: entier court short a;
b: entier long long b;
c: décimal float c;
funion };
u1 : Exemple union Decimal U1;
u1.a ← 10 U1.a = 10;
écrire(u1.a, u1.b, u1.c) printf("%d - %ld - %f",U1.a,U1.b,U1.c);
u1.b ← 70900 U1.b = 70900;
écrire(u1.a, u1.b, u1.c) printf("%d - %ld - %f",U1.a,U1.b,U1.c);
u1.c ← 3.14 U1.c = 3.14;
écrire(u1.a, u1.b, u1.c) printf("%d - %ld - %f",U1.a,U1.b,U1.c);
Les Énumérations
Un type énuméré est un type permettant de représenter des objets pouvant
prendre leur valeur dans une liste finie et ordonnée de noms.
Déclaration:
Type_enum : Énumérations
Valeur1,
Valeur2,
…
ValeurN
fénum
Les Énumérations
Pseudo code Langage C
SAISON : énumération { Déclaration de l'énumération }
PRINTEMPS, typedef enum {
ÉTÉ, ROUGE,
AUTOMNE, VERT,
HIVER, BLEU
fénum } COULEUR;
COULEUR: énumération = (rouge, vert, BLEU) { Déclaration d'une variable de type COULEUR }
COULEUR x;
x : COULEUR { Variable de type COULEUR } { Affectation de la valeur vert }
x ← VERT {Affectation de la valeur vert } x = VERT;
if x = VERT alors if (x == VERT) {
écrire(ma couleur préférée est x) printf("Ma couleur préférée est vert.\n");
fsi }
Les Enregistrements
Exercice
Un joueur de football est défini par :
Nom
Numéro
Poste (Défenseur, Milieu de terrain ou Attaquant
1. Définir la structure du joueur
2. Demander à l’utilisateur de remplir les informations de trois joueurs
3. Afficher les informations
Les Fichiers
Besoin ?
Jusqu’à maintenant nous n'avions vu que des Entrées/Sorties (E/S) sous la forme
d'entrée standard (usuellement le clavier, scanf) et de sorties standards (usuellement
l'écran, printf).
Ce type d’E/S atteint rapidement ses limites...
Utilisation des fichiers : sauvegarde/restitution des données entre le programme et le
disque dur.
ouvrir(fichier F1)
lire(F1, data)
fermer(F1)
Système d’Exploitation T=traiter(data)
ouvrir(fichier F2)
écrire(F2, T)
fermer(F2)
Mémoire Programme
Les Fichiers
Définitions
1) Un fichier est une suite de 0 et de 1 représentant de l’information codée avec un format
prédéfini.
2) Un fichier est une structure de données toutes de même type mais dont le nombre n’est pas
connu à priori.
3) Les fichiers sont conservés en mémoire secondaire (disques et bandes magnétiques,
disquettes, cassettes…) et se conserve tant que cette mémoire secondaire n’est pas effacée
ou endommagée.
4) Chaque fichier est désigné par un nom et possède des attributs tels que date de création,
taille, …
5) Un fichier est un ensemble structuré de données de même type, nommé et enregistré sur un
support lisible par l’ordinateur (disque dur, disquette, flash disque, CD Rom, ..etc).
6) Un fichier peut contenir des caractères (fichier texte), des programmes (fichier binaire), des
valeurs (fichier de données).
Les Fichiers
Types de fichiers
Il existe deux types de fichiers (définitions Wikipédia) :
Les fichiers textes : sont les fichiers dont le contenu représente uniquement une
suite de caractères imprimables, d'espaces et de retours à la ligne (.txt,...). Ils
peuvent être lus directement par un éditeur de texte.
Les fichiers binaires : sont les fichiers qui ne sont pas assimilables à des fichiers
textes (.exe, .mp3, .png, .doc,...). Ils ne peuvent pas être lus directement par un
éditeur de texte.
Les Fichiers
Mécanisme de fonctionnement des fichiers
L'accès à un fichier d’un support de stockage de masse (disque dur, disque
optique,...) est coûteux : temps de transfert, mécanique détériorable,...
Donc, il faut réduire le nombre d'accès ⇒ Utilisation d'une zone mémoire
appelée: zone tampon (buffer).
Ainsi, une instruction d'écriture (resp. lecture) dans le programme ne se traduira
pas immédiatement par une écriture (resp. lecture) sur le disque mais par une
écriture(resp. lecture) dans le buffer, avec écriture (resp. lecture) sur disque
quand le buffer est plein (resp. vide).
Les Fichiers
Mécanisme de fonctionnement des fichiers
Dans mon programme, le système d'exploitation fait :
Ouvrir un fichier. ⇒ créer un buffer(b) dans la RAM
Lire/écrire dans le fichier ouvert. ⇒ lire/écrire dans b
Fermer le fichier. ⇒ flusher le contenu de b, libérer b,...
ouvrir(fichier F1)
lire(F1, data)
fermer(F1)
T=traiter(data)
OS ouvrir(fichier F2)
écrire(F2, T)
fermer(F2)
Mémoire Buffer Programme
Les Fichiers
Types d’accès aux fichiers
Le type d’accès, c’est la manière dont la machine recherche les informations contenues dans
le fichier. On distingue :
L’accès séquentiel : On ne peut accéder à une information qu’en ayant au préalable
examiné celle qui la précède. Dans le cas d’un fichier texte, cela signifie qu’on lit le
fichier ligne par ligne.
L’accès direct (ou aléatoire) : on peut accéder directement à l’enregistrement de son
choix (i.e. quantité de données exprimée en octets), en précisant le numéro de cet
enregistrement. Mais cela veut souvent dire une gestion fastidieuse des déplacements
dans un fichier texte. Cette approche est adaptée aux fichiers binaires.
L’accès indexé : pour simplifier, il combine la rapidité de l’accès direct et la simplicité
de l’accès séquentiel. Il est particulièrement adapté au traitement des fichiers structurés
(avec des index), comme les bases de données.
Les Fichiers
Exercice 1
Écrire un algorithme permettant de de lire un fichier texte et d’afficher son contenu mot par mot.
Procédure lire_mots(nomFichier : chaîne de caractères)
Variable #include <stdio.h>
fichier: FICHIER ← ouvrir(nomFichier, "lecture")
void lire_mots(const char *nomFichier) {
mot : chaîne de caractères
finFichier : bouléen ← Faux FILE *fichier = fopen(nomFichier, "r");
Début char mot[100];
Tant que Non(finFichier) faire while (1) {
résultat ← lire(fichier, mot) fscanf(fichier, "%s", mot);
Si FDF(fichier) alors if (feof(fichier))
finFichier ← Vrai break;
fsi printf("%s\n", mot);
écrire(mot)
ftq
}
fermer(fichier) fclose(fichier);
Fin }
