Inversion d'une liste chaînée

Version imprimable

24/05/2006, 12h26
sossomj

Inversion d'une liste chaînée

svp c'est très très très urgent je suis surtout bloqué dans l'inversion, j'en ai besoin le PLUS VITE possible.

Jje vous donne l'énoncé :

écrire un programme d'une liste chainée personne contenant numero et nom de la personne le programme doit faire:

1- création de la liste personne
2- affichage de la liste.
3- ajout d'une personne:
a/ en tete de liste
b/ a une position K
c/ en que de liste
4- supprimer une personne
a/ en tete de liste
b/ a une position K
c/ en que de liste
5 - inversion de la liste personne.
6- quitter

svp aidez-moi je fais de mon mieux pour réesoudre le problème mais je n'y arrive pas :cry:

Merci d'avance, plein de succès pour le forum !
24/05/2006, 17h09
Eric Sigoillot

C'est pas de bol, nous, on n'est pas pressé... En plus balancer un sujet de TP sans même montrer qu'on y a réfléchi ça a tendance à me ralentir encore un peu plus.

Donc tu n'auras aucune solution (même pas un début) tant que tu ne nous auras pas dit ce que tu as déjà fait.

Et je supprime à vue tout post donnant une solution tant que sossomj n'aura pas fait d'effort.

Sinon pour le Père Noël et ses cadeaux sous forme de programme tout prêt, tu t'es trompé de date :aie:

@++

rep

Citation:

Envoyé par Eric Sigoillot

C'est pas de bol, nous, on n'est pas pressé... En plus balancer un sujet de TP sans même montrer qu'on y a réfléchi ça a tendance à me ralentir encore un peu plus.

Donc tu n'auras aucune solution (même pas un début) tant que tu ne nous auras pas dit ce que tu as déjà fait.

Et je supprime à vue tout post donnant une solution tant que sossomj n'aura pas fait d'effort.

Sinon pour le Père Noël et ses cadeaux sous forme de programme tout prêt, tu t'es trompé de date :aie:

@++

je tiens à vous dire que je ne triche pas et que j'ai fourni beaucoup d'efforts voila mon travail:

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
175
176
177
178
179
180
181
program liste_chaine;
uses wincrt;
function menu: integer;
var choix: integer;
begin
writeln (' Faites votre choix: ');
writeln (' ');
writeln (' 1. Création de la liste chaînée');
writeln (' 2. Consultation de la liste chaînée');
writeln (' 3. Insertion d"un élément');
writeln (' 4. Suppression d"un élément');
writeln (' 6. inversion');
writeln (' 5. Quitter 1"application');
 
readln (choix);
menu:= choix
end;
function sous_menu: integer;
var choix: integer;
begin
writeln ('l. En tête de liste');
writeln ('2. En queue de liste');
writeln('3. A une position k');
writeln ('4. Retour au menu principal');
writeln('Entrez votre choix: ');
readln(choix);
sous_menu:= choix
end;
type pointeur= ^personne;
Personne = record
numero: integer;
nom : string[20];
suivant: pointeur;
end;
var debut, courant, precedent, nouv: pointeur;
choix, s_choix, num: integer;
reponse: char;
begin
writeln (' UNIVERSITE A/MIRA - BEJAIA');
writeln (' ');
writeln (' FACULTE DES SCIENCES ET SCIENCE DE L"INGENIEUR');
writeln (' ');
writeln (' DEPARTEMENT INFORMATIQUE');
writeln (' ');
writeln ( ' BIENVENUE AU TP DE Mr AMGHAR SOFIANE');
writeln (' ');
writeln (' ');
writeln (' ');
 
choix:= menu;
repeat
{ Création de la liste chaînée }
 
if choix = 1 then
begin
new(debut);
courant:= debut;
repeat
writeln ('Entrez le No et le nom de la personne');
readln (courant^.numero, courant^.nom);
writeln('Autre personne à inserer ? o/n ');
readln(reponse);
if reponse = 'o' then
begin new(courant^.suivant);
courant:= courant^.suivant
end
else courant^.suivant:= nil;
until reponse = 'n';
end
{Consultaion de la list}
 
