Q12: concatener

Profil

concatener: liste x liste -> liste

Exemples

concatener( (a b c), (d e) ) = (a b c d e)

Idee: utiliser une fonction auxiliaire et "renverser"

concatener(L1, L2) = aux(renverser(L1), L2)
concatener( (a b c), (d e) ) = aux( (c b a), (d e)) 
                             = aux( (b a), (c d e)) 
                             = aux( (a), (b c d e)) 
                             = aux( (), (a b c d e) ) 
                             = (a b c d e)

Axiomes

concatener(L1, L2) = aux(renverser(L1), L2)
aux(liste_vide(), L) = L
aux(cons(x, L1), L2) = aux(L1, cons(x, L2))

SINON (plus simple)

concatener( () , L2 ) = L2
concatener( cons(x, L1) , L2) = cons(x, concatener(L1, L2))

Algorithme récursif

fonction concatener(L1: liste, L2: liste): liste
debut
 | retourner aux(renverser(L1), L2)
 | --------------------------------
fin

fonction aux(L1: liste, L2: liste): liste
debut
 | si est_vide(L1)
 | ---------------
 |                 | alors retourner L1                                
 |                 | sinon retourner aux(reste(L1), cons(prem(L1), L2))
 | finsi          
fin

Algorithme itératif

fonction concatener(L1: liste, L2: liste): liste
debut
 | retourner(renverser(L1), L2)
 | ----------------------------
fin

fonction aux(L1: liste, L2: liste): liste
debut
 | tant que non est_vide(L1) faire
 | -------------------------------
 |                                 | L2 := cons(prem(L1), L2)
 |                                 | L1 := reste(L1)         
 | fintantque                     
 | retourner L2                   
fin

Traduction en C

liste aux_concatenerR(liste L1, liste L2)
{
  if (est_vide(L1))
  {
    return L2;
  }
  else
  {
    return aux_concatenerR(reste(L1), cons(prem(L1), L2));
  }
}

liste concatenerR(liste L1, liste L2)
{
  return aux_concatenerR(renverserR(L1), L2);
}