Licence Informatique
Algorithmique Avancée
TD 4: 17-18/10/05
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 premiers, 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);
    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.





File translated from TEX by TTH, version 3.05.
On 25 Oct 2005, 17:16.