Discussion :

[Delnir]

bonjour,
voila, je n'est pas très bien comprit la façon de Dépiler:

pour moi Dépiler revien à faire:

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
 program empiler_depiler;
uses crt;
type liste=^cellule;
     cellule=record
             info:integer;
             suivant:liste;
             end;
 
procedure empiler(nb:integer;var a:liste);
var b:liste;
begin
  new(b);
  b^.info:=nb;
  b^.suivant:=a;
  a:=b;
end;
 
procedure depiler(var a:liste);
begin
  if (a<>nil) then a:=a^.suivant;
end;

Mais dans mes cours et tds le professeur le fait comme sa, je ne comprend pas du tout l'intêret de la seconde variable b :

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
 program empiler_depiler;
uses crt;
type liste=^cellule;
     cellule=record
             info:integer;
             suivant:liste;
             end;
procedure depiler(var a:liste);
var b:liste;
begin
  if (a<>nil) then
  begin
    b:=a;
    a:=a^.suivant;
    dispose(b);
end;

[M.Dlb]

Ton professeur a raison de procéder ainsi, puisqu'il désalloue la mémoire pointée par la tête de liste avant de supprimer la référence. Le principe est simple: puisqu'on veut supprimer la valeur en tête de liste, on fait pointer b sur la tête, on avance la "vraie" tête de liste qui restera après l'appel de la fonction, et on désalloue la zone mémoire pointée par b.

[Delnir]

Si je comprend bien, avec ce que j'ai écrit moi a:=a^.suivant, la mémoire pour a^.info est toujours alloué contrairement au professeur qui la désaloue en utilisant dispose?

[darrylsite]

