SHARE
TWEET

Tri Fusion

Kayaite Oct 14th, 2019 (edited) 90 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include "liste_ext.h"
  4.  
  5. // Affiche la liste l
  6. void afficher( Liste l )
  7. {
  8.     if (est_liste_vide(l)) {
  9.         printf( "\n" ) ;
  10.         return ;
  11.     }
  12.     else {
  13.         printf( "%i " , tete(l) ) ;
  14.         afficher( queue(l) ) ;
  15.     }
  16. }
  17.  
  18. // Retourne la longueur de la liste l
  19. int longueur( Liste l )
  20. {
  21.     if( est_liste_vide(l) ) return 0 ;
  22.     else return( 1 + longueur(queue(l)) ) ;
  23. }
  24.  
  25. Maillon *deplacer_fin( Maillon *m, Maillon *fin )
  26. {
  27.     if( est_liste_vide(fin) ) {
  28.         fin = m ;
  29.         return fin ;
  30.     }
  31.     fin->suiv = m;
  32.     return fin->suiv ;
  33. }
  34.  
  35. // l est une liste de longueur n
  36. // Renvoie un pointeur pointant sur le debut de la 2ième moitiè de liste
  37. Liste decouper(Liste l,int n)
  38. {
  39.     Liste p=l , lfin ;
  40.     int i ;
  41.  
  42.     i=0 ;
  43.     while( i++ < n-1 ) p= p->suiv ;
  44.     lfin = p->suiv ;
  45.     p->suiv = NULL ;
  46.     return lfin ;
  47. }
  48.  
  49. // l1 et l2 sont 2 listes triées
  50. // Retourne une liste triée produit par la fusion de l1 et l2
  51. Liste fusion( Liste l1, Liste l2 )
  52. {
  53.     Liste debut = creer_liste_vide();
  54.     Liste l0 = creer_liste_vide() ;
  55.    
  56.     while( !(est_liste_vide(l1)) && !(est_liste_vide(l2)) ) {
  57.         if( tete(l1)<tete(l2) ){
  58.             l0= deplacer_fin(l1,l0) ;
  59.             l1 = l1->suiv;
  60.         } else{
  61.             l0 = deplacer_fin(l2,l0) ;
  62.             l2 = l2->suiv;
  63.         }
  64.         if (est_liste_vide(debut)) debut = l0 ;
  65.     }
  66.     while( !est_liste_vide(l1) ) {
  67.         deplacer_fin(l1, l0) ;
  68.         l1 = l1->suiv;
  69.     }
  70.     while( !est_liste_vide(l2) ) {
  71.         deplacer_fin(l2, l0) ;
  72.         l2 = l2->suiv;
  73.     }
  74.    
  75.     return debut ;
  76. }
  77.    
  78. // Effectue le trie fusion sur la liste l de longueur n
  79. Liste tri_fusion_rec( Liste l, int n )
  80. {  
  81.    if( n<=1 ) return l ;
  82.    
  83.    else {
  84.         int n_debut = n/2;
  85.         int n_fin = n - n_debut ;
  86.         Liste l_fin ;
  87.         l_fin = decouper(l,n_debut) ;
  88.         l = tri_fusion_rec(l,n_debut) ;
  89.         l_fin = tri_fusion_rec(l_fin,n_fin) ;
  90.         return fusion(l,l_fin) ;
  91.     }
  92. }
  93.  
  94. // Eeeeennnnfffiiiiiiiiiinnnnnnnnnnnnnnn
  95. Liste tri_fusion( Liste l )
  96. {
  97.     return tri_fusion_rec( l, longueur(l) ) ;
  98. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top