Université Bordeaux 1
Licence Semestre 2   Initiation à l'algorithmique
Dernière mise à jour effectuée le 2 Juillet 2007

Listes


  1. Définition
  2. Définition 6.1. Une liste est une table d'association à clé unique telle que
    • le nombre d'éléments de la table (dimension ou taille) est variable,
    • l'accès aux éléments s'effectue indirectement par le contenu de la clé qui le localise appelée pointeur.
    La complexité de l'accès à un élément par son pointeur est O(1).
    Si p est un pointeur vers un élément alors contenu(p) est l'élément lui-même. Un pointeur qui n'adresse aucun élément a pour valeur NIL. On écrit en EXALGO pour déclarer un pointeur
    nom_pointeur=^type_predefini;
    
    On écrit en EXALGO pour déclarer une liste
    type_liste=liste de type_predefini;
    
    La manipulation des éléments de la liste dépend des fonctions définies comme s'exécutant en temps O(1).

  3. Liste simplement chainée
  4. Définition 6.2. Une liste est dite simplement chainée si les opérations suivantes s'effectuent en O(1).
    • accès
      fonction premier(val L:type_liste):^type_predefini;
      fonction suivant(val L:type_liste;
                       val P:^type_predefini):^type_predefini;
      fonction listeVide(val L:type_liste):booléen;
    • modification
      fonction créer liste(ref L:type_liste):vide;
      fonction insérerAprès(val x:type_prédéfini;
                            ref L:type_liste;
                            P:^type_predefini):vide;
      fonction insérerEnTete(val x:type_prédéfini;
                            ref L:type_liste):vide;
      fonction supprimerAprès(ref L:type_liste;val P:^type_predefini):vide;
      fonction supprimerEnTete(ref L:type_liste):vide;
      
    On écrira en EXALGO listeSC pour préciser qu'il s'agit d'une liste simplement chainée.

    Test de fin de liste

    fonction estDernier(ref L:listeSC de type_prédéfini;
                      ref P:^type_prédéfini):booléen;
        début
          retourner(suivant(L,P)=NIL)
        fin
    finfonction
    

    Chercher un élément dans une liste

    fonction chercher(ref L:listeSC de type_prédéfini;
                      ref E:type_prédéfini):^type_predefini;
      début
      var p:^type_prédéfini;
      début
        si listeVide(L) alors
          retourner(NIL)
        sinon
          p=premier(L);
          tant que non(estDernier(L,p)) et (contenu(p)!=e) faire
              p=suivant(L,p);
          fintantque
          si (contenu(p)!=e) alors
             retourner(NIL)
          sinon
             retourner(p)
          finsi
        finsi
      fin
    finfonction
    
    Complexité:
    • minimum : O(1)
    • maximum : O(n)

    Trouver le dernier élément

    fonction trouverDernier(ref L:listeSC de type_prédéfini):^type_predefini;
      var p:^type_prédéfini;
      début
        si listeVide(L) alors
          retourner(NIL)
        sinon
          p=premier(L);
          tant que non(estDernier(L,P)) faire
              p=suivant(L,p);
          fintantque
          retourner(p)
        finsi
      fin
    finfonction
    
    Complexité: O(n).

  5. Liste doublement chainée
  6. Définition 6.3. Une liste doublement chainée est une liste pour laquelle les opérations en temps O(1) sont celles des listes simplement chainées auxquelles on ajoute les fonctions d'accès
    fonction dernier(val L:type_liste):^type_predefini;
    fonction précédent(val L:type_liste;
                       val P:^type_predefini):^type_predefini;
    
    On écrira en EXALGO listeDC pour préciser qu'il s'agit d'une liste doublement chainée.

    Supprimer un élément

    fonction supprimer(ref L:listeDC de type_predefini;
                       val e: type_prédéfini):booléen;
      var p,prec,suiv:^type_prédéfini;
      début
        p=chercher(L,e);
        si p==NIL alors
          retourner(FAUX)
        sinon
          si estPremier(L,p) alors
            supprimerEnTete(L)
          sinon
            prec=précédent(L,p);
            supprimerApres(L,prec);
          finsi
          retourner(VRAI)
        finsi
      fin
    finfonction
    
    Complexité
    • minimum : O(1)
    • maximum : O(n)

  7. Quelques algorithmes
  8. Taille

    fonction taille(val L:type_liste):entier;
      var p:^type_prédéfini;
      var t:entier;
      début
        si listeVide(L) alors
          retourner(0)
        sinon
          retourner(1+taille(suivant(L,premier(L))))
        finsi
      fin
    finfonction
    
    Complexité: O(n).

    Insérer dans une liste triée

    On suppose la liste triée doublement chainée dans l'ordre croissant
    fonction insertionTrie(ref L:listeDC de type_prédéfini;
                         val e: type_prédéfini):vide;
      var p:^type_prédéfini;
      début
        si listeVide(L) alors
          insererEnTete(e,L)
        sinon
          si contenu(premier(L))>e alors
            insererEnTete(e,L)
          sinon
            insererTrie(suivant(L,premier(L)),e)
          finsi
        finsi
      fin
    finfonction
    
    Complexité moyenne: O(n).