Discussion :

[Sherwood51]

Bonjour à tous,

je suis étudiant en informatique et cet après-midi j'avais un TP à faire.
Une des questions du TP était celle-ci:

File à priorités (à choix)
Cette structure ressemble à une file d’attente, sauf que cette fois chaque élément possède
une priorité. Pour l’implémentation, les éléments à insérer seront des couples de la forme
(element, priorite). L’élément que nous récupérons en premier est celui avec la priorité la
plus haute.
Implémentez les fonctions supplémentaires suivantes pour gérer les files à priorités :
– (inserer el prio), insère l’élément el avec priorité prio dans la file.
– (recuperer) retourne l’élément avec la priorité la plus haute.
Note : Pour bien implémenter la file de priorité nous avons les choix suivants :
– On insère les éléments dans l’ordre descendant, donc pour chaque élément on doit trouver
la bonne place. L’élément avec la plus grande priorité est alors celui qui se trouve en
premier, comme dans une file traditionnelle.
– Il est aussi possible d’insérer les éléments dans n’importe quel ordre et chercher celui
qui a la plus grande priorité à l’heure de faire les extractions.
La file à priorités est une structure plus générale que la pile et la file. Réfléchir à comment
implémenter une pile et une file en utilisant une file à priorités.

Et voilà le code que j'ai fourni:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
; Applications
; File à priorités
(define file2 '())

(define l '())
(define (inserer e1 prio file3)
  (let ((couple (cons e1 (cons prio '()))))
  (if (null? file3)
      (begin
        (set! l (append l (list couple)))
        l)
      (if (>= prio (cadar file3))
          (begin
            (set! l (append l (list couple) file3))
            l)
          (begin
            (append l (list (car file3)))
            (inserer e1 prio (cdr file3)))))))

(define (ltofile2 e1 prio)
  (set! file2 (inserer e1 prio file2)))

(ltofile2 'a 1)
(ltofile2 'b 2)
(ltofile2 'c 0)
(ltofile2 'd 3)

Le but de la fonction inserer est de sortir une file avec les éléments directement ordonnancés en fonction de leur priorité (couple = '(élément priorité)). Ceci parce qu'il est nettement plus optimisé de créer une file directement ordonnée et d'extraire chaque fois le premier élément (la plus forte priorité étant le premier élément de la liste et decrescendo) que de créer une file et d'utiliser ensuite une fonction de tri dessus.

Cependant, vous pensez bien que si j'écris ici, c'est parce que mon code ne fonctionne pas vraiment. J'ai tenté plusieurs retouches mais en vain. Je ne trouve pas où est le problème et je commence à m'arracher les cheveux!

Bref, je serais super heureux si un de vous, expert, arrive à m'expliquer là où mon code ne fonctionne pas parce qu'il me semble que l'algorithme n'est pas faux à la base...

Merci d'avance!!

[Sherwood51]

Je crois que je suis arrivé à mes fins!
Pour ceux que cela intéresse, il est possible de comparer mon nouveau code à l'ancien.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
; Applications
; File à priorités
(define FileP '())

(define FileSortie '())

(define (CreerFileSortie e1 prio file4 FileSortie DebutFileP)
  (let ((couple (list e1 prio)))
    (if (null? file4)
        (begin
          (set! FileSortie (append DebutFileP (list couple)))
          FileSortie)
        (if (> prio (cadar file4))
            (begin
              (set! FileSortie (append DebutFileP (list couple) file4))
              FileSortie)
            (begin
              (set! DebutFileP (append DebutFileP (list (car file4))))
              (CreerFileSortie e1 prio (cdr file4) FileSortie DebutFileP))))))

(define (inserer e1 prio)
  (set! FileP (CreerFileSortie e1 prio FileP FileSortie '())))

(define (recuperer)
  (if (null? FileP)
      null
      (let ((x (car FileP)))
        (begin
          (set! FileP (cdr FileP))
          x))))