Algorithmic and Data Structures Courses

Complexité et structures des
données
Elaboré par Mme Elkamel Hager


FSM de Monastir 2020-2021
1ere année Licence en Sciences de l’Informatique
Semestre 2
H. Jamoussi Elkamel , FSM 1
Alg Avancée




Plan du cours

Chapitre 1 : La récursivité
Chapitre 2 : Les enregistrements
Chapitre 3 : Les pointeurs
Chapitre 4 : Les Listes chainées
Chapitre 5 : Les Types Abstraits des données
Chapitre 6 : Les piles
Chapitre 7 : Les Files
Chapitre 8 : Les Arbres
Chapitre 9 : Les Arbres binaires de recherche
Chapitre 10 : Analyse et complexité des
algorithmes
H. Jamoussi Elkamel , FSM 2
Alg Avancée




1

, Chapitre 4 : Les Listes Chainées




H. Jamoussi Elkamel , FSM 3
Alg Avancée




Introduction : Notion d’une liste
• La liste est la forme la plus commune d’organisation de données.
• Définition : Une liste est une suite finie, éventuellement vide,
d’éléments de même type.
• Un élément dans la liste est caractérisé par sa position (suivant,
précédent, premier, dernier, kième)

• Notation : L = <e1, e2, e3,…, en>
On dit que : e2 succède l’élément e1 et précède l’élément e3.
e1 est le premier élément
en est le dernier élément
• Exemple : Liste d’entiers L = <10, 2, 37, 4>
Liste de personnes L= <Ali, Mohamed, Salah, Aya>
H. Jamoussi Elkamel , FSM 4
Alg Avancée




2

, Les opérations sur une Liste
• Pour manipuler une Liste il faut définir un
ensemble d’opérations.
• Ces opérations doivent être minimales tout en
étant suffisantes pour permettre de manipuler la
Liste.
• Ces opérations sont de deux types
– les Observateurs
– les Constructeurs.



H. Jamoussi Elkamel , FSM 5
Alg Avancée




Les opérations sur une Liste

• Les observateurs (méthodes d’accès Access Methods)
• informe sur l’état de la Liste sans la modifier
• exemple: tester si la liste est vide
• Les constructeurs
Les constructeurs permettent
• Soit la création d’une nouvelle Liste
• Soit la modification d’une Liste existante sans pour autant
retourner des informations à propos de la Liste
Remarque : Une opération est soit un observateur, soit un
constructeur, mais jamais les deux en même temps.

H. Jamoussi Elkamel , FSM 6
Alg Avancée




3

, Les conditions sur une opération
• Une opération est considérée comme une fonction totale ou
une fonction partielle dont la restriction s’exprime par des
conditions d’applications qu’on doit spécifier
• Ces conditions sont :
• Pré conditions: conditions supposées êtres vraies quand on fait
appel à une opération.
• Exemple: supprimer un élément d’une liste
pré conditions: la liste n’est pas vide
• les pré conditions d’une opération ne doivent jamais être vérifiées à
l’intérieur de celle-ci, mais par la méthode appelante.
• Post conditions: conditions supposées êtres vraies après appel à
une opération.
• Exemple: insérer un élément dans une liste
post conditions: la liste n’est pas vide
• les observateurs ne font aucune modification des objets, donc n’admettent
pas de post conditions.

H. Jamoussi Elkamel , FSM 7
Alg Avancée




Type Abstrait des Données Liste
• Type Liste
Paramètres : Elément
Utilise : Booléen, Position
Opérations :
constructeurs
créerListe :  Liste
• Post condition: la liste est crée et elle est vide
insérer : Elément  Position  Liste Liste
• Insère un élément à une position donnée. Dépendamment de la stratégie, on peut
développer d’autres opérations spécifiques d’insertion: fin, début, ..
• Pré conditions: position valide
• Post condition: la liste ne pas vide
supprimer : Position  Liste Liste
• Supprime un élément dans une position donnée.
• Pré conditions: Liste non vide et position valide
modifier : Elément  Position  Liste Liste
• Remplace l’élément se trouvant dans une position donnée par un autre
• Pré conditions: Liste non vide et position valide
H. Jamoussi Elkamel , FSM 8
Alg Avancée




4