Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Ed2 corrige Corrigé E D Algorithmes et Structures de Données n Thème Les Listes Exercice II Manipulation d ? une liste cha? née circulaire q r L d d d d r valeur d q suivant r q suivant valeur d r suivant suivant valeur d Exercice II Question Que fait cet

Corrigé E D Algorithmes et Structures de Données n Thème Les Listes Exercice II Manipulation d ? une liste cha? née circulaire q r L d d d d r valeur d q suivant r q suivant valeur d r suivant suivant valeur d Exercice II Question Que fait cette méthode La méthode quifaitquoi a pour résultat la liste courante dans laquelle on a inséré dans l ? ordre l ? élément x s ? il n ? existait pas déjà dans la liste sans doublon On suppose la liste courante non vide Si xfaitquoi Cr null r suivant valeur r suivant suivant valeur un peu plus et si avec cette nouvelle liste r on exécute r quifaitquoi on obtient r null Exercice II Inversion d'une liste cha? née Question On veut écrire une nouvelle méthode renverser qui inverse la liste courante l pointera au fur et à mesure sur la partie non encore inversée de la liste Nous utilisons pointeurs supplémentaires ?? r qui pointe sur la tête de la sous-liste déjà inversée de la liste Initialisé à null ?? p est ? simplement un pointeur auxiliaire qui permet d ? e ?ectuer le transfert d ? un élément de la tête de l vers la tête de r Liste renverser Liste l this Liste r null Liste p début tant que l null faire p l -- on sauvegarde dans p la tête de la liste l l l suivant -- on avance l on enlève la tête de l -- on insère p en tête de r p suivant r r p fait -- ici l null et r contient le résultat de l ? inversion retourner r ?n Sur l ? exemple au début l r CPremier passage dans la boucle tant que r l Deuxième passage dans la boucle tant que r l Etc ? à la ?n r l Question Calculer la complexité de cette procédure Si n est le nombre d ? éléments ou longueur de la liste alors la boucle s ? exécute n fois Un passage par la boucle correspond à opérations Donc la complexité de cette procédure est O n CExercice II Inversion récursive d'une liste cha? née Illustration de l ? idée de la récursion Une liste L non vide peut toujours être considérée comme la juxtaposition de son premier élément ou de son en tête que nous notons x avec une autre liste L ? qui est en fait L privée de x x Reste de L ou L ? L Si on sait inverser L ? alors on sait inverser L puisque Inverse L ? x Inverse L Question Elt en tete debut retourner this valeur ?n Question public Liste inverser inversion recursive Liste l this if l suivant null return this Elt x l entete l l suivant l est alors tronquée de son entete l l inverser appel récursif l insererenqueue x return l Question Calculer la complexité de cette procédure Exemple d ? exécution