Probleme avec une liste chainée

**apen2k2** · 13/12/2006, 15h16

Voici ma structure de liste utilisé :

Code :

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

1
2
3
4
5
6
 
typedef struct s_list
{
                int valeur;
                list suiv;
} slist ;

Voici mes methodes respective :

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
void Insert(slist **sl, int*Val)
{
	slist *tmp = NULL;
	slist *csl = *sl;
	slist *elem = malloc(sizeof(slist));
	if(!elem) return;
	elem->valeur = Val;
 
 
	while(csl && csl->valeur->poid > Val->poid)
	{
		tmp = csl;
		csl = csl->suiv;
	}
	elem->suiv = csl;
	if(tmp) tmp->suiv = elem;
	else *sl = elem;
}
 
t_noeud Pop(slist **sl)
{
	t_noeud *Val;
	t_noeud *nul;
	creerNoeud(&nul);
	nul = NULL;
	slist *tmp;
	if(!*sl) return *nul;     
	tmp = (*sl)->suiv;
	*Val = (*(*sl)->valeur);
	free(*sl);
	*sl = tmp;             
	return *Val;            
}
 
void Clear(slist **sl)
{
	slist *tmp;
	while(*sl)
	{
		tmp = (*sl)->suiv;
		free(*sl);
		*sl = tmp;
	}
}
 
int Length(slist *sl)
{
	int n=0;
	while(sl)
	{
		n++;
		sl = sl->suiv;
	}
	return n;
}
 
void View(slist *sl)
{
	while(sl)
	{
		printf("%d\n",sl->valeur);
		sl = sl->suiv;
	}
}

Maintenant quand j'effectue un parcourt sur ma liste par exemple de cette facon :

Code :

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

1
2
3
4
	while(sl)
	{
		sl = sl->suiv;
	}

L'affichage fonctionne correctement mais forcement je me retrouve en fin de liste et donc lorsque j'essaie de re afficher une seconde fois ma liste et bien cela marche pas. Comment faire pour conserver une sauvegarde du premier élément de la liste pour pouvoir remettre la liste correctement apres affichage ? J'ai essayé plusieurs choses mais j'avoue me perdre un peu dans les pointeurs...

Ou alors est-il possible de copier simplement le contenu de la liste ?

**Fabllot** · 13/12/2006, 15h23

Code :

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

1
2
3
4
5
6
7
 
slist* maListe; 
[...]
slist* listeTmp;
for (listeTmp = maListe; listeTmp; listeTmp=listeTmp->suiv) {
     /* Code à faire pour chaque élément */
}

**apen2k2** · 13/12/2006, 15h31

Si je ne m'abuse le faite d'utiliser des pointeurs et de faire

Code :

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

listeTmp = maListe

Cela reviens finalement a la meme chose puisque je modifie l'objet a la meme adresse et du coup je modifie mon premier élément de maListe ?

**Fabllot** · 13/12/2006, 16h13

Envoyé par apen2k2

Si je ne m'abuse le faite d'utiliser des pointeurs et de faire

Code :

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

listeTmp = maListe

Cela reviens finalement a la meme chose puisque je modifie l'objet a la meme adresse et du coup je modifie mon premier élément de maListe ?

Non, quand je fais

Code :

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

listeTmp = maListe;

Je ne change pas "maListe", qui pointe toujours vers le premier élément de la liste. Et quand je fais

Code :

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

listeTmp = listeTmp->suiv;

je fais pointer "listeTmp" vers un autre objet, mais je ne touche pas aux objets pointés.
Ton problème, c'est que tu modifiais le pointeur "maListe", qui du coup, pointait vers un autre objet. En utilisant, un second pointeur, tu ne modifies rien.

**koala01** · 13/12/2006, 17h17

Salut,

J'ai l'impression que tu te complique la vie avec des pointeurs de pointeurs pour pas grand chose...

Un simple exemple: l'insertion pourrait tres bien fonctionner en lui passant un pointeur de type slist au lieu d'une pointeur de pointeur:

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
 
