Discussion :

[orfix]

Salut,
C'est une question concernant ce cours : http://nicolasj.developpez.com/articles/listesimple/
vu que je débute en programmation, et que le concept des listes chainées est tout nouveau pour moi, je n'ai pas compris l'utilité de la sentinelle utilisée en début de chaine ... pourquoi ne pas faire pointer directement p_start sur le premier èlément ?

Merci

[Plorf]

afin d'éviter une seg fault si ce lien vaut NULL ;-)

[Sve@r]

Salut,
C'est une question concernant ce cours : http://nicolasj.developpez.com/articles/listesimple/
vu que je débute en programmation, et que le concept des listes chainées est tout nouveau pour moi, je n'ai pas compris l'utilité de la sentinelle utilisée en début de chaine ... pourquoi ne pas faire pointer directement p_start sur le premier èlément ?

Merci

Parce que le concept de liste peut s'envisager même si elle ne contient pas (encore) d'élément. Dans ce cas, il faut bien mettre une valeur particulière à ce p_start pour indiquer justement que la liste est vide => d'où le NULL

[Médinoc]

Pour moi, ça ne sert à rien, et on pourrait directement initialiser p_start à NULL pour une liste vide.

[Trap D]

Pour moi, ça ne sert à rien, et on pourrait directement initialiser p_start à NULL pour une liste vide.

Je pense que l'explication de l'utilité de la sentinelle est ici :

III-I. Accès au premier élément de la liste
Cette fonction est rendue extrêmement simple par l'existence de la sentinelle :

[Médinoc]

Ben pour moi, c'est encore plus simple sans: Le premier élément de la liste, c'est l'élément pointé par p_start...

[orfix]

Je pense que l'explication de l'utilité de la sentinelle est ici :
Citation:
III-I. Accès au premier élément de la liste
Cette fonction est rendue extrêmement simple par l'existence de la sentinelle :

Oui je me disais aussi mais comme la dit "Médinoc" elle serais encore plus simple :

Code :

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

1
2
3
4
5
6
7
8
 
void sll_first (sll_s * p_sll)
{
   if (p_sll)
   {
      p_sll->list = p_sll->p_start->next;
   }
}

Sera remplacer par :

Code :

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

1
2
3
4
5
6
7
8
 
void sll_first (sll_s * p_sll)
{
   if (p_sll)
   {
      p_sll->list = p_sll->p_start;
   }
}

Parce que le concept de liste peut s'envisager même si elle ne contient pas (encore) d'élément. Dans ce cas, il faut bien mettre une valeur particulière à ce p_start pour indiquer justement que la liste est vide => d'où le NULL

Voilà je vous explique ce que j'ai compris et vous me dites si c'est juste :

La fonction d'initialisation de la liste crée un premier noeud (Une sentinelle) qui pointe vers NULL, puis elle fait pointer p_start sur ce noeud (Une sentinelle), les éléments insérés viendrons après cette sentinelle, elle pointera donc toujours sur le premier noeud de la liste, Je me disais que ça c'était le boulot de p_start de pointer toujours sur le premier noeud de la liste ...

Enfin il ya surement une subtilité qui se cache derrière tout ceci

Merci

[Médinoc]

En fait, il y a autre chose que j'ai du mal à comprendre, c'est le fait de stocker un pointeur "nœud courant" dans la structure sll.
Pour moi, c'est le genre de chose qui se met à l'extérieur.

...Par contre, on peut stocker un pointeur "dernier nœud"...

[Sve@r]

Voilà je vous explique ce que j'ai compris et vous me dites si c'est juste :

La fonction d'initialisation de la liste crée un premier noeud (Une sentinelle) qui pointe vers NULL, puis elle fait pointer p_start sur ce noeud (Une sentinelle), les éléments insérés viendrons après cette sentinelle, elle pointera donc toujours sur le premier noeud de la liste, Je me disais que ça c'était le boulot de p_start de pointer toujours sur le premier noeud de la liste ...

Enfin il ya surement une subtilité qui se cache derrière tout ceci

Merci

C'est pas tout à fait exact.

Dans la notion de liste telle que je la conçois (et comme ça semble être expliqué aussi dans le premier lien de ce topic), on distingue deux éléments
1) le membre de la liste (un wagon quoi). Il contient son contenu et le pointeur sur le suivant. On peut avoir aussi un pointeur sur le précédent si on a besoin de faire des parcours dans les deux sens mais c'est facultatif
Exemple

