Discussion :

[sorry60]

Salut,

Bon je debute niveau liste chainée, j'ai besoin de m'y exercer avant de continuer mon projet reseau.
Donc pour le moment je commence calme : une liste simplement chaînée.
Dont voici la structure :

Code :

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

1
2
3
4
5
6
 
typedef struct liste
{
	int val;
	struct liste* suivant;
}liste;

J'ai écrit, avec un peu de mal, une première fonction qui ajoute un élément en fin de liste, la voici :

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
 
#ifdef __cplusplus
#error Be sure you are using a C compiler...
#endif
 
#include "liste.h"
 
liste* ajouter(liste *pListe, int valeur)
{
	liste nouv;
	/* On se positionne à la fin */
	while(pListe)
	{
		pListe = pListe->suivant;
	}
	nouv.val = valeur;
	nouv.suivant = NULL;
	pListe = &nouv;
 
	return pListe;
}

Ensuite, une petite main pour tester..

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
 
#ifdef __cplusplus
#error Be sure you are using a C compiler...
#endif
 
#include "liste.h"
 
int main()
{
	/* notre pointeur sur une liste bientot chainée ! */
	liste* pMaListe = malloc(sizeof(liste));
	pMaListe = NULL;
	/* on ajouter un élément ! */
	pMaListe = ajouter(pMaListe,0);
	/* on regarde si ça marche...*/
	if(pMaListe)
	{
		printf("Valeur : %d\n",pMaListe->val);
	}
	else
	{
		printf("Ta liste est toujours vide idiot...\n");
	}
 
	system("Pause");
	return 0;
}

Ca compile bien mais fonctionne pas correctement à l'execution.

Valeur : 8
Appuyez sur une touche pour continuer...

Je ne trouve pas mon erreur

[Emmanuel Delahaye]

Bon je debute niveau liste chainée, j'ai besoin de m'y exercer avant de continuer mon projet reseau.

C'est la panique !

Ton code commenté mais non corrigé.

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
 
#include "liste.h"
 
#include <stddef.h>
 
liste* ajouter(liste *pListe, int valeur)
{
    liste nouv;
    /* On se positionne à la fin */
 
    /* -ed- etant donne que l'on demarre avec pListe valant NULL, on entre pas ici. */
    while(pListe != NULL)
    {
        pListe = pListe->suivant;
    }
 
    /* -ed- tout ca est local. */
    nouv.val = valeur;
    nouv.suivant = NULL;
 
    /* -ed- l'adresse d'une local ? */
    pListe = &nouv;
 
    /* -ed- Mais c'est qu'il la retourne l'animal  !!!
    Comportement indefini
    */
    return pListe;
}

et

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
 
#include "liste.h"
 
int main()
{
    /* notre pointeur sur une liste bientot chainée ! */
 
/* -ed- 
    liste* pMaListe = malloc(sizeof(liste));
    pMaListe = NULL;
    
Pourquoi avoir alloue un bloc pour en perdre l'adresse a la ligne suivante ? 
*/
 
    liste* pMaListe = NULL;
 
    /* on ajouter un élément ! */
    pMaListe = ajouter(pMaListe,0);
 
    /* on regarde si ça marche...*/
    if(pMaListe != NULL)
    {
        printf("Valeur : %d\n",pMaListe->val);
    }
    else
    {
        printf("Ta liste est toujours vide idiot...\n");
    }
 
    system("Pause");
    return 0;
}

[sorry60]

Bon je debute niveau liste chainée, j'ai besoin de m'y exercer avant de continuer mon projet reseau.

C'est la panique !

Non pas du tout, ce n'est qu'un projet personnel, pas scolaire
Ok merci pour tes commentaires, je vais les etudier et corriger mon code.

[sorry60]

Ok ok j'ai fait en effet un peu n'importe quoi
Voila mon code corrrigé, qui maintenant semble être ok

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
 
