Revision sheet: Listes, piles, files et arbres

📋 Plan du Cours

1. Pointeurs et allocation dynamique
2. Recherche, tri et récursivité
3. Structures et gestion des fichiers
4. Listes simplement chaînées
5. Listes doublement chaînées
6. Piles et files
7. Applications des piles
8. Arbres binaires
9. Mesures récursives d’un arbre
10. Parcours d’un arbre binaire
11. Création et insertion d’éléments
12. Recherche et suppression d’un arbre

📖 1. Pointeurs et allocation dynamique

🔑 Notions clés & Définitions

• Adressage direct : L’adressage direct permet d’accéder au contenu d’une variable par le nom de cette variable.
• Pointeur : Une variable spéciale qui contient l’adresse d’une autre variable et qui est limité à un type de données.
• Allocation dynamique : L’allocation dynamique réserve la mémoire pendant l’exécution du programme lorsque le nombre ou la taille des données n’est pas prévisible à la compilation.

📝 Points essentiels

★ À maîtriser

📌 En C, l’opérateur & récupère l’adresse d’une variable et l’opérateur unaire * permet d’accéder au contenu de la variable pointée.

📌 La fonction malloc réserve un bloc de la taille demandée en octets et renvoie son adresse, ou NULL si la mémoire disponible est insuffisante.

📌 Après une allocation dynamique, il faut tester le pointeur retourné contre NULL, puis libérer la mémoire obtenue avec malloc, calloc ou realloc à l’aide de free lorsqu’elle n’est plus utilisée.

Compléments

📌 La fonction calloc alloue la mémoire pour un nombre donné d’éléments et initialise cette zone à zéro, tandis que realloc réduit ou augmente la taille d’un bloc existant.

💡 Astuce mémo

Adresse → pointeur → contenu

📖 2. Recherche, tri et récursivité

🔑 Notions clés & Définitions

• Récursivité : La récursivité est le mécanisme par lequel une fonction s’appelle elle-même.

📝 Points essentiels

★ À maîtriser

🔄 Processus — La recherche séquentielle compare successivement chaque élément du tableau avec l’objet recherché et s’arrête lorsque l’objet est trouvé ou que tous les éléments ont été examinés.

🔄 Processus — La recherche dichotomique découpe à chaque étape une collection triée autour d’un indice médian et poursuit la recherche dans la moitié inférieure ou supérieure selon la comparaison.

🔄 Processus — Le tri par sélection recherche le plus petit élément de la partie non triée et le permute avec le premier élément de cette partie.

🔄 Processus — Le tri à bulles compare des cases contiguës et fait remonter les plus petits éléments vers le début en répétant les passages dans le tableau.

🔄 Processus — Le calcul récursif de la factorielle utilise le cas de base 0! = 1 et la relation n! = n × (n−1)! pour les autres valeurs de n.

⚡ La recherche repose sur une relation d’équivalence telle que l’égalité, tandis que le tri repose sur une relation d’ordre total telle que l’infériorité ou l’égalité.

Compléments

🧮 Formule — Le tri par sélection et le tri à bulles présentés ont une complexité en temps de l’ordre de O(n²) dans le cas étudié.

💡 Astuce mémo

Chercher, ordonner, s’appeler

📖 3. Structures et gestion des fichiers

🔑 Notions clés & Définitions

• Fichier : Un ensemble de données stockées sur une mémoire de masse persistante, utilisée pour sauvegarder ou lire des informations.

📝 Points essentiels

★ À maîtriser

🔄 Processus — La manipulation d’un fichier suit l’ordre général ouverture, lecture ou écriture, puis fermeture.

📌 La fonction fopen associe un fichier physique à un descripteur FILE* et renvoie NULL si l’ouverture échoue.

📌 La fonction fread lit des éléments binaires dans un tampon et la fonction fwrite écrit des éléments binaires depuis un tampon, en utilisant leur taille et leur nombre.

⚡ Un fichier texte est une suite de caractères à accès séquentiel, tandis qu’un fichier binaire est organisé en enregistrements et permet notamment l’accès direct.

Compléments

📌 La fonction fseek déplace le descripteur d’un nombre d’octets calculé depuis SEEK_SET, SEEK_CUR ou SEEK_END, et renvoie zéro en cas de réussite.

