Licence Informatique Algorithmique Avancée TD 4: Octobre 2006

Opérations sur des Structures définies récursivement

Dans les 3 premiers exercices il s’agit de structures construites d’enregistrements

liste de 2 champs (valeur: entier; queue: ^liste); dans les deux pre-

miers, on peut supposer que la liste est terminée par un pointeur nul

1. Afficher une liste (une procédure récursive avec comme paramètre un pointeur)

2. Copier une liste (une fonction qui construit une copie de la liste et retourne un pointeur vers la copie.

3. Décider si une liste est circulaire, c’est-à-dire si elle a un pointeur vers un noeud déjà présent; (un indice: si deux pointeurs parcourent une liste circulaire, l’un deux fois plus vite que l’autre, le plus rapide va rattraper l’autre quand les deux sont dans la boucle.)

Dans les deux derniers exercices, il s’agit d’enregistrements noeud de 4

champs, (valeur: entier; marqueur: booleen; g,d: ^noeud).

4. Copier un arbre (vous pouvez supposer que c’est un vrai arbre sans boucles ni parties partagées)

5. Décider si une structure (pas forcément un arbre) est correctement marquée (c’est-à-dire que tous les champs marqueur des noeuds accessibles de la racine sont faux). (Oui, on peut le faire en temps linéaire dans la taille de la structure)

Réponses dans un programme exo

programme TD4;
type listeptr: ^liste;
type liste: enreg
valeur:entier;
queue: listeptr
finenreg;
procedure afficheliste(val p:listeptr);
dbut
   si p!=nul alors
      printf("%i\n",p^.valeur);
      afficheliste(p^.queue)
   finsi
fin
finprocedure;
fonction copieliste(val p:listeptr):listeptr;
var temp: listeptr;
dbut
   si p=nul alors retourne nul
   sinon
      allouer(temp);
      temp^.valeur:=p^.valeur;
      temp^.queue:=copieliste(p^.queue);
      retourne temp
   finsi
fin
finfonction;
fonction circulaire(val p:listeptr):booleen;
var lent:listeptr;
var rapide:listeptr;
debut
   si p=nul alors retourne faux finsi;
   lent:=p;
   rapide:=p^.queue;
   tantque rapide!=nul et lent!=rapide faire
      lent:=lent^.queue;
      rapide:=rapide^.queue;
      si rapide=nul alors retourne faux finsi;
      rapide:=rapide^.queue
   fin tantque;
   retourne lent=rapide
fin

finfonction;
type arbreptr: ^arbre;
type arbre: enreg
valeur:entier;
marqueur:booleen;
g:arbreptr;
d:arbreptr
finenreg;

fonction copiearbre(val p:arbreptr):arbreptr;
var temp: arbreptr;
debut
   si p=nul alors retourne nul
   sinon
      allouer(temp);
      temp^.valeur:=p^.valeur;
      temp^.marqueur:=p^.marqueur;
      temp^.g:=copiearbre(p^.g);
      temp^.d:=copiearbre(p^.d);
      retourne temp
   finsi
fin
finfonction;
fonction compter(val p:arbreptr; val m:booleen): entier;
debut
/* compter les noeuds accessible de p sans passer par un noeud
marqu m
(et les marquer avec m) */
   si p=nul ou p^.marqueur=m alors retourne 0
   sinon
      p^.marqueur:=m;
      retourne 1+compter(p^.g,m)+compter(p^.d,m)
   finsi
fin
finfonction;
fonction corrmarque(val p:arbreptr): booleen;
debut
   retourne compter(p,vrai)=compter(p,faux)
/* depend d'un ordre squentiel d'valuation */
fin
finfonction;

debut fin.

4