Discussion :

[Camaryl]

Bonjour,

Je bloque sur un exercice (pourtant assez facile) d'ajout d'un élément à une liste chainée. Concrètement je dois faire passer le premier élément d'une liste A à une liste B.
Voici mon code :

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
 
t_push          *put_in_b(t_push **list_a, t_push **list_b)
{
  t_push        *lptr;
 
  if ((lptr = malloc(sizeof(t_push))) == NULL)
    return (NULL);
  if (lptr != NULL)
    {
      lptr->data = (*list_a)->data;
      lptr->prev = NULL;
      if ((*list_b)->tail == NULL)
        {
          lptr->next = NULL;
          (*list_b)->head = lptr;
          (*list_b)->tail = lptr;
        }
      else
        {
          (*list_b)->head->prev = lptr;
          lptr->next = (*list_b)->head;
          (*list_b)->head = lptr;
        }
      (*list_b)->data = lptr->data;
      (*list_b)->len++;
    }
  decal(list_a);
}

la fonction decal(t_push **list_a) fonctionne sans problème (elle supprime l'élément de la liste A passé dans la liste B).
Mon souci est que ma fonction put_in_b, plutôt que de stocker les éléments mis dans la liste B au fur et à mesure, remplace à chaque fois le premier élément ce qui fait que ce genre d'appel :
list_a : 3 5 4 6
list_b :
put_in_b(&list_a, &list_b);
put_in_b(&list_a, &list_b);
put_in_b(&list_a, &list_b);

me donne : my_show_list(list_b) = 4 alors que je veux : my_show_list(list_b) = 4 5 3

Je ne sais pas si je suis très claire,
merci d'avance

[Sve@r]

Bonjour
Sur le papier, ton algo me semble bon. On peut avoir le source complet pour tester ???
Sinon 2 remarques

1. t'as pas besoin de retester si lptr != NULL
2. il semblerait que ton t_push (qui possède un élément "head", "len" et "tail") soit un type dédié à gérer la liste elle-même, et qui possède un élément "data", "prev" et "next", soit aussi un type dédié à gérer un noeud. C'est pas bon. Déjà tous les noeuds auront un "len", "first" et"tail" mais un seul d'entre eux aura ces éléments corrects et il est probable que la confusion vienne de ça. Tu peux pas créer un type dédié à la liste, et un autre dédié au noeud ???

[stendhal666]

Je plussoie les remarques de Sve@r, tu devrais avoir une structure Liste et une autre Noeud, dans le genre:

Code :

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

1
2
3
4
5
6
7
8
9
struct Noeud {
  int val; // ou tout autre type d'élément
  struct Noeud *prev, *next;
};
 
struct Liste {
  size_t len;
  struct Noeud *head, *tail;
};

Ensuite fais des fonctions basiques, genre push et pop:

Code :

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

1
2
3
4
5
6
7
struct Node* pop(struct Liste **l) {
  struct Node* n = (*l)->head;
  /* faire les différentes opérations pour que (*l)->head devienne (*l->head->next) */
  return n;
}
 
void push(struct Liste** a, struct Node* n) { /* modifier a->head, n->next, n->next->prev */ }

de même pour push et ensuite tu peux écrire (sans qu'il soit besoin d'allouer ou de libérer de la mémoire, cela soit dit en passant):

Code :

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

1
2
3
void pushtoB (struct Liste** a, struct Liste** b) {
  push(b, pop(a));
}

[Sve@r]

Je plussoie les remarques de Sve@r, tu devrais avoir une structure Liste et une autre Noeud, dans le genre:

Code :

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

1
2
3
4
5
6
7
8
9
struct Noeud {
  int val; // ou tout autre type d'élément
  struct Noeud *prev, *next;
};
 
struct Liste {
  size_t len;
  struct Noeud *head, *tail;
};

Perso je préfère nommer les structures "s_xxx" mais c'est pas mal.

Code :

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

1
2
3
4
5
struct Node* pop(struct Liste **l) {
  struct Node* n = (*l)->head;
  /* faire les différentes opérations pour que (*l)->head devienne (*l->head->next) */
  return n;
}

Pas besoin de double pointeur (ce qui t'évitera les erreurs (*l->head->next) au lieu de (*l)->head->next)

Code :

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

1
2
3
4
5
struct Node* pop(struct Liste *l) {
  struct Node* n = l->head;
  /* faire les différentes opérations pour que l->head devienne l->head->next */
  return n;
}

Et pareil pour le push.

de même pour push et ensuite tu peux écrire

Code :

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

1
2
3
void pushtoB (struct Liste** a, struct Liste** b) {
  push(b, pop(a));
}

Yeah classe !!! (mais avec une seule étoile ça le fait aussi

Sauf que peut-être on peut revenir au standard et mettre en premier la liste destinatrice (comme c'est le cas dans strcpy et autres)...

Code :

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

1
2
3
void pushToOtherList (struct Liste* dest, struct Liste* src) {
  push(dest, pop(src));
}

Mais tu gardes ton

(sans qu'il soit besoin d'allouer ou de libérer de la mémoire, cela soit dit en passant):

Exact parce que heureusement tu ne fais pas de free()

[Camaryl]

Dacodac, merci tout le monde pour votre aide ! J'ai finalement trouvé de mon côté une méthode un peu plus optimisée pour contourner le problème et je viens de voir où était mon soucis,
Merci