• Les modes d’ouverture principaux sont r pour la lecture, w pour l’écriture avec remplacement, a pour l’ajout, r+ pour la lecture-écriture sur un fichier existant, w+ pour la lecture-écriture avec remplacement et a+ pour la lecture-écriture en ajout.

💡 Astuce mémo

Ouvrir → traiter → fermer

📖 4. Listes simplement chaînées

🔑 Notions clés & Définitions

• Liste simplement chaînée : Possède une tête, une queue et des maillons contenant chacun une information et un pointeur vers le maillon suivant.
• Liste simplement chaînée : Une structure composée d’éléments reliés par un pointeur suivant, chaque élément pointant vers le suivant et le dernier pointant vers NULL.

📝 Points essentiels

★ À maîtriser

🔄 Processus — L’initialisation d’une liste consiste à affecter NULL à debut et fin et zéro à taille avant toute autre opération.

🔄 Processus — L’insertion d’un maillon consiste à déclarer ou créer l’élément, allouer sa mémoire, remplir ses données, mettre à jour les pointeurs nécessaires et incrémenter la taille de la liste.

🔄 Processus — L’initialisation d’une liste simplement chaînée met les pointeurs debut et fin à NULL et la taille à zéro avant toute autre opération.

🔄 Processus — Pour insérer en tête, on crée un maillon, on lui affecte la donnée, on fait pointer son champ suivant vers debut, on actualise debut et, si la liste était vide, fin, puis on incrémente la taille.

🔄 Processus — La suppression en tête sauvegarde le premier maillon, avance debut vers son successeur, décrémente la taille, met fin à NULL si la liste devient vide, récupère la donnée puis libère le maillon.

• Les maillons d’une liste chaînée sont alloués dynamiquement et peuvent être dispersés en mémoire, contrairement aux éléments contigus d’un tableau.

⚡ Les tableaux offrent un accès direct au iᵉ élément sans dépendre de i, tandis que les listes chaînées nécessitent un parcours séquentiel depuis la tête et utilisent un espace supplémentaire pour les pointeurs.

• Une structure de liste contient généralement un pointeur debut vers le premier maillon, un pointeur fin vers le dernier maillon et un champ taille indiquant le nombre d’éléments.

Compléments

🔄 Processus — L’insertion après une position donnée est refusée si la position est inférieure à 1 ou supérieure ou égale à la taille, et sinon le nouveau maillon est relié entre l’élément courant et son successeur avant l’incrémentation de la taille.

🔄 Processus — L’affichage parcourt les maillons de debut jusqu’à NULL, tandis que la destruction supprime successivement les maillons en tête jusqu’à obtenir une taille nulle, puis libère la structure de liste.

💡 Astuce mémo

Tête → maillon → queue

📖 5. Listes doublement chaînées

🔑 Notions clés & Définitions

• Liste doublement chaînée : Une liste dont chaque maillon pointe à la fois vers son successeur et vers son prédécesseur.

📝 Points essentiels

★ À maîtriser

🔄 Processus — Lors d’une insertion dans une liste doublement chaînée, les pointeurs suivant et precedent du nouveau maillon ainsi que les pointeurs des maillons voisins sont actualisés, avec une mise à jour de debut ou fin si nécessaire.

🔄 Processus — La suppression par position traite le premier élément, le dernier ou un élément intermédiaire en reliant ses voisins, en récupérant sa donnée, en libérant sa mémoire et en décrémentant taille.

• Une liste doublement chaînée contient les pointeurs debut et fin ainsi qu’un champ taille, tandis que chaque maillon contient une donnée, un pointeur suivant et un pointeur precedent.

Compléments

🔄 Processus — L’initialisation d’une liste doublement chaînée affecte NULL à debut et fin et zéro à taille après l’allocation de la structure.

⚡ Une liste doublement chaînée permet un affichage direct de debut vers fin et un affichage inverse de fin vers debut grâce à ses deux pointeurs de liaison.

💡 Astuce mémo

Suivant et précédent

📖 6. Piles et files

🔑 Notions clés & Définitions

• Pile : Une structure linéaire dynamique de type LIFO, dans laquelle le dernier élément inséré est le premier extrait et seul l’élément au sommet est directement accessible.
• File : Une structure linéaire de type FIFO, dans laquelle le premier élément entré est le premier sorti, avec insertion en queue et suppression en tête.

📝 Points essentiels

★ À maîtriser

