ALGORITHME
STRUCTURES
ET
LISTE/PILE/FILE
Mr KHATORY: PARTIE 3
1
LES STRUCTURES
Encore plus puissant que les tableaux, les structures permettent de déclarer des types
personnalisés.
Chaque variable dans la structure représente un champ.
Chaque champ représente une case ;
STRUCTURE <nom_structure>
{
champ1 : type;
champ2 : type;
}
Les champs peuvent être de n’importe quel type … même structurés.
Exemple :
STRUCTURE POINT
{ Abscisse : REEL
Ordonne : REEL
}
N.B : contrairement aux tableaux, on peut avoir des valeurs de types différents dans les cases 2
LES STRUCTURES
Écrire un algorithme qui permet de calculer la distance entre deux points
ALGORITHME
STRUCTURE POINT
{ Abscisse : REEL
Ordonne : REEL
} Pour accéder à un champ de la structure :
VAR PT1,PT2 : POINT
Dist : REEL
DEBUT
ECRIRE (" Donner l’abscisse et l’ordonnée du premier point: ")
LIRE(PT1. Abscisse,[Link])
ECRIRE (" Donner l’abscisse et l’ordonnée du deuxième point: ")
LIRE(PT2. Abscisse,[Link])
Dist Racine( Carre([Link])+ Carre(PT2. Abscisse-PT1. Abscisse) )
ECRIRE(" la distance entre ces deux points est : ",Dist)
FIN
3
LES STRUCTURES
STRUCTURE ETUDIANT
{ NOM : CHAINE
NOTE : REEL
Classement :ENTIER
}
VAR ETUD : ETUDIANT
DEBUT
[Link] "MOUJTAHID" Pour accéder au champ NOM de l'étudiant: [Link]
[Link]19.5
[Link] 1
FIN
La structure la plus utilisée pour manipuler des données est le tableau
LISTE_ETUD: TABLEAU [1..100] de ETUDIANT
NOM NOTE Classement
LISTE_ETUD[1] AHMED 17 3
LISTE_ETUD[2] ATIKA 13 24
MOHA 8 70
LISTE_ETUD[3]
4
……. ………. …….
LISTE
Problème: ajout et suppression d'un étudiant de la liste ?
Inconvénient du tableau:
pour insérer un élément dans un tableau:
il faut d'abord déplacer (décalage vers la droite d'une case) tous les éléments
qui sont en amont de l'endroit où l'on souhaite effectuer l'insertion,
pour supprimer un élément du tableau:
il faut déplacer (décalage vers la gauche d'une case ) tous les éléments qui
sont en amont.
LISTES chaînées
une liste simplement chaînée est en fait constituée de maillons ayant la possibilité de
pointer vers une donnée accessible et modifiable par l'utilisateur ainsi qu'un lien vers le
maillon suivant.
5
LISTE
La figure suivante représente de façon schématique un élément de ce type :
Donnée Pointeur sur le
utilisateur Maillon suivant
Une liste chaînée étant une succession de maillons, dont le dernier pointe vers une
adresse invalide (NULL); voici une représentation possible :
NULL
6
LISTE
Au vu de l'utilisation des listes chaînées, il se dessine clairement quelques fonctions indispensables :
Initialisation
Ajout d'un élément
Suppression d'un élément
Accès à l'élément suivant
Accès aux données utilisateur
Accès au premier élément de la liste
Accès au dernier élément de la liste
Calcul de la taille de la liste
Suppression de la liste entière
Le principal problème des listes simplement chaînées est l'absence de pointeur sur l'élément
précédent du maillon, il est donc possible de parcourir la chaîne uniquement du début vers la fin
7
LISTE
1:
AJOUT D’UN
P
ELEMENT
8
LISTE
1:
AJOUT D’UN P
ELEMENT
2:
9
LISTE
1: P
SUPRESSION
D’UN ELEMENT
2:
10
LISTE
1: P
SUPRESSION
D’UN ELEMENT
2:
11
LISTE
1:
AJOUT D’UN P
ELEMENT
2:
1: P
SUPPRESSION
D’UN ELEMENT
2:
12
LISTE
A la différence des listes simplement chaînées, les maillons d'une liste doublement chaînée
possèdent un pointeur sur l'élément qui les précèdent :
Figure : représentation d'un élément d'une liste doublement chaînée.
13
PILE
EMPILER
Les piles peuvent être représentées comme une pile d'assiettes
vous pouvez ajouter des assiettes au sommet de la pile
lorsque vous voulez en enlever une, il s'agit de la dernière ajoutée
DEPILER
On parle de liste LIFO (Last In First Out).
Les piles ne sont que des cas particuliers de listes chaînées dont les éléments ne peuvent être
ajoutés et supprimés qu'en FIN de liste (QUEUE).
De ce fait la manipulation s'en trouve grandement simplifiée puisqu'elle ne nécessite que deux
fonctions :
Une fonction pour ajouter un élément au sommet de la pile
Une seconde pour le retirer
14
FILE
Une File est une liste linéaire particulière : DEFILER
On ne peut ajouter qu'en queue,
consulter qu'en tête,
et supprimer qu'en tête.
ENFILER
Comme pour une file d'attente ... !
Les files sont aussi appelées structures FIFO pour First In First Out,
c-à-d : premier-entré-premier-sorti.
15
FIN
16