/* insertion d'un élément en fin de liste
   @in: début de la liste
        valeur à introduire
   @out: pointeur sur l'élément rajouté */
slist* Insert(slist* debut,int val)
{
    /* tout ce qu'il nous faut, c'est un pointeur temporaire */
    slist* temporaire=NULL;
    /* dans cette fonction, il n'est pas grave de "perdre" le début de 
       la liste allons y gaiement ;) 
       recherche du dernier élément de la liste*/
    while(debut->suiv!=NULL)
        debut=debut->suiv;
    /* création du nouvel élément */
    temporaire=malloc(sizeof(slit));
    /* vérification du nouvel éleme et initialisation */
    if(temporaire!=NULL)
    {
         /* j'ai toujours peur d'oublier d'initialiser un pointeur à NULL...
             je le fais donc dés que possible */
        temporaire->suiv=NULL;
        temporaire->valeur=val;
    }
    else
    {
        /* l'allocation a échoué... on l'indique ici à l'utilisateur */
         printf("Erreur d'allocation de mémoire\n");
    }
    /* "yapuka" mettre transformer l'élélement rajouté en dernier élément
       de la liste */
    debut->suiv=temporaire;
    /* et à le renvoyer */
    return temporaire;
   /* fini :D */
}

La fonction clear est dans la meme veine... Allons-y

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
 
void Clear(slist* debut)
{
    /* il nous faut un temporaire */
    slist* temporaire=NULL;
    while(debut!=NULL)/* je préfère toujours préciser le !=NULL plutot que d'
                         avoir un while (debut)... 
                         le but du test est plus clair :P */
    {
         /* on récupère le suivant dans la liste */
        temporaire=debut->suiv;
        /* on libère correctement le premier de la liste */
        debut->suiv=NULL; /* pas forcément nécessaire, mais une habitude
                           bonne à prendre ;) */
        free(debut);
        /* le temporaire devient le nouveau début */
        debut=temporaire;
    }
    /* fini :D */
}

Pour la fonction Length, la récursivité, j'adore ca

Code :

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

1
2
3
4
5
6
7
 
int Length(slist* travail)
{
    if(travail->suivant==NULL)
        return 1;
    return Length(travail->suivant)+1;
}

La fonction Pop, j'ai du mal à comprendre ce que tu veux faire... mais il *semblerait* que tu veuille pouvoir enlever le premier élément de la liste...

Si c'est ça, voilà comment je ferais:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
/* @in: début de la liste
    @out: nouveau premier élément 
  */
slist* Pop(slist* debut)
{
    /* il nous faut un temporaire 
        autant lui faire prendre tout de suite la valeur du deuxieme élément*/
    slist *temporaire=debut->suiv;
    /* on peut maintenant supprimer debut proprement */
    debut->suiv=NULL;/* les vieilles habitudes ont la peau dure ;) */
    free(debut);
    return temporaire;
}

Pour View, à part que j'expliciterais le test (sous la forme de while(s1!=NULL) ), ce serait pareil...

Tiens, une petite fonction sympa...

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
 
/* @in: élément de la liste (début lors de l'appel) 
        numéro dans la liste
    @out: élément de la liste
  */
slist* GetByNum(slist* travail,int index)
{
    /* un pointeur temporaire */
    slist* temporaire=NULL;
    if(index==1)
        temporaire=travail;
    else
    {
        if(travail->suiv!=NULL)
            temporaire=GetByNum(travail->suivant,--index);
        else
            temporaire=NULL;
    }
    return temporaire;
}

Maintenant, il faut voir à utiliiser toutes ces fonctions à bon escient...

"codé en dur" cela se passerait sous la forme de

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
 
