Clonage d'une liste simplement chaînée

Version imprimable

Bonjour à tous,

mon problème est le suivant, je dois réaliser une routine qui clone une liste simplement chaînée. Seulement, je ne vois pas très bien comment la réaliser.
Je vois bien pour 2 éléments mais après, je bloque ( et même avec des petits dessins :P).
Comme vous pouvez le voir, le éléments clonés à partir du 3e, seront mis avant le 2e... je vois pas du tout comment procéder pour les mettre dans le même ordre que dans la liste originelle.
Merci de me lire.
Voici donc les parties de l'unité que j'ai crée.

Code:

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
procedure   NouvelleListe(var l:Liste);
begin
	l:=nil;
 
end;
 
(* ------------------------------------------- *) 
 
function  ListeVide(l:Liste):boolean;
begin
	result:=l=nil;
end;
 
(* ------------------------------------------- *)
function  DansListe(e:ElemListe;l:Liste):boolean;
var temp:Liste;
begin
	temp:=l;
	while (temp<>nil) and not ElemlisteEgal(temp^.info,e) do  
		begin
			temp:=temp^.svt;
		end;
	result:=temp<>nil;
end;
 
(* ------------------------------------------- *)
 
function  InsererListe(E:ElemListe;var L:Liste):boolean;
var nouveau:liste;
begin
	if (not DansListe(E,L)) then
		begin
			new(nouveau);
			nouveau^.info:=E;
			nouveau^.svt:=L;
			L:=nouveau;
			result:=true;
		end
	else
		result:=false;
end;
 
(* ------------------------------------------- *)
 
procedure InsererModifierListe(E:ElemListe;var l:Liste);
var nouveau:liste;
begin
	nouveau:=l;
	while (nouveau<>nil) and not ElemlisteEgal(nouveau^.info,e) do  
			begin
				nouveau:=nouveau^.svt;
			end;
	if nouveau=nil then
		begin
			new(nouveau);
			nouveau^.info:=E;
			nouveau^.svt:=l;
			l:=nouveau;
		end
	else
		nouveau^.info:=E;		
end;
 
(* ------------------------------------------- *)
 
procedure Afficherliste(L:liste);
var temp:liste;
begin
	temp:=L;
	while (temp<>nil) do 
		begin
			write(temp^.info,' ');
			temp:=temp^.svt;
		end;
end;
 
(* ------------------------------------------- *)
 
procedure ClonerListe(var dest:Liste;source:Liste);
var svtsource,nouveaudest:Liste;
begin
	if source=nil then
		dest:=nil
	else
		begin
			new(dest);
			CopyElemListe(dest^.info,source^.info);
			dest^.svt:=nil;
			svtsource:=source^.svt;
			while (svtsource<>nil) do 
				begin
					new(nouveaudest);
					CopyElemListe(nouveaudest^.info,source^.info);
					nouveaudest^.svt:=dest^.svt;
					dest^.svt:=nouveaudest;
					svtsource:=source^.svt
				end;
			nouveaudest^.svt:=nil;
		end;
end;

07/06/2009, 20h57
M.Dlb

Il te faut faire avec un pointeur temporaire au lieu d'utiliser dest, car dest doit rester un pointeur sur la premier cellule de ta chaîne. Ensuite, toutes les opérations doivent se faire avec ce pointeur temporaire. ;)
10/06/2009, 11h13
xinx1

Bonjour et merci pour ta réponse.

J'ai fait exactement ce que tu m'as dit sur le code ci-dessus.
Dest pointe vers la première cellule de la liste, nouveaudest étant le pointeur temporaire.

Voilà, j'ai apporté des corrections. Ça marche, cependant, il me reste encore un problème à l'affichage de la liste clonée.
Voilà ce qui s'affiche sur la console:

voici la liste 2(liste clone) \377 \377 \377 \377 \377

Et voici ma routine de Clone:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 procedure ClonerListe(var dest:Liste;source:Liste); var svtsource,nouveaudest:Liste; begin if source=nil then dest:=nil else begin new(dest); CopyElemListe(dest^.info,source^.info); svtsource:=source^.svt; nouveaudest:=dest; while (svtsource<>nil) do begin new(nouveaudest^.svt); nouveaudest:=nouveaudest^.svt; CopyElemListe(nouveaudest^.info,source^.info); svtsource:=svtsource^.svt end; nouveaudest^.svt:=nil; end; end;
et tant qu'on y est, ma procédure Affiche:
Code:

