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.