Dans les 3 premiers exercices il s'agit de structures construites d'enregistrements liste de 2 champs (valeur: entier; queue: ^liste); dans les deux premiers, on peut supposer que la liste est terminée par un pointeur nul
Réponses dans un programme exo
programme TD4;
type listeptr: ^liste;
type liste: enreg
valeur:entier;
queue: listeptr
finenreg;
procedure afficheliste(val p:listeptr);
début
si p!=nul alors
printf("%i\n",p^.valeur);
afficheliste(p^.queue)
finsi
fin
finprocedure;
fonction copieliste(val p:listeptr):listeptr;
var temp: listeptr;
début
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 marques 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 séquentiel d'évaluation */
fin
finfonction;
debut
fin.