/* Fonction qui ajoute un élément en fin de liste */
liste* ajouter(liste *pListe, int valeur)
{
	int nbElements = 0;
	liste *nouv = malloc(sizeof(liste));
	/* On se positionne à la fin */
	while(pListe)
	{
		pListe = pListe->suivant;
		nbElements++;
	}
	printf("La liste comportait %d element(s) avant l'ajout.\n",nbElements);
	nouv->val = valeur;
	nouv->suivant = NULL;
	pListe = nouv;
 
	return pListe;
}

Le main est inchangé...
Tampon "lu et approuvé" ?

Edit :
Si le main est changé !

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
 
int main()
{
	/* notre pointeur sur une liste bientot chainée ! */
	liste* pMaListe = NULL;
 
	/* on ajouter un élément ! */
	pMaListe = ajouter(pMaListe,5);
	fflush(stdout);
	/* on regarde si ça marche...*/
	if(pMaListe)
	{
		printf("Valeur : %d\n",pMaListe->val);
	}
	else
	{
		printf("Ta liste est toujours vide idiot...\n");
	}
 
	system("Pause");
	return 0;
}

[sorry60]

J'ai essayé d'ajouter 3 éléments, puis de les afficher, mais ça ne m'affiche que le dernier

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
 
/* notre pointeur sur une liste bientot chainée ! */
	liste* pMaListe = NULL;
	/* on ajouter un élément ! */
	pMaListe = ajouter(pMaListe,1);
	/* on en ajoute un deuxieme ! */
	pMaListe = ajouter(pMaListe,2);
	/* on en ajoute un troisieme ! */
	pMaListe = ajouter(pMaListe,3);
 
	/* On verifie...*/
	while(pMaListe)
	{
		printf("Valeur : %d\n",pMaListe->val);
		pMaListe = pMaListe->suivant;
	}

[Emmanuel Delahaye]

Voila mon code corrrigé, qui maintenant semble être ok <...> Tampon "lu et approuvé" ?

Non !

Cest un peu mieux, mais ca ne fonctionne que pour un element.

Essaye maintenant d'en ajouter un second. Tu vas voir que ca se passe mal. En effet, tu ne fais pas de lien.

En fait, il y a 2 cas.

• la liste est vide, et on fait ce tu as fait, sauf qu'il est initile de chercher la fin, on yest.
• la liste est non vide et la, on cherche le dernier element
  (celui qui pointe vers NULL), et on fait les liens qui vont bien.

Nota. La premiere chose a faire quand on implemente les listes chainees est de realiser un outill de lecture de la liste.
Ca permet tout de suite de visualiser le chainage.
Ne pas oublier non plus la liberation de la liste qui est un peu particuliere...

Code commenté mais non (peu) corrigé

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
 
/* Fonction qui ajoute un élément en fin de liste */
#include "liste.h"
#include <stdlib.h>
 
liste* ajouter(liste *pListe, int valeur)
{
    int nbElements = 0;
 
    /* -ed-
       liste *nouv = malloc(sizeof(liste));
     
       je rappelle l'ecriture 'canonique' 
       
       Ne pas oublier non plus le test. Comme toujours, malloc() peut echouer
    */
    liste *nouv = malloc(sizeof*nouv);
 
    if (nouv != NULL)
    {
        /* On se positionne à la fin */
        while (pListe)
        {
            pListe = pListe->suivant;
            nbElements++;
        }
        printf("La liste comportait %d element(s) avant l'ajout.\n",nbElements);
        nouv->val = valeur;
        nouv->suivant = NULL;
        pListe = nouv;
    }
    return pListe;
}

[Jack_serious]

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
 
int main()
{
	/* notre pointeur sur une liste bientot chainée ! */
	liste* pMaListe = NULL;
 
	/* on ajouter un élément ! */
	pMaListe = ajouter(pMaListe,5);
 
        /*
        **   ...
        */
 
	return (0);
}

Ton code pour ajouter en fin de liste me semble tout a fait correct.

Par contre, ce qui me chagrine, c'est que l'instruction :

Code :

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

1
2
 
