supprimer les repetitions dans une liste chaînée

Version imprimable

Bonjour
je doit écrire une fonction qui supprime les répétitions dans une liste chainée

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
 
 
typedef struct cel 
{
  int val;
  struct cel * suivant;
} liste;
 
typedef liste* PListe ;
 
int taille(PListe L);//return la taille de la liste
 
Liste suprimer(PListe L, int k);// supprimer l element du rang k

j ai écrit cette fonction mais ça marche pas

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
 
 
PListe supprimer_repe(PListe L)
 {
     PListe p=NULL,pc=NULL,  prec=NULL;
 int k=0,i;
   p = L ;
 
   while ( p != NULL )
     { k++;
         pc=p->suivant ; 
         prec = p ;
 
for(i=k;k<taille(L);i++)
            {
 
                if (pc->val == p->val)
L=supprimer(L,i);
                else
                     prec = pc ;
 
                pc = pc->suivant ;
            }                
 
         p=p->suivant; 
    }
 
return L;
}

SVp aider moi

Citation:

Envoyé par Layla

je doit écrire une fonction qui supprime les répétitions dans une liste chainée
SVp aider moi

C'est un problème d'algorithme. Je conseille de créer une deuxième liste temporaire.

Et de déplacer les éléments de la première liste dans le 2ème, en vérifiant avant que l'élément n'y est pas. Quand c'est termine (liste initiale vide), la liste devient la nouvelle.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 liste_s liste initaliser (liste) liste_s temp Pour chaque élément de liste : element := retirer (liste) SI est_absent(temp, element) ajouter (temp, element) SINON liberer(element) FIN SI liste := temp

29/04/2007, 14h57
Franck.H

Ceci ne me semble pas correcte:

Code:

for (i = k; k < taille (L); i++)

La valeur de k change vu que c'est le début de ta boucle mais dans le parcours de ta liste jusqu'à atteindre la valeur retournée par:

Code:

taille (L)

Tu peux avoir des surprises car là à chaque fois que tu supprime un noeud la taille change. J'aurais fait simplement une seconde boucle while comme la première.

PS: il faudrait faire un effort de présentation du code...
29/04/2007, 15h05
Layla
Citation:

Envoyé par Franck.H

Ceci ne me semble pas correcte:

Code:

for (i = k; k < taille (L); i++)

oui oui c'est
Code:

1 2 for (i = k; i < taille (L); i++)
Mais toujours ca marche pas
29/04/2007, 16h00
DavidDeharbe

Demande de clarification
Citation:

Envoyé par Layla

Bonjour

Je dois écrire une fonction qui supprime les répétitions dans une liste chainée .

Bonjour,

Cette fonction doit elle modifier la liste passee en parametre ou construire une nouvelle liste dont les elements sont ceux de la liste passee en parametre, sans repetition?

Si la premiere interpretation est la bonne, il faudrait plutot considerer le prototype suivant:
Code:

1 2 void supprimer_repe(Pliste * L);
David.
--
29/04/2007, 16h16
Layla

La fonction va biensur changer la liste passer en argument c pour ça elle doit retourné le debut

C'est un petit tant que

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
void supprimer_repe(PListe L)
 {
 
   PListe p;
 
   while (p != NULL )
   { 
	p->suivant = retirer(p->val, p->suivant);
        p  = p->suivant;
   }
}
 
PListe retirer(int val, PListe l)
{
   PListe p = L;
 
   // traitement special de debut
   // on supprime les éléments de tête 
   // si leur valeur est val
   while(p!= NULL && p->val == val)
   {
     PListe tmp = p;
     p = p->suivant;
     free(tmp);
   }
   l = p;  
   // ici on est assuré, soit d'avoir un noeud NULL,
   // soit que p->val != val
   while(p != NULL && p->suivant != NULL)
   {
       if (p->suivant->val == val)
       {
          PListe tmp = p->suivant;
          p->suivant = tmp->suivant;
          free(tmp);
       }
   }
   return l;
}

Cette fonction ne peut pas changer le premier noeud de la liste donc il est inutile de renvoyer une nouvelle tête de liste.