Enfin c' est pas exactement ça.
Quand tu fait un new(a), tu reserves une place en memoire et tu pointes a vers cette adresse (l' adresse de la place que tu a alouée).
Or a contient un autre pointeur suivant ,qui lui pointe vers une autre adresse b.
Si tu fais seulement a:=a.suivant, tu abandonnes la place prealablement pointée par a pour l' adresse b puisque a.suivant egal à b.
Mais la place que tu as abandonnée existe toujours et tu ne pourras plus l' utiliser. Ce qui consommera de la memoire inutilement.

Or si tu fais

Code :

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

1
2
3
c:=a;
a:=a.suivant;
dispose(c);

c pointe bien vers l' adresse abandonnée par a. Et comme ça tu pourras la desallouer.

[droggo]

Zue,

Enfin c' est pas exactement ça.
Quand tu fait un new(a), tu reserves une place en memoire et tu pointes a vers cette adresse (l' adresse de la place que tu a alouée).
Or a contient un autre pointeur suivant ,qui lui pointe vers une autre adresse b.
Si tu fais seulement a:=a.suivant, tu abandonnes la place prealablement pointée par a pour l' adresse b puisque a.suivant egal à b.
Mais la place que tu as abandonnée existe toujours et tu ne pourras plus l' utiliser. Ce qui consommera de la memoire inutilement.

Or si tu fais

Code :

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

1
2
3
c:=a;
a:=a.suivant;
dispose(c);

c pointe bien vers l' adresse abandonnée par a. Et comme ça tu pourras la desallouer.

C'est précisément ce que Delnir semble avoir compris

Si je comprend bien, avec ce que j'ai écrit moi a:=a^.suivant, la mémoire pour a^.info est toujours alloué contrairement au professeur qui la désaloue en utilisant dispose?

suite au message de wormful_sickfoot

Ton professeur a raison de procéder ainsi, puisqu'il désalloue la mémoire pointée par la tête de liste avant de supprimer la référence. Le principe est simple: puisqu'on veut supprimer la valeur en tête de liste, on fait pointer b sur la tête, on avance la "vraie" tête de liste qui restera après l'appel de la fonction, et on désalloue la zone mémoire pointée par b.

[Delnir]

Merci pour votre aide !
j'ai un peut de mal sur les pointeurs donc j'ai une autre question:
Voila le but de l'exercice est l'insertion en fin de liste

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
Program pointeur;
uses crt;
type liste=^cellule;
     cellule=record
     info:integer;
     suivant:liste;
     end;
 
procedure lire(a:liste);
var x:integer;
    b:liste;
begin
  x:=1;
  new(b);
  b:=a;
  while (b<>nil) do
  begin
    writeln('element ',x,' :',b^.info);
    b:=b^.suivant;
    x:=x+1;
  end;
end;
 
procedure insertete(var a:liste;x:integer);
var b:liste;
begin
  new(b);
  b^.info:=x;
  b^.suivant:=a;
  a:=b;
end;
 
function dernier(a:liste):liste;
var b:liste;
begin
  new(b);
  b:=a;
  while (b^.suivant<>nil) do
  begin
    b:=b^.suivant;
  end;
  dernier:=b;
end;
 
procedure inserfin(a:liste;x:integer);
begin
  if dernier(a)=nil then insertete(a,x)
  else insertete(dernier(a)^.suivant,x);
end;
 
 
 
var a,b,c:liste;
    x,y:integer;
begin
  clrscr;
  new(a);
  a^.info:=1;
  a^.suivant:=nil;
  new(b);
  b^.info:=2;
  b^.suivant:=nil;
  a^.suivant:=b;
  new(c);
  c^.info:=3;
  c^.suivant:=nil;
  b^.suivant:=c;
  lire(a);
  writeln('donnez un entier:');
  readln(x);
  writeln;
  insertete(a,x);
  lire(a);
  writeln;
  writeln;
  writeln('donnez un entier:');
  readln(y);
  inserfin(a,y);
  lire(a);
end.

je comprend pas l'inserfin
pour moi dernier(a) c'est 3 et nil (le dernier élement pointer)
donc dernier(a)^.suivant ne pointe vers rien vu que dernier(a) c'est 3 et nil
je comprend absolument pas pourquoi inserfin marche!
si c'est possible de m'expliquer étape par étape ce que donne cette procédure car la je suis perdut...

[droggo]

Vou,

Attention, cette fonction peut poser un problème:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
function dernier(a:liste):liste;
var b:liste;
begin
  new(b);
  b:=a;
  while (b^.suivant<>nil) do
  begin
    b:=b^.suivant;
  end;
  dernier:=b;
end;

la ligne

Code :

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

  while (b^.suivant<>nil) do

va provoquer une erreur si b = nil

D'autre part, partout où tu fais

Code :

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

1
2
  new(b);
  b:=a;

il ne faut pas faire un new(b) pour immédiatement modifier la valeur de b en lui affectant la valeur d'un autre pointeur, qui écrase celle que tu viens d'obtenir, et qui ne pourra jamais servir.
Ce new(b) est une fuite de mémoire typique.

Il te faut corriger ça de partout où c'est nécessaire.

Corrections faites, la fonction devrait donc être quelque chose comme ceci :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function dernier(a:liste):liste;
var b:liste;
begin
  b:=a;
  if b <> nil then
  begin
    while (b^.suivant<>nil) do
    begin
      b:=b^.suivant;
    end;
  end;
 
  dernier:=b;
end;

Le code

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
begin
  clrscr;
  new(a);
  a^.info:=1;
  a^.suivant:=nil;
  new(b);
  b^.info:=2;
  b^.suivant:=nil;
  a^.suivant:=b;
  new(c);
  c^.info:=3;
  c^.suivant:=nil;
  b^.suivant:=c;
  lire(a);
  writeln('donnez un entier:');
  readln(x);
  writeln;
  insertete(a,x);
  lire(a);
  writeln;
  writeln;
  writeln('donnez un entier:');
  readln(y);
  inserfin(a,y);
  lire(a);
end.

est très laid.

Pourquoi insérer manuellement des valeurs dans la liste, alors que tu as des fonctions dont c'est le travail ?

Fonction lire : je l'aurais plutôt appelée Afficher, ou quelque chose du genre, qui représente mieux ce qu'elle fait : afficher les données de la liste.

Un principe important est d'utiliser des noms de fonctions/procédures/constantes/variables... significatifs pour leur fonction : le code devient plus clair à comprendre, et on évite quelques commentaires du style "lire va afficher...".
Il ne serait pas inutile de compléter cette procédure en faisant afficher "La liste est vide", le cas échéant.

Dans le cadre des noms significatifs, il n'est pas bon de cacher le fait qu'un type représente un pointeur. Une bonne habitudes est d'utiliser alors un nom qui commence par P, qui est le choix le plus fréquent.

Toujours dans le même cadre, mais c'est plutôt une question de formatage : il est bon, quand un nom provient de la concaténation de plusieurs mots, de mettre en majuscule la 1ère lettre de chaque, à l'exception éventuelle du 1er mot.
insertete
serait donc écrit préférentiellement
inserTete ou InserTete


Pour ta question, la fonction dernier(a) ne renvoie nil que si a = nil, donc si la liste est vide. On insère alors la nouvelle valeur en tête, sinon à la fin.
D'autre part, il serait utile de stocker la valeur renvoyée par le premier appel à dernier, ce qui éviterait le double appel de cette fonction, j'aurais donc plutôt fait

Code :

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

1
2
3
4
5
6
7
8
procedure inserfin(a:liste;x:integer);
var
  tampon : liste;
begin
  tampon := dernier(a);
  if tampon=nil then insertete(a,x)
  else insertete(tampon^.suivant,x);
end;

Après un coup d'oeil assez rapide, c'est tout pout l'instant.

[darrylsite]

Merci pour votre aide !
j'ai un peut de mal sur les pointeurs donc j'ai une autre question:
Voila le but de l'exercice est l'insertion en fin de liste

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
Program pointeur;
uses crt;
type liste=^cellule;
     cellule=record
     info:integer;
     suivant:liste;
     end;
 
procedure lire(a:liste);
var x:integer;
    b:liste;
begin
  x:=1;
  new(b);
  b:=a;
  while (b<>nil) do
  begin
    writeln('element ',x,' :',b^.info);
    b:=b^.suivant;
    x:=x+1;
  end;
end;
 
procedure insertete(var a:liste;x:integer);
var b:liste;
begin
  new(b);
  b^.info:=x;
  b^.suivant:=a;
  a:=b;
end;
 
function dernier(a:liste):liste;
var b:liste;
begin
  new(b);
  b:=a;
  while (b^.suivant<>nil) do
  begin
    b:=b^.suivant;
  end;
  dernier:=b;
end;
 
procedure inserfin(a:liste;x:integer);
begin
  if dernier(a)=nil then insertete(a,x)
  else insertete(dernier(a)^.suivant,x);
end;
 
 
 
var a,b,c:liste;
    x,y:integer;
begin
  clrscr;
  new(a);
  a^.info:=1;
  a^.suivant:=nil;
  new(b);
  b^.info:=2;
  b^.suivant:=nil;
  a^.suivant:=b;
  new(c);
  c^.info:=3;
  c^.suivant:=nil;
  b^.suivant:=c;
  lire(a);
  writeln('donnez un entier:');
  readln(x);
  writeln;
  insertete(a,x);
  lire(a);
  writeln;
  writeln;
  writeln('donnez un entier:');
  readln(y);
  inserfin(a,y);
  lire(a);
end.

je comprend pas l'inserfin
pour moi dernier(a) c'est 3 et nil (le dernier élement pointer)
donc dernier(a)^.suivant ne pointe vers rien vu que dernier(a) c'est 3 et nil
je comprend absolument pas pourquoi inserfin marche!
si c'est possible de m'expliquer étape par étape ce que donne cette procédure car la je suis perdut...

Il faut avouer qu' on ne peut le voir du premier coup d' oeil. J' ai meme desiné les differentes listes pour voir ce qui passe vraiment.

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
begin
  clrscr;
  new(a);
  a^.info:=1;
  a^.suivant:=nil;
  new(b);
  b^.info:=2;
  b^.suivant:=nil;
  a^.suivant:=b;
  new(c);
  c^.info:=3;
  c^.suivant:=nil;
  b^.suivant:=c;
  lire(a);
  writeln('donnez un entier:');
  readln(x);
  writeln;

A ce niveau, c vaut 3 et nil. Apres, on fait insertfin(a,y), ce qui a pour effet:
comme dernier(a)<>nil alors on fait insertete(c.suivant,y).Puisque c est le dernier element.

Code :

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

1
2
3
4
5
6
7
8
procedure insertete(var a:liste;x:integer);
var b:liste;
begin
  new(b);
  b^.info:=x;
  b^.suivant:=a;
  a:=b;
end;

On crée alors une nouvelle liste b qu' on fait pointer vers c.suivant qui vaut nil (b.suivant vaut donc nil) et on pointe c.suivant vers b (le nouvel element).
Le chainage en fin de liste est ainsi réalisé.

Cette maniere de faire n' est pas très propre (excuse moi, meme si c' est un professeur qui l' a fait mais il faut le dire). Il aurait du faire:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
procedure inserfin(a:liste;x:integer);
 var b:liste;
begin
  if dernier(a)=nil then insertete(a,x)
  else 
   begin
   new(b);
   b.info:=x;
   dernier(a)^.suivant:=b;
  end;
end;

[Delnir]

Voila une version plus clair avec aucun apelle de procedure pour mieux comprendre:

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
 
procedure ajoutEnQueue(var a:liste;x:integer);
var e,d:liste;
begin
  if a=nil then
  begin
    a^.info:=x;
    a^.suivant:=nil;
  end
  else
  begin
    e:=a;
    new(d);
    while (e^.suivant<>nil) do e:=e^.suivant;
    d^.info:=x;
    d^.suivant:=nil;
    e^.suivant:=d;
  end;
end;

Alors pour le cas ou a=nil ok, mais pour a <>nil je comprend pas du tout, point par point:
- A la fin du while e c'est le dernier élement de a donc e^.info=3 et e^.suivant=nil
-e^.suivant:=d -> on a e^.info=3 ensuite e pointe vers d qui lui vaux d^.info=x et d^.suivant=nil
donc au final je n'est absolument pas changer la liste a si j'avais voulut la changer j'aurai par exemple fait a^.suivant^.suivant:=e et la ok j'ai changer la liste a.
Je teste sur pc et j'ai la liste a changer, je comprend absolument pas pourquoi ! (j'ai dût louper quelque chose dans mon cour ou pas assimiler un point important)
merci d'avance pour vos explication !

pour suprimer en queue cela marche?
je ne sait pas si je doit utiliser dispose car je vois pas comment faire vu que je doit utiliser nil

Code :

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

1
2
3
4
5
6
7
8
9
10
11
procedure suprEnQueue(var a:liste);
var b,c:liste;
begin
  if a=nil then writeln('liste vide!')
  else
  begin
     b:=a;
    while (b^.suivant^.suivant<>nil) do b:=b^.suivant;
     b^.suivant:=nil;
  end;
end;

[droggo]

Boi,

Voila une version plus clair avec aucun apelle de procedure pour mieux comprendre:

Code :

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

1
2
3
4
5
6
7
8
9
 
procedure ajoutEnQueue(var a:liste;x:integer);
var e,d:liste;
begin
  if a=nil then
  begin
    a^.info:=x;
    a^.suivant:=nil;
  end

Alors pour le cas ou a=nil ok,

Ah bon ?

Tu testes si un pointeur est nil, et si c'est le cas, tu l'utilises tel quel ?

Pas envie de lire plus loin.

[darrylsite]

Voila une version plus clair avec aucun apelle de procedure pour mieux comprendre:

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
 
procedure ajoutEnQueue(var a:liste;x:integer);
var e,d:liste;
begin
  if a=nil then
  begin
    a^.info:=x;
    a^.suivant:=nil;
  end
  else
  begin
    e:=a;
    new(d);
    while (e^.suivant<>nil) do e:=e^.suivant;
    d^.info:=x;
    d^.suivant:=nil;
    e^.suivant:=d;
  end;
end;

Alors pour le cas ou a=nil ok, mais pour a <>nil je comprend pas du tout, point par point:
- A la fin du while e c'est le dernier élement de a donc e^.info=3 et e^.suivant=nil
-e^.suivant:=d -> on a e^.info=3 ensuite e pointe vers d qui lui vaux d^.info=x et d^.suivant=nil
donc au final je n'est absolument pas changer la liste a si j'avais voulut la changer j'aurai par exemple fait a^.suivant^.suivant:=e et la ok j'ai changer la liste a.
Je teste sur pc et j'ai la liste a changer, je comprend absolument pas pourquoi ! (j'ai dût louper quelque chose dans mon cour ou pas assimiler un point important)
merci d'avance pour vos explication !

