Discussion :

[Matheux14]

Bonjour,

Écrire un module permettant d'ajouter dans une liste doublement chainée après une position donnée.

Code Algorithme :

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
PROCEDURE AjouterApresPos ((E/S) tete : liste ; queue : liste ; pos : entier)
 
VARIABLE
 
P ; r : liste
 
i : entier
 
DEBUT 
 
       P <-- tete
 
    Tantque P =! pos et P =! NIL Faire 
 
          i <-- i + 1
    Fintantque
 
         Allouer(r)
 
         Lire(r^.info)
 
         r^.suivant <--

Je n'arrive pas à traduire ma simulation et faire intervenir la queue.

Alors ce serait super, si vous vouliez m'aider.

Merci d'avance.

[tbc92]

Tu écris un peu n'importe quoi au hasard. Ce n'est pas comme ça qu'on programme.

Tu as ces 3 lignes :

Code :

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

1
2
3
Tantque P =! pos et P =! NIL Faire 
    i <-- i + 1
Fintantque

Est-ce que tu vois pourquoi ce bloc de 3 lignes est catastrophique ?

Reprends les tout premiers cours que tu as eus, au collège peut-être. Relis les.

[Matheux14]

Ok, je vais d'abord le faire pour une liste simplement chainée et ensuite vous pourriez me guider sur la liste doublement chainée.

Code Algorithme :

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
PROCEDURE Ajout ((E/S) tete : liste)
 
                             VARIABLE
 
                               P : liste
 
DEBUT
 
        Allouer(P)
 
        Lire(P^.info)
 
         P^.suivant <-- tete
 
         tete <-- P
 
FIN

[Matheux14]

Vous êtes là ?

[Matheux14]

Code Algorithme :

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
PROCEDURE AjouterApresPos Liste doublement chainée ((E/S) liste, queue : liste ; Pos : Variant)
 
 
                              VARIABLES
 
                              P, r : Liste
 
                              i : entier
 
 DEBUT
 
                            P ← tete
 
                            i ← 1
 
                       Tantque P<> Nil et i <> Pos Faire
 
                           P ← P^.suivant
 
                            i ← i +1
 
                       Fintantque
 
                       Si P^.suivant <> Nil alors
 
                           Allouer(r)
 
                           Lire(r^.info)
 
                           r^.precedent ← P
 
                           r^.suivant ← P^.suivant
 
                           P^.suivant ← r
 
                          P^.suivant^.suivant ← r
 
                     Sinon
 
                          AjoutEnQueue (Queue)
 
                     Finsi
 
 FIN

[tbc92]

Gros progrès.
Les 2 premiers messages valaient 0 sur 20, et là, on est proche de la moyenne.

Je remplacerais le mot suivant par précédent ... une fois. Je te laisse trouver où.

Et à la fin, tu as recopié un truc trouvé quelque part : AjoutEnQueue(Queue)
Il faut effectivement traiter ce cas, mais tu ne le fais pas.

Dans ton tout premier message, la ligne d'entête disait : PROCEDURE AjouterApresPos ((E/S) tete : liste ; queue : liste ; pos : entier)Maintenant, c'est PROCEDURE AjouterApresPos Liste doublement chainée ((E/S) liste, queue : liste ; Pos : Variant)Tu sais expliquer/justifier les changements ?

[Matheux14]

La 34e ligne ?

Code Algorithme :

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
PROCEDURE AjoutEnQueue ((E/S) tete : liste ; pos : Entier)
 
                           VARIABLE
 
                            P : liste 
 
 DEBUT 
 
        Queue  ← AccesPosirion (Queue, Pos)
 
 
                    Allouer(P)
 
                    Lire(P^.info)
 
                    P^.suivant ← Nil
 
                    P^.precedent ← Queue
 
                    Queue^.suivant ←P
 
                    Queue ← P
 
FIN

[tbc92]

Non, pas la 34ème ligne.
Tu as dit que P était le précédent de R, donc R est le suivant de P : Ces 2 lignes se complètent bien.

En fait, il faut remplacer 'Suivant' par 'précédent' quelque part, mais pas seulement. J'avais laissé passé une erreur.

Procédure AjoutEnQueue()
Non, je vois au moins 2 trucs qui ne vont pas.

[Matheux14]

