Q10: renverser

Profil

renverser: liste -> liste

Exemples

renverser( (a b c) ) = (c b a)

idée: utiliser une fonction auxiliaire pour construire la liste renversée

renverser( (a b c) ) = aux( (a b c), () ) 
                     = aux( (b c), (a) ) 
                     = aux( ( c ), (b c) ) 
                     = aux( (), (c b a) ) = (c b a)

Axiomes

renverser(L) = aux(L, ())

aux( (), L) = L

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

Algorithme récursif

fonction renverser(L: liste): liste
debut
 | retourner aux(L, liste_vide())
 | ------------------------------
fin

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

Algorithme récursif

fonction renverser(L: liste): liste
debut
 | nL: liste                       
 | ---------                       
 | nL := liste_vide()              
 | tant que non (est_vide(L)) faire
 |                                  | nL := cons(prem(L), nL)
 |                                  | L := reste(L)          
 | fintantque                      
 | retourner nL                    
fin

Traduction en C

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

liste renverserR(liste L)
{
  return aux_renverserR(L, liste_vide());
}

liste renverserI(liste L)
{
  liste nL;
  nL = liste_vide();
  while (! est_vide(L))
  {
    nL = cons(prem(L), nL);
    L = reste(L);
  }
  return nL;
}