Algorithmique et Structures des Données 2: Exercice Guide

Ce document présente une série d'exercices pratiques sur les listes chaînées, destinés aux étudiants de première année en informatique. Il couvre la manipulation de listes simplement et doublement chaînées, la gestion de données complexes comme les polynômes ou les profils clients, ainsi que des opérations courantes telles que la recherche, l'insertion, le tri et le classement.

Les listes chaînées : saisie et affichage

Une liste chaînée est une structure de données dynamique composée d'éléments appelés nœuds, où chaque nœud contient une donnée et un pointeur vers le nœud suivant (ou précédent dans le cas d'une liste doublement chaînée).

Exercice 1 : Liste simplement chaînée d'entiers positifs

Objectif : Saisir une liste d'entiers positifs terminée par un entier négatif, puis afficher la liste.

Algorithme SaisieAffichageListeSimple
  Initialiser liste à vide
  Répéter
    Lire entier n
    Si n >= 0 alors
      Créer un nouveau nœud avec valeur n
      Ajouter ce nœud à la fin de la liste
    Fin Si
  Jusqu'à ce que n < 0

  Afficher la liste depuis le premier nœud jusqu'au dernier
Fin Algorithme

Exercice 2 : Liste doublement chaînée avec affichage inverse

Reprendre l'exercice précédent en utilisant une liste doublement chaînée. L'affichage doit se faire dans l'ordre inverse (du dernier nœud au premier).

Algorithme SaisieAffichageListeDoubleInverse
  Initialiser liste doublement chaînée vide
  Répéter
    Lire entier n
    Si n >= 0 alors
      Créer un nouveau nœud avec valeur n
      Ajouter ce nœud à la fin de la liste
    Fin Si
  Jusqu'à ce que n < 0

  Afficher la liste depuis le dernier nœud jusqu'au premier
Fin Algorithme

Stockage et affichage selon un ordre donné

Exercice 3 : Liste simplement chaînée des nombres inférieurs à un entier saisi

On saisit un entier limite, puis on stocke dans une liste simplement chaînée tous les nombres inférieurs à cette limite. L'affichage se fait dans l'ordre décroissant.

Algorithme StockageNombresInferieurs
  Lire entier limite
  Initialiser liste vide
  Pour i de limite - 1 à 0 par pas -1
    Créer un nœud avec valeur i
    Ajouter ce nœud en tête de la liste
  Fin Pour

  Afficher la liste du premier au dernier (ordre décroissant)
Fin Algorithme

Exercice 4 : Liste doublement chaînée avec choix de l'ordre d'affichage

Reprendre l'exercice 3 avec une liste doublement chaînée. L'utilisateur choisit l'ordre d'affichage : croissant ou décroissant.

Algorithme StockageNombresDoubleOrdre
  Lire entier limite
  Initialiser liste doublement chaînée vide
  Pour i de 0 à limite - 1
    Créer un nœud avec valeur i
    Ajouter ce nœud à la fin de la liste
  Fin Pour

  Lire choix d'affichage (croissant/décroissant)
  Si choix = croissant alors
    Afficher la liste du premier au dernier
  Sinon
    Afficher la liste du dernier au premier
  Fin Si
Fin Algorithme

Recherche et insertion dans une liste chaînée

Exercice 5 : Recherche d'un entier X dans une liste

On recherche un entier X dans une liste chaînée d'entiers. Si X est trouvé, on affiche ses positions d'occurrence et sa fréquence.

Algorithme RechercheEntier
  Initialiser position à 1, fréquence à 0
  Initialiser pointeur au début de la liste
  Tant que pointeur ≠ null faire
    Si pointeur.valeur = X alors
      Afficher "X trouvé à la position" position
      fréquence ← fréquence + 1
    Fin Si
    pointeur ← pointeur.suivant
    position ← position + 1
  Fin Tant que

  Si fréquence = 0 alors
    Afficher "X non trouvé"
  Sinon
    Afficher "Fréquence de X :" fréquence
  Fin Si
Fin Algorithme

Exercice 6 : Insertion d'un caractère dans une liste chaînée

L'algorithme permet d'insérer un caractère dans une liste chaînée de caractères à une position choisie par l'utilisateur : début, fin, ou à droite/gauche d'une position P.

Algorithme InsertionCaractere
  Lire caractère c
  Lire choix position (début, fin, droite de P, gauche de P)
  Selon choix faire
    Cas début :
      Insérer c en tête de liste
    Cas fin :
      Insérer c en fin de liste
    Cas droite de P :
      Trouver nœud à la position P
      Insérer c après ce nœud
    Cas gauche de P :
      Trouver nœud à la position P
      Insérer c avant ce nœud
  Fin Selon