1 2 3 4 5 6 7 8 9 10 procedure Afficherliste(L:liste); var temp:liste; begin temp:=L; while (temp<>nil) do begin write(temp^.info,' '); temp:=temp^.svt; end; end;
Merci de me lire

10/06/2009, 13h57
M.Dlb

Est-ce que ta procédure CopyElemListe fonctionne bien ? Quel est le type du champ info dans ta liste chaînée ?

Regarde du côté de la ligne CopyElemListe(nouveaudest^.info,source^.info); dans le clonage.

Aussi, vérifie bien que write fonctionne correctement pour le champ de ta liste.
10/06/2009, 17h12
xinx1
Et bien, la routine Affiche marche bien car la liste source s'affiche sans problème.

Voilà ma procédure CopyElemListe:
Code:

1 2 3 4 procedure CopyElemListe(el1,el2:ElemListe); (* où ElemListe est de type char*) begin el1:=el2; end;
10/06/2009, 17h54
M.Dlb

Bizarre, quel est le contenu de ta liste de départ ?
10/06/2009, 22h18
xinx1

C'est à l'utilisateur de taper les caractères
Sinon, comme dans mon premier post, tu peux voir que j'initialise la liste comme liste vide.
12/06/2009, 10h47
M.Dlb

Peux-tu faire une batterie de test, avec différentes chaines de caractères en entrée, puis clonage et affichage de la nouvelle chaine ?
12/06/2009, 13h07
xinx1

Le programme à l'écran se présente comme suit:

<1> creer liste1
<2> ajouter elem dans liste1 s'il n'existe pas
<3> ajouter ou modifier s'il existe
<4> afficher liste1
<5> supprimer elem de liste1
<6> copie profonde (clonage) de liste1 vers liste2
<7> affiche liste2
<8> quitter
choix ?

Test 1:

voici la liste 1 H U B L O T (Par ajouts successifs de ces lettres)
choix ? 6
clonage effectue
choix ? 7
voici la liste 2(liste clone) \377 \377 \377 \377 \377 \377

Test 2:

voici la liste 1 M O T U S
choix ? 6
clonage effectue
choix ? 7
voici la liste 2(liste clone) \377 \377 \377 \377 \377
12/06/2009, 13h33
M.Dlb

Honnêtement, je vois pas trop. En tournant ta routine de copie à la main, on obtient bien les mêmes chaînes. Peux-tu essayer, en remplaçant le type ElemListe par char directement ? Si tu peux faire un test avec des integers aussi.
12/06/2009, 13h56
xinx1

3 pièce(s) jointe(s)

Et bien, il y a bien un problème mais je ne vois pas lequel.

Voici, un test avec une liste d'integer:

voici la liste 1 5 9 4 7
choix ? 6
clonage effectue
choix ? 7
voici la liste 2(liste clone) -1 -1 -1 -1

en utilisant le type char sans passer par un types ElemListe, j'ai également le même problème que précédemment.

Enfin, le programme principal a été écrit par le prof, pour qu'on ne perde pas de temps.
Je vais joindre les fichiers pascal pour plus de clareté.
12/06/2009, 15h36
M.Dlb
Je pense avoir vu quelques chose de mal :P

Dans la procédure CopyElemListe, le premier paramètre est passé par valeur, et non par addresse, donc l'affectation n'est pas "propagée". Il faut, soit utiliser une fonction, soit passer le premier paramètre el1 par addresse (mot clé var devant).
Code:

1 2 3 4 procedure CopyElemListe(var el1,el2:ElemListe); (* où ElemListe est de type char*) begin el1:=el2; end;

Merci!!!!!

Je ne l'aurai pas trouvé tout seul :) Ça m'apprendra à être moins distrait!

Et c'est tellement bête....
Voilà donc mon code complet qui marche :D

Code:

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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
unit Uliste;
(* 1) liste dans laquelle on insere en tÍte .
   2)liste vide est un pointeur sur nil *)
INTERFACE
uses UElemListe;
type Liste =^cellule;
      cellule = record
                 info:char;
                 svt:Liste;
                end;
procedure   NouvelleListe(var l:Liste);
{ "crÈe" une liste vide }
function  ListeVide(l:Liste):boolean;
{ renvoie vrai si l est vide, faux sinon }
function  DansListe(e:char;l:Liste):boolean;
{ renvoie vrai si e est dans l
          faux sinon             }
function  InsererListe(E:char;var L:Liste):boolean;
 {  effet : insere E en dÈbut de L si E n'y existe pas,
              sinon ne fait rien  }
