Revision sheet: Structures de données fondamentales en informatique

📋 Plan du Cours

1. Définition, structure et opérations fondamentales des listes en informatique
2. Principes et opérations des piles basées sur le modèle LIFO
3. Concept de types abstraits de données et leur implémentation
4. Implémentation des listes, piles et files avec tableaux et listes chaînées
5. Fonctionnement et insertion dans les listes chaînées
6. Exemple d’implémentation des listes abstraites en Python avec fonctions récursives

📖 1. Définition, structure et opérations fondamentales des listes en informatique

🔑 Notions clés & Définitions

• Liste : Structure de données permettant de regrouper des données, composée d'une tête et d'une queue.
• Fonction cons : Fonction permettant de créer une nouvelle liste en ajoutant un élément en tête d'une liste existante.
• Nombre d'éléments présents dans : Compter le nombre d'éléments dans une liste à l'aide de la fonction compte.
• Souvent noté : Une liste L est composée de 2 parties : sa tête (souvent noté car), qui correspond au dernier élément ajouté à la liste, et sa queue (souvent noté cdr) qui correspond au reste de la liste.

📝 Points essentiels

• Les opérations fondamentales incluent la création d'une liste vide, la vérification si une liste est vide, l'ajout en tête, la suppression de la tête, et le comptage des éléments.
• La fonction cons permet de construire une nouvelle liste en ajoutant un élément en tête, en chaînant plusieurs cons pour former des structures imbriquées.

💡 À retenir

Comprendre la composition interne d'une liste et les opérations de base permet de la manipuler efficacement.

📖 2. Principes et opérations des piles basées sur le modèle LIFO

🔑 Notions clés & Définitions

• Pile : Structure de données où seul le dernier élément ajouté est accessible, suivant le principe LIFO.
• Principe LIFO (Last In First Out) : Principe selon lequel le dernier élément entré dans la pile est le premier à en sortir.

📝 Points essentiels

• Une pile permet uniquement de manipuler le dernier élément ajouté, suivant le principe LIFO.
• Les opérations principales incluent vérifier si la pile est vide, empiler (push), dépiler (pop), accéder au sommet, et connaître sa taille.
• L'opération pop retire et renvoie l'élément au sommet, modifiant la pile.
• Le sommet peut être consulté sans modification via l'opération sommet.

💡 À retenir

Une pile permet uniquement de manipuler le dernier élément ajouté, suivant le principe LIFO.

📖 3. Concept de types abstraits de données et leur implémentation

🔑 Notions clés & Définitions

• Liste chaînée : Structure de données où chaque élément est associé à une donnée et à l'adresse mémoire de l'élément suivant, ce qui facilite l'insertion d'éléments sans nécessiter de déplacement massif.
• Types abstraits : Concepts utilisés pour modéliser des structures logiques telles que les listes, piles et files, qui existent comme des vues intellectuelles indépendantes de leur implémentation concrète.
• Types de données : Catégories de données manipulables par un programme, qui peuvent être représentées concrètement de différentes manières selon le langage de programmation.

📝 Points essentiels

• Les listes, piles et files sont des types abstraits de données, modélisés par des algorithmes, et leur implémentation dépend du langage de programmation.
• Les tableaux sont des suites contiguës de mémoire avec taille fixe, nécessitant la création d'un nouveau tableau pour redimensionner.
• Les listes chaînées associent à chaque élément une donnée et l'adresse du suivant, facilitant l'insertion d'éléments sans déplacement massif.
• Les listes, les piles ou les files sont des "vues de l'esprit" présent uniquement dans la tête des informaticiens, on dit que ce sont des types abstraits de données (ou plus simplement des types abstraits).
• Pour implémenter les listes (ou les piles et les files), beaucoup de langages de programmation utilisent 2 structures : les tableaux et les listes chaînées.

💡 À retenir

Les listes, piles et files sont des types abstraits de données, modélisés par des algorithmes, et leur implémentation dépend du langage de programmation.

📖 4. Implémentation des listes, piles et files avec tableaux et listes chaînées

🔑 Notions clés & Définitions

• Tableau : Structure mémoire contiguë avec une taille fixe, utilisée pour stocker des éléments en séquence.

📝 Points essentiels