Fin Algorithme

Représentation et manipulation de polynômes

Exercice 7 : Représentation d'un polynôme par une liste simplement chaînée

Chaque nœud représente un monôme avec deux champs : coefficient et puissance. Par exemple, le polynôme 3*X^4 + 2*X - X^3 + 2 est représenté par la liste :

• Coefficient : 3, Puissance : 4
• Coefficient : 2, Puissance : 1
• Coefficient : -1, Puissance : 3
• Coefficient : 2, Puissance : 0

On suppose que le nombre de monômes est fourni par l'utilisateur.

Algorithme SaisieAffichagePolynome
  Lire nombreMonomes
  Initialiser liste vide
  Pour i de 1 à nombreMonomes
    Lire coefficient c
    Lire puissance p
    Créer nœud avec (c, p)
    Ajouter nœud à la fin de la liste
  Fin Pour

  Afficher la liste dans l'ordre de saisie
Fin Algorithme

Modifications demandées :

• Afficher la liste dans l'ordre décroissant des puissances.
• Afficher les monômes ayant une puissance paire.

Algorithme AffichageDecroissant
  Trier la liste par ordre décroissant des puissances
  Afficher la liste
Fin Algorithme

Algorithme AffichageMonomesPairs
  Pour chaque nœud dans la liste faire
    Si nœud.puissance mod 2 = 0 alors
      Afficher nœud.coefficient et nœud.puissance
    Fin Si
  Fin Pour
Fin Algorithme

Gestion de clients et sélection selon critères

Exercice 8 : Gestion de clientèle pour une société agricole

Chaque client est identifié par :

• Nom
• Fidèle (1 si fidèle, 0 sinon)
• Prix d'achat proposé

Les clients sont stockés dans une liste chaînée. Le gérant souhaite vendre uniquement aux clients fidèles, en privilégiant le prix d'achat le plus élevé.

Algorithme ChoixClient
  Initialiser meilleurPrix à -∞
  Initialiser clientChoisi à null
  Pour chaque client dans la liste faire
    Si client.fidèle = 1 et client.prix > meilleurPrix alors
      meilleurPrix ← client.prix
      clientChoisi ← client
    Fin Si
  Fin Pour

  Si clientChoisi ≠ null alors
    Afficher "Client choisi :" clientChoisi.nom "avec prix" meilleurPrix
  Sinon
    Afficher "Aucun client fidèle trouvé"
  Fin Si
Fin Algorithme

Vote et détermination du gagnant

Exercice 9 : Vote du président d'un comté national d'étudiants

Chaque candidat est identifié par son nom et un pourcentage de voix. Les candidats sont rangés dans une liste chaînée. Le candidat élu est celui avec le meilleur pourcentage.

Algorithme DeterminerPresident
  Initialiser meilleurPourcentage à -∞
  Initialiser president à null
  Pour chaque candidat dans la liste faire
    Si candidat.pourcentage > meilleurPourcentage alors
      meilleurPourcentage ← candidat.pourcentage
      president ← candidat
    Fin Si
  Fin Pour

  Afficher "Président élu :" president.nom "avec" meilleurPourcentage "%"
Fin Algorithme

Gestion d'une liste chaînée d'étudiants

Exercice 10 - Partie I : Saisie et affichage des étudiants avec meilleure et pire moyenne

Chaque étudiant est défini par :

• Nom
• Prénom
• Date de naissance
• Matricule
• Moyenne

L'algorithme saisit un nombre inconnu d'étudiants dans une liste chaînée, puis affiche l'étudiant avec la meilleure moyenne et celui avec la plus mauvaise.

Algorithme SaisieEtudiants
  Initialiser liste vide
  Répéter
    Lire informations étudiant (Nom, Prénom, DateNaissance, Matricule, Moyenne)
    Si Moyenne < 0 alors sortir de la saisie
    Créer nœud étudiant
    Ajouter nœud à la fin de la liste
  Jusqu'à fin saisie

  Initialiser meilleurEtudiant et pireEtudiant au premier nœud
  Pour chaque étudiant dans la liste faire
    Si étudiant.moyenne > meilleurEtudiant.moyenne alors
      meilleurEtudiant ← étudiant
    Si étudiant.moyenne < pireEtudiant.moyenne alors
      pireEtudiant ← étudiant
  Fin Pour

  Afficher "Meilleur étudiant :" meilleurEtudiant.Nom, meilleurEtudiant.Prénom, meilleurEtudiant.Moyenne
  Afficher "Pire étudiant :" pireEtudiant.Nom, pireEtudiant.Prénom, pireEtudiant.Moyenne