Le truc n' est pas de changer la liste, mais d' ajouter un nouvel element à la liste.
A l' inverse des tableau, une liste chainée n' est pas representée de maniere contigue (les elements ne se suivent pas en memoire). Les elements peuvent etre separés par des kilometres (so to speak). Donc pour avoir la liste complete, il faut connaitre le premier element; c' est en partant de lui que tu peux avoir tous les autres elements (puisque chaque element montre où se trouve celui qui le succede).
Ainsi, pour ajouter un element à la fin, il faut juste crée cet element et faire indiquer sa position par le dernier element de la liste
soit la liste depart : a->b->c
pour ajouter un nouvel element,on fait juste c->d ce qui veut dire :
a->b->c->d. Mais la liste n' a t-elle pas changer ? si, elle a changer puisqu' on a desormais 4 element au lieu de 3.

pour suprimer en queue cela marche?
je ne sait pas si je doit utiliser dispose car je vois pas comment faire vu que je doit utiliser nil

Code :

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

1
2
3
4
5
6
7
8
9
10
11
procedure suprEnQueue(var a:liste);
var b,c:liste;
begin
  if a=nil then writeln('liste vide!')
  else
  begin
     b:=a;
    while (b^.suivant^.suivant<>nil) do b:=b^.suivant;
     b^.suivant:=nil;
  end;
end;

Un pointeur indique (ou contient l' adresse d' une place sur la memoire ou encore le chemin pour touver cette place) un emplacement en memoire.
Alors si plce est une place en memoire et pointe contient l' adresse pour trouver plce.Si je fais "pointe<-nil", j' efface l' adresse que pointe contient mais plce exite toujours puisque je ne l' ai pas touché.
Si je veux effacer plce, je dois faire dispose("adresse pour trouver plce") qui est encore egale à dispose(pointe) puisque pointe contient l' adresse de plce.

[Delnir]

Merci beaucoup darrylsite pour vos explications qui m'ont permit de comprendre comment fonctionner les pointeurs !
(pour le a=nil petit erreur dans le copier/coller)

[droggo]

Fio,

Merci beaucoup darrylsite pour vos explications qui m'ont permit de comprendre comment fonctionner les pointeurs !
(pour le a=nil petit erreur dans le copier/coller)

Une erreur de copier/coller ? Comment peux-tu faire ça ? Ta machine déconne à ce point ?