Insertion dans un arbre (algo tri de l'arbre)

Version imprimable

Bonjour,

J'ai besoin d'aide concernant une fonction lisp.

J'ai deux fonctions :

- add qui ajoute un nombre dans un arbre :
Code:

1 2 3 4 5 6 (defun add (c tree) (cond ((not tree) (list c)) ((char>= c (car tree)) (list (car tree) (cadr tree) (add c (caddr tree)))) ;;((list (car tree) (add c (cadr tree)) (caddr tree))) ) ) ((list (car tree) (add c (cadr tree)) (caddr tree))) ) )
- make-tree qui créer un arbre d'après un fichier :
(le fichier contient un caractère par ligne)
Code:

1 2 3 4 5 6 7 (defun make-tree (fich &aux (liste nil)) (setq charlist (open fich :direction :input :if-does-not-exist :error)) (loop (cond ((not (setq ligne (read-line charlist nil nil))) (return)) ) (setq tree (add (read-from-string ligne) tree)) ) (close charlist) )
Admettons que mon fichier "lettres.txt" contient ceci :
Code:

1 2 3 4 5 6 7 #\r #\a #\j #\b #\m #\k #\p
Alors voici ce que j'obtiens dans l’interprète :
Code:

1 2 3 4 5 6 > (setq tree nil) nil > (make-tree "texte.txt") t > tree (#\r (#\a NIL (#\j (#\b) (#\m (#\k) (#\p)))) NIL)
J'en viens maintenant à la fonction qui me pose problème.
Cette fonction est sensée remplacer la fonction add et insérer directement des éléments dans la liste avec rplacd et replaca.

- On ne peut commencer avec nil car il n'a pas de cdr. Donc on initalise la liste avec le premier élément.

(setq tree (premier_elm))

- Pour ajouter une branche de droite dans un arbre (#\r) il faut au préalable ajoute un branche de gauche : (#\r nil) sinon le second pointeur cdr n'existe pas encore.

- Ma fonction doit comporter un cond avec 6 cas distincts (a, b, c sont des caractères et x est le caractère à insérer) :

1) on a (a) et x > a : on modifie en (#\a nil (x)) avec deux rplacd
2) on a (a (b...)) et x > a : on modifie en (#\a (#\b...) (x)) avec un rplacd
3) on a (# (b...) (c..)) et x >a : on continue avec la branche (c...)
4) on a (a) et x < a : on modifie en (a (x)) avec un rplacd
5) on a (a nil (b...)) et x < a : on modifie en (a (x) (b...)) avec rplaca
6) on a (a (b...) (c...)) et x < a : on continue avec la branche (b...)

Voilà c'est ici que je coince. Je ne sais pas comment m'y prendre pour monter cette fonction. Si quelqu'un peut m'aiguiller je ne refuserais pas.

Merci d'avance.

15/04/2013, 10h34
jack-ft

Citation:

Envoyé par Self-Mao

1) on a (a) et x > a : on modifie en (#\a nil (x)) avec deux rplacd
2) on a (a (b...)) et x > a : on modifie en (#\a (#\b...) (x)) avec un rplacd
3) on a (# (b...) (c..)) et x >a : on continue avec la branche (c...)
4) on a (a) et x < a : on modifie en (a (x)) avec un rplacd
5) on a (a nil (b...)) et x < a : on modifie en (a (x) (b...)) avec rplaca
6) on a (a (b...) (c...)) et x < a : on continue avec la branche (b...)

Voilà c'est ici que je coince.

Bonjour.
Qu'est-ce qui coince?
Qu'as-tu essayé?

Bonjour, merci pour ta réponse tout d'abord !

Voici ce que j'ai :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 (defun insert (tree w) (cond ((and (not (cdr tree)) (char>= w (car tree))) (and (rplacd tree '(nil)) (rplacd (cdr tree) (cons (cons w nil) nil))) ) ((not (cdr tree)) (rplacd tree (cons (cons w nil) nil)) ) ((not (cddr tree)) (rplacd (cdr tree) (cons (cons w nil) nil)) ) ((not (cadr tree)) (rplaca (cdr tree) (cons w nil)) ) ((char>= w (car tree)) (insert (caddr tree) w) ) ((insert (cadr tree) w)) ) )
Et voici ce qui coince :
Code:

