IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

C Discussion :

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


Sujet :

C

  1. #1
    Membre à l'essai
    Profil pro
    Inscrit en
    mars 2009
    Messages
    13
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : mars 2009
    Messages : 13
    Points : 10
    Points
    10
    Par défaut 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 : 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;

  2. #2
    Expert éminent sénior

    Profil pro
    Inscrit en
    janvier 2007
    Messages
    10 591
    Détails du profil
    Informations personnelles :
    Âge : 64
    Localisation : France

    Informations forums :
    Inscription : janvier 2007
    Messages : 10 591
    Points : 17 900
    Points
    17 900
    Billets dans le blog
    2
    Par défaut
    et quelle est ta proposition ??
    "Un homme sage ne croit que la moitié de ce qu’il lit. Plus sage encore, il sait laquelle".

    Consultant indépendant.
    Architecture systèmes complexes. Programmation grosses applications critiques. Ergonomie.
    C, Fortran, XWindow/Motif, Java

    Je ne réponds pas aux MP techniques

  3. #3
    Expert éminent sénior
    Avatar de Médinoc
    Homme Profil pro
    Développeur informatique
    Inscrit en
    septembre 2005
    Messages
    27 289
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 38
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : septembre 2005
    Messages : 27 289
    Points : 41 229
    Points
    41 229
    Par défaut
    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).
    SVP, pas de questions techniques par MP. Surtout si je ne vous ai jamais parlé avant.

    "Aw, come on, who would be so stupid as to insert a cast to make an error go away without actually fixing the error?"
    Apparently everyone.
    -- Raymond Chen.
    Traduction obligatoire: "Oh, voyons, qui serait assez stupide pour mettre un cast pour faire disparaitre un message d'erreur sans vraiment corriger l'erreur?" - Apparemment, tout le monde. -- Raymond Chen.

  4. #4
    Membre à l'essai
    Profil pro
    Inscrit en
    mars 2009
    Messages
    13
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : mars 2009
    Messages : 13
    Points : 10
    Points
    10
    Par défaut
    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...

  5. #5
    Membre du Club
    Profil pro
    Inscrit en
    juillet 2005
    Messages
    55
    Détails du profil
    Informations personnelles :
    Âge : 38
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations forums :
    Inscription : juillet 2005
    Messages : 55
    Points : 61
    Points
    61
    Par défaut
    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 ?

  6. #6
    Expert éminent sénior
    Avatar de Médinoc
    Homme Profil pro
    Développeur informatique
    Inscrit en
    septembre 2005
    Messages
    27 289
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 38
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : septembre 2005
    Messages : 27 289
    Points : 41 229
    Points
    41 229
    Par défaut
    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)
    SVP, pas de questions techniques par MP. Surtout si je ne vous ai jamais parlé avant.

    "Aw, come on, who would be so stupid as to insert a cast to make an error go away without actually fixing the error?"
    Apparently everyone.
    -- Raymond Chen.
    Traduction obligatoire: "Oh, voyons, qui serait assez stupide pour mettre un cast pour faire disparaitre un message d'erreur sans vraiment corriger l'erreur?" - Apparemment, tout le monde. -- Raymond Chen.

  7. #7
    Membre à l'essai
    Profil pro
    Inscrit en
    mars 2009
    Messages
    13
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : mars 2009
    Messages : 13
    Points : 10
    Points
    10
    Par défaut
    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...

  8. #8
    Expert éminent sénior
    Avatar de diogene
    Homme Profil pro
    Enseignant Chercheur
    Inscrit en
    juin 2005
    Messages
    5 761
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Enseignant Chercheur
    Secteur : Enseignement

    Informations forums :
    Inscription : juin 2005
    Messages : 5 761
    Points : 13 727
    Points
    13 727
    Par défaut
    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
    Publication : Concepts en C

    Mon avatar : Glenn Gould

    --------------------------------------------------------------------------
    Une réponse vous a été utile ? Remerciez son auteur en cliquant le pouce vert !

  9. #9
    Membre à l'essai
    Profil pro
    Inscrit en
    mars 2009
    Messages
    13
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : mars 2009
    Messages : 13
    Points : 10
    Points
    10
    Par défaut
    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...

  10. #10
    Membre actif Avatar de amaury pouly
    Profil pro
    Inscrit en
    décembre 2002
    Messages
    157
    Détails du profil
    Informations personnelles :
    Âge : 33
    Localisation : France

    Informations forums :
    Inscription : décembre 2002
    Messages : 157
    Points : 220
    Points
    220
    Par défaut
    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

  11. #11
    Membre à l'essai
    Profil pro
    Inscrit en
    mars 2009
    Messages
    13
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : mars 2009
    Messages : 13
    Points : 10
    Points
    10
    Par défaut
    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)

  12. #12
    Expert éminent sénior
    Avatar de Emmanuel Delahaye
    Profil pro
    Retraité
    Inscrit en
    décembre 2003
    Messages
    14 512
    Détails du profil
    Informations personnelles :
    Âge : 65
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Retraité

    Informations forums :
    Inscription : décembre 2003
    Messages : 14 512
    Points : 20 982
    Points
    20 982
    Par défaut
    Citation Envoyé par arnodujura Voir le message
    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.
    Pas de Wi-Fi à la maison : CPL

  13. #13
    Nouveau Candidat au Club
    Femme Profil pro
    Chercheur en informatique
    Inscrit en
    juin 2014
    Messages
    2
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Âge : 27
    Localisation : Maroc

    Informations professionnelles :
    Activité : Chercheur en informatique

    Informations forums :
    Inscription : juin 2014
    Messages : 2
    Points : 0
    Points
    0
    Par défaut
    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

  14. #14
    Expert éminent sénior
    Avatar de Emmanuel Delahaye
    Profil pro
    Retraité
    Inscrit en
    décembre 2003
    Messages
    14 512
    Détails du profil
    Informations personnelles :
    Âge : 65
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Retraité

    Informations forums :
    Inscription : décembre 2003
    Messages : 14 512
    Points : 20 982
    Points
    20 982
    Par défaut
    Citation Envoyé par Dounia Karym Voir le message
    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 !
    Pas de Wi-Fi à la maison : CPL

  15. #15
    Nouveau Candidat au Club
    Femme Profil pro
    Chercheur en informatique
    Inscrit en
    juin 2014
    Messages
    2
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Âge : 27
    Localisation : Maroc

    Informations professionnelles :
    Activité : Chercheur en informatique

    Informations forums :
    Inscription : juin 2014
    Messages : 2
    Points : 0
    Points
    0
    Par défaut
    hahahaha J mexcuse pr le derangement ! mais comment faire pour la trier !?? SVP

  16. #16
    Expert éminent
    Homme Profil pro
    Analyste/ Programmeur
    Inscrit en
    juillet 2013
    Messages
    4 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Analyste/ Programmeur

    Informations forums :
    Inscription : juillet 2013
    Messages : 4 245
    Points : 9 588
    Points
    9 588

  17. #17
    Expert éminent sénior
    Avatar de Emmanuel Delahaye
    Profil pro
    Retraité
    Inscrit en
    décembre 2003
    Messages
    14 512
    Détails du profil
    Informations personnelles :
    Âge : 65
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Retraité

    Informations forums :
    Inscription : décembre 2003
    Messages : 14 512
    Points : 20 982
    Points
    20 982
    Par défaut
    Citation Envoyé par Dounia Karym Voir le message
    hahahaha J mexcuse pr le derangement ! mais comment faire pour la trier !?? SVP
    "Chercheur en informatique"

    C'est le moment de chercher ! Hi hi !
    Pas de Wi-Fi à la maison : CPL

Discussions similaires

  1. Supprimer les doublons d'une liste déroulante
    Par zanzie dans le forum Flash
    Réponses: 1
    Dernier message: 11/04/2011, 08h34
  2. Supprimer les doublons dans une liste
    Par inforum dans le forum SL & STL
    Réponses: 2
    Dernier message: 22/11/2009, 15h21
  3. Supprimer les doublons d'une liste
    Par bibi206 dans le forum Scheme
    Réponses: 23
    Dernier message: 13/06/2009, 09h53
  4. [E-03] Supprimer les doublons d'une liste
    Par Loki83 dans le forum Macros et VBA Excel
    Réponses: 5
    Dernier message: 05/12/2008, 16h34
  5. Réponses: 10
    Dernier message: 19/09/2006, 03h15

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo