Problème de suppression d'un chainon de ma liste doublement chainée

Version imprimable

Il y a quelque jours je me suis mis au liste chainée simple puis double;
j'ai donc créé un programme qui obtient par ordre alphabétique un nom et un age.
L'ajout marche impec', l'affichage aussi mais lorsqu'il s'agit de supprimer un chainon ca plante.

Voici 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
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define a 100
#define sp printf("\n")
#define v fflush(stdin)
typedef struct fic
{
    char nom[a];
    int x;
    struct fic *svt;
    struct fic *pcd;
}fic;
 
fic * ajouter(fic*);
void afficher(fic*);
fic * suppression(fic*);
 
void main(void)
{
    fic *ptrfic=NULL;
 
    //ajout trié
    do
    {ptrfic=ajouter(ptrfic);
    }while(ptrfic->x!=0);
 
    //suppression d'un chainon
    ptrfic=suppression(ptrfic);
 
    //affichage
    afficher(ptrfic);
 
    sp;
    system("pause");
 
 
}
 
fic * ajouter(fic *ptrfic)
{
    fic *newptr=malloc(sizeof(fic));
    fic *savptr=NULL,*suiv=ptrfic;
 
    puts("Notez votre nom:");
    v;
    gets(newptr->nom);
 
    puts("age:");
    v;
    scanf("%d",&newptr->x);
 
    newptr->svt=newptr->pcd=NULL;
 
    while(suiv!=NULL && strcmp(suiv->nom,newptr->nom)<0)
    {
        savptr=suiv;
        suiv=suiv->svt;
    }
 
    newptr->svt=suiv;
    newptr->pcd=savptr;
 
    if(savptr)savptr->svt=newptr;
    if(suiv){
    suiv->pcd=newptr;}
 
    if(savptr)return ptrfic;
 
    return newptr;
}
 
void afficher(fic *ptrfic)
{
    fic *tmp;
 
    if(ptrfic==NULL)
    puts("liste vide");
    else
    {
        tmp=ptrfic;
        tmp=tmp->svt;
        system("cls");
 
        while(tmp!=NULL)
        {
            sp;
            printf("Nom: %s",tmp->nom);
            printf("\nage: %d",tmp->x);
            sp;
            tmp=tmp->svt;
        }
    }
}
 
fic * suppression(fic  *ptrfic)
{
     fic *psup=malloc(sizeof(fic));
     fic *suiv=ptrfic,*savptr=NULL;
 
     puts("Notez votre nom a supprimer:");
     v;
     gets(psup->nom);
 
     psup->svt=psup->pcd=NULL;
 
     while(suiv!=NULL && strcmp(suiv ->nom,psup->nom)<0)
     {
         savptr=suiv;
         suiv=suiv->svt;
     }
 
     if(suiv=NULL || strcmp(suiv->nom,psup->nom)!=0)
     puts("pas trouvé");
     else
     {
         if(savptr->pcd==NULL){
             suiv->pcd=NULL;
             return suiv;}
         else
         {
 
             savptr->svt=suiv->svt;
             return savptr;
             }
 
     }
 
 
}

Je pense que ca doit etre une petite erreur, mais je n'arrive pas à voir laquelle.

Si vous la trouviez, ca m'aiderait beaucoup! :)

20/05/2012, 19h12
diogene

La fonction est à réécrire : dans une liste doublement chainée, on n'a pas besoin de mémoriser le pointeur sur la cellule précédente (savptr) puisque cette information est inscrite dans la cellule.

Lorsqu'on a un pointeur x (!=NULL) sur la cellule à enlever,
- on refait le chainage du maillon précédent avec le suivant

Code:

if (x->pcd != NULL) x->pcd->svt = x->svt;

- et du suivant avec le précédent

Code:

if(x->svt != NULL) x->svt->pcd = x->pcd;

- si x est la tête de liste, on remplace la tête de liste par x->svt

x est maintenant sorti de la liste.

j'ai fait comme tu m'as dit, mais mon prog' plante quand meme :?

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
fic * suppression(fic  *ptrfic)
{
     fic *psup=malloc(sizeof(fic));
     fic *suiv=ptrfic;
 
     puts("Notez votre nom a supprimer:");
     v;
     gets(psup->nom);
 
     psup->svt=psup->pcd=NULL;
 
     while(suiv!=NULL && strcmp(suiv ->nom,psup->nom)<0)
     {
         suiv=suiv->svt;
     }
 
     if((suiv=NULL) || (strcmp(suiv->nom,psup->nom)!=0))
     puts("pas trouvé");
     else
     {
         if(suiv->pcd=NULL)suiv=suiv->svt;
         else{
         if(suiv->pcd){
             suiv->pcd->svt=suiv->svt;}
         if(suiv->svt){
             suiv->svt->pcd=suiv->pcd;}}
    }
    free(psup);
    return suiv;
}

pour le retour je ne sais pas tres bien lequel mettre...

1- Placer correctement les délimiteurs de blocs { et } : c'est indispensable pour que le code soit clair. En particulier, ne pas placer } en fin de ligne.

2- Qu'est-ce que la fonction doit retourner ? La nouvelle tête de liste par exemple puisqu'elle peut changer

3- A quoi sert psup? uniquement à stocker le nom lu. Alors pourquoi pas un simple tableau. Pour la lecture, préférez fgets(....,stdin) plutôt que gets() qui est déconseillé.
Voir FAQ Comment lire une ligne de manière securisée ?

4- La ligne 7 : v; A la lecture, rien ne laisse supposer qu'il s'agit d'une macro (de même a est un identificateur bien mal choisi); c'est syntaxiquement pervers.
fflush(stdin) a un comportement indéterminé : cette fonction ne doit pas être utilisée pour des flots d'entrée. Voir FAQ : A quoi sert la fonction fflush ? , Pourquoi ne faut-il pas utiliser fflush(stdin) pour vider le buffer clavier ? et Comment vider le buffer clavier ?
Vider systématiquement le buffer clavier avant une lecture est bizarre : on ne sait pas dans quel état il se trouve. Il est préférable de vider le buffer clavier après une lecture (là on sait si il y a quelque chose à vider ou non) de façon à le laisser "propre" pour l'entrée suivante.

Cela donne :
Code:

1 2 3 4 5 char nom[a+1]; //a+1 : a pour le nom ,+1 pour le '\n' lu par fgets() fgets(nom,a+1,stdin); // fgets lit la ligne y compris le '\n' : le buffer d'entrée est vidé char *p = strchr(nom,'\n'); // supprimer le '\n' if(p!=NULL) *p = '\0'; while(suiv!=NULL && strcmp(suiv ->nom,nom)<0) suiv=suiv->svt;
5- Ne pas confondre l'assignation (=) et la comparaison (==)

Code:

if((suiv==NULL) || (strcmp(suiv->nom,nom)!=0))

6- faire les choses dans l'ordre :
Code:

1 2 3 4 5 // refaire le chainage if(suiv->pcd)suiv->pcd->svt=suiv->svt; if(suiv->svt)suiv->svt->pcd=suiv->pcd; // placer suiv sur la nouvelle tete de liste if(suiv->pcd==NULL)suiv=suiv->svt;
Ce qui peut donner au final :
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 fic * suppression(fic *ptrfic) { fic *suiv=ptrfic; char nom[a+1]; //a+1 : a pour le nom ,+1 pour le '\n' lu par fgets() char *p; if(ptrfic == NULL) { puts("Liste vide"); return NULL; } // entrez le nom puts("Notez votre nom a supprimer:"); fgets(nom,a+1,stdin); // fgets lit la ligne y compris le '\n' : le buffer d'entrée est vidé p = strchr(nom,'\n'); // supprimer le '\n' if(p!=NULL) *p = '\0'; // cherchez le nom while(suiv!=NULL && strcmp(suiv ->nom,nom)<0) suiv=suiv->svt; if(suiv==NULL || strcmp(suiv->nom,nom)!=0)puts("pas trouvé"); else { // refaire le chainage if(suiv->pcd)suiv->pcd->svt=suiv->svt; if(suiv->svt)suiv->svt->pcd=suiv->pcd; // placer la nouvelle tete de liste if(suiv->pcd==NULL)ptrfic=suiv->svt; // détruire la cellule free(suiv); } return ptrfic; // renvoyer la nouvelle tête de liste } ..... tete = supprimer(tete);

22/05/2012, 12h32
diablo9

Merci à toi diogène :ccool: