Discussion :

[samos2]

Bonjour a tous,

Voila, je viens d’implémenter les listes chainées en C, j'aimerai avoir vos avis. Je donne juste le module ou est le code qui concerne les listes.

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
#include <stdlib.h>
#include <stdio.h>
#include "list.h"
 
struct Cell
{
    int integer;
    struct Cell *next;
};
 
struct LinkedList
{
    struct Cell *first;
    struct Cell *it;
};
 
void createListe(struct LinkedList *list) /* Initialise la list */
{
    list->first = NULL;
    list->it = NULL;
}
 
void deleteListe(struct LinkedList *list)
{
    list->it = list->first;
    struct Cell *temp;
 
    while((list->it)->next != NULL)
    {
        temp = (list->it)->next;
        free(list->it);
        list->it = temp;
    }
 
    free(list->it);
 
    list->it = NULL;
    list->first = NULL;
}
 
void incrementIt(LinkedList *list)
{
    list->it = (list->it)->next;
}
 
void push(struct LinkedList *list, int x)
{
    struct Cell *p = malloc(sizeof(struct Cell));
 
    p->next = list->first; // First vaut NULL si la list est vide
    p->integer = x;
 
    list->first = p;
    list->it = p;
}
 
void printList(struct LinkedList *list)
{
    list->it = list->first;
 
    if(list->it == NULL)
        printf("<empty>");
 
    while(list->it != NULL)
    {
        printf("%d ", (list->it)->integer);
        list->it = (list->it)->next;
    }
 
    printf("\n");
}

En faite la ou j’ai un doute c'est sur l'utilisation des doubles flèches, notamment parce que j’en utilise 2 dans une même expression.

Je declare ma liste comme ceci:

Code :

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

LinkedList *list;

Et je fais aussi un typdef dans le .h:

Code :

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

typedef struct LinkedList LinkedList;

Merci d'avance.

[fregolo52]

Pourquoi LinkedList ?
Ca ert just à garder le pointeur sur le 1er élément, dans quel intérêt ?

Ton programme doit garder en permanence un pointeur sur le 1er élément dans la chaine. Style :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
int main(){
struct Cell *first;
struct Cell *chaine;
 
// tu initiales ta chaine (en gros tu crées le 1er élément) puis
first = chaine;
 
// tu bosses avec le pointeur chaine qui se déplace et quand tu veux lister la chaine tu repars de first
 
// attention first est en "lecture seule" et ne doit jamais se déplacer
}

[samos2]

Dans la structure LinkedList, ya effectivement un pointeur sur le premier élément et aussi une clé qui est placer selon le besoin. La clé que j'appelle it(rateur).

Après l’intérêt de mettre les deux variables dans une structure et que je peut faire des appels de fonction du genre:

Code :

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

1
2
push(maList, 7);
printList(maList);

, par exemple.

Ou alors la fonction ajouterApresCle() que j'ai pas encore implémentée qui est simplement appeler comme ceci:

Code :

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

ajouterApresCle(maListe);

[diogene]

Pourquoi LinkedList ?
Ca ert just à garder le pointeur sur le 1er élément, dans quel intérêt ?

Pour la clarté du code, encapsuler ce pointeur dans une structure est bénéfique. De plus, cela permet éventuellement de compléter la définition de la liste avec d'autres informations (pointeur de queue, nombre d'éléments, ici un itérateur,...)

Par contre, la liste doit être déclarée par

Code :

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

1
2
LinkedList list;
createListe(&list); // MAIS ne crée pas la liste !

ou alors

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
LinkedList * createListe() /* crée et initialise la list */
{
  LinkedList * list= malloc(sizeof *list);
  if(list != NULL)
  {
    list->first = NULL;
    list->it = NULL;
  }
  return list;
}
...
LinkedList *list = createListe();

et la récupération de la mémoire allouée est faite dans deleteListe() par un free(list) à la fin.

Le coup de l'itérateur n'est pas terrible à cause des modifications implicites et inattendues (comme dans printList()) qui le rendront difficile à utiliser de façon fiable.

j’ai un doute c'est sur l'utilisation des doubles flèches

Pas de problèmes et inutile de sur-parenthèser

Code :

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

list->it = list->it->next;

[fregolo52]

oups. J'avais mis une analyse foireuse !!! (meesage supprimé)

Ok j'ai compris le principe.
J'ai été perturbé par la fonction push. J'ai plus l'habitude de push_back.

[samos2]

Le coup de l'itérateur n'est pas terrible à cause des modifications implicites et inattendues (comme dans printList()) qui le rendront difficile à utiliser de façon fiable.

A quel niveau dans printList() ?

Sinon merci pour les precisions

[diogene]

A quel niveau dans printList() ?

Sinon merci pour les precisions

L'utilisateur pense utiliser cet itérateur pour se déplacer et se positionner lui-même dans la liste.
Tu utilises ton itérateur pour parcourir la liste afin de l'afficher ce qui détruit sa valeur inutilement et l'utilisateur a maintenant un itérateur à NULL. C'est un comportement inattendu et inutile :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
void printList(LinkedList *list)
{
    struct Cell *it = list->first;
    if(it == NULL)
        printf("<empty>");
    while(it != NULL)
    {
        printf("%d ", it->integer;
        lit = it->next;
    } 
    printf("\n");
}

Le problème est sans importance dans deleteListe() puisque de toute façon la liste est détruite.

[samos2]

Ok ça marche. Merci pour ton aide diogene.