Discussion :

[darkwall_37]

Bonsoir,

J'essaye de résoudre un exercice dont voici l'énoncé :

On considère deux liste chainées L1 et L2 contenant des entiers et triées par ordre croissant.
On souhaite créer une troisième liste L3, sans détruire les précédentes, et vérifiant la propriété suivante :
L3 contient, dans l'ordre croissant, les entiers communs à L1 et L2.

1°] Proposer un algorithme pour résoudre ce problème ( en considérant que L1 et L2 ne contiennent pas de doublons ).

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
/* On crée 2 nouvelles listes L1' et L2' pour ne pas modifier L1 et L2 */
L1'<-L1 
L2'<-L2

/* De même on fait pointer L3' sur L3 pour ne pas modifier L3 */
Allouer(L3')
L3<-L3'

/* Tant que l'on est pas arrivé au bout d'une des deux liste */
Tant que ( L1' <> NIL ou L2' <> NIL )

   /* Si une valeur du tableau L1 est aussi dans le tableau L2 */
   Si L1'.val = L2'.val  Alors
      L3'.val <- L1'.val    /* Alors on recopie cette valeur dans L3 */
      L3'<-L3'|.suiv        /* On passe à l'élément suivant de la liste L3 */
      Allouer(L3')          /* On alloue cet élément */      
      L1'<-L1'|.suiv        /* On passe à l'élément suivant dans L1 */

   Sinon L2'<-L2'|.suiv /* Sinon on passe à l'élément suivant dans L2 */

   Fin Si

Fin tant que

L3'<-NIL
Retourner(L3)

Par contre comme j'alloue déjà la mémoire pour la cellule suivante de la liste L3 dans la première structure de contrôle, au dernier passage je vais donc allouer une nouvelle cellule ayant un élément avec une valeur aléatoire et dont l'adresse de la cellule suivante va pointer sur n'importe quoi.
Du coup je met à NIL L3 le champs qui pointe sur la cellule suivante donc je me retrouve quand même avec un élément en trop. Donc je devrais reparcourir toute la liste pour supprimer ce dernier élément. Y'a pas un moyen de faire en sorte que ce problème ne se pose plus ?
Est-ce juste ? merci d'avance !

[Alikendarfen]

Bonjour Darkwall,

Plusieurs petites remarques :

- Il faut boucler tant qu'on est arrivé au bout d'aucune des listes L1 et L2 : donc le test est avec un "et" et non pas un "ou".

- Ensuite, il faut faire avancer la liste "la plus en retard". Tester si L1'.Val > L2'.Val ou si L1'.Val < L2'.Val et en fonction passer à l'élément suivant de la liste en retard

- Enfin, pour l'allocation, il ne faut allouer que si tu constates un élément commun et non pas allouer en avance : s'il n'y a pas d'éléments communs, il n'y a rien à allouer

bonne journée

[darkwall_37]

Pour l'allocation comme j'ai pu le faire remarquer je sais que j'ai un soucis mais je ne vois pas comment faire autrement. C'est pour ça que je demandais si quelqu'un avait une solution à me proposer.

J'arrête la boucle lorsque l'on arrive à la fin de L1 ou L2 en somme dès que l'on arrive à la fin de la plus petite liste. Je ne vois pas en quoi cela pose problème dans la mesure ou les listes sont triées par ordre croissant et qu'il n'y a pas de doublons. Les tests que tu mentionnes sont donc inutiles dans ce cas particulier non ? Si tu as un exemple pour illustrer...

Merci pour ta réponse.

[Alikendarfen]

Pour l'alloc, tu ne dois allouer que si tu constates un élément commun : pas d'allocation sinon.

Pour un exemple :
- L1 = [1 ; 2]
- L2 = [2]

Première itération : L1' = 1 ; L2' = 2 donc L2'<-L2'.suiv (soit nil)
Second itération : L1' = 1 ; L2' = nil donc ... je te laisse conclure

... et repense aussi à cette histoire de test de fin de ta boucle.

A+

[istace.emmanuel]

Si je puis me permettre discrètement,
pour ma part je me serais plutôt diriger vers les opérations ensembliste avec un petit algo de calcul d'intersection d'ensemble et un chouilla de récursivité pour parcourir mes données