• Les tableaux sont des structures mémoire contiguës avec une taille fixe, utilisées pour stocker des éléments en séquence.
• Les tableaux dynamiques ont une taille variable, facilitant l'insertion d'éléments dans des structures comme listes, piles et files.
• L'insertion dans une liste chaînée consiste à modifier les pointeurs pour insérer un nouvel élément sans déplacer les autres.
• L'implémentation des piles et files peut s'appuyer sur ces structures selon les besoins de performance et flexibilité.
• Il est relativement facile d'insérer un élément dans une liste chaînée : File
• On retrouve dans les piles une partie des propriétés vues sur les listes.

💡 À retenir

Les structures mémoire sous-jacentes, comme les tableaux et les listes chaînées, influencent directement la gestion et la performance des types abstraits tels que les piles et les files.

📖 5. Fonctionnement et insertion dans les listes chaînées

🔑 Notions clés & Définitions

• Élément rentré dans la file : Un élément ajouté à une file, qui est une structure où les éléments sont insérés à une extrémité et retirés de l'autre, respectant l'ordre FIFO.

📝 Points essentiels

• Dans une liste chaînée, chaque élément contient une donnée et un pointeur vers l'élément suivant.
• La suppression d'un élément dans une liste chaînée nécessite également la mise à jour des pointeurs pour exclure l'élément supprimé.

💡 À retenir

La structure des listes chaînées permet une grande flexibilité pour insérer et supprimer des éléments en manipulant uniquement les pointeurs, sans nécessiter de déplacement des données.

📖 6. Exemple d’implémentation des listes abstraites en Python avec fonctions récursives

🔑 Notions clés & Définitions

• SupprEnTete(L) : Une fonction qui retourne un couple contenant la tête de la liste abstraite L et la queue correspondante, permettant d'accéder séparément au premier élément et au reste de la liste.
• Queue contient : AjoutEnTete(5,L)

📝 Points essentiels

• Les fonctions sur listes abstraites peuvent être définies récursivement, par exemple pour compter les éléments ou tester si la liste est vide.
• La fonction ajouteEnTete utilise cons pour ajouter un élément en tête d'une liste abstraite.
• La fonction supprEnTete retourne la tête et la queue d'une liste abstraite, facilitant la manipulation récursive.
• L'utilisation de fonctions récursives permet de traiter élégamment les opérations sur les listes abstraites en Python.
• L=vide() => on a créé une liste vide

💡 À retenir

Les listes abstraites peuvent être implémentées simplement en Python avec des tuples, et les fonctions récursives permettent de manipuler efficacement ces structures en accédant à la tête et à la queue.

📊 Tableaux de Synthèse

Comparaison des structures de stockage

Type de structure	Contiguïté mémoire	Facilité d'insertion	Facilité de suppression
Tableau	Contiguë	Facile si fin	Facile si début
Liste chaînée	Non contiguë	Facile à insérer n'importe où	Facile à supprimer n'importe où

⚠️ Pièges & Confusions Fréquentes

1. Confusion entre liste et tableau, notamment en termes de gestion de la mémoire.
2. Confusion entre pile et liste, notamment en ce qui concerne l'accès aux éléments.
3. Erreur dans la compréhension du principe LIFO pour les piles.
4. Confusion entre liste chaînée simple et double, notamment pour l'insertion et la suppression.
5. Mauvaise utilisation des fonctions récursives, notamment en oubliant la condition de terminaison.
6. Confusion entre types abstraits et leur implémentation concrète.
7. Erreur dans la manipulation des pointeurs dans les listes chaînées.

✅ Checklist Examen

1. Comprendre la définition et la structure d'une liste.
2. Maîtriser les opérations fondamentales sur les listes.
3. Connaître le principe LIFO et ses opérations.
4. Différencier liste chaînée, tableau, pile et file.
5. Savoir implémenter une liste avec tableau ou liste chaînée.
6. Comprendre l'insertion dans une liste chaînée.
7. Utiliser des fonctions récursives pour manipuler des listes abstraites.
8. Différencier liste, pile et file dans leur comportement.
9. Identifier les avantages et inconvénients des structures mémoire.
10. Appliquer les concepts de types abstraits de données.
11. Manipuler efficacement la tête et la queue dans une liste chaînée.
12. Éviter les erreurs courantes dans la gestion des pointeurs.