pMaListe = ajouter(pMaListe,5);

va faire pointer ton pMaListe sur le dernier element de ta liste chainee, et ce d'apres ta fonction.

Donc la question est la suivante :

Comment vas-tu te referer a ta liste et l'utiliser par la suite ?

Avec une liste simplement chainee, il faut veiller a toujours garder dans un coin un pointeur sur le premier element de la liste.

Deux solutions :

• Tu peux changer le type de valeur de retour de ta fonction, recevoir un pointeur sur l'element que l'on vient d'ajouter ne servant (en general, dependant du programme) pas a grand chose.
• Tu peux creer un deuxieme pointeur pour cet usage, en gardant au chaud celui sur le debut de ta liste.

[sorry60]

J'ai REcorrigé mon 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
27
28
29
30
31
32
33
34
35
36
37
38
 
/* Fonction qui ajoute un élément en fin de liste */
liste* ajouter(liste *pListe, int valeur)
{
	int nbElements = 0;
	liste *nouv = malloc(sizeof(*nouv));
 
	if(nouv)
	{
		/* On teste si la liste est vide ou non */
		if( !pListe )
		{
			/* La liste est vide donc on peut rajouter l'element directement */
			nouv->val = valeur;
			nouv->suivant = NULL;
			pListe = nouv;
		}
		else
		{
			/* On parcourt la liste pour se positionner en queue */
			while(pListe)
			{
				pListe = pListe->suivant;
				nbElements++;
			}
			/* Ici pListe pointe sur NULL, on va le faire pointer sur le nouvel element */
			/* Et ce dernier sur NULL */
			nouv->val = valeur;
			nouv->suivant = NULL;
			pListe = nouv;
		}
	}
	else
	{
		perror("malloc()");
	}
	return pListe;
}

En revanche, oui j'ai bien le soucis que mon pointeur ne pointe plus en tete.

Deux solutions :


* Tu peux changer le type de valeur de retour de ta fonction, recevoir un pointeur sur l'element que l'on vient d'ajouter ne servant (en general, dependant du programme) pas a grand chose.
* Tu peux creer un deuxieme pointeur pour cet usage, en gardant au chaud celui sur le debut de ta liste.

Je penche pour la premiere solution mais je ne vois pas quoi renvoyer a part le pointeur pListe

[Emmanuel Delahaye]

En revanche, oui j'ai bien le soucis que mon pointeur ne pointe plus en tete.

Ben oui. Regarde la condition de sortie de la boucle. Elle n'est pas conforme à ce que j'avais expliqué...

on cherche le dernier element
(celui qui pointe vers NULL)

[Jack_serious]

J'ai REcorrigé mon 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
 
