Liste chainée c++ [Résolu]

Petit rappel sur les références :

Une référence sur un objet de type plop_t appelé plop s'écrit :

plop_t & p

Une référence permet de faire comme si on passait un pointeur sur p (son adresse), sauf que syntaxiquement tout se passe comme si c'était l'objet plop_t qui était passé. Ainsi :

#include <iostream>

void incrementer1(int & i){
  ++i;
}

void incrementer2(int * i){
  ++(*i);
}

void incrementer3(int i){
  ++i; 
  // on incrémente pas le i du main : 
  // le i passé à incrementer3 est une recopie du i de main
  // i est donc incrémentée juste dans la fonction incrementer3
}

int main(){
  int i = 0;
  std::cout << i << std::endl;
  incrementer1(i);
  std::cout << i << std::endl;
  incrementer2(&i);
  std::cout << i << std::endl;
  incrementer3(i); // ne modifiera pas i !!
  std::cout << i << std::endl;
  return 0;
}

affichera :

0
1
2
2

Une référence permet donc de bénéficier d'une syntaxe plus légère que celle basée sur des pointeurs tout en bénéficiant du passage par adresse ie :
- possibilité de modifier le paramètre (on utilise directement le "i" de main dans "incrementer1")
- il est plus rapide de passer une référence ou un pointeur que de recopier l'objet (incrementer1, incrementer2 sont donc plus rapides que incrementer3 car on ne recopie pas i) en particulier si l'objet est très gros.

Retour sur ton code

Ici on passe une référence sur un pointeur. Tout se passe syntaxiquement comme si on avait passé le pointeur lui même (un element *).

Le fait de passer un element *& revient cependant à passer l'adresse de ce pointeur (et donc permet de le modifier), ie un element **.

Cela signifie que la fonction qui appelle supprimer(debut) verra sa valeur de début modifiée. Ici c'est légitime car sinon cette variable début pointerait sur un objet que tu viens de supprimer (et son utilisation engendrerait probablement une erreur de segmentation).

En pratique

En pratique on utilise directement la classe de liste chaînée de la STL (standard template library) :
http://www.sgi.com/tech/stl/List.html

#include <list>
#include <iostream>

int main(){
    std::list<int> l;
    l.push_back(1);
    l.push_back(5);
    l.push_back(3);
    std::list<int>::const_iterator
        lit(l.begin()),
        lend(l.end());
    for(;lit!=lend;++lit){
        const int & elt = *lit;
        std::cout << elt << ' ';
    }
    std::cout << std::endl;
    return 0;
}

Bonne chance

Ok je vais te faire une explication plus détaillée.

Voici une fonction main toute simple:

int main()
{
    int *i = NULL;
    alloc(i);
    *i = 1

    return 0;
}

Voyons ce qui se passe ici.
je déclare int *i = NULL;

Ca signifie que quelque part dans la mémoire, mettons à l'adresse 100, je reserve une petite place pour ma variable i.
Dans cet emplacement mémoire, je vais mettre la valeur NULL, qui correspond à 0.

Voici donc ce qui se passe:

adresse | contenu
99     |       ?            
100    |       0
101    |       ?

Imagine qu'à ce niveau, tu essaies de faire:
*i = 2
La on va t'envoyer bouler car tu fais *i, ça signifie que tu essaies d'aller à l'adresse 0 pour y mettre la valeur 1. Or 0
est une adresse illégale.
Il faut que tu alloues une zone mémoire et que tu mettes l'adresse dans i. C'est à dire qu'à l'adresse 100, tu dois mettre une adresse qui pointe vers une zone ou tu peux déposer des trucs.

Alors mettons que le profil de alloc ce soit:

void alloc(int *test)
{
	test = new int;
}

Tu vas donc faire alloc(i).

Qu'est ce qui se passe quand tu fais ça?
Alloc va avoir sa variable test propre à lui à l'adresse 200 (au pif).
Et la valeur de i sera mise dans la variable test. Or la valeur de i c'est 0 (et non pas son adresse qui est 100).
Voici donc ce qui se passe:

adresse | contenu
200    |       0

Passons donc à
test = new int;

new int va retourner uen adresse vers une zone mémoire ou on peut stocker un entier. On va dire que cette adresse sera 300.
Voici ce qu'on a:

adresse | contenu
200    |       300

Et je te rappelle que pendant ce temps là il y a un endroit qui n'a pas changé:

adresse | contenu
100    |       0

Maintenant la fonction alloc est terminée. Et, comme c'est ce qu'il se passe en général avec une fonction, ses variables seront détruites. Donc test n'existera plus. Ca veut dire que tu as alloué une place dans ta mémoire à l'adresse 300 mais elle est perdue puisqu'il n'y a plus aucun pointeur qui contient cette adresse.

On sort de la fonction alloc donc et on arrive à
*i = 1

Je rappele que i c'est ça:

adresse | contenu
100    |       0

Et qu'avec cette instruction tu essaies de faire ça:

adresse | contenu
0    |       1

Impossible, l'adresse 0 est illégale!

Il faudrait trouver un moyen pour passer l'adresse de i dans alloc plutôt que de passer va valeur (qui est zero).
Et c'est ce que fait un pointeur de référence.
Avec cette fonction:

void alloc(int *&test)
{
	test = new int;
}

Voici ce qui se passe quand on fait alloc(i)
alloc va avoir sa variable test, mais l'adresse de cette variable sera la même que celle de i:

adresse | contenu
100      |       0

Donc quand on fera test = new int, il se passera ceci:

adresse | contenu
100       |       300

On sortira de la fonction, et on essaiera de faire *i=1
Et comme l'adresse de i est 100 est que son contenu est l'adresse 300, on aura

adresse | contenu
300     |     1

Et là ya plus de soucis.

Salut,

C'est une référence vers un pointeur.

Imaginons que tu veuilles allouer un entier en passant par une fonction.
Tu le ferais peut être comme ça:

void alloc(int *test)
{
	test = new int;
}

int main()
{
	int *pint = NULL;
	alloc(pint);
	delete pint;
	return 0;
}

Et là tu te mangerais une sale erreur durant l'execution.
Effectivement, tu passes pint en argument de alloc mais en fait tu passes juste la valeur de ce pointeur, c'est à dire l'adresse vers laquelle il pointe: NULL.
Dans alloc, test prendra donc la valeur NULL puis l'écrasera avec le resultat de new.
Après alloc pint vaudra toujours NULL puisqu'il n'a pas été changé. Donc le delete va échouer.
En fait ce qu'il faut passer dans alloc c'est une référence vers le pointeur:

void alloc(int *&test)
{
	test = new int;
}

Là ça marchera car ce ne sera plus NULL qui sera passé en argument mais l'adresse du pointeur pint et pint prendra
donc la valeur retournée par new. Et après l'execution de alloc, pint aura gardé cette valeur.

Donc dans ton code:
debut=debut->suivant;
Là après l'execution de la fonction, la pointeur passé en tant que debut aura bien changé pour pointer vers le suivant.

Tu saisis?

Merci de rependre à ma question
mais j'ai pas bien compri ce que Kilian dit, svp expliquer mois les chose d'une autre façon et avec plus de detail

Mais tu as bien lu la version de mamiemando? Ya plus de détails que dans mon explication....

Bon, en interne ça se passe pas tout à fait comme ça, mais je veux pas compliquer les choses. En visionnant
les choses comme je les ai expliquées ça fonctionne.

Merci beaucoup.