🔄 Processus — L’empilement crée un maillon, place la donnée dans ce maillon, le relie à l’ancien debut, actualise debut et incrémente taille.

🔄 Processus — Le dépilement retire le maillon pointé par debut, avance debut vers le maillon suivant, récupère la donnée, libère le maillon et décrémente taille, sauf si la pile est vide.

🔄 Processus — L’enfilement crée un maillon et l’ajoute à fin, en faisant aussi pointer debut vers ce maillon lorsque la file est vide, puis incrémente taille.

🔄 Processus — Le défilement retire le maillon pointé par debut, avance debut, récupère sa donnée, libère le maillon, décrémente taille et met fin à NULL si la file devient vide.

💡 Astuce mémo

LIFO contre FIFO

📖 7. Applications des piles

📝 Points essentiels

★ À maîtriser

🔄 Processus — Pour reconnaître un mot bien parenthésé, on empile chaque parenthèse ouvrante et on dépile la parenthèse correspondante à chaque parenthèse fermante; le mot est accepté si la pile n’est jamais vide lors d’une fermeture et est vide à la fin.

🔄 Processus — L’évaluation postfixée empile les valeurs et, pour chaque opérateur, dépile ses opérandes, applique l’opération dans l’ordre approprié, puis empile le résultat; la seule valeur restante est le résultat final.

🔄 Processus — La conversion infixe-postfixée envoie directement les opérandes dans la sortie, empile les opérateurs selon leur précédence et dépile les opérateurs de précédence supérieure ou égale avant d’empiler l’opérateur courant.

⚡ La notation infixée place les opérateurs entre leurs opérandes, la notation préfixée place l’opérateur avant ses opérandes et la notation postfixée place l’opérateur après ses opérandes.

Compléments

• L’expression postfixée 6 5 2 3 + 8 * + 3 + * a pour valeur finale 288.

💡 Astuce mémo

Empiler pour analyser et calculer

📖 8. Arbres binaires

🔑 Notions clés & Définitions

• Arbre binaire : Une structure dynamique non linéaire dont chaque nœud possède au maximum deux fils, appelés fils gauche et fils droit.

📝 Points essentiels

★ À maîtriser

⚡ Dans un arbre, la racine n’a pas de père, une feuille n’a pas de fils et un nœud interne possède au moins un fils.

• Un nœud d’arbre binaire contient une information, un pointeur vers le sous-arbre gauche et un pointeur vers le sous-arbre droit.

🧮 Formule — La hauteur d’un arbre vide vaut 0 et celle d’un arbre non vide vaut 1 plus le maximum des hauteurs de ses sous-arbres gauche et droit.

⚡ Un parcours en profondeur explore complètement une branche avant de passer à la suivante, tandis qu’un parcours en largeur visite les nœuds niveau par niveau.

Compléments

🧮 Formule — Le nombre de nœuds d’un arbre vide vaut 0 et celui d’un arbre non vide vaut 1 plus la somme des nombres de nœuds de ses deux sous-arbres.

💡 Astuce mémo

Racine, fils, feuilles

📖 9. Mesures récursives d’un arbre

📝 Points essentiels

★ À maîtriser

🔄 Processus — Le nombre de nœuds d’un arbre vide vaut 0 ; sinon il vaut 1 plus la somme des nombres de nœuds de ses sous-arbres gauche et droit.

🔄 Processus — Le nombre de feuilles d’un arbre vide vaut 0 ; celui d’un arbre dont la racine est une feuille vaut 1 ; sinon il est égal à la somme des nombres de feuilles de ses deux sous-arbres.

🔄 Processus — Le nombre de nœuds internes d’un arbre vide ou d’un arbre réduit à une feuille vaut 0 ; sinon il vaut 1 plus la somme des nombres de nœuds internes de ses sous-arbres.

💡 Astuce mémo

Vide = 0 ; sinon on décompose en sous-arbres

📖 10. Parcours d’un arbre binaire

📝 Points essentiels

★ À maîtriser

📌 Dans un parcours préfixe RGD, on traite la racine avant le fils gauche puis le fils droit.

📌 Dans un parcours infixe GRD, on traite le fils gauche, puis la racine, puis le fils droit ; appliqué à un arbre binaire de recherche, il fournit les valeurs dans l’ordre croissant.

📌 Dans un parcours postfixe GDR, on traite le fils gauche, puis le fils droit, puis la racine.

