les redondances en listes chainées?

Version imprimable

06/04/2007, 01h38
milouky

les redondances en listes chainées?

bonsoir tout le monde :D

j ai un probleme :? et je suis besoin de l aide :oops: :(

comment faire un programme en langage c qui elimine les redondances a partir d une liste chainée?8O

merci d' avance pour votre aide :king:

bonne nuit
:merci:
06/04/2007, 17h46
Jedai

Tu n'es pas sur le bon forum (il y a un forum sur le Langage C, ou éventuellement sur l'Algorithmique), par ailleurs "redondance" est un terme un peu vague en informatique. Veux-tu dire les doublons ? Et dans ce cas ne comptes-tu comme doublon que des éléments identiques qui se suivent ou n'importe quels éléments identiques, même s'il ne sont pas consécutifs ?
Reformule ta question et va la poster dans le bon forum, tu recevras sans doute très rapidement une réponse.

--
Jedaï
06/04/2007, 20h33
milouky

bsr tous

merci pour vous jedai

ma qestion etait :dans une liste chainée j ai des élément qui se repetent alors comment faire pour eliminer cette repetition ?
j'espere que m a question est maintenant claire .

merci d'avance pour votre aide.
06/04/2007, 20h36
Trap D

Tu peux la trier éventuellement puis éliminer les doublons, mais c'est surtout au moment de la création de la liste qu'il faut opérer, c-a-d tu n'insères un élément que s'il n'est pas déjà présent dans la liste, fais une insertion dans un ordre croissant par exemple.
06/04/2007, 20h58
milouky

Citation:

Envoyé par Trap D

Tu peux la trier éventuellement puis éliminer les doublons, mais c'est surtout au moment de la création de la liste qu'il faut opérer, c-a-d tu n'insères un élément que s'il n'est pas déjà présent dans la liste, fais une insertion dans un ordre croissant par exemple.

n y a-t-il pa une autre façon de le faire pour une liste déja criée?sans la triée8O
j ai ponsé qu il fallait avoir 3 pointeur un qui parcoure la liste un precedentet un tempant de fason que j initialise le tmp a la tete de la liste et je parcoure la liste a l aide de par et pred et a chaque fois que la valeur de la cellule est egale à la valeur de tmp je supprime la cellule et j incremante le tmp
je n sait pa si c est comme ça ke se fait mai en tout ca ça ne veu pa marcher.

:merci: pour vous
06/04/2007, 22h34
Trap D

Oui, on peut aussi faire comme celà, si j'ai bien compris ce que tu écris, mais ce sera forcément très long, en O(n^2) n étant le nombre d'éléments de la liste.
06/04/2007, 23h09
milouky

:D ok merci a vous:D

et c est vraiment trop long

mais sa marche pa

je refaire le programme pour savoir le probleme

merci a vous et bn8
06/04/2007, 23h31
Trap D

Montre ton code, c'est peut-être une simple erreur sur un pointeur.
07/04/2007, 15h02
Emmanuel Delahaye

Citation:

Envoyé par milouky

comment faire un programme en langage c qui elimine les redondances a partir d une liste chainée?

Problème d'algorithme. La redondance est une plaie qui doit être traitée en amont, c'est à dire au moment de l'ajout d'un donnée nouvelle. Pour ça, on commence pas vérifier si elle est présente dans la liste. Si elle existe, on met à jour ou on ne fait rien.

Si le mal est fait, le mieux est de recréer une liste en déplaçant les éléments de l'ancienne à la nouvelle, un par un et testant les doublons à chaque fois. Si un élément est en double, il est détaché et détruit.
07/04/2007, 21h26
HanLee

Est-ce que tu es obligé d'utiliser une liste ? Tu peux pas utiliser un arbre rouge-noir à la place, par exemple ?

j'avais fait ce code pour résoudre un problème de multiplication de 2 polynomes,

à un moment je devais supprimer les noeuds de même degré, tu pourras probablement t'en inspirer, il est commenté donc tu comprendras facilement je pense.

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
85
86
87
88
89
90
91
92
 
typedef struct noeud noeud_s;
/* structure d'un monome */
struct noeud
{
   /* Coefficient d'un monome */
   float coefficient;
   /* Degre d'un monome */
   int degre;
   /* stocke l'adresse du noeud suivant */
   noeud_s *p_suivant;
};
 
 
/* --------------------------------------------------------------------------
   supprimer_noeud ()
   --------------------------------------------------------------------------
   Role : supprime un noeud a la position p
   -------------------------------------------------------------------------- */
