Rajout d'une structure (liste)

**souviron34** · 22/10/2009, 18h12

Envoyé par m@tix

au début, pourquoi faire:

Code :

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

if ( nouveau_maillon != NULL )

?

Parce que si l'allocation échoue, il n'y rien à faire ni à changer

Ce qui se passe est simplement :

on veut ajouter un élément dans la liste :
- on tente d'allouer un élément
- si cela échoue, on ne fait rien
- si cela réussit :
-- on rempli les champs
-- si la liste est vide, on y installe le premier élément
-- si la liste est non vide, on va juste mettre à jour le pointeur "suivant" du dernier élment déjà stocké.

Envoyé par m@tix

Enfin, que représente le pointeur elt concrètement, et quelle est son utilité?

C'est juste un pointeur temporaire , permettant d'une part de ne pas faire de crash, et secondo de récupérer l'adrese du dernier élement de la liste.

Comme faire "liste->premier_maillon->suivant" ne t'amènera qu'au suivant, tu ne peux pas faire un truc itératif.. Le seul moyen de le faire est d'abstractiser "liste->premier_maillon" pour le rendre comme les autres maillons. D'où le "elt"..

@Médinoc : le problème est qu'il passe un objet et non un maillon, ce qui complexifie un peu par rapport à ta solution.. MAintenant, que tu en fasses une fonction sépparée ou que tu mettes directement dans le code, bof... D'autre part dans ton code tu ne mets pas à jour la liste

.. De plus, ton while ne donnera pas le bon résultat : le dernier de la liste est non null, donc tu passes dans le while.. On fait donc suivant.. Donc NULL. Et c'est la valeur qu'on renvoie..

En fait il faut mettre while ( maillon->suivant != NULL )

@diogene : je suis d'accord, mais vu qu'il n'avait qu'un seul pointeur, tu modifies sa spec..

**diogene** · 22/10/2009, 18h24

@diogene : je suis d'accord, mais vu qu'il n'avait qu'un seul pointeur, tu modifies sa spec..

Non, j'utilise ses spécifications . Dès son premier post, ontrouve :

Code :

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

1
2
3
4
5
6
7
struct liste{
 
	un_maillon * premier_maillon;
	un_maillon * dernier_maillon;
	un_maillon * maillon_courant; // pour se déplacer dans la liste sans perdre la place du premier maillon
 
};

**Médinoc** · 22/10/2009, 20h02

Envoyé par souviron34

De plus, ton while ne donnera pas le bon résultat : le dernier de la liste est non null, donc tu passes dans le while.. On fait donc suivant.. Donc NULL. Et c'est la valeur qu'on renvoie..

En fait il faut mettre while ( maillon->suivant != NULL )

Mais je ne demande pas le dernier maillon, je demande le dernier pointeur (enfin, son adresse): Celui, justement, qui est nul. Pour le modifier.

**souviron34** · 23/10/2009, 00h24

Envoyé par diogene

Non, j'utilise ses spécifications . Dès son premier post, ontrouve :

Code :

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

1
2
3
4
5
6
7
struct liste{
 
	un_maillon * premier_maillon;
	un_maillon * dernier_maillon;
	un_maillon * maillon_courant; // pour se déplacer dans la liste sans perdre la place du premier maillon
 
};

ok j'avais pas lu ça , désolé

C'était d'après le reste du code et de ce qu'il disait....

Envoyé par Médinoc

Mais je ne demande pas le dernier maillon, je demande le dernier pointeur (enfin, son adresse): Celui, justement, qui est nul. Pour le modifier.

Ou alors je ne comprend rien, mais :

Code :

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

1
2
3
	while(*ppMaillon != NULL)
		ppMaillon = &(*ppMaillon)->suivant;
	return ppMaillon;

le while ira bien jusqu'au dernier élément non null de la liste.. Donc on exécutera la ligne :

Code :

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

		ppMaillon = &(*ppMaillon)->suivant;

qui vaut NULL, et c'est bien celui ci qu'on va retourner, non ??

**Médinoc** · 23/10/2009, 09h21

À moins que je ne relise mal ce que j'ai écris, ppMaillon pointera sur le pointeur nul.

**souviron34** · 23/10/2009, 10h26

Envoyé par Médinoc

À moins que je ne relise mal ce que j'ai écris, ppMaillon pointera sur le pointeur nul.

absolument

Donc à quoi ça sert ?

**Médinoc** · 23/10/2009, 10h48

À modifier ce pointeur, pour ajouter le nouveau maillon tout à la fin de la liste simplement chaînée, peut-être?

Et comme au début il pointe sur le pointeur "premier" de la liste, ça marche même si celle-ci est vide.

**SofEvans** · 23/10/2009, 10h54

Souviron34, le pointeur pointe effectivement sur NULL mais on recupere l'adresse de ce pointeur ! Et non ce qu'il pointe.

On modifira ensuite ce que pointe le pointeur pour y mettre une adresse valide (celle du nouvel element).

**souviron34** · 23/10/2009, 10h55

Envoyé par Médinoc

À modifier ce pointeur, pour ajouter le nouveau maillon à la fin de la liste?

ta fonction GetPtr renvoie toujours NULL.