Non, pas la 34ème ligne.
Tu as dit que P était le précédent de R, donc R est le suivant de P : Ces 2 lignes se complètent bien.

En fait, il faut remplacer 'Suivant' par 'précédent' quelque part, mais pas seulement. J'avais laissé passé une erreur.

Je ne vois pas vraiment, quand je simule ; tout me semble bon.

Qu'est-ce qui n'est pas juste ?

Procédure AjoutEnQueue()
Non, je vois au moins 2 trucs qui ne vont pas.

Qu'est-ce qui n'est pas bon ?

[tbc92]

Sur ta procédure AjoutEnQueue() :
- Ligne 1 : Dans la ligne de déclaration de la procédure, tu as une variable nommée tête. Elle ne sert nulle part dans la suite.
- Ligne 9 : Tu appelles une fonction nommée AccesPosition() , ce n'est pas un mot clé du langage, c'est une fonction que tu dois décrire. Ce n'est pas fait.
- Ligne 9 encore : Dans l'appel de cette fonction, tu parles d'une variable Queue, on ne sait pas d'où elle vient.
- Ligne 14 : Tu exécutes l'instruction Lire (P.info) ; donc quand l'utilisateur utilise ton programme, il a déjà répondu à cette question au tout début du processus, et si on a besoin d'ajouter la nouvelle valeur en queue de liste, alors le programme ne se rappelle plus de la valeur à insérer, et l'utilisateur doit à nouveau répondre à la même question.

[Matheux14]

Code Algorithme :

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
FONCTION AccesPos((E/S) tete : liste Pos : entier)
 
              VARIABLE
 
                P : liste
 
DEBUT
 
        P <-- tete
 
   Tantque P <> Nil et Pos <> Faire
 
        Pos <--  Pos - 1
 
        P <-- P^.suivant
 
   Fintantque
 
     Retourner(P)
 
FIN

[Matheux14]

Code Algorithme :

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
PROCEDURE AjoutEnQueue ((E/S)  pos : Entier)
 
                           VARIABLE
 
                            P : liste 
 
 DEBUT 
 
        Queue  ← AccesPosirion (Queue, Pos)
 
 
                    Allouer(P)
 
                    P^.suivant ← Nil
 
                    P^.precedent ← Queue
 
                    Queue^.suivant ←P
 
                    Queue ← P
 
FIN

[tbc92]

Tout ça est très aléatoire.
Tu fais une proposition, en mettant des trucs au hasard. Puis tu changes des trucs au hasard. Et à un moment ou un autre, tu vas tomber sur quelque chose de plus ou moins correct. On te dira que c'est bon, et tu croiras que tu as trouvé.

Revenons à la première procédure. Samedi 17h59.
Tu avais en ligne 40 : AjoutEnQueue (Queue)Donc, tu considères que quand on va appeler la procédure AjoutEnQueue, on va lui passer un paramètre, et ce paramètre, c'est l'objet 'Queue'. Cet objet est de quelle nature ? C'est une liste.

Donc, quand tu écris la sous-procédure AjoutEnQueue, dans la première ligne de cette sous-procédure, tu dois être cohérent avec ce que tu écrivais la veille. La procédure AjoutEnQueue reçoit comme paramètre un objet de type Liste, pas un objet de type Entier.

En plus, en vrai, pour que le programme fonctionne, la ligne 40 du programme principal ne devrait pas être AjoutEnQueue (Queue) mais AjoutEnQueue (Queue, P) ...

Mais le vrai problème, c'est que des incohérences comme ça, il y en a encore plein. Même ce que tu avais proposé pour les listes simplement chaînées, ça ressemblait à peu près à rien du tout.

Pour faire des exercices de programmation, il faut programmer. Tu peux installer Python sur ton ordi, ou tu peux utiliser Python en ligne sur un lien comme celui-ci : Python en ligne
Et tu fais des essais. Tu écris un programme très court, 5 lignes, et tu testes.
Là, tu manipules des concepts abstraits... qui te dépassent complètement. En programmant avec Python (ou un autre langage) des trucs simples, tu vas rendre concret tous ces trucs.

Cet exercice est beaucoup trop compliqué pour toi... Révise les bases, relis les cours que tu as eus depuis le tout-début, refais tous les exercices.

[Matheux14]

D'accord et merci beaucoup.