Listes Chaînées

ALGORITHMIQUE AVANCÉE ET OPTIMISATION

Ce document couvre les concepts fondamentaux de l'algorithmique avancée, l'optimisation, et les structures de données essentielles pour les étudiants en L2 IRT. Il met l'accent sur la compréhension et l'application pratique des types abstraits de données, des structures de données, de la complexité algorithmique, des représentations de données (contiguës et chaînées), ainsi que des algorithmes de recherche et de tri.

Définitions Générales

• Type Abstrait de Données (TAD) : Une spécification mathématique d'un ensemble de données et des opérations applicables, sans détailler la représentation ou l'implémentation.
  Exemples : Tableau, liste, file, pile, ensemble, arbre.
  Caractéristiques : Nom, opérations (avec spécifications et complexité), mode d'utilisation, rôle/comportement, complexité temporelle.
  Nota : Un TAD est indépendant de son implémentation.

• Structure de Données : Une manière spécifique d'organiser et de stocker des données pour faciliter leur traitement (création, stockage, accès, extraction, suppression).
  Exemple : Une liste chaînée peut implémenter un TAD "liste".
  Relation TAD vs. Structure de Données: C'est le lien entre l'abstraction et la réalisation, la spécification et l'implémentation, le "quoi" et le "comment". Le choix d'une structure dépend du TAD, des contraintes et des objectifs du problème.

• Complexité : Mesure des ressources (temps, espace) nécessaires à l'exécution d'un algorithme. Elle permet de comparer l'efficacité des algorithmes.
  Notation Standard : Big (notation de Landau) pour mesurer la performance en fonction de la taille des données en entrée. Exemple : indique une complexité linéaire.

Représentation Contiguë de Données

Ce sont des structures stockant les données dans un espace mémoire adjacent.

• Exemples : Tableaux, Structures composées finies, Enregistrements.

• Avantages : Meilleure performance d'accès, utilisation optimale de la mémoire, simplicité d'implémentation.

• Inconvénients : Difficulté de modification (insertion/suppression), taille fixe prédéfinie, dépendance à l'ordre physique des données.

Les Tableaux

Un tableau est une structure de données qui permet de stocker des éléments de même type dans un espace mémoire contigu.

Caractéristiques

• Un tableau a un nom (identificateur).

• Les éléments sont stockés dans des cases contiguës (cellules) et accessibles par le nom du tableau et un indice.

• Peuvent être unidimensionnels (une seule ligne/colonne) ou multidimensionnels (plusieurs lignes/colonnes).

• Deux types :

  • Tableaux Statiques : taille fixe et prédéfinie.

  • Tableaux Dynamiques :taille variable.

• Utilité : Regrouper plusieurs variables de même nature sous un même nom.

Complexité et Opérations

