Discussion :

[Layla]

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

Code :

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

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 :

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

[Emmanuel Delahaye]

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 :

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

[Franck.H]

Ceci ne me semble pas correcte:

Code :

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

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 :

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

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

[Layla]

Ceci ne me semble pas correcte:

Code :

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

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

oui oui c'est

Code :

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

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

Mais toujours ca marche pas

[DavidDeharbe]

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 :

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

1
2
 
void supprimer_repe(Pliste * L);

David.
--

[Layla]

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

[Trap D]

C'est un petit tant que

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