Liste simplement chainée

Version imprimable

Voir 40 message(s) de cette discussion en une page

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:

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:

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:

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.

Citation:

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

Je ne trouve pas mon erreur :(

Re: Liste simplement chainée

Citation:

Envoyé par 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 !

Ton code commenté mais non corrigé.

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
 
#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;
}

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
 
#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;
}

26/11/2005, 17h29
sorry60

Re: Liste simplement chainée

Citation:

Envoyé par Emmanuel Delahaye

Citation:

Envoyé par 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 :wink:
Ok merci pour tes commentaires, je vais les etudier et corriger mon code.

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

Code:

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é" ? :wink:

Edit :
Si le main est changé !

Code:

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;
}

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

Code:

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;
	}

Citation:

Envoyé par sorry60

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:

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; }

Citation:
Envoyé par sorry60
Code:

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:

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 :

:arrow: 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.

J'ai REcorrigé mon code :
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 /* 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.

Citation:

Envoyé par Jack_serious

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 :?

26/11/2005, 18h30
Emmanuel Delahaye

Citation:

Envoyé par 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é...

Citation:

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

Citation:
Envoyé par sorry60
J'ai REcorrigé mon code :
Code:

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.

Citation:

Envoyé par sorry60

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

Oui.

Citation:

Envoyé par sorry60

Citation:

Envoyé par Jack_serious

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:

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); }

26/11/2005, 18h33
Jack_serious

Emmanuel tu es trop rapide pour moi...

Ca fait deux fois que tu reponds pendant que je redige.
26/11/2005, 18h38
sorry60
Citation:

Envoyé par Emmanuel Delahaye

Citation:

Envoyé par 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é...

Citation:

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

Bah..
Code:

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
26/11/2005, 18h43
Emmanuel Delahaye
Citation:

Envoyé par sorry60

Citation:

Envoyé par Jack_serious

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:

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:

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:

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:

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

Citation:

Envoyé par sorry60

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:

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;
}

26/11/2005, 18h56
Emmanuel Delahaye
Citation:
Envoyé par sorry60

Bah..

Code:

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...
26/11/2005, 19h05
sorry60

Citation:

Envoyé par Emmanuel Delahaye

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:

while(pListe->suivant) != NULL)

Je repars corriger mon corps :wink:

Voila c'est fait :

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
 
/* 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 ?

26/11/2005, 19h13
Emmanuel Delahaye

Citation:

Envoyé par sorry60

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.

Citation:

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

Code:

while(pListe->suivant) != NULL)

:yaisse:
26/11/2005, 19h16
Emmanuel Delahaye
Citation:

Envoyé par 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 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:

1 2 3 4 nouv->suivant = 0; <...> if( !pListe )
soit on écrit
Code:

1 2 3 4 nouv->suivant = NULL; <...> if (pListe != NULL)
S'agissant de pointeurs, la deuxième solution est évidemment la meilleure.
26/11/2005, 19h18
sorry60

Citation:

Envoyé par Emmanuel Delahaye

Citation:

Envoyé par 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 :koi:

Voir 40 message(s) de cette discussion en une page

Fuseau horaire GMT +2. Il est actuellement 19h34.