1 2 3 4 5 6 7 8 9 10 > (setq arbre '("k")) ("k") > (insert arbre "m") => ("k" NIL ("m")) > (insert arbre "a") => ("k" ("a") ("m")) > (insert arbre "n") => ("k" ("a") ("n"))
Je pense que le soucis vient de l'action a effectué dans la première clause de la condition.

Code:

(and (rplacd tree '(nil)) (rplacd (cdr tree) (cons (cons w nil) nil)))

Car avec la trace de la fonction je m’aperçois que l'arbre est modifié ainsi :
Code:

1 2 3 => ("k" ("a") ("m")) => ("k" ("a") ("m" nil)) => ("k" ("a") ("n"))
Il y a une erreur quelque part c'est sûr mais je ne sais pas où malheureusement.

!!!!! EDIT !!!!!

Bon apparemment j'ai résolu le problème en modifiant une ligne dans la fonction :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 (defun insert (w tree) (cond ((and (not (cdr tree)) (char>= w (car tree))) (rplacd tree (list nil (list w))) ) ((not (cdr tree)) (rplacd tree (cons (list w) nil)) ) ((not (cddr tree)) (rplacd (cdr tree) (cons (list w) nil)) ) ((not (cadr tree)) (rplaca (cdr tree) (cons w nil)) ) ((char>= w (car tree)) (insert w (caddr tree)) ) ((insert w (cadr tree))) ) )
Je ne comprend pas pourquoi la solution avec les deux rplacd ne fonctionne pas. Elle donne des résultats vraiment étranges. Mais cette nouvelle fonction à l'air de fonctionner parfaitement.

18/04/2013, 13h11
jack-ft

Pourquoi si compliqué?

Essaie plutôt de reprendre la structure de la fonction 'add' en supprimant les 'list' (sauf le premier) et faisant systématiquement des rplaca (attention toutefois aux valeurs retournées!)

La fonction devrait faire juste 2 ou 3 lignes de plus que 'add' (à cause des valeurs retournées (progn implicite dans les clauses de cond)).

Voici une solution possible calquée sur 'add', courte, mais qui fait beaucoup d'écritures:

Code:

1
2
3
4
5
6
7
8
9
(defun insert (c tree)
  (cond
   ((not tree) (list c))
   ((char>= c (car tree))
    (rplaca (caddr tree) (insert c (caddr tree)))
    tree)
   (t
    (rplaca (cadr tree) (insert c (cadr tree)))
    tree)))

et une solution un peu plus longue (qui duplique le code '(list c)'), qui fait le double de tests, mais qui fait juste les écritures nécessaires:

Code:

1
2
3
4
5
6
7
8
9
10
11
(defun insert (c tree)
  (cond
   ((not tree) (list c))
   ((char>= c (car tree))
    (if (caddr tree)
        (insert c (caddr tree))
      (rplaca (cddr tree) (list c)) ))
   (t
    (if (cadr tree)
        (insert c (cadr tree))
      (rplaca (cdr tree) (list c)) ))))

et une solution encore plus rapide:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
(defun insert (c tree)
  (if tree
      (insert-aux c tree))
  (list c))
 
(defun insert_aux (c tree)
  (if (char>= c (car tree))
      (if (caddr tree)
          (insert_aux c (caddr tree))
        (rplaca (cddr tree) (list c)) )
    (if (cadr tree)
        (insert_aux c (cadr tree))
      (rplaca (cdr tree) (list c)) )))

24/04/2013, 16h45
Self-Mao

Merci pour ta réponse.

En effet j'avais tenté quelque chose du genre avec des if, peut-être pas aussi rapide mais c'est pour un devoir et je suis forcé d'utiliser des cond mais en définissant les clauses je suis parvenu à un bon compromis, avec cond et pas de if.

Merci infiniment de ton aide !!
25/07/2013, 14h52
simnitch

Aucune de tes fonctions ne marche chez moi jack-ft...
25/07/2013, 15h14
Trap D

Genre déterrage c'est pas mal !
En plus quelques explications sur les erreurs/problèmes rencontrés serait utile.
25/07/2013, 17h37
simnitch

Genre déterrer un vieux sujet c'est mal? On parle d'arbres là en plus, donc c'est dans le vif du sujet, ahah.
Le problème c'est que ça ne marche pas du tout, même message d'erreur pour les trois fonctions : rplaca : nil n'est pas une paire.
Ca marche seulement pour rentrer un caractère dans un arbre vide.
Voilà c'est tout...
30/07/2013, 13h55
simnitch

Du coup personne n'a une solution qui marche?
Merci d'avance ;)