Compléments

🔄 Processus — La fonction DFS parcourt récursivement un arbre non vide en plaçant le traitement de la racine avant l’appel gauche pour le préfixe, entre les appels gauche et droit pour l’infixe, ou après l’appel droit pour le postfixe.

💡 Astuce mémo

RGD, GRD, GDR : la position de la racine change

📖 11. Création et insertion d’éléments

🔑 Notions clés & Définitions

• Arbre vide : Représenté par le pointeur NULL.

📝 Points essentiels

★ À maîtriser

🔄 Processus — La création d’un arbre à partir d’un élément et de deux sous-arbres consiste à allouer un nœud, à lui attribuer sa valeur et à placer les deux sous-arbres dans ses fils gauche et droit, puis à renvoyer un pointeur vers ce nœud.

🔄 Processus — L’insertion simple cherche récursivement un fils vide ; si l’arbre est vide, elle crée un arbre, si un fils est vide, elle y insère le nouvel élément, et sinon elle poursuit l’insertion du côté choisi, par exemple à gauche.

📌 Dans un arbre binaire de recherche contenant des entiers, les valeurs du sous-arbre gauche sont inférieures à la racine et celles du sous-arbre droit lui sont supérieures ou égales, les valeurs égales étant insérées à droite.

Compléments

🔄 Processus — Pour insérer une valeur dans un arbre binaire de recherche, on crée un nœud si l’arbre est vide ; sinon on compare la valeur à la racine et on poursuit récursivement à gauche si elle est plus petite, ou à droite dans le cas contraire.

💡 Astuce mémo

Créer, puis insérer selon la structure choisie

📖 12. Recherche et suppression d’un arbre

📝 Points essentiels

★ À maîtriser

🔄 Processus — Dans un arbre quelconque, la recherche renvoie 0 si l’arbre est vide, 1 si la racine contient la valeur cherchée, et sinon le résultat logique de la recherche dans les sous-arbres gauche et droit.

🔄 Processus — Dans un arbre binaire de recherche, la recherche renvoie 0 pour un arbre vide, 1 si la racine contient la valeur cherchée, puis explore le sous-arbre gauche si la valeur cherchée est plus petite que la racine et le sous-arbre droit sinon.

🔄 Processus — La suppression complète d’un arbre consiste à supprimer récursivement le sous-arbre gauche, puis le sous-arbre droit, avant de libérer la racine ; elle correspond donc à un parcours postfixe.

⚡ Dans un arbre quelconque, la recherche peut explorer les deux sous-arbres, tandis que dans un arbre binaire de recherche elle suit une seule branche grâce à l’ordre des valeurs.

Compléments

📌 Dans le cours, la suppression d’un nœud est limitée à la suppression d’une feuille, car supprimer un nœud possédant des fils impose de réorganiser ou de supprimer ses sous-arbres.

• Dans un arbre quelconque, le temps de recherche peut nécessiter le parcours de presque tous les nœuds, tandis que dans un arbre binaire de recherche il est proportionnel à la hauteur de l’arbre.

💡 Astuce mémo

Recherche guidée ou exhaustive ; suppression des feuilles

📊 Tableaux de synthèse

Tableaux et listes chaînées

Dimension	Tableau	Liste chaînée
Accès	Direct au iᵉ élément	Séquentiel depuis la tête
Mémoire	Éléments contigus	Maillons dispersés possibles
Taille	Fixée à l’avance	Adaptée au nombre d’éléments
Insertion et suppression	Peu flexibles	Réalisées par modification des pointeurs

Pile et file

Structure	Insertion	Suppression	Ordre
Pile	Tête	Tête	LIFO
File	Queue	Tête	FIFO

⚠️ Pièges & confusions fréquents

1. L’adressage indirect utilise l’adresse de la variable au lieu de son nom.
2. Les nombres complexes ne permettent pas directement ces opérations d’ordre ou d’égalité générale en C.
3. Les variables utilisées par les programmes sont généralement stockées en RAM, plus rapide que la mémoire de masse.
4. Le dernier maillon pointe vers NULL et non vers le premier maillon.
5. Le pointeur precedent du premier élément et le pointeur suivant du dernier élément valent NULL.
6. Une pile insère et supprime en tête, contrairement à une file.
7. Une pile vide à la fin ne suffit pas si elle est devenue vide trop tôt lors d’une fermeture.