Quel peut bien être son intérêt ??

En plus tu l'écrases...

Note : Ah !! J'ai compris.... !!! à cause des **...

obfuscation....

Pourquoi faire compliqué quand on peut faire simple ????

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
un_maillon *GetDernierElt(une_liste *pListe)
{
	un_maillon *ppMaillon = pListe->premier_maillon;
	while(ppMaillon->suivant != NULL)
		ppMaillon = ppMaillon->suivant;
	return ppMaillon;
}
 
void AjouterEnDernier(une_liste *pListe, un_maillon *pNouveauMaillon)
{
	un_maillon *ppDernier = GetDernierElt(pListe);
	ppDernier->suivant = pNouveauMaillon ;
}

Ceci en assumant que la liste est non vide (sinon il faut affecter le premier-maillon)

Note 2 : d'ailleurs, dans ton code

Code :

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

1
2
 
&(*ppMaillon)->suivant;

ce serait plus lisible si c'était écrit (bien que ton écriture soit valable) :

Code :

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

&((*ppMaillon)->suivant) ;

**Médinoc** · 23/10/2009, 11h01

Le "truc" du double-pointeur a le mérite de marcher même quand la liste est vide, et marche aussi bien pour l'ajout à la fin que pour l'insertion n'importe où dans la liste (y compris au début).

C'est pour ça que j'aime bien le parcours indirect, quand j'ai besoin d'un itérateur permettant de modifier la liste.

**souviron34** · 23/10/2009, 11h02

Envoyé par Médinoc

À modifier ce pointeur, pour ajouter le nouveau maillon tout à la fin de la liste simplement chaînée, peut-être?

Et comme au début il pointe sur le pointeur "premier" de la liste, ça marche même si celle-ci est vide.

Envoyé par SofEvans

Souviron34, le pointeur pointe effectivement sur NULL mais on recupere l'adresse de ce pointeur ! Et non ce qu'il pointe.

On modifira ensuite ce que pointe le pointeur pour y mettre une adresse valide (celle du nouvel element).

ok, mais je répète :

obfuscation...

Pour économiser un if, on complexifie tellement la lecture que s'en devient ridicule...

M'enfin c'est mon point de vue...

**Médinoc** · 23/10/2009, 11h21

C'est peut-être une question de point de vue, ça me parait plus simple et plus naturel comme ça (en plus, j'ai des conventions de nommage qui aident). Bien sûr, si la liste est doublement chaînée, c'est une autre histoire.

**souviron34** · 23/10/2009, 11h33

je ne sais pas..

peut-être viens-tu du C++ ?

moi ce qui me paraît naturel c'est ce que j'ai écrit 2 pages plus haut, de même que diogene....

Qu'à la limite on coupe en 2 avec un GetLast, m'enfin..

**Médinoc** · 23/10/2009, 11h46

Ben non, je suis venu du C (j'ai même été grandement handicappé pour le C++, car mon me l'a mal enseigné), mais lors de mon premier TP sur les listes chaînées, j'ai mis un chaînage double.

Je ne sais pas trop pourquoi, mais les coups du "dernier objet" ou du if() m'ont paru moins naturels que le double-pointeur. Je pense que c'est parce qu'à mes débuts, je n'avais pas de structure liste, donc ma fonction d'insertion prenait un double-pointeur en paramètre de toute façon...

**souviron34** · 23/10/2009, 11h54

disons que je dirais que, sous-jacent, est plutôt la notion d'objet liste en tant que tel...

Pour moi, n'ayant eu aucun cours de POO, mais pensant naturellement OO (comme on l'a discuté ailleurs) en tant que physicien, pour moi une liste est juste une collection d'objets équivalent à un tableau, et donc je n'ai jamais eu besoin de doubles pointeurs...

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
typedef struct pRecord {
   int Param;
   ...
} Record ;
 
 
Record *Liste=NULL, *Last=NULL ;
 
 
....
 
Record *elt ;
 
for ( i = 0 ; i < N ; i++ )
  {
     elt = CreateRecord (Last);
     if ( Liste == NULL )
         Liste = elt ;
     Last = elt ;       
  }

**Médinoc** · 23/10/2009, 12h04

Je pense que les double-pointeurs me sont venus presque instinctivement quand j'ai eu besoin d'une fonction qui devait à la fois modifier un pointeur et retourner une valeur, comme mes reallocs.

D'un autre côté, quand on pense "objet", si l'on mettait tous les pointeurs dans des objets, on n'aurait en effet jamais besoin de double-pointeur. Mais dans ce cas, j'aurais pensé la liste comme ça:

Code C :

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
struct chainon;
 
struct lien
{
	struct chainon *p;
};
 
struct chainon
{
	int toto;
	struct lien suivant;
};
 
struct liste
{
	struct lien premier;
};

Là, on élimine, de manière un peu détournée, les double-pointeurs, mais n'empêche que pour ajouter un élément, ce sont les liens que je chercherais à modifier, pas les chainons.
Quand les structures liste et chainon sont différentes, je me concentre sur la partie commune: le lien.

Rajout d'une structure (liste)

C

Discussions similaires

Partager

Partager