Correction du TD N° 7 sur les listes != exprime la différence 1) Listes simplement chainées booléen estVide(L) renvoyer (L.premier = nil) supprimerPremier(L) si L.premier != nil L.premier <- L.premier.suivant vider(L) L.premier <- nil ajouterEnTete(x, L) x.suivant <- L.premier L.premier <- x ajouterApres(x, y, L) # si y est nil on ajoute en tete si y = nil ajouterEnTete(x, L) sinon x.suivant <- y.suivant y.suivant <- x supprimerSuivant(x, L) # on considere que x n'est pas nil si x.suivant != nil x.suivant <- x.suivant.suivant entier numElts(L) cpt <- 0 e <- L.premier tant que e != nil cpt <- cpt + 1 e <- e.suivant renvoyer cpt 1.1) L.taille doit être mis à jour booléen estVide(L) renvoyer L.premier = nil supprimerPremier(L) si L.premier != nil L.premier <- L.premier.suivant L.taille <- L.taille - 1 vider(L) L.premier <- nil L.taille <- 0 ajouterEnTete(x, L) x.suivant <- L.premier L.premier <- x L.taille <- L.taille + 1 ajouterApres(x, y, L) # si y est nil on ajoute en tete si y = nil ajouterEnTete(x, L) sinon x.suivant <- y.suivant y.suivant <- x L.taille <- L.taille + 1 supprimerSuivant(x, L) # on considere que x n'est pas nil si x.suivant != nil x.suivant <- x.suivant.suivant L.taille <- L.taille - 1 entier numElts(L) renvoyer L.taille 1.2) Pour pouvoir ajouter en fin de liste il est plus agréable de disposer de l'attribut L.dernier qui contient une référence au dernier de la liste. Sinon, il faut le chercher ce qui nécessite de traverser la liste Le maintien de l'attribut dernier impacte presque toutes les méthodes. Il faut faire attention au fait que le premier peut-être aussi le dernier et donc que les méthodes modifiant le dernier peuvent aussi modifier le dernier Les méthodes deviennent : booléen estVide(L) renvoyer L.premier = nil supprimerPremier(L) si L.premier != nil L.premier <- L.premier.suivant si L.premier = nil L.dernier <- nil vider(L) L.premier <- nil L.dernier <- nil ajouterEnTete(x, L) si L.premier = nil L.dernier <- x x.suivant <- L.premier L.premier <- x ajouterApres(x, y, L) # si y est nil on ajoute en tete si y = nil ajouterEnTete(x, L) sinon si y.suivant = nil) # le dernier est y L.dernier <- x x.suivant <- y.suivant y.suivant <- x supprimerSuivant(x, L) # on considere que x n'est pas nil elt <- x.suivant # on supprime elt si elt != nil si elt.suivant = nil L.dernier <- x x.suivant <- elt.suivant entier numElts(L) cpt <- 0 e <- L.premier tant que e != nil cpt <- cpt + 1 e <- e.suivant renvoyer cpt Insertion dans une liste triée. On considère un ordre croissant. algorithme classique : on cherche le premier élément plus grand et on insère juste avant. On a donc besoin de mémoriser le précédent inserer(elt, L) prec <- nil e <- L.premier tant que e != nil et e.donnee < elt.donnee prec <- e e <- e.suivant ajouterApres(elt, prec, L) On peut eviter cela en modifiant la donnée. quand on trouve l'élément qui est plus grand alors on l'échange avec l'élément courant et ont dit que l'on doit insérer cet élément. Dans ce cas, on a immédiatement sa position. Pour simplifier l'algorithme, on considérera qu'on ne va pas ajouter en fin inserer(elt, L) e <- L.premier tant que e != nil et e.donnee < elt.donnee e <- e.suivant echanger e.donnee et elt.donnee ajouterApres(elt, e, L) On va en profiter pour ecrire une fonction qui nous sera utile pour la fusion de listes. Cette fonction insère dans une liste a partir d'un élément début donné. L'insertion ne peut avoir lieu qu'apres le début. inserer(elt, debut, L) prec <- debut si debut = nil e <- L.premier sinon e <- debut.suivant tant que e != nil et e.donnee < elt.donnee prec <- e e <- e.suivant ajouterApres(elt, prec, L) 1.3) La premiere version détruit la liste L2. L'idée est la suivante : on balaie la liste L2 et on cherche à quel endroit dans L1 on va insérer l'élément fusion(L1, L2) e1 <- nil e2 <- L2.premier tant que e2 != nil # ici il faut faire attention car on traverse la liste L2 et on va la modifier suiv2 <- e2.suivant inserer(e2, e1, L1) e1 <- e2 # un peu etrange mais en fait on veut démarrer APRES l'élément que l'on vient d'introduire e2 <- suiv2 L2.premier <- nil Pour la seconde version, la solution la plus simple est de copier la liste L2 dans une autre liste, par exemple L3 puis d'appliquer l'algorithme précédent avec L1 et L3. 2) supprimerPremier(L) si L.premier != nil suiv <- L.premier.suivant L.premier <- suiv si suiv != nil suiv.precedent <- nil vider(L) L.premier <- nil ajouterEnTete(x, L) si L.premier = nil L.premier.precedent <- x x.suivant <- L.premier x.precedent <- nil L.premier <- x ajouterApres(x, y, L) # si y est nil on ajoute en tete si y = nil ajouterEnTete(x, L) sinon x.precedent <- y si y.suivant != nil # le dernier est y y.suivant.precedent <- x x.suivant <- y.suivant y.suivant <- x supprimerSuivant(x, L) # on considere que x n'est pas nil elt <- x.suivant # on supprime elt si elt != nil si elt.suivant != nil elt.suivant.precedent <- x x.suivant <- elt Liste avec sentinelle: L.sentinelle contient une référence à la sentinelle de L premier(L) renvoyer L.sentinelle.suivant dernier(L) renvoyer L.sentinelle.precedent booleen estVide(L) renvoyer premier(L) = L.sentinelle supprimerPremier(L) premier(L).suivant.precedent <- L.sentinelle L.sentinelle.suivant <- premier(L).suivant vider(L) L.sentinelle.suivant <- L.sentinele L.sentinelle.precedent <- L.sentinelle ajouterEnTete(x, L) x.suivant <- premier(L) x.precedent <- L.sentinelle premier(L).precedent <- x L.sentinelle.suivant <- x ajouterApres(x,y,L) # x apres y # si y est nil on ajoute en tete si y = nil ajouterEnTete(x, L) sinon y.suivant.precedent <- x x.suivant <- y.suivant y.suivant <- x x.precedent <- y supprimer(x, L) x.precedent.suivant <- x.suivant x.suivant.precedent <- x.precedent 3) Operation sur les listes ajouterEnFin(L1, L2) d1 <- L1.dernier p2 <- L2.premier d2 <- L2.dernier d1.suivant <- d2 p1.precedent <- d1 L1.sentinelle.precedent <- d2 d2.suivant <- L1.sentinelle ajouterAuDebut(L1, L2) p1 <- L1.premier p2 <- L2.premier d2 <- L2.dernier p1.precedent <- d2 d2.suivant <- p1 L1.sentinelle.suivant <- p2 p2.precedent <- L1.sentinelle supprimerImpaireAjouterPair(L1, L2) e1 <- L1.premier tant que e1 != L1.sentinelle suiv1 <- e1.suivant si e1.donnee est impaire supprimer(e1, L1) e1 <- suiv1 e2 <- L2.premier tant que e2 != L2.sentinelle suiv2 <- e2.suivant si e2.donnee est paire supprimer(e2, L2) ajouterApres(e2, L1.dernier, L1) e2 <- suiv2