Code :

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

1
2
3
4
typedef struct s_elem {
    int valeur;
    struct s_elem *next;
} t_elem;

2) l'objet qui tient la liste et c'est là que les avis divergent. Certains disent "tenir le premier wagon est amplement suffisant". Ce n'est pas faux. Le problème c'est que quand ce premier wagon change, comme on a en main un simple pointeur ben il faut que la fonction qui fait le changement modifie ce pointeur. Et toute fonction qui modifie un truc doit recevoir l'adresse de ce truc. Donc si elle modifie un pointeur elle doit travailler sur l'adresse de ce pointeur (l'adresse d'une adresse). C'est faisable. Exemple avec une fonction qui va modifier le premier élément d'une liste en le remplaçant par un nouvel élément

Code :

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

1
2
3
4
5
void modif_first(t_elem **first, t_elem *new)
{
    new->next=(*first);
    (*first)=new;
}

Devoir travailler sans cesse avec "*first" dans la fonction devient vite chiant. On peut se planter, etc. De plus, un autre problème se pose quand on veut manipuler "n" listes. Il faut tenir "n" premiers pointeurs. Et là le risque de s'embrouiller les pinceaux est encore plus grand.
Un 3° problème se pose si on veut avoir des éléments subsidiaires de la liste comme son nb d'éléments. Il faut une seconde variable style "nb_elem". Mais maintenant qu'on doit gérer "n" listes faut gérer "n" premiers pointeurs PLUS "n" nb_elem. Lourd lourd.
De plus, conceptuellement, quand une variable "x" est associée à une variable "y" (comme hh et mn) ben il est courant de les regrouper en structures.

C'est là qu'arrive donc une seconde opinion => rajouter une structure qui manipule la liste. Exemple

Code :

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

1
2
3
typedef struct {
    t_elem *first;
} t_liste;

Ca semble tout con d'avoir une structure qui ne contient qu'un seul élément mais après, on s'aperçoit qu'on en ressort plein d'avantages dans la manipulation. Par exemple si je reprends la fonction qui modifie le premier élément de la liste

Code :

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

1
2
3
4
5
void modif_first(t_liste *liste, t_elem *new)
{
    new->next=liste->first;
    liste->first=new;
}

On constate maintenant une plus grande simplicité dans l'écriture. Plus la peine de se palucher des "**" à tour de bras en bossant ensuite avec (*ceci)=truc.

A partir de là, une fois qu'on a l'outil, on peut l'enrichir en y rajoutant le nb d'élements ou autres trucs perso qui aideront à la manipulation de la liste. On peut créer une fonction d'initialisation style

Code :

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

1
2
3
4
5
void initListe(t_liste *liste)
{
    liste->first=NULL;
    liste->nb=0;
}

Et d'autres fonctions très basiques d'insertion ou autre. Une fois que tous les outils sont créés, il ne reste plus qu'à les utiliser pour une liste, style

Code :

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

1
2
3
4
5
6
int main()
{
    t_liste maListe;
    initListe(&maListe);
    <...>
}

Ou bien pour un gros paquet de listes, style

Code :

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

1
2
3
4
5
6
7
8
9
int main()
{
    t_liste monTableauDeListe[100];
    size_t i;
 
    for (i=0; i < 100; i++)
        initListe(&monTableauDeListe[i]);
    <...>
}

Bon, je sais que ça te semble un peu obscur. Quand tu auras un peu plus l'habitude, que tu auras travaillé, créé des algo, tu te rendras compte qu'avoir un objet (hoho, on parle d'objet ?) + des fonctions associés à chaque concept permet ensuite une plus grande simplicité dans la programmation.

En fait, il y a autre chose que j'ai du mal à comprendre, c'est le fait de stocker un pointeur "nœud courant" dans la structure sll.
Pour moi, c'est le genre de chose qui se met à l'extérieur.

Ben justement, avec le type t_liste, t'as le choix. Ca peut être inclus dans la structure (toute fonction recevant la structure en paramètre saura où en est le courant) ou en dehors (pour un travail local). Alors que sans le type t_liste ben t'étais limité à une seule possibilité...