Discussion :

[jeremux]

Bonsoir à tous j'essaie d'implanter les listes doublements chaînées, du moins en suivant les indications d'un tp mais je sèche pour la fonction inserer_avant . Je viens donc vous crier secours!

L'interface listeit.mli :

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
type 'a liste;;
type 'a iterateur;;
 
exception ListeVide;;
exception IterateurEnDebut;;
exception IterateurEnFin;;
 
(**
   [liste_vide] : crée une nouvelle liste vide
*)
val liste_vide : unit -> 'a liste
 
 
(** [ajouter_en_tete l e] : ajoute l'élément [e] en tête de la liste
    [l]
*)
val ajouter_en_tete : 'a liste -> 'a -> unit
 
(** [imprimer_sans_iterateur l f] : imprime le contenu de la liste [l]
    de la tête vers la queue en utilisant la fonction d'impression [f]
*)
val imprimer_sans_iterateur : 'a liste -> ('a -> unit) -> unit
 
(** [imprimer_sans_iterateur_envers l f] : imprime le contenu de la
    liste [l] de la queue vers la tête en utilisant la fonction
    d'impression [f]
*)
val imprimer_sans_iterateur_envers : 'a liste -> ('a -> unit) -> unit
 
(** [iterateur_en_debut l] : retourne un nouvel itérateur placé en
    début de la liste [l]
 
    Leve l'exception ListeVide si la liste est vide. 
*)
val iterateur_en_debut : 'a liste -> 'a iterateur
 
(** [iterateur_en_fin l] : retourne un nouvel itérateur placé en fin
    de la liste [l]
 
    Leve l'exception ListeVide si la liste est vide. 
*)
val iterateur_en_fin : 'a liste -> 'a iterateur
 
(** [est_en_debut it] : retourne vrai si l'itérateur [it] est en tête
    de liste
 
    Note : l'iterateur est en debut de liste si il est positionne sur
    le premier element de la liste.
*)
val est_en_debut : 'a iterateur -> bool
 
(** [est_en_debut it] : retourne vrai si l'itérateur [it] est en fin
    de liste
 
    Note : l'iterateur est en fin de liste si il est positionne sur le
    dernier element de la liste.
*)
val est_en_fin : 'a iterateur -> bool
 
(** [valeur it] : retourne la valeur de l'element ou se trouve
    positionne l'iterateur [it]
*)
val valeur : 'a iterateur -> 'a
 
(** [avancer it] : positionne l'itérateur [it] sur l'élément suivant
    de la liste
 
    Lève l'exception IterateurEnFin si on est en fin de liste. Dans ce
    cas l'itérateur n'est pas modifié.
*)
val avancer : 'a iterateur -> unit
 
(** [reculer it] : positionne l'itérateur [it] sur l'élément précédent
    de la liste
 
    Leve l'exception IterateurEnDebut si on est en fin de liste. Dans ce
    cas l'itérateur n'est pas modifié.
*)
val reculer : 'a iterateur -> unit
 
 
(** [inserer_avant it e] : insère l'élément [e] avant l'élément pointé
    par l'itérateur [it]
*)
val inserer_avant : 'a iterateur -> 'a -> unit
 
 
(** [inserer_apres it e] : insère l'élément [e] après l'élément pointé
    par l'itérateur [it]
*)
val inserer_apres : 'a iterateur -> 'a -> unit

La source: listeit.ml

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
exception ListeVide;;
exception IterateurEnDebut;;
exception IterateurEnFin;;
 
 
type 'a liste = {
  mutable tete     : 'a liste_interne;
  mutable queue    : 'a liste_interne }
and 'a liste_interne = 
  | Vide 
  | Cons of 'a cellule 
and 'a cellule = {
  valeur : 'a;
  mutable suivant   : 'a liste_interne;
  mutable precedent : 'a liste_interne }
and 'a iterateur = {
  mutable p: 'a liste_interne;
  mutable c: 'a liste_interne;
  mutable s: 'a liste_interne
}
 
 
let liste_vide () = 
  { tete = Vide; queue = Vide }
 
 
let la_cellule l =
  match l with
    | Vide -> raise ListeVide
    | Cons a -> a
 
 
