Cherche algo supprimer les doublons d'une liste chainée

**arnodujura** · 06/03/2009, 17h38

Bonjour,
je suis débutant, je travaille sur les listes chainées, j'aimerais avoir le code d'une fonction qui supprime les doublons dans une liste.

...voici mon type liste, il marche j'ai les fonctions d'affichage, d'insertion etc... qui fonctionnent parfaitement.

Code :

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

1
2
3
4
5
6
7
struct maille{
	int valeur;
	struct maille *suivant;
};
 
typedef struct maille Maillon;
typedef Maillon *Liste;

**souviron34** · 06/03/2009, 17h40

et quelle est ta proposition ??

**Médinoc** · 06/03/2009, 17h47

Mon conseil 1: Deux boucles imbriquées (complexité: O(n²))
Mon conseil 2: Tu tries la liste, puis tu trouveras plus facilement les doublons (complexité: O(n) pour la suppression, mais pour le tri d'une liste chaînée je ne sais pas).

**arnodujura** · 06/03/2009, 18h00

Alors je précise, ma liste est déjà trié, mais il y a des doublons...
C'est le sujet de mon TP, faut pas essayer de comprendre pourquoi la fonction d'insertion trie et autorise les doublons...
J'ai une liste chainée trié, il y a des doublons et je veux les supprimer, je commence seulement en c, je n'arrive pas a réaliser cette fonction...

**cedriku** · 06/03/2009, 18h06

Bonjour,

est ce que ta liste peut contenir n'importe quel entier ou bien tu connais le maximum qu'elle puisse avoir ??

Si oui et que ce maximum n'est pas "trop grand" alors il y a un moyen simple et efficace en utilisant un tableau de booleen annexe dont la taille vaut l'entier maximum que ta liste peut contenir. Dans ce tableau (notons le tab) une case i vaut 1 si l'entier i a deja ete trouve dans la liste. L'algorithme consiste alors a parcourir la liste et pour chaque entier X lu, tu test si tab[X]=1. Si oui alors c'est que l'entier X a deja ete lu avant et donc il faut le supprimer, sinon alors c'est que c'est la premiere fois que tu rencontre X et donc tu mets 1 dans tab[X] (pour dire que l'entier X appartient a ta liste). Du coup, la prochaine fois que tu rencontrera l'entier X alors en testant tab[X] tu sauras qu'il faut le supprimer.

Enfin bon cet algo est tres efficace etant donne qu'il est lineaire en le nombre d'element de la liste mais a l'inconvenient d'utiliser un tableau qui peut etre de taille tres tres grande (si le maximum de ta liste est un nombre tres grand voir infini !).

D'ou la question: est ce que tu as des hypotheses sur tes entiers dans ta liste ?

**Médinoc** · 06/03/2009, 18h21

Si elle est déjà triée, c'est simple: Tu parcours la liste, en mémorisant la valeur (et sûrement aussi l'adresse) du dernier élément parcouru, et si l'élément courant est égal, tu supprimes l'élément courant (en utilisant par exemple l'adresse du précédent)

**arnodujura** · 06/03/2009, 19h28

Pr répondre à cedriku : non je n'ai pas de maximum donc je ne pense pas que ta solution avec un tableau soit optimisé...

La solution pour moi est celle de médinoc, c'est ce que je veux faire depuis le début sauf que je n'arrive pas à le coder... je n'arrive pas à supprimer l'élément courant...

**diogene** · 06/03/2009, 19h35

Le problème de base est "Comment supprimer un élément d'une liste chaînée".

C'est assez simple à écrire pour une liste doublement chaînée, mais plus délicat pour une liste simplement chaînée puisque, comme le mentionne Médinoc, il faut avoir l'adresse du chaînon précédant celui que tu veux enlever pour reconstituer le chaînage.

Dans ton cas, heureusement, c'est plus simple puique tu veux simplement supprimer les doublons et que ta liste est classée.
Ton problème se simplifie en "Comment supprimer le chaînon suivant un chaînon donné".

Par conséquent :

1- Tu ne supprime jamais le chaînon de tête et la tête de liste n'est donc pas modifiée

2-a- Si la liste n'est pas vide, désigner le chaînon de tête comme chaînon courant
sinon, c'est fini.

2-b- Tant que le suivant du chaînon courant existe et fait doublon avec le chaînon courant, supprimer le chaînon suivant.

2-c- Si le (nouveau) suivant du chaînon courant existe (et donc d'après 2-b ne peut être un doublon) , changer le chaînon courant pour son (nouveau) suivant
Sinon, c'est fini

**arnodujura** · 06/03/2009, 20h14

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
void deletedoublons(Liste *l){
    Maillon *e;
    e=(Maillon*)malloc(sizeof(Maillon));
    if((*l)!=NULL){
        e->valeur=(*l)->valeur;
        while((e->suivant!=NULL) && ((e->suivant)->valeur)==e->valeur ){
            free(e->suivant);
            if(e->suivant!=NULL) e=e->suivant;
        }
        *l=e;
    }
}

voila ce que ça donne pour le dernier message posté... malheureusement je suis pas du tout callé avec ces listes chainées et je comprends rien... c'est gentil quand même de vouloir m'expliquer en francais...

**amaury pouly** · 06/03/2009, 20h49

Bonjour, il y a de l'idée dans ton code mais aussi quelque problèmes:

Code :

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

1
2
3
 
free(e->suivant);
if(e->suivant!=NULL) e=e->suivant;

Ici, tu vas libérer e->suivant puis ensuite y accéder

Il y a donc un problème.
De plus, au début de ta fonction, tu alloues e alors qu'un pointeur suffit.

Plutôt que de te pondre le code, je te propose moi aussi un algorithme pour faire ça mais différent de celui de diogene (parfait il suffit de changer de point de vue pour mieux comprendre):

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
1. Si la liste est vide ou a un seul élément, STOP
2. Precedent <- La tête de la liste
3. Courant <- Le second de la liste
4. Tant que Courant n''est pas le pointeur nul
5.    Si la valeur de Courant est la même que celle de Precedent
6.       Faire Precedent.Suivant=Courant.Suivant
7.       Supprimer Courant
8.       Courant <- Precedent.Suivant
9.     Sinon
10.       Precedent <- Courant
11.       Courant <- Courant.Suivant
12.    Fin si
13.  Fin tant que

**arnodujura** · 06/03/2009, 21h50

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
void deletedoublons(Liste *l){
    Maillon *precedent,*courant;
    precedent=(Maillon*)malloc(sizeof(Maillon));
    courant=(Maillon*)malloc(sizeof(Maillon));
    if((*l)!=NULL){
       precedent->valeur=(*l)->valeur;
       courant=(*l)->suivant;
        while(courant != NULL){
            if(courant->valeur==precedent->valeur)
            {
                    precedent->suivant=courant->suivant;
                    free(courant);
                    courant=precedent->suivant;
            }
            else
            {
                    precedent=courant;
                    courant=courant->suivant;
            }
 
        }
    }
    *l=precedent;
}

seulement je ne conserve plus le debut de ma liste :
pour une liste (6,6,6,7,9,23,45,45,65)
j'obtiens comme résultat (65)

**Emmanuel Delahaye** · 07/03/2009, 10h44

Envoyé par arnodujura

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
void deletedoublons(Liste *l){
    Maillon *precedent,*courant;
    precedent=(Maillon*)malloc(sizeof(Maillon));
    courant=(Maillon*)malloc(sizeof(Maillon));
    if((*l)!=NULL){
       precedent->valeur=(*l)->valeur;
       courant=(*l)->suivant;
        while(courant != NULL){
            if(courant->valeur==precedent->valeur)
            {
                    precedent->suivant=courant->suivant;
                    free(courant);
                    courant=precedent->suivant;
            }
            else
            {
                    precedent=courant;
                    courant=courant->suivant;
            }
 
        }
    }
    *l=precedent;
}

seulement je ne conserve plus le debut de ma liste :
pour une liste (6,6,6,7,9,23,45,45,65)
j'obtiens comme résultat (65)

Il n'y a rien à allouer dans un algo qui supprime des éléments...

Il faut que tu apprennes à implémenter strictement un algorithme (amaury pouly)...

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
79
80
81
82
83
84
 
#include <stdio.h>
 
struct node
{
   int value;
   struct node *next;
};
 
static void display (struct node const *head)
{
   struct node const *p = head;
   while (p != NULL)
   {
      printf ("%2d", p->value);
      p = p->next;
   }
   printf ("\n");
}
 
void unique (struct node *head)
{
 
/* 1. Si la liste est vide ou a un seul élément, STOP */
   if (head != NULL && head->next != NULL)
   {
/* 2. Precedent <- La tête de la liste */
      struct node *prec = head;
 
/* 3. Courant <- Le second de la liste */
      struct node *curr = head->next;
 
/* 4. Tant que Courant n'est pas le pointeur nul */
      while (curr != NULL)
      {
 
/* 5.    Si la valeur de Courant est la même que celle de Precedent */
         if (curr->value == prec->value)
         {
 
/* 6.       Faire Precedent.Suivant=Courant.Suivant */
            prec->next = curr->next;
 
/* 7.       Supprimer Courant */
            /* a faire dans une application reelle */
 
/* 8.       Courant <- Precedent.Suivant */
            curr = prec->next;
 
/* 9.     Sinon */
         }
         else
         {
/* 10.       Precedent <- Courant */
             prec = curr;
 
/* 11.       Courant <- Courant.Suivant */
             curr = curr->next;
 
/* 12.    Fin si */
         }
      }
   }
 
}
 
int main (void)
{
   static struct node list[] = {
      {1, list + 1},
      {1, list + 2},
      {2, list + 3},
      {2, list + 4},
      {2, list + 5},
      {3, list + 6},
      {3, NULL},
   };
 
   display (list);
   unique (list);
   display (list);
 
   return 0;
}

donne :

Code :

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

1
2
3
4
5
6
 
 1 1 2 2 2 3 3
 1 2 3
 
Process returned 0 (0x0)   execution time : 0.039 s
Press any key to continue.

**Dounia Karym** · 03/06/2014, 02h51

Salut J vois que vos idées sont tréés bonnes mais ce n'est utile lorsqu 'on aura des doublons séparés par exemple l'un en tete et l autre en queue séparés par plusieurs elements par 3 élements par exemple ou plus !! ca c'est utile juste lorsque les doublons sont l un a cote de l autre sinn ca marche po !! Quoi faire

**Emmanuel Delahaye** · 03/06/2014, 03h18

Envoyé par Dounia Karym

Salut J vois que vos idées sont tréés bonnes mais ce n'est utile lorsqu 'on aura des doublons séparés par exemple l'un en tete et l autre en queue séparés par plusieurs elements par 3 élements par exemple ou plus !! ca c'est utile juste lorsque les doublons sont l un a cote de l autre sinn ca marche po !! Quoi faire

Alors 5 ans après, alors que je ne pratique plus la programmation en C, tu me fais relire un vieux post qui demandait comment retirer les doublons d'une liste triée ...

Est-il nécessaire d'en ajouter plus ? Je peux me rendormir ?

hint : si la liste n'est pas triée, la trier !