void supprimer_noeud (noeud_s *p_liste, noeud_s *p_position)
{
   /* on declare un pointeur pour stocker l'adresse du noeud precedent */
   noeud_s *p_precedent = p_liste;
 
   /* On parcours la liste a la recherche du noeud precedent */
   while (p_precedent->p_suivant != NULL)
   {
      if (p_precedent->p_suivant == p_position)
      {
         /* Si on a trouver le noeud precedent la position p on effectue la
            suppression */
         /* Le noeud precedent pointe sur le noeud suivant */
         p_precedent->p_suivant = p_position->p_suivant;
         /* On libere le noeud courant */
         free (p_position);
         /* Le traitement effectue, on sort */
         break;
      }
      else
      {
         /* Sinon on se deplace vers la droite pour chercher le precedent */
         p_precedent = p_precedent->p_suivant;
      }
   }
}
 
/* --------------------------------------------------------------------------
   fusionner_noeuds ()
   --------------------------------------------------------------------------
   Role : Dans le polynome resultat cette fonction fusionne 2 noeuds ayant le
          même degre (en sommant leur coefficient) et supprime le noeud le plus
          a droite a l'aide de supprimer_noeud ()
   -------------------------------------------------------------------------- */
void fusionner_noeuds (noeud_s *p_liste)
{
   /* On declare 2 pointeurs temporaires pour parcourir la liste */
   noeud_s *p_tmp1 = p_liste->p_suivant;
   noeud_s *p_tmp2;
   /* pointeur de sauvegarde d'adresse */
   noeud_s *p_tmp3;
 
   while (p_tmp1 != NULL)
   {
      /* On compare le degre d'un noeud avec le degre de ceux qui le suivent */
      p_tmp2 = p_tmp1->p_suivant;
 
      while (p_tmp2 != NULL)
      {
         if (p_tmp1->degre == p_tmp2->degre)
         {
            /* Si les monomes ont meme degre, on les fusionne en additionnant leur
               coefficient*/
            p_tmp1->coefficient+= p_tmp2->coefficient;
            /* La fusion implique la suppression du noeud le plus a droite,
               on sauvegarde avant l'adresse du noeud suivant le noeud a
               supprimer pour pouvoir continuer le traitement */
            p_tmp3 = p_tmp2->p_suivant;
            supprimer_noeud (p_liste, p_tmp2);
            p_tmp2 = p_tmp3;
         }
         else
         {
            /* Sinon on avance de la chaine pour continuer le traitement */
            p_tmp2 = p_tmp2->p_suivant;
         }
      }
 
      /* On a comparer le degre d'un monome avec tous les monomes qui le suivent,
         on avance dans la chaine */
      p_tmp1 = p_tmp1->p_suivant;
   }
}

c y est ca marche voila le code de la fonction
je ne sais pas si

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
 
ptrcellule *eleminerod(ptrcellule *liste)
 {
     ptrcellule *par1,*par2;
     ptrcellule  *tmp;
     par1=liste;
     int i,j,l,pos;
 
l=calcullong(liste);
/*c est une fonction ke j ai et ki calcule la langueur d une liste*/
 
  for(i=1;i<=l;i++)
    {
       par2=par1->suiv;
 
 
             for(j=i+1;j<=l;j++)
                {
                   if(par2->val==par1->val)
                     {
                         pos=j;
                         liste = suprimerpos(liste,pos);
/*suppression fonction ki supprime une position de la liste*/
                         return eleminerod(liste);
                      }
 
                    else
                        par2=par2->suiv;
                 }
 
         par1=par1->suiv;
 
    }
return liste;
}

si vous avez des remarques ca serai gentille de votre part.
:merci:

Tu peux te passer ET des indices ET de la longueur de la liste ET de la récursivité :

En ajoutant un paramètre prec qui est l'élément précdent de celui que tu élimines (à moins que tu aies une liste doublement chaînée).

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
 
ptrcellule *eleminerod(ptrcellule *liste)
 {
     ptrcellule *par1=NULL,*par2=NULL;
     ptrcellule  *tmp=NULL, *prec=NULL;
 
   par1 = liste ;
 
   while ( par1 != NULL )
     {
         par2=par1->suiv ; 
         prec = par1 ;
 
         while ( par2 != NULL )
            {
                tmp = par2->suiv ;
 
                if (par2->val == par1->val)
                  {
                      prec->suiv = par2->suiv ;
 
                      /* libère ce qui il y a à libérer dans par2 */
                      /* puis libère par2 */
                  }
                else
                     prec = par2 ;
 
                par2 = tmp ;
            }                
 
         par1=par1->suiv; 
    }
 
return liste;
}

14/04/2007, 23h29
Jedai

Pour diminuer la complexité temporelle, mais augmenter la complexité spatiale, et si tu as un toolkit correct, tu peux utiliser une table de hachage : tu parcours ta liste, et à chaque élément rencontré tu vérifies s'il est dans ta table de hachage, si oui tu le supprimes, si non tu le mets dans la table et tu passes à l'élément suivant. La complexité théorique est en O(n) (en supposant le temps d'accès à la table de hachage constant, ce qui est une approximation convenable pour une implémentation correcte), ce qui représente une amélioration notable par rapport au O(n²) de ton approche actuelle, en pratique il faut que tes listes soient relativement longues pour que tu ais réellement un gain.

--
Jedaï