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

Version imprimable

06/03/2009, 17h38
arnodujura

Cherche algo supprimer les doublons d'une liste chainée
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:

1 2 3 4 5 6 7 struct maille{ int valeur; struct maille *suivant; }; typedef struct maille Maillon; typedef Maillon *Liste;
06/03/2009, 17h40
souviron34

et quelle est ta proposition ??
06/03/2009, 17h47
Médinoc

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).
06/03/2009, 18h00
arnodujura

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...
06/03/2009, 18h06
cedriku

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 ?
06/03/2009, 18h21
Médinoc

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)
06/03/2009, 19h28
arnodujura

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...
06/03/2009, 19h35
diogene

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 :

Citation:

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

Code:

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

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

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 8O
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:

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

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

Citation:

Envoyé par arnodujura

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

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:

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.

03/06/2014, 02h51
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 :calim2:
03/06/2014, 03h18
Emmanuel Delahaye

Citation:

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

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 !
03/06/2014, 03h31
Dounia Karym

hahahaha J mexcuse pr le derangement ! mais comment faire pour la trier !?? SVP :mouarf::roll:
03/06/2014, 04h49
foetus

Trier une liste chaînée de caractères
03/06/2014, 07h39
Emmanuel Delahaye

Citation:

Envoyé par Dounia Karym

hahahaha J mexcuse pr le derangement ! mais comment faire pour la trier !?? SVP :mouarf::roll:

"Chercheur en informatique"

C'est le moment de chercher ! Hi hi !