Cours Algorithmes et complexité méthodes et explications
….
1.1 Les types
1.1.1 Les types de base
- Toute variable utilisée dans un algorithme doit avoir un type qui caractérise l’ensemble de valeur qu’elle peut prendre dans cet algorithme, ce type peut être un type de base (prédéfinit) ou un type composé qui est définit par l’utilisateur.
- Les types de base se divisent en 2 catégories : les types simples et les types complexe.
1.1.2 Les types simples
Les types de simple qui peuvent être utilisé pour représenter les variables d’un algorithme sont :
- Entier : la variable peut prendre des valeurs entières positives ou négatives, pour utiliser ce type on utilise le mot clé « entier »
- Reel : la variable peut prendre des valeurs réelles, pour utiliser ce type on utilise le mot clé « reel »
- Caractere : la variable peut prendre tout caractère qu’on peut saisir avec un clavier standard, pour utiliser ce type on utilise le mot clé « reel »
- Booleen : la variable a 2 valeurs VRAI ou FAUX, pour utiliser ce type on utilise le mot clé « booleen »
1.1.3 Les types complexes
Les types simples servent pour définir les types complexes qui permettent de représenter des structures de données plus compliqués, ces types sont :
- Tableau :
o la variable est formée par l’union de plusieurs cases mémoire qui contiennent chacune le même type.
o la déclaration d’un tableau se fait comme suit : « nom : Tableau [i_deb .. i_fin] de type ».
o i_deb et i_fin représentent l’indice de début et l’indice de fin du tableau.
- Chaîne de caractère :
o C’est la concaténation de plusieurs caractères qui finissent par le marqueur de fin de chaîne. C’est ainsi un tableau de caractères qui contient comme dernier caractère un caractère spécial pour représenter le marqueur de fin de chaîne.
o La déclaration se fait comme suit : « nom : chaine [ Max ] »
o Max est le nombre maximum de caractère.
1.2 Définition d’un enregistrement
1.2.1 Utilité
Contrairement aux types de base les types composés sont définit par l’utilisateur. Les types de bases servent pour définir de nouveaux types composés. Ces nouveaux types servent pour représenter des structures de données plus complexes qu’on ne peut pas représenter par les types de bases.
Exemple :
Si on veut représenter les données relatives à une personne telle que le nom et l’âge dans une seule variable ou une seule structure de donnée, on ne peut pas faire ça avec les types de bases et particulièrement avec les tableaux. On peut utiliser un nouveau type appelé enregistrement qui contient 2 champs, un pour représenter le nom de type chaîne de caractère et le 2ème pour représenter l’age de type entier. On remarque qu’on ne peut pas représenter la personne par un tableau car elle est formée de 2 types différents.
Ainsi on définit le type personne par un enregistrement comme suit :
Personne = Enreg
nom : chaîne [30]
age : entier
FinEnreg
1.2.2 Définition
L’enregistrement est une structure de données (ou un type) composée, qui est formé par plusieurs autres structures de données de nature différentes. Il permet ainsi de les regrouper dans une seule structure de données.
1.2.3 Syntaxe
Nom = Enreg
Champ1 : type
…
Champs N : type
FinEnreg
On désigne par :
- Nom : représente le nom de l’enregistrement.
- Champs 1…N : les noms des champs qui constituent l’enregistrement.
- Type : est le type de chaque champ.
1.2.4 Représentation
Les enregistrements sont représentés en mémoire sous forme de suite de zones contiguës qui servent chacune à représenter les différents champs, ces zones sont de taille différentes puisque chaque champ a un type différent. Par exemple l’enregistrement personne sera représenter en mémoire comme suit :
Octet 1 Octet 2 … Octet 30 Octet
nom age
1.3 Utilisation d’un enregistrement
1.3.1 Déclaration
La déclaration d’un enregistrement se fait comme étant un nouveau type définit par l’utilisateur dans l’algorithme, il doit être déclaré dans la partie Type avant d’être utilisé comme type de variable dans la partie Var.
1.3.2 Accès
L’enregistrement qui est une structure de données composé de plusieurs champs n’est pas accessible dans sa totalité, donc pour faire un accès à un enregistrement on accède à tous les champs un par un. Et pour utiliser un champ on écrit le nom de la variable de type enregistrement suivi de « point » suivi du champ auquel on veut accéder : Nom_enregistrement.champ_desire
1.3.3 Exemple
On veut écrire un algorithme qui lit le nom, le prénom et la moyenne générale d’un étudiant puis il affiche si cet étudiant a réussi ou non selon que sa moyenne est >= 10 ou non. Utiliser un enregistrement pour représenter l’étudiant.
Algorithme Resultat
Type
Etudiant = Enreg
nom : chaîne [30]
prenom : chaîne [30]
MG : reel
R : caractere
FinEnreg
Var
E : Etudiant
Debut
Lire (E.nom)
Lire (E.prenom)
Lire (E.MG)
Si (E.MG >= 10) Alors
E.R 'A'
Ecrire (''Admis '')
Sinon
E.R 'R'
Ecrire (''Refusé '')
FinSi
Fin
1.4 Les types abstraits
Les enregistrements permettent de représenter des structures de données complexes et formées par des types non homogènes. Mais ils ne présentent pas une abstraction au niveau des structures de données de l’algorithme. Pour résoudre ce problème on fait recours à une généralisation du type enregistrement par les types abstraits. Ce qui donne une indépendance vis-à-vis d’une implémentation particulière et les données sont considérées d’une manière abstraite.
1.4.1 Définition
Un type abstrait permet de représenter les données, les opérations faites sur ces données et les propriétés de ces opérations, dans une même structure de données.
1.4.2 Exemple :
Si on veut représenter un Compte Bancaire par un type abstrait il sera composé des données et des opérations concernant les Comptes Bancaires :
- Les données seront :
- Les opérations sur les comptes bancaires:
- Les propriétés des opérations :
1.4.3 Signature d’un type abstrait
La signature d’un type abstrait de données est définie par :
La signature décrit la syntaxe du type abstrait mais elle ne le définie pas réellement. Ainsi pour l’exemple précédent la signature est :
- Les types des données :
- les opérations et leurs profils :
1.5 Exercices d’application
Exercice 1 : Saisie d’une fiche
Une fiche contient les coordonnées suivantes:
-Nom (chaîne de caractères de longueur 10)
-Prénom (chaîne de caractères de longueur 10)
-Age (entier)
-Note (réel)
Ecrire un algorithme puis un programme C qui permet de créer la structure ci-dessus, saisir une fiche et l'afficher.
Exercice 2 : Somme et produit de deux nombres complexes
Ecrire un algorithme puis un programme C qui lit deux nombres complexes C1 et C2 et qui affiche ensuite leur somme et leur produit.
On utilisera les formules de calcul suivantes :
Exercice 3 : Coordonnées d’un point
Créer une structure Point qui contient les champs suivants :
Ecrire un programme C qui permet de saisir 4 points, les ranger dans un tableau puis les afficher.
Exercice 4 : Tableau des employés
Ecrire un programme C qui permet de créer un tableau TabEmp qui contiendra les informations sur les 10 employés d’une entreprise (Matricule, Nom, Salaire, Etat_Civil), le remplir puis afficher le nombre d’employés dont le salaire est compris entre 500 et 700 D.
1.6 Solutions des exercices
Exercice 1 :
Algorithme Saisie_Fiche
Type
fiche=enreg
nom : chaine[10]
prenom : chaine[10]
age : entier
note : reel
FinEnreg
Var
f : fiche
Début
Lire (f.nom)
Lire (f.prenom)
Lire (f.age)
Lire (f.note)
Ecrire (f.nom, f.prenom,f.age,f.note)
Fin
Exercice 2 :
Algorithme CalculComplexe
Type
Complexe=enreg
Re : Réel
Im : Réel
FinEnreg
Var
C1, C2, S, P : Complexe
Début
Ecrire (‘’ Partie réelle du premier nombre :’’)
Lire (C1.Re)
Ecrire (‘’ Partie imaginaire du premier nombre :’’)
Lire (C1.Im)
Ecrire (‘’ Partie réelle du deuxième nombre :’’)
Lire (C2.Re)
Ecrire (‘’ Partie imaginaire du deuxième nombre :’’)
Lire (C2.Im)
S.Re = C1.Re + C2.Re
S.Im = C1. Im + C2.Im
Ecrire (‘’Somme=’’, S.Re, ‘’+’’, S.Im, ‘’i’’)
P.Re = (C1.Re * C2.Re) – (C1. Im * C2.Im)
P.Im = (C1.Re * C2.Im) + (C1. Im * C2.Re)
Ecrire (‘’Produit=’’, P.Re, ‘’+’’, P.Im, ‘’i’’)
Fin
Exercice 4 :
Algorithme Personnel
Constantes
n = 50
Types
Employé=Struct
Matricule : Entier
Nom : Chaîne
Sal : Réel
Etat_Civil : Caractère
Fin Struct
Tab = Tableau [1..n] de Employé
Variables
TabEmp : Tab
I, nb : Entier
Procédure Remplir (Var T :Tab)
Début
Pour i de1 à n faire
Ecrire (‘’ Matricule de l’employé :’’)
Lire (T[i].Matricule)
Ecrire (‘’ Nom de l’employé :’’)
Lire (T[i].Nom)
Ecrire (‘’ Salaire de l’employé :’’)
Lire (T[i].Sal)
Ecrire (‘’ Etat civil de l’employé :’’)
Lire (T[i].Etat_Civil)
Fin pour
Fin
Fonction Compter (T : Tab) : Entier
Début
Compter 0
Pour i de 1 à n faire
Si (T[i].Sal >=500) ET (T[i].Sal <=700) alors
Compter Compter + 1
Fin si
Fin pour
Fin
Début
Remplir (TabEmp)
Nb Compter (TabEmp)
Ecrire ( nb, ‘’employés touchent entre 500 et 700 Dt’’)
Fin
Chapitre 2 : Les pointeurs
Vue d’ensemble
Cette leçon présente la définition et l’utilisation des pointeurs.
Objectifs
Ce chapitre a pour objectifs de permettre aux étudiants d’acquérir les connaissances de base se rapportant aux objectifs spécifiques suivants:
Pré-requis
Durée
Eléments de contenu
2.1 Rappel
2.1.1 Mémoire centrale (MC)
La mémoire centrale mémorise les données en cours de traitement par l’unité de traitement (UT). Elle contient les instructions et les données du programme en cours. L’UT lit une instruction, les opérandes de cette instruction, calcule le résultat puis l’écrit dans la mémoire centrale. En entrée, l’UT lit une donnée depuis une unité d’Entré\sortie et l’écrit dans la MC et inversement pour une sortie.
2.1.2 Structure de la mémoire centrale
La mémoire centrale est composée de cellules mémoire. Une cellule est un ensemble de 8 circuits électroniques. Chaque circuit est capable de soutenir dans un de deux états :
Haut représente le bit 1
Bas représente le bit 0
Une cellule est donc un ensemble de 8 bits dit un octet (8 bits = 1 octet). Les cellules de la mémoire sont numérotées de 0 à n-1, avec n est le nombre de cellules qu’elle contient.
Pour mémoriser plus d’informations, on utilise deux cellules adjacentes (un mot) ou 4 cellules adjacentes (un double mot).
Une variable est en faite une petite zone mémoire issue de n octets que l’on s’alloue et dans laquelle les informations sont rangées.
2.1.3 La notion d’adresse
Lors de la compilation d’un programme, l’ordinateur réserve dans sa mémoire une zone mémoire pour chaque variable déclarée. C’est à cet endroit que la valeur de la variable est stockée. Il associe alors au nom de la variable l’adresse de stockage. Ainsi, pendant le déroulement du programme, quand il rencontre un nom de variable, il va chercher à l’adresse correspondante la valeur en mémoire.
En langage C, il est possible de mettre une valeur dans une variable à l’aide de l’opérateur = ou de la fonction scanf( ). L’adresse mémoire est accessible en faisant précéder la variable de l’opérateur &.
Exemple :
char car = ‘c’;
printf ("adresse de car %lx", &car);
2.2 Les pointeurs
2.2.1 Définition
Un pointeur est une variable qui a pour valeur l’adresse mémoire d’une autre variable sur laquelle il pointe. Le pointeur est déterminé par le type sur lequel il pointe (variable, premier élément d’un tableau, ….).
2.2.2 Déclaration d’un pointeur
En algorithmique, on déclare un pointeur en précédant son type de base par le caractère « ^ ».
Syntaxe :
Nom_pointeur : ^ type
Exemple 1 :
P : ^caractère déclarer un pointeur appelé P sur une variable de type caractère.
- La variable pointeur P a pour valeur l’adresse « 43 ». Elle pointe sur l’espace mémoire « P^ » à l’adresse 43 dont le contenu est le caractère « T ».
- La déclaration d’une variable de type pointeur a pour effet la réservation d’une case mémoire qui va contenir l’adresse de la variable pointé.
Exemple 2 :
Si on déclare 2 pointeurs Pe et Pf
- Pe pointe vers une variable de type entier ;
-Pf pointe vers une variable de type réel,
Ceci implique la création de deux variables qui contiennent respectivement l’adresse d’un entier et l’adresse d’un réel comme suit :
Pe : ^entier
Pf : ^reel
2.2.3 Création d’un pointeur
Pour utiliser la variable pointé il faut d’abord la créer, ce qui a pour effet de réserver un bloc en mémoire capable de stocker la valeur de cette variable. Pour créer une variable pointé, on utilise l’instruction Allouer.
Syntaxe :
Allouer (nom_pointeur)
Exemple :
Pour créer la variable pointé par Pe on écrit : Allouer (Pe), et pour créer la variable pointé par Pf on écrit : Allouer (Pf).
- L’instruction Allouer (P) :
2.2.4 Utilisation d’un pointeur
Pour accéder à la variable pointé par un pointeur appelé P on utilise l’opérateur ^.
Syntaxe :
P^ : désigne la variable pointée par P.
Exemple :
L’algorithme suivant stocke la valeur 10 dans une variable de type pointeur.
Algorithme Pointeur_element
Var
P : ^entier
Debut
Allouer (P)
P^ 10
Fin
2.2.5 Suppression d’une variable pointé
Lorsqu’une variable pointée n’a plus d’utilité, il est possible de la supprimer et de rendre disponible l’espace mémoire qu’elle occupe. L’instruction qui réalise cette tâche est « Liberer ».
Syntaxe :
Liberer (nom_pointeur)
Exemple :
L’exemple suivant montre l’effet de l’instruction « Liberer » sur la mémoire.
Algorithme exemple
Var
P : ^entier
Debut
Allouer (P)
P^ 10
Liberer (P)
P^ 4 {erreur}
Fin
- « Liberer (P) » supprime la variable pointé par P et libère l’espace mémoire occupé par cette variable. Par contre la variable pointeur « P » n’est pas supprimée mais son contenu n’est plus l’adresse de la variable pointé mais une adresse non significative.
Remarque :
- L’utilisation de la variable pointé après l’instruction Liberer provoque une erreur.
2.2.6 Arithmétiques sur les pointeurs
2.2.6.1 Initialisation d’un pointeur
Pour initialiser un pointeur on lui affecte une valeur constante appelé « Nil ». Cette constante signifie que le pointeur ne pointe sur rien.
Syntaxe :
P Nil
Exemple :
On peut aussi initialiser un pointeur à partir d’un autre pointeur comme le montre l’exemple suivant :
- Supposons qu’on soit dans la situation initiale illustrée par la figure a :
Si l’instruction : PQ est exécuté, nous passerons à la nouvelle situation illustrée par la figure b.
Dans ce cas, on a : P^ = Q^ = « Sousse »
- Si on modifie la valeur de Q^, P^ sera également modifié et restera égal à Q^.
- Par contre, si l’instruction : P^Q^ est exécuté. On passe à la nouvelle situation illustrée par la figure c.
Dans ce cas, on a également P^ = Q^ = « Sousse » ; Mais si l’on modifie la valeur de Q^, P^ ne sera pas modifié.
2.2.6.2 Affectation d’un pointeur à un autre
Le contenu d’une variable pointeur peut être recopié dans une autre variable pointeur grâce à l’instruction d’affectation, à condition que les 2 pointeurs soit de même type.
Exemple :
Les pointeurs P1 et P2 pointent sur un entier. L’instruction « P1 P2 » permet de copier l’adresse contenu dans P2 dans le pointeur P1. Donc P1 et P2 vont pointer vers la même variable.
2.2.6.3 L’opérateur d’adresse
L’opérateur d’adresse permet de récupérer l’adresse en mémoire d’une variable il se note « &». Comme le pointeur contient l’adresse d’une variable pointeur on peut utiliser l’opérateur d’adresse pour affecter à un pointeur l’adresse d’une autre variable et ainsi il va pointer vers cette nouvelle variable. La syntaxe est la suivante : « pointeur & variable »
2.2.6.4 Comparaison de pointeurs
- On peut comparer 2 pointeurs entre eux avec l’opérateur = ou <> à condition qu’ils ont le même sous type. Et on peut comparer la valeur Nil à n’importe quel pointeur quelque soit son sous-type.
- On peut aussi comparer les valeurs des variables pointées par 2 pointeurs.
2.2.6.5 Exemple
Algorithme Adresse
Var
P : ^entier
A : entier
Debut
Allouer (P)
A 10
P & A
Ecrire (A) {10}
Ecrire (P^) {10}
Liberer (P)
Fin
…
Chapitre 3 : Les listes
Vue d’ensemble
Ce Chapitre présente la définition et l’utilisation des listes
Objectifs
Ce chapitre a pour objectifs de permettre aux étudiants d’acquérir les connaissances de base se rapportant aux objectifs spécifiques suivants:
Pré-requis
Durée
Eléments de contenu
3.1 Introduction
Le principal problème des données stockées sous forme de tableaux est que celles-ci doivent être ordonnées : le "suivant" doit toujours être stocké physiquement derrière. Imaginons gérer une association. Un tableau correspond à une gestion dans un cahier : un adhérent par page. Supposons désirer stocker les adhérents par ordre alphabétique. Si un nouvel adhérent se présente, il va falloir trouver où l'insérer, gommer toutes les pages suivantes pour les réécrire une page plus loin, puis insérer le nouvel adhérent. Une solution un peu plus simple serait de numéroter les pages, entrer les adhérents dans n'importe quel ordre et disposer d'un index : une feuille où sont indiqués les noms, dans l'ordre, associés à leur "adresse" : le numéro de page. Toute insertion ne nécessitera de décalages que dans l'index. Cette méthode permet l'utilisation de plusieurs index (par exemple un second par date de naissance). La troisième solution est la liste chaînée : les pages sont numérotées, sur chaque page est indiquée la page de l'adhérent suivant, sur le revers de couverture on indique l'adresse du premier. Ainsi, l'insertion d'un nouvel adhérent se fera avec le minimum d'opérations. Nous intéressons dans ce chapitre de cette nouvelle structure de données, sa création et surtout les opérations de base sur une liste chaînée.
3.2 Définition
Les listes font parties des structures de données abstraites très couramment utilisées dans les programmes. Une structure de donnée abstraite est un type de donnée défini par l’utilisateur sous forme de deux composantes une pour représenter les données (les notations) et une pour représenter les opérations d’accès aux données et ses caractéristiques.
Une liste stocke un ensemble de données et permet de parcourir cet ensemble du début à la fin dans l'ordre. C’est une suite finie (éventuellement vide) d'éléments, Lorsque elle n’est pas vide, son premier élément est appelé tête et la suite constituée des autres éléments est appelée queue.
Remarque : Les listes servent pour représenter des structures de données dont la taille change souvent ou pour stocker des données dans l'ordre en ayant la possibilité de les mettre à jour quand il y a des changements.
3.3 Opérations sur les listes
Il existe un certain nombre d'opérations classiques sur les listes.
o au début de la liste
o à la fin de la liste
o à un rang donné
o résultat booléen
o résultat = rang de la première occurrence
o résultat = nombre d'occurrences
o caractérisé par sa valeur
o caractérisé par son rang
3.4 Représentation
3.4.1 Représentation graphique
3.4.2 Représentation des données
La structure de donnée qui permet de représenter une liste chaînée dans le cas général est déclarée comme suit :
Type
Cellule = enreg
valeur : type
suivant : ^Cellule
FinEnreg
Liste : ^Cellule
Ainsi le type Liste est un pointeur vers le type Cellule qui est un enregistrement formé de deux champs : un qui contient la valeur de l’élément donc le type peut être un type quelconque et le 2ème champ contient un pointeur vers la cellule suivante. C'est-à-dire il contient l’adresse de la cellule suivante. La dernière cellule ne pointe vers rien donc elle doit contenir la valeur Nil.
Le type Liste contient un pointeur vers le type Cellule qui contient l’adresse du 1er élément de la liste.
3.5 Algorithmes de quelques opérations sur les listes
Pour simplifier on va travailler sur une liste dont les valeurs sont de type entier. Alors la définition du type liste sera comme suit :
Type
Cellule = enreg
valeur : entier
suivant : ^Cellule
FinEnreg
Liste : ^Cellule
La 1ère fonction de base qu’on doit écrire pour pouvoir manipuler des données de type liste est la fonction ListeVide () qui prend en entrée une liste et retourne vrai si elle est vide et faux sinon.
Fonction ListeVide (liste1 : Liste) : Booleen
Debut
Si (liste1 = Nil) Alors
Retourner (Vrai)
Sinon
Retourner (Faux)
FinSi
Fin
La fonction PosFin () prend en entrée une liste et retourne un pointeur vers le dernière élément de la liste.
Fonction PosFin (liste1 : Liste) : Liste
Var listeAux : Liste
Debut
listeAux liste1
Si (listeAux <> Nil) Alors
Tantque (listeAux^.suivant <> Nil) Faire
listeAux listeAux^.suivant
Fintanque
FinSi
Retourner (listeAux)
Fin
La fonction AjouterTete () prend en entrée une valeur à ajouter en tête d’une liste donnée et retourne un pointeur vers le début de la nouvelle liste.
Cette fonction doit créer une nouvelle variable dynamique pour contenir la nouvelle cellule, puis remplir le champ valeur et le champ suivant de cette cellule ensuite mettre l’adresse de cette cellule dans le pointeur vers la tête de liste et retourner cette valeur.
Fonction AjouterTete (v : entier, L : Liste) : Liste
Var C : ^Cellule
Debut
Allouer (C)
C^.valeur v
C^.suivant L
L C
Retourner (L)
Fin
La fonction Ajouter_fin() prend en entrée une valeur à ajouter à la fin d’une liste donnée et retourne un pointeur vers le début de la nouvelle liste.
procedure ajouter_fin(liste1 : Liste, e : entier)
liste2 : Liste;
debut
oSi (liste1= Nil) Alors liste1 new couple(e, null)
sinon
/* parcours de la liste vers la fin */
Liste2 PosFin(liste1)
/*ajout de l’élèment e à la fin de la liste */
liste2.suivant new couple(e, null)
fisi /* nous pouvons ajouter le retour en tête de la liste */
fin ajouter_fin;
Cette fonction calcule le nombre des éléments de la liste. Elle prend comme argument à l’entrée une liste et retourne comme sortie un entier présentant la langueur de la liste.
function longueur(liste1 : Liste) : entier
x : entier
listeAux : Liste
début
x 0
listeAux liste1
Tantque (listeAux^.suivant <> Nil) Faire
x x + 1
listeAux listeAux^.suivant
Fintanque
retourner x;
fin longueur
Cette fonction permet de rechercher la position d’un élément dans une liste en supposant qu’il existe, sinon, la fonction retourne faux. Ses paramètres d’entrée sont alors la liste et l’élément recherché, et son paramètre de sortie étant un booleén.
function appartient(x : entier; liste1 : Liste) : booleén
liste2 : Liste
début
liste2 liste1
tantque (liste2 != null && liste2^.valeur <>x)
liste2 liste2^.suivant
fin tantque
si (liste2^.valeur <>x) alors
retourner (vrai)
sinon
retourner (faux)
fin si
fin appartient;
Chapitre 4 : Les Piles et les Files
Vue d’ensemble
Ce Chapitre présente la définition et l’utilisation des Piles et des files
Objectifs
Ce chapitre a pour objectifs de permettre aux étudiants d’acquérir les connaissances de base se rapportant aux objectifs spécifiques suivants:
Pré-requis
Durée
Eléments de contenu
4.1 Les piles
4.1.1 Présentation
Une pile est une suite de cellules allouées dynamiquement (liste chaînée) où l’insertion et la suppression d’un élément se font toujours en tête de liste.
L’image intuitive d’une pile peut être donnée par une pile d’assiettes, ou une pile de dossiers à condition de supposer qu’on prend un seul élément à la fois (celui du sommet). On peut résumer les contraintes d’accès par le principe « dernier arrivé, premier sorti » qui se traduit en anglais par : Last In First Out (figure 1).
La structuration d’un objet en pile s’impose lorsqu’on mémorise des informations qui devront être traitées dans l’ordre inverse de leur arrivée. C’est le cas, par exemple, de la gestion des adresses de retour dans l’exécution d’un programme récursif.
En supposant que les éléments de la pile sont des entiers, celle-ci se déclare de la façon suivante :
Types
Pile = ^Cellule
Cellule = Enreg
Elem : Entier
Suiv : Pile
FinEnreg
Var
P : Pile
4.1.2 Manipulation d’une pile
D’un point de vue manipulation, les contraintes d’accès sont matérialisées par les procédures et les fonctions suivantes :
Procédure Initialiser (Var P : Pile)
Début
P Nil
Fin
Fonction Pile_Vide (P : Pile) : Booléen
Début
Pile_Vide (P = Nil)
Fin
Procédure Empiler (x : Entier ; Var P : Pile)
Variables
Q : Pile
Début
Allouer (Q)
Q^.Elem x
Q^.Suiv P
P Q
Fin
Procédure Dépiler (Var x : Entier ; Var P : Pile)
Début
Si NON (Pile_Vide(P)) Alors
x P^ .Elem
Q P
P P^ .Suiv
Libérer (Q)
Sinon
Ecrire (“Impossible, la pile est vide”)
FinSi
Fin
4.2 Les Files
4.2.1 Présentation
Une file est une suite de cellules allouées dynamiquement (liste chaînée) dont les contraintes d’accès sont définies comme suit :
- On ne peut ajouter un élément qu’en dernier rang de la suite.
- On ne peut supprimer que le premier élément.
L’image intuitive d’une file peut être donnée par la queue devant un guichet lorsqu’il n’y a pas de resquilleurs. On peut résumer les contraintes d’accès par le principe « premier arrivé, premier sorti » qui se traduit en anglais par : First In First Out.
La structuration d’un objet en file s’impose en particulier lorsqu’une ressource doit être partagée par plusieurs utilisateurs : il y a formation d’une file d’attente.