int main()
{
    /* il nous faut un pointeur le début de la liste */
    slist* Debut;
    /* il nous faut un pointeur temporaire */
    slist* temporaire;
    /* et, tant qu'à faire, un pointeur sur la fin de la liste ;) */
    slist* Fin;
    /* insertion du premier élément
    Debut=Insert(NULL,5);
    /* si l'insertion a échoué, on ne sait plus rien faire */
    if(Debut==NULL)
    {
          /*on l'affiche, et on sort */
          printf("L'application va quitter\n");
          return EXIT_FAILURE;
    }
    /* Sinon, le debut est aussi la fin */
    Fin=Debut;
    /* insertion d'un nouvel élément (finalement, on peut passer 
        directement la fin de la liste ;) )/*
    temporaire=Insert(Fin, 3);
    /* encore une fois, on vérifie que ca se soit bien passé */
    if(temporaire==NULL)
    {
         /* si ce n'est pas le cas, on l'affiche, on vide la liste et on sort
             mais d'autres actions pourraient etre envisagées */
        printf("L'application va quitter\n");
        /* on n'oublie pas de vider la liste */
        Clear(Debut);
        return EXIT_FAILURE;
    }
    /* sinon, le nouvel élément devient la fin */
    Fin=temporaire
    temporaire=Insert(Fin, 4);
    if(temporaire==NULL)
    {
        printf("L'application va quitter\n");
        Clear(Debut);
        return EXIT_FAILURE;
    }
    Fin=temporaire;
    temporaire=Insert(Fin, 7);
    if(temporaire==NULL)
    {
        printf("L'application va quitter\n");
        Clear(Debut);
        return EXIT_FAILURE;
    }
    temporaire=Insert(Fin, 9);
    if(temporaire==NULL)
    {
        printf("L'application va quitter\n");
        /* on n'oublie pas de vider la liste */
        Clear(Debut);
        return EXIT_FAILURE;
    }
    Fin=temporaire;
    /* affichage de la taille */
    printf("%d",Length(Debut);
    /* Affichage des éléments de la liste */
    View(Debut);
    /* Pour montrer que ca fonctionne */
    View(Debut);
    /* récupérer le deuxieme élément de la liste*/
    temporaire=GetByNum(Debut,2);
    /* et l'afficher */
    printf("%d\n",temporaire->valeur);
    /* vidange de la liste avant de quitter */
    Clear(Debut);
    /* et remise des pointeurs à 0 */
    Debut=NULL;
    Fin=NULL;
    temporaire=NULL;
    /* sortie sur un succes */
    return EXIT_SUCCESS;
}

Evidemment, rien ne t'empeche de demander à l'utilisateur d'introduire les valeurs à insérer dans la chaine... mais, ca, ce sera pour une autre réponse de ma part

**apen2k2** · 13/12/2006, 22h10

Merci a toi pour ta reponse, je vais tester tout cela

J'editerai mon message

**apen2k2** · 14/12/2006, 13h05

Encore merci a toi

Visiblement je n'ai plus de bug d'affichage, j'ai reduit considerablement la complexité du programme en utilisant des pointeurs simple (je sais pas pourquoi je me suis embrouillé avec des pointeurs de pointeurs). Merci pour ton exemple qui ma beaucoup aider.

@+

**koala01** · 14/12/2006, 17h31

La solution la plus simple est toujours la moins compliquée

Retiens toujours ceci: tu ne dois commencer à t'embeter avec des pointeurs de pointeurs que:

s'il faut modifier la valeur du pointeur (via realloc ou autre) et
que tu n'a pas l'occasion de le renvoyer à la fin de la fonction (parce que tu veux renvoyer une autre valeur, entre autres)

Sinon, tôt ou tard, tu te trouvera dans une situation dans laquelle tu sera tenté de créer une fonction qui prendra en argument ... un pointeur de pointeur de pointeur de pointeur (...de pointeur)... chose que les compilateur n'acceptent qu'avec difficulté (le genre de fonction void mafonct(type ****arg) )

Et ce, d'autant plus qu'il y a toujours lieu, quand tu veux modifier un pointeur, de vérifier que la modification se soit correctement déroulée, et de se laisser "une porte de sortie":

Ce n'est pas, par exemple, parce qu'un realloc échoue que tu dois vider la mémoire et sortir sans autre forme de proces...

Tu peux très bien envisager de sauvegarder le travail déjà effectué sur les éléments existants ou proposer différentes alternatives à l'utilisateur

Probleme avec une liste chainée

C

Discussions similaires

Partager

Partager