let ajouter_en_tete l v =
  let nouvelle_tete = { valeur = v ; suivant = l.tete ; precedent = Vide }
  in
  match l.tete with
    | Vide -> 
      l.tete <- Cons nouvelle_tete;
      l.queue <- l.tete
    | Cons ancienne_tete ->
      l.tete <- Cons nouvelle_tete;
      ancienne_tete.precedent <- l.tete
 
 
let imprimer_sans_iterateur l imp =
  let rec imprimer_interne li =
    match li with
      | Vide -> 
	Printf.printf "\n"
      | Cons c -> 
	imp c.valeur;
	imprimer_interne c.suivant
  in
  imprimer_interne l.tete
 
let imprimer_sans_iterateur_envers l imp =
  let rec imprimer_interne li =
    match li with
      | Vide -> 
	Printf.printf "\n"
      | Cons c -> 
	imp c.valeur;
	imprimer_interne c.precedent
  in
  imprimer_interne l.queue
 
let iterateur_en_debut l =
	if (l.tete=Vide) then
		raise ListeVide
	else
		{p=Vide;c=l.tete;s=(la_cellule (l.tete)).suivant};;
 
 
 
let iterateur_en_fin l =
	if (l.tete=Vide) then
		raise ListeVide
	else
		{p=(la_cellule (l.queue)).precedent;c=l.queue;s=Vide};;
 
let est_en_fin it =
	if (it.s=Vide) then
		true
	else
		false;;
 
let est_en_debut it =
	if (it.p=Vide) then
		true
	else
		false;;
 
let avancer it =
	if (est_en_fin it) then
		raise IterateurEnFin
	else
	begin
		it.p<-it.c;
		it.c<-it.s;
		it.s<-(la_cellule (it.s)).suivant
	end;;
 
 
let reculer it =
	if (est_en_debut it) then
		raise IterateurEnDebut
	else
	begin
		it.s<-it.c;
		it.c<-it.p;
		it.p<-(la_cellule (it.p)).precedent
	end;;
 
 
let valeur it =
	(la_cellule (it.c)).valeur;;
 
let inserer_avant it e =
	let it2 = {p=it.p;c=Cons {valeur=e;suivant=it.s;precedent=it.p};s=it.c}
	in
	it.p<-it2.c;
	reculer it;;
 
 
let inserer_apres it e =
	let it2 = {p=it.c;c=Cons {valeur=e;suivant=it.s;precedent=it.c};s=it.s}
	in
	it.s<-it2.c;
	avancer it;;

C'est un peu compliqué mais je pense que pour les habitués de ce langage ce que j'ai écrit reste lisible.

Merci d'avance et bonne soirée,

Jeremux.

[gorgonite]

encore un problème de "pureté" (enfin d'absence de pureté)
tu modifies l'itérateur mais pas la liste...


il ne faut pas seulement changer le pointeur interne dans ton itérateur, mais également répercuter le changement sur la vraie liste

je te laisse réfléchir

[jeremux]

C'est ce que je me suis dit également avant mon sommeil . Merci beaucoup .

[jeremux]

J'ai un début de code, mais ça pose problème lorsque je souhaite ajouter un élément avant le premier élément de la liste, ce problème je l'ai remarqué en affichant la liste.

Le code de la fonction:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
let inserer_avant it e =
	let list_interne = Cons {valeur=e;suivant=it.c;precedent=it.p}
	in
	if (est_en_debut it) then
		(la_cellule it.c).precedent<-list_interne
	else
	begin
		(la_cellule it.c).precedent<-list_interne;
		(la_cellule it.p).suivant<-list_interne
	end;
	let it2 = {p=it.p;c=Cons {valeur=e;suivant=it.s;precedent=it.p};s=it.c}
	in
	it.p<-it2.c;
	reculer it;;

Pour inserer_apres c'est quasi similaire.

[Cacophrene]

Bonjour,

J'avais écrit un billet sur les listes doublement chaînées (circulaires). Tu peux peut-être y trouver des infos, même si nous n'utilisons pas tout à fait la même implémentation.

Cordialement,
Cacophrène

[gorgonite]

pour infos, est-il vraiment sûr que la rôle insérer_avant ne dépende que de l'itérateur ?