3. Majuscules, Shadoks et franges
3. Parcours d’arbre, fork et signaux.

Vous créerez dans votre répertoire personnel, s'il n'est pas déjà là, le sous-répertoire "public_html" dans lequel vous placerez toutes vos réponses, qui y seront automatiquement ramassées. Seuls les fichiers demandés le seront, aussi il est impératif de bien contrôler leur création: nom exact (sans confondre minuscules et majuscules, tiret et souligné etc, ni placer des espaces autour du nom) et droit d'accès 640 pour un fichier non exécutable et droit d'accès 750 pour ses répertoires parents ou un fichier exécutable. Dans le cas où une réponse nécessite les fonctions écrites dans une réponse précédente, celles-ci ne doivent pas être recopiées, le recours au mécanisme d'inclusion des langages de programmation étant plus fiable et plus lisible.

On s’intéresse au problème suivant : déterminer si deux arbres binaires ayant pour feuilles un caractère de l’alphabet ASCII ont la même suite de feuilles lorsqu’on les parcourt, indépendamment de leurs nœuds. Par exemple les deux arbres binaires :

|----|---- c
|    |
a    b

et

|---------- c
|  
|----  b
|
a

ont même suite de feuilles bien qu’ils soient balancés différemment (le premier a une feuille comme fils gauche, alors que le deuxième a un sous-arbre).

Si deux arbres n’ont pas le même nombre de feuilles, ils n’ont évidemment pas la même suite de feuilles, même si la suite du plus petit est égale au début de même longueur de la suite du plus grand. On considère aussi que l’ordre des feuilles doit être respecté, l’arbre ci-dessous n’ayant pas même suite que les deux ci-dessus :

|---------- b
|  
|---- c
|
a

Pour fixer l’implémentation, vous sont fournies une structure C arbrebin implémentant un arbre binaire en C, et deux fonctions ab1 et ab2 construisant les deux arbres binaires ci-dessus.

Notes sur 10.


Warning: fsockopen(): unable to connect to ssl://www-master.ufr-info-p6.jussieu.fr:8083 (Connection refused) in /dsk/www-master/html/2016/ecrire/inc/distant.php on line 699

Warning: fsockopen(): unable to connect to ssl://www-master.ufr-info-p6.jussieu.fr:8083 (Connection refused) in /dsk/www-master/html/2016/ecrire/inc/distant.php on line 699

Warning: fsockopen(): unable to connect to ssl://www-master.ufr-info-p6.jussieu.fr:8083 (Connection refused) in /dsk/www-master/html/2016/ecrire/inc/distant.php on line 699

Warning: fsockopen(): unable to connect to ssl://www-master.ufr-info-p6.jussieu.fr:8083 (Connection refused) in /dsk/www-master/html/2016/ecrire/inc/distant.php on line 699

1 Fonction Fringe (1  point(s))

Ecrire la fonction C

void fringe (struct arbrebin *a, int fildes)

qui parcourt récursivement l’arbre donné en premier argument, et qui, à chaque rencontre d’une feuille, l’écrit sur le flux donné en deuxième argument.

Barème

- 


2 Comparer (3  point(s))

Ecrire un programme C construisant 2 arbres binaires, créant 2 processus fils et allouant 2 tubes. Chaque processus fils parcourt un des arbres et écrit sur un des tubes. Comment rédiger ce programme pour que le processus principal lise les deux tubes, caractère par caractère, affiche leur comparaison et s’arrête dès qu’ils se révèlent différents si c’est le cas ? On évitera de laisser orphelins les processus fils.

Exemple d'appel :
$PWD/bin/samefringe_full
Barème

- 
- 
- 


3 Suspendre (3  point(s))

La solution précédente a le défaut de toujours parcourir l’intégralité des deux arbres, ce qui n’est pas acceptable par exemple en cas d’arbre volumineux différant dès leur première feuille. Donner une nouvelle version de la fonction fringe suspendant le processus à chaque feuille rencontrée, et indiquer comment modifier le programme principal pour qu’il relance ou supprime les processus selon que les deux feuilles sont égales ou non.

Exemple d'appel :
$PWD/bin/samefringe_opt
Barème

- 
- 
- 


4 Interrompre (3  point(s))

On souhaite enfin modifier cette dernière version pour que la frappe de ^C au clavier permette d’interrompre par le signal SIGINT le processus principal, sans que ce signal interrompre l’un et/ou l’autre de ses processus fils. Le processus principal doit alors forcer ses processus fils à se terminer, et éviter qu’ils ne deviennent orphelins avant de se terminer lui-même.

Exemple d'appel :
$PWD/bin/samefringe_sigint
Barème

- 
- 
-