• Complexité d'accès :

  • Tableau Statique : (temps d'accès indépendant du nombre de cellules).

  • Tableau Dynamique : Généralement , mais peut atteindre selon l'implémentation.

• Opérations applicables :

  • Création.

  • Initialisation (accès en écriture).

  • Consultation (accès en lecture).

  • Modification (mise à jour des éléments ou de la taille pour les dynamiques).

  • Tri.

  • Suppression (pour les dynamiques).

Tableaux Statiques

Déclaration/Création

Syntaxe :

Tableau Nom_du_Tableau[taille du tableau] en type_élément_du_tableau
Ou
Tableau Nom_du_Tableau[taille du tableau] de type_élément_du_tableau

Exemples :

Accès aux Cellules (Écriture ou Lecture)

L'accès se fait via le nom du tableau et l'indice de la cellule.

• Convention d'Indice : Nous adopterons la valeur 0 pour la première cellule (logique de gestion mémoire), tout en reconnaissant la validité de l'indice 1 (logique humaine).

• Accès en écriture :

  • nom_tableau[indice] ← valeur (affectation directe)

  • Lire (nom_tableau[indice]) (affectation depuis l'entrée standard)

• Accès en lecture :

  • nom_variable ← nom_tableau[indice] (récupération dans une autre variable)

  • Ecrire (nom_tableau[indice]) (affichage du contenu)

Exemple de Création et d'Accès

Algorithme Exemple
    Variable Nb en Entier
    Tableau Tab[10] d'Entiers
Début
    Tab[1] ← 5
    Ecrire("Entrer la valeur de la cellule 2")
    Lire (Tab[2])
    Nb ← Tab[1]
    Ecrire("T[2] contient : ", Tab[2])
Fin

Tri de Tableaux

Organiser le contenu d'un tableau selon un critère de comparaison des éléments.

• Objectifs du tri :

  • Hiérarchisation et lisibilité.

  • Facilitation de la recherche.

  • Facilitation des opérations de suppression/ajout.

  • Préparation à d'autres traitements (analyse de données).

• Algorithmes de tri : Choisis en fonction des objectifs, complexité temporelle, coût en mémoire, facilité d'implémentation et taille du tableau.

  • Tri par insertion

  • Tri par sélection

  • Tri à bulles

  • Tri rapide

  • Tri fusion

  • Tri par comptage

Les Enregistrements

Les enregistrements (ou structures) regroupent des données de types différents en une seule entité. Les "Structures composées finies" sont un cas particulier d'enregistrements avec des champs de longueur fixe.

Structure de type Enregistrement

Regroupe un ensemble de données de types différents en une seule unité, chaque élément étant associé à un nom (champ) pour lecture/modification.

• Les enregistrements peuvent avoir des champs de longueur variable, les rendant plus flexibles que les structures composées finies.

• Unenregistrement a un nom (identificateur).

• Les éléments sont appelés champs, généralement de taille fixe mais potentiellement variable. Ils peuvent être de types de base, pointeurs, structurés ou un mélange.

• Les structures à champs de taille fixe permettentune représentation contiguë ; celles à champs de taille variable peuvent ne pas le permettre.

• Utilité :

  • Regrouper des données de types différents mais apparentées.

  • Créer des entités complexes.

  • Gérer des enregistrements agrégés (fichiers, bases de données).

  • Améliorer la lisibilité du code.

  • Passer des données complexes en paramètre.

• Complexité d'accès aux champs : .

• Opérations applicables : Création d'instances, initialisation/consultation/modification des champs, suppression d'instances.

Déclaration/Création

Syntaxe de déclaration d'un type enregistrement :

STRUCTURE Nom_Structure
    champ_1 en type_1
    champ_2 en type_2
    *
    *
    champ_n en type_n
FIN STRUCTURE

Exemples :

STRUCTURE Point
    x en Entier
    y en Entier
FIN STRUCTURE

STRUCTURE Personne
    nom enChaine
    age en Entier
    sexe en Caractère
FIN STRUCTURE

Création d'une variable d'un type Enregistrement

Syntaxe de déclaration :

Nom_variable en Nom_Structure

Exemples :

A en Point
P1 en Personne

Nota : Les champs sontles propriétés des variables d'un type enregistrement. Ainsi, A (type Point) a les champs x et y ; P1 (type Personne) a les champs nom, age, et sexe.

Accès aux Champs

Utilise l'opérateur point (.) entre le nom de la variable et le nom du champ.

• Accès en écriture :

  • nom_variable.nom_champ ← valeur

  • Lire(nom_variable.nom_champ)

• Accès en lecture :

  • nom_variable ← nom_variable.nom_champ

  • Ecrire(nom_variable.nom_champ)

Exemple 1 : Point

Algorithme Exemple_Point
    Variable P1 en Point
Début
    Ecrire("Entrer l'abscisse du point : ")
    Lire (P1.x)
    Ecrire("Entrer l'ordonnée du point : ")
    Lire (P1.y)
    Ecrire("Le point P1 a pour coordonnées : ",P1.x, " et " , P1.y)
Fin

Exemple 2 : Personne

Algorithme Exemple_Personne
    Variable E1 en Personne
Début
    E1.nom ← "Moussa"
    E1.age ← 19
    E1.sexe ← 'M'
    Ecrire("Je suis : ", E1.nom, " de sexe : ", E1.sexe, " et j'ai " , E.age, "ans")
Fin

Les algorithmes de Recherche

Applicables aux tableaux, ces algorithmes visent à trouver une valeur cible. Deux types principaux sont abordés ici.

La Recherche Linéaire (ou Séquentielle)

Parcourt le tableau élément par élément depuis le début jusqu'à trouver la valeurcible ou atteindre la fin du tableau.

La Recherche Binaire (ou Dichotomique)

S'utilise sur un tableau trié. Elle divise le tableau en deux à chaque étape et compare la valeur cible avec l'élément médian, éliminant ainsi la moitié du tableau. Plus efficace que la recherche linéaire pour les grands tableaux triés.

FONCTION RechDicho(tableau[n]en Entier, valeur en Entier)
Variables
    first, milieu, last en Entier
DEBUT
    first ← 1
    last ← n // C'est longueur(tableau)
    TANT QUE first <= last FAIRE
        milieu ← (first + last) DIV 2
        SI tableau[milieu] = valeur ALORS
            RETOURNER milieu // La valeur cible a été trouvée
        SINON SI tableau[milieu] < valeur ALORS
            first ← milieu + 1
        SINON
            max ← milieu - 1
        FIN SI
    FIN TANT QUE
    RETOURNER -1*valeur // La valeur cible n'a pas été trouvée
FIN

Nota : Proposer un code qui fait la recherche Binaire mais qui retourne un booléen plutôt que lavaleur recherchée ou son opposée.

Listes Chaînées

Face aux limites des structures à représentation contiguë (statiques), les listes chaînées offrent une solution dynamique. Elles peuvent s'agrandir ou diminuer au fil du temps.

Définition

Une liste chaînée est un ensemble de nœuds de même nature, liés les uns aux autres par des pointeurs. Chaque nœud est une structure de données contenant un ou plusieurs champs de données et au moins un pointeur vers le nœud suivant.

Uneliste est un ensemble fini d'éléments , où est le premier élément. Si , la liste est vide.

Représentation

Bien qu'une représentation tabulaire soit possible (deux tableaux : un pour les éléments, un pour l'ordre), seule la représentation chaînée à base de pointeurs est abordée ici.

Deux approches pour la représentation chaînée :

1. Utilisation de deux structures de type Enregistrement.

2. Utilisation d'un pointeur et d'unestructure de type Enregistrement.

La première approche sera privilégiée dans ce cours.

Première Approche

Une structure Noeud pour les éléments et une structure Liste pour la liste.

STRUCTURE Noeud
    champ_1 en type_1
    champ_2 en type_2
    ...
    champ_n en type_n
    suivant en ^Noeud
FIN STRUCTURE

SRTUCTURE Liste
    premier en ^Noeud
FIN STRUCTURE

Note : La structure `Liste` n'a qu'un seul champ, un pointeur vers le premier élément (la tête de liste).

Accès et Traitements

L'accès aux éléments se fait en suivant les pointeurs, à partir du pointeur sur le premier élément (tête de liste). Quand un pointeur vaut`Nil`, c'est la fin de la liste.

Traitements Applicables

Une liste non exhaustive des traitements pour les listes chaînées :

Créer une liste vide

Fonction creerListe(L en Liste)
Début
    L.premier ← Nil
    retourner L
Fin

Insérer un élément en tête de Liste

Fonction RemplirNoeud( N en Noeud)
Début
    N.champ_1 ← valeur_1 // on peut aussi lire
    ... // les valeurs au clavier
    N.champ_n ← valeur_n
    N.suivant ← Nil
Fin

//Ajout d'un nœud en tête de liste
Fonction AjouterNoeud(L en Liste, N en Noeud )
Début
    N.suivant ← L.premier
    L.premier ← adresse (N)
    Retourner L
Fin

Insérer un élément en queue de Liste

1. Un pointeur `P2` est placé sur le premier élément.

2. Si le premier est `Nil`, le nouveau nœud devient le premier.

3. Sinon, `P2` parcourt la liste jusqu'à l'avant-dernier élément (celui dont le `suivant` est `Nil`).

4. Le `suivant` dudernier élément (`P2^.suivant`) pointe alors vers le nouveau nœud.

Fonction RemplirNoeud( N en Noeud)
Début
    N.champ_1 ← Valeur_1 // on peut aussi lire
    ...
    N.champ_n ← Valeur_n
    N.suivant ← Nil
Fin

//Ajout d'un nœud en queue de liste
Fonction AjouterNoeud(L en Liste, N en Noeud )
Variables p, p2 en ^Noeud
Début
    p ← adresse(N)
    Si L.premier = Nil alors
        L.premier ← p
    sinon
        p2 ← L.premier
        Tant que p2^.suivant <> Nil Faire
            p2 ← p2^.suivant
        FinTantque
        p2^.suivant ← p
    FinSi
    Retourner L
Fin

Gestion directe des créations de nœuds

Cas d'insertion en tête de liste

Fonction AjouterNoeud(L en Liste )
Variable P en ^Noeud
Début
    //Allocation dynamique de mémoire
    P ← allouer(taille(Noeud))
    //Renseignement des champs du nœud
    Lire(P^.champ_1)
    ...
    Lire(P^.champ_n)
    //Insertion du nœud en tête de liste
    P^.suivant ← L.premier
    L.premier ← P
    //on retourne la nouvelle liste
    Retourner L
Fin

Cas d'insertion en queue de liste

//Ajout d'un nœud en queue de liste
Fonction AjouterNoeud(L en Liste)
Variables P,P2 en ^Noeud
Début
    //Allocation dynamique demémoire
    P allouer(taille(Noeud))
    //Renseignement des champs du nœud
    Lire(P^.champ_1)
    ...
    Lire(P^.champ_n)
    P^.suivant ← Nil //initialisation par précaution
    Si L.premier = Nil alors
        L.premier ← p
    sinon
        p2 ← L.premier
        Tant que p2^.suivant <> Nil Faire
            p2 ← p2^.suivant
        FinTantque
        p2^.suivant ← p
    FinSi
    Retourner L
Fin

Insertion à une position quelconque

Permet d'insérer un nouveau nœud en fonction d'un critère, avant ou après un nœud spécifique, ou en maintenant un ordre croissant/décroissant.

• Si la liste est vide ou le nouvel élément doit précéder le premier, utiliser l'insertion en tête.

• Sinon, rechercher l'élément prédécesseur de l'emplacement d'insertion (avec un pointeur `P2`).

• Le `suivant` du nouveau nœud (pointé par `P`) devient le `suivant` du prédécesseur (pointé par `P2`).

• Le`suivant` du prédécesseur (pointé par `P2`) devient le nouveau nœud (pointé par `P`).

Fonction AjouterNoeud(L en Liste, N en Noeud )
Variables p,p2 en ^Noeud
Début
    p ← adresse (N)
    Si L.premier = Nil ou L.premier.champ_critère est satisfait alors
        p^.suivant ← L.premier
        L.premier ← p
    sinon
        p2 ← L.premier //on met un nouveau pointeur sur la tête
        Tant quep2^.suivant <> Nil et p2^.suivant.champ_critère pas satisfait Faire
            p2 ← p2^.suivant
        FinTantque
        p^.suivant ← p2^.suivant
        p2^.suivant ← p
    FinSi
    Retourner L
Fin

Suppression d'un élément d'une liste

Implique la recherche de l'élément puis sa suppression en préservant le chaînage.

• Si la liste est vide, ne rien faire.

• Suppression en tête: Déplacer la tête avant la suppression pour ne pas la perdre.

• Suppression en queue : Parcourir jusqu'à l'avant-dernier élément, pointer sur son suivant, puis isoler et supprimer le dernier élément.

• Suppressionà une position donnée (selon critère) : Rechercher l'élément et son prédécesseur, puis ajuster les pointeurs.

Exercice

Pour illustrer la suppression, considérons une liste chaînée de monômes représentant un polynôme.

1. Proposez une structure de données pour représenter un monôme.

2. Proposez une structure pour représenter un polynôme.

3. Proposez un programme pour construire le polynôme suivant : .

4. Écrivez une fonction pour supprimer du polynôme le monôme dont le degré est 2.

5. Écrivez une fonctionqui parcourt la nouvelle liste (nouveau polynôme) et l'affiche de la façon suivante : .

C'est en forgeant qu'on devient forgeron. Alors, bonne chanceà vous.

Programmes Avancés

Contenu additionnel du cours pour compléter la section.

• Structures de données et type abstrait

• Représentation contiguë et chaînée

• Recherche ettris avancés

• Arbres binaires, arbres planaires généraux et Arbres binaires de recherche

• Graphes

• Introduction aux algorithmes gloutons

• Introduction aux problèmes NP-complets

• Introduction aux algorithmes par évaluation et séparation

• Introduction aux algorithmes d'approximation

• Introduction aux algorithmes probabilistes

Pensée Inspirante

"The way to get started is to quit talking and begin doing."
Walt Disney

Résumé Final

Avec PowerPoint, vous pouvez créer des présentations et partager votre travail avec d'autres, où qu'ils soient. Tapez le texte que vous voulez ici pour commencer. Vous pouvez également ajouter des images, des œuvres d'art et des vidéos sur ce modèle. Enregistrez sur OneDrive et accédez àvos présentations depuis votre ordinateur, votre tablette ou votre téléphone.