else if choix= 2 then
begin
courant:= debut;
while courant <> nil do
begin
writeln(courant^.numero,' ',courant^.nom);
writeln ('');
courant:= courant^.suivant
end
end
{Insertion d'un Elément}
else if choix = 3 then
begin
repeat
s_choix:= sous_menu; { Afficher le sous menu }
if s_choix <> 4 then
{On crée le nouveau élément à insérer}
begin
new(nouv);
writeln ('Entrez le No et le nom de la personne');
readln(nouv^.numero, nouv^.nom);
end;
{Insertion en tête de liste }
if s_choix = 1 then
begin
nouv^.suivant:= debut;
debut:= nouv;
end
 
else if s_choix = 2 then
{Insertion en queue de liste}
begin
courant:= debut;
while courant^.suivant <> nil do
courant:= courant^.suivant;
courant^.suivant:= nouv;
nouv^.suivant:= nil;
end
 
else if s_choix = 3 then
{ Insertion à une position k }
begin
writeln ('N° de la personne après laquelle insérer');
readln(num);
courant:= debut;
while courant <> nil do
begin
if courant^.numero = num then
begin nouv^.suivant:= courant^.suivant;
courant^.suivant:= nouv;
end;
courant:= courant^.suivant;
end;
end;
until s_choix = 4
end
 
else if choix = 4 then {Suppression d'un élément}
begin
repeat
s_choix:= sous_menu;
 
if s_choix = 1 then {Suppression en tête de liste }
begin
dispose(debut);
debut:= debut^.suivant;
writeln('Suppression éffectuée');
end
 
else if s_choix = 2 then
{ Suppression en queue de liste}
begin
courant:= debut;
while courant^.suivant^.suivant <> nil do
courant:= courant^.suivant;
dispose(courant^.suivant);
courant^.suivant:= nil;
writeln ('Suppression effectuée')
end
 
else if s_choix = 3 then
{Suppression à une position k }
begin
writeln ('N° de la personne à supprimer');
readln(num);
precedent:= debut;
courant:= debut^.suivant;
while courant <> nil do
begin
if num = courant^.numero then
begin
dispose(courant);
precedent^.suivant:= courant^.suivant;
courant:= nil;
end
else begin
precedent:= courant;
courant:= courant^.suivant
end
end;
writeln('Suppression effectuee');
end
until s_choix = 4;
end
else
writeln ('Choix de menu inexistant! Recommencez.');
 
choix:= menu;
until choix = 5;
end.

voila! le seul truc qui me manque c'est l'inversion, svp aidez moi :cry:

24/05/2006, 20h58
Loceka
L'algorithme d'inversion est relativement simple si tu le fais de manière récursive.

Il suffit de se placer sur le dernier élément puis de le faire pointer vers l'élément "père" et de remonter la chaîne de cette manière.
Code:

1 2 3 4 5 6 7 8 inverseListe(noeud, pere) debut si (courant.suivant != vide) debut inverseListe(courant.suivant, courant); fin si courant.suivant = pere; fin
Bon, j'ai pas testé et je n'ai jamais utilisé de listes chaînées, mais ça me semble correct.

Si ça ne l'est pas, ta question a plus sa place dans le forum algorithmie, mais je te conseille de faire un tour sur google, car il doit bien y avoir la réponse quelque part...

PS :
Pense à la balise "code" (je la vois pas d'ailleurs dans les options WYSIWYG), mais c'est [ code ] et [ /code ], sans les espaces.
La couleur c'est bien, mais avoir un texte indenté, c'est mieux ! ;)

Loceka.
24/05/2006, 21h16
sossomj

rep
Citation:
Envoyé par Loceka

L'algorithme d'inversion est relativement simple si tu le fais de manière récursive.

Il suffit de se placer sur le dernier élément puis de le faire pointer vers l'élément "père" et de remonter la chaîne de cette manière.

Code:

1 2 3 4 5 6 7 8 inverseListe(noeud, pere) debut si (courant.suivant != vide) debut inverseListe(courant.suivant, courant); fin si courant.suivant = pere; fin

Bon, j'ai pas testé et je n'ai jamais utilisé de listes chaînées, mais ça me semble correct.

Si ça ne l'est pas, ta question a plus sa place dans le forum algorithmie, mais je te conseille de faire un tour sur google, car il doit bien y avoir la réponse quelque part...

PS :
Pense à la balise "code" (je la vois pas d'ailleurs dans les options WYSIWYG), mais c'est [ code ] et [ /code ], sans les espaces.
La couleur c'est bien, mais avoir un texte indenté, c'est mieux ! ;)

Loceka.
merci je v essayer
24/05/2006, 21h47
Tuxico

la récursivité c'est p-e pas le plus efficace si?
24/05/2006, 22h28
Eric Sigoillot
L'inversion d'une liste chaînée est une des opérations les plus simples, en effet.
Un algo simple suffit :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 T = Tête de liste Q = nul P = nul Tant que T n'est pas nul faire P = T T = T.suivant P.suivant = Q Q = P Fin tant que Q représente la liste inversée
Ca doit fonctionner tout seul... Algorithme en O(n), on ne fera pas mieux.

@++
24/05/2006, 23h12
Loceka

@ Tuxico : j'ai pas dit que ça l'était, j'ai seulement dit que c'était un algo qui devait répondre au problème.

Enfin, ça me semble relativement proche de la solution d'Eric Sigoillot (dur de se faire au changement de login ^^), sauf peut-être en ce qui concerne les appels de fonction (je sais pas si ça prend plus de temps de calcul).

En tout cas la dernière solution proposée semble être la méthode itérative associée à la méthode récursive que j'ai écrite.
25/05/2006, 11h27
Eric Sigoillot

En Pascal, l'itératif a des chances de mieux passer (mais c'est à étudier au cas par cas). Mais c'est en effet le même algorithme (y'en n'a pas 500 de toutes façons !).

Sinon, Loceka, tu peux m'appeler Eric, on est entre amis ;)

@++
25/05/2006, 19h50
sossomj

rep
Citation:
Envoyé par Eric Sigoillot

L'inversion d'une liste chaînée est une des opérations les plus simples, en effet.
Un algo simple suffit :

Code:

1 2 3 4 5 6 7 8 9 10 11 12 T = Tête de liste Q = nul P = nul Tant que T n'est pas nul faire P = T T = T.suivant P.suivant = Q Q = P Fin tant que Q représente la liste inversée

Ca doit fonctionner tout seul... Algorithme en O(n), on ne fera pas mieux.

@++
merci je v essayer de l'integrer dans mon programme, je vous tien au courant
25/06/2006, 15h51
mario52
bonjour

une suggestion dans ce cas de programme
pourquoi ne pas utiliser la fonction "case" plutôt que if...then....else
Code:

1 2 3 4 5 6 case s_choix of 1: begin instruction end; 2: begin instruction end; 3: begin instruction end else begin instruction end; end;
c'est pas plus clair ? et moins de code non ?