Listes chainées en C

Version imprimable

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:

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:

LinkedList *list;

Et je fais aussi un typdef dans le .h:

Code:

typedef struct LinkedList LinkedList;

Merci d'avance.

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:

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 }

10/10/2011, 17h17
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:

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:

ajouterApresCle(maListe);

Citation:

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:

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

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.

Citation:

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

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

Code:

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

11/10/2011, 09h05
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.
11/10/2011, 11h17
samos2

Citation:

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

Citation:

Envoyé par samos2

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:

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.

13/10/2011, 12h44
samos2

Ok ça marche. Merci pour ton aide diogene.