/* Fonction qui ajoute un élément en fin de liste */
liste* ajouter(liste *pListe, int valeur)
{
	int nbElements = 0;
	liste *nouv = malloc(sizeof(*nouv));
 
	if(nouv)
	{
		/* On teste si la liste est vide ou non */
		if( !pListe )
		{
			/* La liste est vide donc on peut rajouter l'element directement */
			nouv->val = valeur;
			nouv->suivant = NULL;
			pListe = nouv;
		}

pListe est une variable locale.
Donc pListe = nouv; n'aura aucune incidence sur ta liste. Il faut que tu passe un pointeur sur pListe pour pouvoir le modifier.

En revanche, oui j'ai bien le soucis que mon pointeur ne pointe plus en tete.

Oui.

Deux solutions :


* Tu peux changer le type de valeur de retour de ta fonction, recevoir un pointeur sur l'element que l'on vient d'ajouter ne servant (en general, dependant du programme) pas a grand chose.
* Tu peux creer un deuxieme pointeur pour cet usage, en gardant au chaud celui sur le debut de ta liste.

Je penche pour la premiere solution mais je ne vois pas quoi renvoyer a part le pointeur pListe

Baaah tu renvoie 1, ou 0 si le malloc a echoue... Par exemple. Le monde est plein de choses a renvoyer a une fonction.

Tiens c'est comme ca que j'ajouterais 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
 
int             ajouter(liste **pListe, int valeur)
{
  liste         *new;
  liste         *tmp;
 
  new = xmalloc(sizeof(*new));       /* NOTE: xmalloc fait la verification de la valeur retournee par malloc() et fait un exit() si ca a foire. */
  new->val = valeur;
  tmp = *pListe;
  if (!tmp)
    tmp = new;
  else
    {
      while (tmp->suivant)
        tmp = tmp->suivant;
      tmp->suivant = new;
    }
  new->suivant = NULL;
  return (0);
}

[Jack_serious]

Emmanuel tu es trop rapide pour moi...

Ca fait deux fois que tu reponds pendant que je redige.

[sorry60]

En revanche, oui j'ai bien le soucis que mon pointeur ne pointe plus en tete.

Ben oui. Regarde la condition de sortie de la boucle. Elle n'est pas conforme à ce que j'avais expliqué...

on cherche le dernier element
(celui qui pointe vers NULL)

Bah..

Code :

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

1
2
3
4
5
while(pListe)
			{
				pListe = pListe->suivant;
				nbElements++;
			}

La seule condition pour que le while s'arrette c'est bien que pListe pointe sur NULL, donc le dernier élément. Elle est donc conforme à ce que tu m'as expliqué, non ?

Edit : pour Jack, j'aimerais évité si c'est possible les **, pour rester dans la simplicité pour le moment

[Emmanuel Delahaye]

Deux solutions :
* Tu peux changer le type de valeur de retour de ta fonction, recevoir un pointeur sur l'element que l'on vient d'ajouter ne servant (en general, dependant du programme) pas a grand chose.
* Tu peux creer un deuxieme pointeur pour cet usage, en gardant au chaud celui sur le debut de ta liste.

Je penche pour la premiere solution mais je ne vois pas quoi renvoyer a part le pointeur pListe

En fait, ta façon de coder la fonction implique des précautions d'usage assez drastiques,.

Code :

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

1
2
3
4
5
 
liste* pListe = ajouter(NULL, 123);
 
(void) ajouter(pListe, 456);
(void) ajouter(pListe, 789);

Pour éviter ça, on définit une structure supplémentaire est est la liste.

Code :

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

1
2
3
4
5
6
 
struct list
{
   struct node *p_head;
   struct node *p_tail;
};

Ce que tu appelais 'liste' est en fait un 'node'

Code :

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

1
2
3
4
5
6
 
struct node
{
   struct node *p_next;
   /* data ... */
};

Les fonctions gèrent alors les deux pointeurs (début et fin). Le pointeur de fin permet d'accélerer le traitement (plus besoin de faire une boucle pour ajouter en fin)...

Maintenant, tous devient simple et clair :

Code :

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

1
2
3
4
5
6
7
 
/* evidemment, il ne vaut pas oublier ca ! */
   struct list Liste = {0}; 
 
   ajouter(&Liste, 123);
   ajouter(&Liste, 456);
   ajouter(&Liste, 789);

On peut aussi travailler en 'anonyme' et utiliser la technique ADT qui oblige à une creation/initialisation (constructeur).

http://emmanuel-delahaye.developpez.com/tad.htm

[Emmanuel Delahaye]

J'ai REcorrigé mon code :

• Il est inutile d'écrire 2 fois le code d'init
• Il ne faut plus toucher à pListe une fois que la liste n'est plus vide.

Commentaire, quelques ameliorations. Il manque du 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
27
28
29
30
31
32
 
#include "liste.h"
#include <stdlib.h>
 
liste* ajouter (liste *pListe, int valeur)
{
    int nbElements = 0;
    liste *nouv = malloc(sizeof(*nouv));
 
    if(nouv != NULL)
    {
        /* -ed- donnees, chainage par defaut */
        nouv->val = valeur;
        nouv->suivant = NULL;
 
        /* On teste si la liste est vide ou non */
        if( pListe ==NULL)
        {
            /* La liste est vide donc on peut rajouter l'element directement */
            pListe = nouv;
        }
        else
        {
            /* -ed- la, il y a encore du boulot... */
        }
    }
    else
    {
        perror("malloc()");
    }
    return pListe;
}

[Emmanuel Delahaye]

Bah..

Code :

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

1
2
3
4
5
while(pListe)
			{
				pListe = pListe->suivant;
				nbElements++;
			}

La seule condition pour que le while s'arrette c'est bien que pListe pointe sur NULL, donc le dernier élément. Elle est donc conforme à ce que tu m'as expliqué, non ?

Ben non. Il faut s'arréter quand le pointeur pointe sur le dernier élément, pas quand il vaut NULL, sinon, c'est trop tard. Fait le schéma...

La réponse se trouve dans la structure...

[sorry60]

Ben non. Il faut s'arréter quand le pointeur pointe sur le dernier élément, pas quand il vaut NULL, sinon, c'est trop tard. Fait le schéma...

La réponse se trouve dans la structure...

Ah d'accord, j'avais cru que tu voulais qu'on s'arrette sur l'element NULL.
Ok donc dans ce cas, pour s'arretter sur le dernier element, c'est :

Code :

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

while(pListe->suivant) != NULL)

Je repars corriger mon corps

[sorry60]

Voila c'est fait :

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
 
/* Fonction qui ajoute un élément en fin de liste */
liste* ajouter(liste *pListe, int valeur)
{
	int nbElements = 0;
	liste *nouv = malloc(sizeof(*nouv));
 
	if(nouv)
	{
      nouv->val = valeur;
		nouv->suivant = NULL;
		/* On teste si la liste est vide ou non */
		if( !pListe )
		{
			/* La liste est vide donc on peut rajouter l'element directement */
			pListe = nouv;
		}
		else
		{
			/* On parcourt la liste pour se positionner en queue */
			while(pListe->suivant)
			{
				pListe = pListe->suivant;
				nbElements++;
			}
			/* Ici pListe pointe sur le dernier element */
			pListe->suivant = nouv;
		}
	}
	else
	{
		perror("malloc()");
	}
	return pListe;
}

A la fin de la fonction, le pointeur qui est retourné, si je ne me trompe pas, pointe sur l'avant dernier élément.
Pour pouvoir retourner un pointeur sur le 1er élément à chaque fois, je suis obligé d'utiliser une structure supplémentaire, comme tu as expliqué plus haut ?

[Emmanuel Delahaye]

Ah d'accord, j'avais cru que tu voulais qu'on s'arrette sur l'element NULL.

J'ai jamais dit ça. On veut ajouter au dernier. Il faut donc bien s'arréter au dernier.

Ok donc dans ce cas, pour s'arreter sur le dernier element, c'est :

Code :

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

while(pListe->suivant) != NULL)

[Emmanuel Delahaye]

Pour pouvoir retourner un pointeur sur le 1er élément à chaque fois, je suis obligé d'utiliser une structure supplémentaire, comme tu as expliqué plus haut ?

Avec la structure supplémentaire, il n'y a plus rien à retourner. Le code est auto-démerdant (c'est comme ça qu'on l'aime).

Nota : 'NbElement' ne sert plus a rien.

Autre chose. Il faut être cohérent. Soit on écrit

Code :

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

1
2
3
4
 
      nouv->suivant = 0;
   <...>
      if( !pListe )

soit on écrit

Code :

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

1
2
3
4
 
      nouv->suivant = NULL;
   <...>
      if (pListe != NULL)

S'agissant de pointeurs, la deuxième solution est évidemment la meilleure.

[sorry60]

Pour pouvoir retourner un pointeur sur le 1er élément à chaque fois, je suis obligé d'utiliser une structure supplémentaire, comme tu as expliqué plus haut ?

Avec la structre supplémentaire, il n'y a plus rien à retourner. Le code est auto-démerdant (c'est comme ça qu'on l'aime).

Ok je me lance