procedure InsererModifierListe(E:char;var l:Liste);
 { effet : insËre E en dÈbut de l si E n'existe pas
           ou remplace E dÈj‡ existant par E }
procedure Afficherliste(L:liste);
{ affiche le contenu de L Ècran }
procedure ClonerListe(var Dest:Liste;Source:Liste);
{ dest devient une liste clone de source }
function SupprimerDeListe(E:char;var L:Liste):boolean;
{ effet: supprime E dans L
         ne fait rien si E n'est pas dans L }
 
         IMPLEMENTATION
 
(* ------------------------------------------- *)
 
procedure   NouvelleListe(var l:Liste);
begin
	l:=nil;
 
end;
 
(* ------------------------------------------- *) 
 
function  ListeVide(l:Liste):boolean;
begin
	result:=l=nil;
end;
 
(* ------------------------------------------- *)
function  DansListe(e:char;l:Liste):boolean;
var temp:Liste;
begin
	temp:=l;
	while (temp<>nil) and not ElemlisteEgal(temp^.info,e) do  
		begin
			temp:=temp^.svt;
		end;
	result:=temp<>nil;
end;
 
(* ------------------------------------------- *)
 
function  InsererListe(E:char;var L:Liste):boolean;
(* Cette fonction ajoute un element par l'avant *)
var nouveau:liste;
begin
	if (not DansListe(E,L)) then
		begin
			new(nouveau);
			nouveau^.info:=E;
			nouveau^.svt:=L;
			L:=nouveau;
			result:=true;
		end
	else
		result:=false;
end;
 
(* ------------------------------------------- *)
 
procedure InsererModifierListe(E:char;var l:Liste);
var nouveau:liste;
begin
	nouveau:=l;
	while (nouveau<>nil) and not ElemlisteEgal(nouveau^.info,e) do  
			begin
				nouveau:=nouveau^.svt;
			end;
	if nouveau=nil then
		begin
			new(nouveau);
			nouveau^.info:=E;
			nouveau^.svt:=l;
			l:=nouveau;
		end
	else
		nouveau^.info:=E;		
end;
 
(* ------------------------------------------- *)
 
procedure ClonerListe(var dest:Liste;source:Liste);
var svtsource,nouveaudest:Liste;
begin
	if source=nil then
		dest:=nil
	else
		begin
			new(dest);
			CopyElemListe(dest^.info,source^.info);
			nouveaudest:=dest;
			svtsource:=source^.svt;
			while (svtsource<>nil) do 
				begin
					new(nouveaudest^.svt);
					nouveaudest:=nouveaudest^.svt;
					CopyElemListe(nouveaudest^.info,svtsource^.info);
					svtsource:=svtsource^.svt
				end;
			nouveaudest^.svt:=nil;
		end;
end;
(* ------------------------------------------- *)
 
function SupprimerDeListe(E:char;var L:liste):boolean;
var temp,precedent:Liste;
begin
	if (L=nil) then
		result:=false
	else if ElemlisteEgal(L^.info,E) then
		begin
			temp:=L;
			L:=L^.svt;
			dispose(temp);
			result:=true;
		end
	else
		begin
			temp:=L;
			while (temp<>nil) and not ElemlisteEgal(temp^.info,E) do
				begin
					precedent:=temp;
					temp:=temp^.svt;
				end;
			if (temp<>nil) then
				begin
					precedent^.svt:=temp^.svt;
					dispose(temp);
					result:=true;
				end
			else
				result:=false;
		end;
end;
 
(* ------------------------------------------- *)
 
procedure Afficherliste(L:Liste);
var temp:liste;
begin
	temp:=L;
	if (temp=nil) then
		writeln('La Liste est vide');
	while (temp<>nil) do 
		begin
			write(temp^.info,' ');
			temp:=temp^.svt;
		end;
end;
 
(* ------------------------------------------- *)
begin
	randomize
end.

et l'unité ElemListe:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
unit UElemListe;
 
interface
 
function ElemlisteEgal(el1,el2:char):boolean;
procedure CopyElemListe(var el1,el2:char);
 
implementation
(* ----------------------------------------------- *)
function ElemlisteEgal(el1,el2:char):boolean;
begin
	result:=el1=el2;
end;
(* ----------------------------------------------- *)
procedure CopyElemListe(var el1,el2:char);
begin
	el1:=el2;
end;
 
begin
	randomize
end.

Maintenant, je vais m'attaquer à l'insertion dans différents endroits de la liste et aussi faire une liste doublement chaînée... J'ai de quoi m'amuser encore quelques jours!

Merci beaucoup