Question sur un tuto sur les listes doublement chainée

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Bonjour,

depuis le début des vacances (soit lundi 19/10) je m'amuse a coder une lib de liste doublement chainée en C avec ce tuto.

Jusque là, j’étais plutôt d'accord avec l'auteur (à pars que j'ai préféré utiliser des pointeurs sur pointeurs de Dlist au lieu d'en retourner une a chaque fonction qui la modifie) mais à la fonction dlist_find je comprends pas trop ce qu'il fait.

Pourquoi retourner une liste alors qu'il n'y a qu'un seul élément a retourner ?

Pourquoi retourner data et pas l'index de l'élément ?

J'espère que vous pourrez m’éclaircir à ce sujet, j’attends vos réponses pour coder la fonction de la manière la plus logique.

P.S. : Si vous trouvez un meilleur titre pour le sujet dite le moi

Édité par LudoBike

« La Nature est un livre écrit en langage mathématique », Galilée

+0 -0

Cette réponse a aidé l'auteur du sujet

Ça tombe bien, je suis l'auteur de ce tuto ;) (enfin, ça fait longtemps maintenant).

Jusque là, j’étais plutôt d'accord avec l'auteur (à pars que j'ai préféré utiliser des pointeurs sur pointeurs de Dlist au lieu d'en retourner une a chaque fonction qui la modifie) mais à la fonction dlist_find je comprends pas trop ce qu'il fait.

Pourquoi retourner une liste alors qu'il n'y a qu'un seul élément a retourner ?

A vrai dire, je ne me souviens plus exactement du pourquoi, et c'est vrai que ça fait étrange.

C'est très probablement une maladresse due à la difficulté de savoir quoi retourner si on ne trouve pas. En effet, il faut que cet élément soit différentiable d'un élément valide de la liste, or le type ne le permet pas. En C++ par exemple, une fonction de find va retourner un iterator, qui vaudra truc.end() s'il n'a pas trouvé, et un itérateur valide sinon. L'autre solution "propre" que je vois serait de renvoyer une exception, mais ce n'est pas faisable en C.

Pourquoi retourner data et pas l'index de l'élément ?

On retourne rarement l'index de l'élément lorsqu'on utilise des listes, ça n'a aucun intérêt si c'est pour accéder directement à l'élément en question. Soit on retourne l'élément en question (et on a le problème que j'ai mentionné plus haut), soit on retourne un itérateur sur l'élément (et c'est moche comme en C++).

Édité par yoch

+1 -0
Auteur du sujet

Ça tombe bien, je suis l'auteur de ce tuto ;) (enfin, ça fait longtemps maintenant).

yoch

Je pensais pas si bien tombé ! :D

Mais sinon j'ai pensé que l'on pourrait renvoyer une valeur booléen, 0 si l'élément est dans la liste, 1 s'il n'y est pas. Mais du coup c'est plus trop une fonction find.

« La Nature est un livre écrit en langage mathématique », Galilée

+0 -0
Auteur du sujet

Il y a plus simple: renvoyer l'adresse de l'élément si on l'a trouvé, NULL sinon.

Grimur

Ouais mais je par l'élément tu vois le Node ou le int data. Parce que sauf erreur de ma part l'utilisateur ne doit pas utiliser de Node.

« La Nature est un livre écrit en langage mathématique », Galilée

+0 -0
Auteur du sujet

Voilà ce que ça rend en C

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
int *dlist_find(Dlist *list, int data)
{
    int *ret = NULL;
    Node *tmp = list->p_head;
    while (!ret)
    {
    if (tmp->data == data)
    {
        ret = &(tmp->data);
    }
    else if (!tmp->p_next)
    {
        break;
    }
    tmp = tmp->p_next;
    }
    return ret;
}

« La Nature est un livre écrit en langage mathématique », Galilée

+0 -0

Cette réponse a aidé l'auteur du sujet

Ça se simplifie vachement tout ça.

Déjà, si tu retourne l'élément recherché quand tu tombe dessus, plus besoin de ret, et tu peux juste itérer tant que tmp est différent de NULL. Si tu as pu parcourir tout les éléments de list alors tu retourne NULL.

Tu peux aussi utiliser une boucle for qui est un peu plus adaptée ici, et préciser que list est constant.

À la fin on se retrouve donc avec quelque chose comme ceci:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
int*
dlist_find(const Dlist* list, int data)
{
    for (const Node* cur = list->p_head; cur != NULL; cur = cur->next)
    {
        if (cur->data == data)
        {
            return &cur->data;
        }
    }

    return NULL;
}

Édité par superlama

+0 -0
Auteur du sujet

Oui c'est vrai que c'est plus lisible. Je savais pas que l'on pouvait faire des paramètres constant en C.

Par contre tu a fais une erreur dans la declaration de la boucle for tu a mis

1
cur = cur>next

au lieu de

1
cur = cur->next

et aussi pourquoi cur est constant alors que tu changes sa valeur ?

Édité par LudoBike

« La Nature est un livre écrit en langage mathématique », Galilée

+0 -0

J'avais vu l'erreur et je l'ai corrigé. cur est tout à fait modifiable, ce sont les valeurs pointées qui ne le sont pas (le const s'applique à Node et pas à *).

Édité par superlama

+0 -0
Auteur du sujet

Ok mais c'est bizard mon code compile pas et j'ai ces erreurs

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
# ludovic at Christophe in ~/workspace/C/lib/dlist on git:master x [17:39:36]
$ gcw main.c dlist.c dlist.h
dlist.c: In function ‘dlist_find’:
dlist.c:254:5: error: ‘for’ loop initial declarations are only allowed in C99 or C11 mode
     for (const Node *cur = list->p_head; cur; cur = cur->p_next)
     ^
dlist.c:254:5: note: use option -std=c99, -std=gnu99, -std=c11 or -std=gnu11 to compile your code
dlist.c:258:6: error: return discards ‘const’ qualifier from pointer target type [-Werror]
      return &(cur->data);
      ^
cc1: all warnings being treated as errors

la 1er j'ai compris il faut juste rajouter -std=c99 pour que ça compile par contre la 2éme

« La Nature est un livre écrit en langage mathématique », Galilée

+0 -0

Tu devrais supprimer -Werror. Parce qu'actuellement tu ne peux pas compiler strchr non plus:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
char*
strchr(const char* s, int c)
{
    assert(s != NULL);

    for (; *s != c; ++s)
    {
        if (*s == '\0')
        {
            return NULL;
        }
    }

    return s;
}

Le truc c'est que je retourne un pointeur non-constant vers des données qui ont étés marquées comme étant constante. Ça ne plait pas au compilateur, mais c'est valide et correct, la fonction n'a pas le droit de modifier les données, mais celle qui va récupérer la valeur trouvée peut vouloir le faire.

Édité par superlama

+0 -0

Après en dessous d'un certain niveau de warning, faire un cast explicite peut aussi régler le problème:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
int*
dlist_find(const Dlist* list, int data)
{
    for (const Node* cur = list->p_head; cur != NULL; cur = cur->next)
    {
        if (cur->data == data)
        {
            return (int*) &cur->data;
        }
    }

    return NULL;
}

Mais:

  • C'est moche
  • Ajouter -Weverything (> -Wcast-qual) va reposer le problème, on a le warning cast from 'const T *' to 'T *' drops const qualifier.

Édité par superlama

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte