Filtrer une liste chainée

**INSPIRATION** · 27/05/2012, 04h30

Bonsoir,
je suis entrain de construire une fonction qui supprime des éléments d'une liste chaînée qui ont une occurrence <=x. D'après les cours et les tutos que je les ai trouvé sur internet j'ai constaté qu' il faut tester si l'élément a supprimer est au début de la liste ou non car la suppression au début de la liste n'est pas la même que dans dans une autre position de la liste.Je veut comprendre est ce que ce teste est obligatoire?
j'ai tester ce bout de code mais il m'affiche toujours 0 et lorsque je le débugge il m'affiche

une violation d’accès(erreur de segmentation) est apparue dans votre programme

mais je vois pas pourquoi?pouvez vous m'aidez a trouver la faille dans 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
 
T *filtrer(T *Liste,int Nb,float x)
{
  T *head=NULL,*precedent=NULL,*next=NULL;
  T *courant=Liste;
  for(courant=Liste; courant!=NULL; courant=next) {
    next = courant->suiv;
    if (courant->occ<=x) 
     { courant=courant->suiv;
      free(courant);
      if (precedent!=NULL) 
      precedent->suiv = next;
    } else {
      precedent = courant;
      if (head==NULL) head=courant;
    }
  }
 
  return head;
}

cordialement

**Neckara** · 27/05/2012, 09h34

Tu devrais essayer de soigner l'indentation pour que l'on puisse comprendre plus facilement ce que tu fais

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
T *head=NULL,*precedent=NULL,*next=NULL;
T *courant=Liste;
for(courant=Liste; courant!=NULL; courant=next)
{
    next = courant->suiv;
    if (courant->occ<=x) 
    {
         courant=courant->suiv;//courant = next;
         free(courant);// ?? Ne devrait-il pas être placé une ligne avant ? Tu veux supprimer le (*courant) dont occ est <= x pas le (*courant) suivant le (*courant) dont occ est <= x non ?
         if (precedent!=NULL) 
               precedent->suiv = next;
    }
    else
    {
      //Il ne manque pas un "precedent->suiv = courant;" ?
      precedent = courant;
      if (head==NULL) head=courant;
    }
}

**edgarjacobs** · 27/05/2012, 15h55

D'une manière générale, sans utiliser de nom de variables, voici de quoi supprimer une entrée <= X dans une liste doublement chaînée (first pointe sur le premier élement, last sur 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
courant=first;
while(courant) {
	if(courant->????<=X) {
		if(courant->prev) courant->prev->next=courant->next;
		else first=courant->next;
		if(courant->next) courant->next->prev=courant->prev;
		else last=courant->prev;
		old=courant;
		courant=courant->next;
		free(old);
		}
	else courant=courant->next;
	}

Bien à toi. Edgar.

**INSPIRATION** · 27/05/2012, 17h12

Envoyé par edgarjacobs

D'une manière générale, sans utiliser de nom de variables, voici de quoi supprimer une entrée <= X dans une liste doublement chaînée (first pointe sur le premier élement, last sur 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
courant=first;
while(courant) {
	if(courant->????<=X) {
		if(courant->prev) courant->prev->next=courant->next;
		else first=courant->next;
		if(courant->next) courant->next->prev=courant->prev;
		else last=courant->prev;
		old=courant;
		courant=courant->next;
		free(old);
		}
	else courant=courant->next;
	}

Bien à toi. Edgar.

Merci bien Edgar pour votre réponse,mais j'ai une ambiguïté au niveau de la déclaration des pointeur tête et fin de la liste:est ce que cette déclaration ce fait d'une manière locale c'est a dire dans ma fonction filtrer ou dans dans la déclaration de ma liste chaînée?

**edgarjacobs** · 27/05/2012, 19h20

Les pointeurs de début et de fin liste ont normalement été créés lors de la création de la liste. Sinon, comment savoir où commence la liste? Et comment ajouter un élément en fin de liste sans la parcourir au complet à chaque insertion (à moins que les nouveaux éléments soient toujours ajoutés au début, ou que l'insertion soit faite suivant un certain critère) ?

**denispir** · 27/05/2012, 19h50

Envoyé par INSPIRATION

Bonsoir,
[...] j'ai constaté qu' il faut tester si l'élément a supprimer est au début de la liste ou non car la suppression au début de la liste n'est pas la même que dans dans une autre position de la liste.Je veut comprendre est ce que ce teste est obligatoire?
cordialement

Je te conseille de te faire un petit dessin (en remplaçant les liens/pointeurs de début/fin de liste par le signe ensemble vide, par exemple). Représente ou note bien, "bêtement", les actions à effectuer pour supprimer un noeud, suivant les différents cas de position de celui-ci. Tu vas vite comprendre, je crois, c'est pas sorcier. Ce dépend aussi si la liste est simplement ou doublement chaînée, bien sûr.
En cas de question, n'hésite pas à redemander,
denis

**INSPIRATION** · 28/05/2012, 02h50

Mille mercis pour vos conseils, d’après vos réponses j'ai conclu qu'il faut vérifier la position de l’élément a supprimer (début,milieu ou fin) en utilisant les pointeurs début et fin lors de la construction de ma liste chaîne(simplement chaînée),donc la déclaration de ces pointeurs est obligatoire.Désolé je vous dérange mais vu que je suis débutante en c,je trouve une difficulté dans l’utilisation et la manipulation des pointeurs surtout au niveau des liste chaînées.

**INSPIRATION** · 28/05/2012, 05h25

D’après vos conseils je suis arrivé a écrire ce bout de code mais il me donne toujours comme résultat zéro (nombre de variable restante dans la liste après le filtrage=0),je vois pas pourquoi

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
T *filtrer(T *Liste,int Nb,float x){
T *courant;
courant=Liste;
 while(courant!=NULL)//parcourir la liste
 { if(courant->fc<=Nb*x)//test sur le premier element{
 courant=courant->suiv;}
 else {
 courant->suiv=courant->suiv->suiv;
 
        }
 
}
}

**Neckara** · 28/05/2012, 07h56

edgarjacobs t'a donné un algorithme pour les liste doublement chaînée or tu essayes de l'utiliser pour des listes simplement chaînée.

Voici un petit algorithme pour les listes simplement chaînées :

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
 
//traiter le cas de la liste vide
//cas de la liste à 1 élément.
Liste courant = debut;
int k = 20;
 
//traitement de tous les éléments sauf du premier
tant que courant->suiv != NULL
     if(courant->suiv->x <= k)
     {
               Liste tmp = courant->suiv->suiv;
               //suppression du maillon
               courant -> suiv = ... ;
      }
 
     courant = courant->suiv;
fin tant que
 
//traitement du premier élément
 
return debut;

**denispir** · 28/05/2012, 11h34

Envoyé par INSPIRATION

D’après vos conseils je suis arrivé a écrire ce bout de code mais il me donne toujours comme résultat zéro (nombre de variable restante dans la liste après le filtrage=0),je vois pas pourquoi

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
T *filtrer(T *Liste,int Nb,float x){
T *courant;
courant=Liste;
 while(courant!=NULL)//parcourir la liste
 { if(courant->fc<=Nb*x)//test sur le premier element{
 courant=courant->suiv;}
 else {
 courant->suiv=courant->suiv->suiv;
 
        }
 
}
}

Il y a au moins 3 problèmes dans ton code :

1. Il est presque illisible du fait de l'espacement et l'indentation. Voici un exemple (juste un exemple) de version plus lisible :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
T *filtrer(T *Liste, int Nb, float x) {
   // parcourir la liste en testant les elements suivant le critère
   // et supprimant les noeuds qui n'y répondent pas
   T *courant = Liste;
   while (courant != NULL) {
      // test sur l'element courant
      if (courant->fc <= Nb*x) {
         courant=courant->suiv;
      } else {
         courant->suiv = courant->suiv->suiv;
      }
   }
}

2. Tu n'as pas encore bien compris, apparemment, comment on peut supprimer un noeud dans une liste chaînée. Tu pourrais faire une mini-fonction 'supprimer_noeud' juste pour ça. Quel(s) paramètre(s) nécessite-t-elle ? Vérifie qu'elle marche bien ; puis utilise-la dans 'filtrer'. Ensuite, si tu n'en as pas besoin ailleurs, tu peux éventuellement en réintégrer le code dans filtrer.
Indice: Tu as raison dans le fait que cela consiste à "sauter" un noeud comme tu le fais par "courant->suiv=courant->suiv->suiv". Mais (1) quel noeud est à sauter ? (2) quelles variables sont en jeu ?

3. Tu ne traites pas spécialement le cas du premier noeud de la liste, malgré ta question initiale.
Indice : Attention, comme dans la fonction 'filtrer' tu supprimes des noeuds, tu ne peux pas traiter le premier noeud avant de commencer le cycle (ce qui serait plus simple). Pourquoi ? Mais tu peux dans un premier traiter ce cas hors du cycle pour bien le comprendre, avec des données qui vont bien, puis le réintégrer dans le cycle.

Denis

**Médinoc** · 28/05/2012, 21h37

Pour filtrer une liste simplement chaînée indépendamment du fait qu'un nœud soit le premier, il faut faire un parcours indirect: http://www.developpez.net/forums/d62...e/#post3675588

Filtrer une liste chainée

C

Discussions similaires

Partager

Partager