Scribd Logo
Importer

Bienvenue sur Scribd !

  • 131 vues

    ED2 Corrige

    Transféré par

    Maria

    Droits d'auteur :

    Attribution Non-Commercial (BY-NC)
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd

    ED2 Corrige

    Transféré par

    Maria
    131 vues5 pages

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Formats disponibles

    PDF, TXT ou lisez en ligne sur Scribd

    Avez-vous trouvé ce document utile ?

    Ce contenu est-il inapproprié ?

    Droits d'auteur :

    Attribution Non-Commercial (BY-NC)
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    131 vues5 pages

    ED2 Corrige

    Transféré par

    Maria

    Droits d'auteur :

    Attribution Non-Commercial (BY-NC)
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    Vous êtes sur la page 1sur 5

    Corrig E.D. Algorithmes et Structures de Donnes n 2 Thme : Les Listes Exercice II.

    1 Manipulation dune liste chane circulaire


    q r

    L d3 d4

    d1

    d2

    r.valeur = d3 q.suivant = r q.suivant.valeur = d3 r.suivant.suivant.valeur = d1

    Exercice II.2
    Question 1 Que fait cette mthode ? La mthode qui_fait_quoi a pour rsultat la liste courante dans laquelle on a insr dans lordre llment x sil nexistait pas dj dans la liste (sans doublon). On suppose la liste courante non vide. Si x<premier lment, on insre entte de la liste Si x=premier lment, la liste est inchange. Sinon parcourir la liste jusqu' trouver la position de llment x dans la liste p.suivant.valeur x ou pointer vers le dernier lment p.suivant==null Si p.suivant.valeur == x, la liste est inchange Sinon insrer llment x, Liste q = new Liste(x,p.suivant) p.suivant=q ; Question 2 Voici la liste obtenue partir de la liste donne ci-dessus et APRES appel de qui_fait_quoi (20);

    r 10
    r.suivant.valeur = 17 r.suivant.suivant.valeur = 20 un peu plus ... et si, avec cette nouvelle liste r, on excute r.qui_fait_quoi (5), on obtient :

    17

    20

    25

    null

    r 5 10 17 20 25
    null

    Exercice II.3 Inversion d'une liste chane


    Question 1 On veut crire une nouvelle mthode renverser qui inverse la liste courante. - l pointera au fur et mesure sur la partie non encore inverse de la liste. Nous utilisons 2 pointeurs supplmentaires : r qui pointe sur la tte de la sous-liste dj inverse de la liste. Initialis null. p est simplement un pointeur auxiliaire qui permet deffectuer le transfert dun lment de la tte de l vers la tte de r.
    Liste renverser Liste l=this ; Liste r= null; Liste p ; dbut tant que l /= null faire p = l; -- on sauvegarde dans p la tte de la liste l l = l.suivant; -- on avance l (on enlve la tte de l) -- on insre p en tte de r p.suivant = r; r = p; fait;
    -- ici l==null et r contient le rsultat de linversion.

    retourner r; fin

    Sur lexemple, au dbut :

    l 4 7 2 8 1

    Premier passage dans la boucle tant que :

    l 4 7 2 8 1

    Deuxime passage dans la boucle tant que :

    l 7 2 8 1

    Etc la fin :

    Question 2 Calculer la complexit de cette procdure. Si n est le nombre dlments (ou longueur) de la liste, alors la boucle sexcute n fois. Un passage par la boucle correspond 4 oprations. Donc la complexit de cette procdure est O(n).

    Exercice II.4 Inversion rcursive d'une liste chane Illustration de lide de la rcursion : Une liste L non vide peut toujours tre considre comme la juxtaposition de son premier lment (ou de son en_tte), que nous notons x, avec une autre liste L (qui est en fait L prive de x). x

    Reste de L (ou L)

    Si on sait inverser L alors on sait inverser L puisque : Inverse(L) x

    Inverse(L) Question 1
    Elt en_tete { debut retourner this.valeur ; fin

    Question 2
    public Liste inverser (){ //inversion recursive Liste l = this ; if ( l.suivant == null) return this ; Elt x = l.entete(); l=l.suivant; //l est alors tronque de son entete l=l.inverser() ; //appel rcursif l.insererenqueue (x); return (l); }

    Question 3 Calculer la complexit de cette procdure. Exemple dexcution : Si n est le nombre dlments de la liste, alors la procdure inversion est invoque n fois.
    4

    arrt
    Inversion{a,b,c} Inversion{b,c} Inversion{c} Inversion{}

    A chaque fois, il faut au pire n oprations pour effectuer linsertion en queue. Cette procdure est donc en O(n2). A comparer avec la procdure dinversion de la question prcdente.

    Exercice II.5 Inversion d'une liste contigu


    Question 1 Dfinir un principe efficace dinversion dune liste reprsente par un tableau.

    On peut permuter les contenus des lments extrmes, par paires. On permute 1 et n, puis 2 et (n-1), puis 3 et (n-2), . Si n est pair, tous les lments sont permuts 2 deux et cela fait n/2 permutations. Si n est impair, llment central ne change pas et cela fait (n-1)/2 permutations. Question 2 crire la mthode inverser et calculer sa complexit.
    Liste inverser Indice milieu; Elt tamp ; dbut Indice n = this.longueur; milieu = n / 2; -- division entire pour i allant de 1 milieu faire -- permutation des lments dindice i et n-i+1 tamp = tab[n-i+1]; tab [n-i+1]= tab[i]; tab[i ]=tamp; fait fin

    De lordre de n/2 passages dans la boucle pour (3 oprations lmentaires chaque fois) donc la complexit est O(n).

    Vous aimerez peut-être aussi