Fin Algorithme

Exercice 10 - Partie II : Calcul du rang d'un étudiant

Le rang d'un étudiant est déterminé en comptant le nombre d'étudiants ayant une moyenne strictement supérieure à la sienne, puis en ajoutant 1.

Exemple : Si 3 étudiants ont une moyenne supérieure à 15, alors le rang de l'étudiant ayant 15 est 4.

Algorithme CalculRangs
  Pour chaque étudiant E dans la liste faire
    compteur ← 0
    Pour chaque étudiant F dans la liste faire
      Si F.moyenne > E.moyenne alors
        compteur ← compteur + 1
    Fin Pour
    rangE ← compteur + 1
    Afficher E.Nom, E.Prénom, "rang :", rangE
  Fin Pour
Fin Algorithme

Exercice 10 - Partie III : Notes par matière et meilleur étudiant par matière

La moyenne est remplacée par un tableau de taille 3 contenant les notes en Mathématiques, Physique et Informatique.

L'algorithme doit afficher le meilleur étudiant dans chaque matière ainsi que le majeur de la classe (celui avec la meilleure moyenne générale).

Algorithme MeilleursEtudiantsParMatiere
  Initialiser meilleurMath, meilleurPhysique, meilleurInfo, meilleurGeneral à null
  Initialiser maxMath, maxPhysique, maxInfo, maxGeneral à -∞

  Pour chaque étudiant dans la liste faire
    moyenneGeneral ← (étudiant.notes[0] + étudiant.notes[1] + étudiant.notes[2]) / 3

    Si étudiant.notes[0] > maxMath alors
      maxMath ← étudiant.notes[0]
      meilleurMath ← étudiant
    Si étudiant.notes[1] > maxPhysique alors
      maxPhysique ← étudiant.notes[1]
      meilleurPhysique ← étudiant
    Si étudiant.notes[2] > maxInfo alors
      maxInfo ← étudiant.notes[2]
      meilleurInfo ← étudiant
    Si moyenneGeneral > maxGeneral alors
      maxGeneral ← moyenneGeneral
      meilleurGeneral ← étudiant
  Fin Pour

  Afficher "Meilleur en Mathématiques :" meilleurMath.Nom, meilleurMath.Prénom, maxMath
  Afficher "Meilleur en Physique :" meilleurPhysique.Nom, meilleurPhysique.Prénom, maxPhysique
  Afficher "Meilleur en Informatique :" meilleurInfo.Nom, meilleurInfo.Prénom, maxInfo
  Afficher "Majeur de la classe :" meilleurGeneral.Nom, meilleurGeneral.Prénom, maxGeneral
Fin Algorithme

Glossaire des termes clés

• Liste chaînée : Structure de données composée de nœuds liés entre eux par des pointeurs.
• Liste simplement chaînée : Liste où chaque nœud pointe vers le nœud suivant uniquement.
• Liste doublement chaînée : Liste où chaque nœud pointe vers le nœud suivant et le nœud précédent.
• Nœud : Élément d'une liste chaînée contenant une donnée et un ou plusieurs pointeurs.
• Insertion : Ajout d'un élément à une position donnée dans une liste.
• Recherche : Parcours d'une liste pour trouver un élément spécifique.
• Polynôme : Expression mathématique composée de monômes, représentée ici par une liste de coefficients et puissances.
• Monôme : Terme d'un polynôme, défini par un coefficient et une puissance.
• Fréquence : Nombre d'occurrences d'un élément dans une liste.
• Rang : Position d'un étudiant dans un classement basé sur les moyennes.

Points clés à retenir

• Les listes chaînées permettent une gestion dynamique des données avec insertion et suppression aisées.
• Les listes doublement chaînées facilitent les parcours dans les deux sens, utile pour affichage inversé.
• La recherche dans une liste chaînée nécessite un parcours séquentiel.
• La gestion de structures complexes comme les polynômes ou profils clients peut être modélisée efficacement avec des listes chaînées.
• Le classement et le tri peuvent être réalisés par des parcours et comparaisons successives.
• La flexibilité des listes chaînées permet d'adapter les algorithmes à différents besoins (affichage, insertion, recherche, tri).