Salut tout le monde !

Il y'a quelques mois de celà, j'ai ouvert un sujet sur la Suppression d'un élément dans une liste chaînée(lien ici: https://openclassrooms.com/forum/sujet/suppression-dun-element-dans-une-liste-chainee) et j'avais reçu divers feedbacks concernant mon code.

Si vous avez suivi le lien, vous verez qu'ils n'y sont pas allés de main morte. Les nombreuses critiques m'ont cependant permis de m'améliorer, car comme le dit le dicton <<C'est en forgeant qu'on devient forgeron>>.

Certains m'avaient proposés d'utiliser l'encapsulation, terme que je n'avais encore jamais entendu. Néanmoins, un tour dans le C++ m'a permis de comprendre que l'encapsulation est une charactéristique propre aux langages orientés objet, ce qui n'est pas le cas du langage C. Je reconnais qu'utiliser des classes pour créer une liste chaînée serait beaucoup plus pratique, cependant j'aimerais quand même d'abord le réussir en C avec de simples structures (Je dois être têtu, c'est pour ça ). Ce qui me ramène au sujet de ce post.

Mon but ici est de créer une liste SIMPLEMENT chaînée et bien sûr des fonctions permettant de gérer celle-ci. Les dites fonctions auront pour rôles de:

• créer et initialiser une liste (create_list)
• créer un nœud pour la liste (create_node)
• ajouter un élément au début de la liste (add_first)
• ajouter un élément au milieu de la liste (insert_in_list)
• supprimer un élément au début de la liste (delete_first)
• supprimer un élément au milieu de la liste (delete_in_list)
• détruire une liste (delete_list)
• afficher le contenu de la liste (display_list)
• aficher la taille de la liste (display_len)

Maintenant que tout est dit, j'aimerais avoir vos avis sur mon code (surtout l'aspect critique).

#Le fichier .h

#ifndef FUNCTIONS_H_INCLUDED
#define FUNCTIONS_H_INCLUDED

    typedef struct Node Node;
    struct Node
    {
        int number;
        Node *next;
    };

    typedef struct List List;
    struct List
    {
        int length;
        Node *first;
    };

    List *create_list();

    void add_first(List *list, int newNumber);
    void insert_in_list(List *list, int newNumber, int index);

    void delete_first(List *list);
    void delete_in_list(List *list, int index);
    void delete_list(List *list);

    void display_list(List *list);
    void display_len(List *list);

#endif // FUNCTIONS_H_INCLUDED

#Le fichier .c

#include <stdio.h>
#include <stdlib.h>

#include "functions.h"


static Node *create_node(int number)
{
    Node *node = malloc(sizeof(*node));

    if(node == NULL)
    {
        puts("Unable to create the node due to memory allocation failure");
        exit(EXIT_FAILURE);
    }

    node->number = number;
    node->next = NULL;

    return node;
}


List *create_list()
{
    List *list = malloc(sizeof(*list));

    if(list == NULL)
    {
        puts("Failed to allocate the memory for the creation of the list");
        exit(EXIT_FAILURE);
    }

    list->first = NULL;
    list->length = 0; // Initialize the length of the list

    return list;
}



/* Functions to add nodes in the list */

void add_first(List *list, int newNumber)
{
    if(list == NULL)
    {
        puts("The passed list does not exist");
        exit(EXIT_FAILURE);
    }

    // Create the new node
    Node *newNode = create_node(newNumber);
    newNode->number = newNumber;

    // Insert the node at the beginning of the list
    newNode->next = list->first;
    list->first = newNode;

    list->length++; // Increment the length
}


void insert_in_list(List *list, int newNumber, int index)
{
    if(list == NULL)
    {
        puts("The passed list does not exist");
        exit(EXIT_FAILURE);
    }

    // Verify that the passed index is not out of range
    if(!(index < list->length))
    {
        printf("Error: list index %d is out of bounds, unable to insert the node\n", index);
        exit(EXIT_FAILURE);
    }

    if(index == 0)
    {
        add_first(list, newNumber);
    }
    else
    {
        Node *newNode = create_node(newNumber);
        Node *previousNode = list->first;

        while(index > 1)
        {
            previousNode = previousNode->next;
            index--;
        }

        newNode->number = newNumber;

        // Insert the node at the passed index
        newNode->next = previousNode->next;
        previousNode->next = newNode;

        list->length++; // Increment the length
    }
}



/* Functions to delete nodes from the list */

void delete_first(List *list)
{
    if(list == NULL)
    {
        puts("The passed list does not exist");
        exit(EXIT_FAILURE);
    }

    if(list->first != NULL) //Verify that the list is not empty
    {
        Node *toDelete = list->first;
        list->first = list->first->next; // Same as list->first = toDelete->next
        free(toDelete);

        list->length--; // Decrement the length
    }
    else
    {
        puts("WARNING: Cannot delete a node from an empty list");
    }
}


void delete_in_list(List *list, int index)
{
    if(list == NULL)
    {
        puts("The passed list does not exist");
        exit(EXIT_FAILURE);
    }

    // Verify that the passed index is not out of range
    if(!(index < list->length))
    {
        printf("Error: list index %d is out of bounds, cannot delete a non-existent node\n", index);
        exit(EXIT_FAILURE);
    }

    if(index == 0)
    {
        delete_first(list);
    }
    else
    {
        Node *previousNode = list->first;

        while(index > 1)
        {
            previousNode = previousNode->next;
            index--;
        }

        Node *toDelete = previousNode->next;
        previousNode->next = previousNode->next->next; // Same as previousNode->next = toDelete->next
        free(toDelete);

        list->length--; // Decrement the length
    }
}


void delete_list(List *list)
{
    if(list == NULL)
    {
        puts("The passed list does not exist");
        exit(EXIT_FAILURE);
    }

    while(list->first != NULL)
    {
        delete_first(list);
    }
}



/* Functions to display the list and the length of the list */

void display_list(List *list)
{
    if(list == NULL)
    {
        puts("The passed list does not exist");
        exit(EXIT_FAILURE);
    }

    Node *currentNode = list->first;

    while(currentNode != NULL)
    {
        printf("%d -> ", currentNode->number);
        currentNode = currentNode->next;
    }
    puts("NULL");
}


void display_len(List *list)
{
    if(list == NULL)
    {
        puts("The passed list does not exist");
        exit(EXIT_FAILURE);
    }

    printf("Length of the list : %d node(s)\n", list->length);
}

#Le fichier main

#include <stdio.h>
#include <stdlib.h>

#include "functions.h"

int main(int argc, char *argv[])
{
    List *myList = create_list();

    /* Adding nodes */
    add_first(myList, 4);
    add_first(myList, 8);
    add_first(myList, 15);
    insert_in_list(myList, 12, 0);
    display_list(myList);

    /* Deleting nodes */
    delete_in_list(myList, 2);
    delete_first(myList);
    display_list(myList);

    display_len(myList);

    delete_list(myList);

    return EXIT_SUCCESS;
}

# output

-
Edité par ChristianAlbertLamy 16 juin 2022 à 23:28:54

Il est possible de faire de l'encapsulation en C, il suffit d'utiliser un type abstrait. En gros on déclare juste la struct sans la définir dans le header et on est sûr que l'utilisateur ne pourra pas accéder aux entrailles de la struct. C'est un peu comme si on avait mis des trucs en "privé" dans d'autres langages.

Par contre ça a un inconvénient c'est qu'on est obligé de manipuler le type uniquement à travers des pointeurs, puisque l'utilisateur ne verrait pas la définition. Ça ne pose pas de problème pour les fonctions qui manipulent la liste, mais ça oblige à faire une allocation dynamique (qui peut foirer, comme tu fais bien de vérifier) pour créer la liste, alors qu'on pourrait typiquement s'en passer en renvoyant directement une "List" et pas un pointeur. C'est le cas ici puisque la définition est dans le header.

Et sinon que fait la fonction "create_list" à part ça ? Elle met simplement les champs à 0... Sans aller jusqu'à dire qu'il faut virer cette fonction qui ne sert à rien, on pourrait directement créer la liste l'initialisant à 0 :

List myList = {0}; // Inititialise la liste à 0
 
add_first(&myList, 4);
add_first(&myList, 8);
add_first(&myList, 15);
insert_in_list(&myList, 12, 0);
display_list(&myList);

Mais bon c'est pas plus mal d'avoir une fonction qui initialise, peut être que plus tard il y aura d'autres champs qui devront être initialisés autrement qu'avec 0.

Donc là c'est comme si tu avais les inconvénients des 2 méthodes. En gros là tu peux mettre la définition dans le .c pour que l'utilisateur ne la voit pas, ou alors profiter du fait que l'utilisateur la voit et renvoyer une "List" dans "create_list" pour éviter l'allocation dynamique de la liste.

Aussi, qu'est-ce que tu fais quand on passe un pointeur de liste qui est NULL ? Tu fais quelque chose de très bien, c'est de planter misérablement. Eh oui, il n'y a pas grand chose qu'on puisse faire si l'utilisateur de la liste fait n'importe quoi. Est ce qu'il est censé faire n'importe quoi ? Non, il est de sa responsabilité de s'assurer de passer un pointeur valide. On peut donc littéralement enlever cette vérification, auquel cas le comportement sera déjà de planter misérablement, au premier déréférencement. Mais ce n'est pas plus mal de rendre cette précondition "explicite", mais non pas en faisant une vérification avec un if, mais avec un assert :

void display_len(List *list)
{
    assert(list && "The passed list does not exist");
 
    printf("Length of the list : %d node(s)\n", list->length);
}

Si l'utilisateur passe une liste NULL, l'assert va lui péter à la gueule, et il pourra corriger son code. D'ailleurs c'est pas forcément nécessaire de mettre un message puisque si l'assert se déclenche, on se doute bien que c'est parce qu'on a passé une liste qui n'existe pas. 

J'ai écris une bêtise.

-
Edité par edgarjacobs 17 juin 2022 à 0:23:12

LucieNottin1 a écrit:
add_first(&myList, 4);
C'est justement le genre de choses qui m'agacent que de passer l'adresse avec le & ...

Justement en C++, c'est dans la définition de la fonction qu'on décide si on passe par valeur ou par référence.
J'aime bien le create_list.
@ChristianAlbertLamy:
Je n'ai pas remarqué d'erreur grossière dans ton code.

Tu n'as pas inclus create_node dans ton header.
La première qualité d'un code est qu'il fonctionne. Et j'ai l'intuition que c'est le cas pour le tien.

edit: pas tout à fait ... avec insert_in_list, tu ne peux pas insérer à la fin. Tu peux le faire si tu permets que index soit égal à length.

Petite remarque bénigne.
Là où tu vérifies l'index, s'il y a erreur, affiches la valeur attendue en plus de la valeur de l'index.
Quand on joue beaucoup avec une liste, il arrive qu'on ne sache plus la longueur.
Pour détruire toute la liste, tu pourrais faire plus efficace que de détruire toujours le premier en boucle.

-
Edité par PierrotLeFou 17 juin 2022 à 6:51:56

PierrotLeFou a écrit:

Tu n'as pas inclus create_node dans ton header.

 C'est une fonction static seulement accessible dans fichier.c 

LucieNottin1 a écrit:

Et sinon que fait la fonction "create_list" à part ça ? Elle met simplement les champs à 0... Sans aller jusqu'à dire qu'il faut virer cette fonction qui ne sert à rien, on pourrait directement créer la liste l'initialisant à 0 :

Si tu as suivi le lien que j'ai posté au début, tu verras que justement @Whitecrow avait souligné le fait que ce genre d'initialisation ne permettait pas d'obtenir une liste vide si on le souhaitait. Je n'ais pas d'exemple sous la main mais tu conviendras avec moi qu'avoir une liste initialement vide peut parfois s'avérer utile.

LucieNottin1 a écrit:

Mais ce n'est pas plus mal de rendre cette précondition "explicite", mais non pas en faisant une vérification avec un if, mais avec un assert :

Je n'avais encore jamais entendu parlé du macro assert mais après quelque recherches, je comprends à présent son utilité. Cependant j'ai une question (même si elle peut sembler un peu bête) : Etant donné que l'assert interrompt le programme si la condition est fausse, cela ne revient-il pas au même? La principale différence étant bien sûr le message renvoyé. J'ai encore quelques doutes (surtout corrige moi si je me trompe).

PierrotLeFou a écrit:

Tu n'as pas inclus create_node dans ton header.

 Justement à ce propos, j'aimerais savoir: est-ce judicieux d'inclure une fonction statique dans le header ? Il semblerait d'ailleurs que @rouloude soit du même avis.

PierrotLeFou a écrit:

Petite remarque bénigne.
Là où tu vérifies l'index, s'il y a erreur, affiches la valeur attendue en plus de la valeur de l'index.
Quand on joue beaucoup avec une liste, il arrive qu'on ne sache plus la longueur.

Pas faux, merci du conseil.

PierrotLeFou a écrit:

Pour détruire toute la liste, tu pourrais faire plus efficace que de détruire toujours le premier en boucle.

 Des suggestions ?

PierrotLeFou a écrit:

 Tu ne détruit pas le descripteur de liste. Ce n'est pas forcément une erreur. Je préfère personnellement le faire.

Je vais peut-être passer pour le dernier des idiots mais à vrai dire, je ne sais pas comment m'y prendre. J'ai essayé en mettant un free(list) dans delete_list, suivi d'un list = NULL, mais ça n'a pas marché. En effet, lorsque je le fait et que j'appelle la fonction display_list après le delete_list dans la fonction main, au lieu d'un <<The passed list does not exist>>, c'est une boucle infinie qui m'accueille . Ou devrais-je plutôt le faire directement dans le main ?

# Auto critique

On dirait que personne ne l'a remarqué mais j'ai fait une énorme bêtise dans les fonctions add_first et insert_in_list . En effet, aux lignes 54 et 94 du fichier source, je fais :

newNode->number = newNumber;

Or ayant déja appelé la fonction createNode, ces lignes deviennent absolument inutiles.

-
Edité par ChristianAlbertLamy 17 juin 2022 à 11:38:30

ChristianAlbertLamy a écrit:

 Justement à ce propos, j'aimerais savoir: est-ce judicieux d'inclure une fonction statique dans le header ? Il semblerait d'ailleurs que @rouloude soit du même avis.

 Non, d'ailleurs le compilateur n'apprécie pas.

Il y a deux type d'erreur à gérer :

Les erreurs que peut corriger le développeur qui utilise ta liste, comme par exemple insérer un élément si la liste n'est pas initialisée. Elles devront être signalé au développeur.

et il y a celle qu'on ne peut pas prévoir comme l’échec d'un malloc, qui devront être gérer par le programme. 

ChristianAlbertLamy a écrit:

LucieNottin1 a écrit:

Et sinon que fait la fonction "create_list" à part ça ? Elle met simplement les champs à 0... Sans aller jusqu'à dire qu'il faut virer cette fonction qui ne sert à rien, on pourrait directement créer la liste l'initialisant à 0 :

Si tu as suivi le lien que j'ai posté au début, tu verras que justement @Whitecrow avait souligné le fait que ce genre d'initialisation ne permettait pas d'obtenir une liste vide si on le souhaitait. 

Je ne comprends pas ce que cette phrase veut dire. Pour avoir une liste vide il suffit de ne pas créer un élément lors de l'initialisation, c'est ce que tu fais dans la fonction "create_list", et qu'on pourrait faire tout aussi bien en créant une liste sur la pile et initialisée à 0 :

int main() {
    List list = {0};

    // ...    

    return 0;
}

Ou alors en gardant la fonction d'initialisation mais en ne faisant pas d'allocation dynamique :

List create_list()
{
    List list = {
        .first = NULL,
        .length = 0,
    };

    return list;
}

int main(void) {
    List list = create_list();

    // ...

    return 0;
}

Ce qui revient à initialiser la liste à "0", qu'on peut donc écrire plus succinctement :

List create_list() {
    return (List){0};
}

D'où le fait que je disais que cette fonction ne "sert à rien", puisqu'on peut initialiser la liste à 0 nous même côté utilisateur. Comme je l'ai dit plus haut, c'est à toi de voir si tu veux utiliser un type "abstrait" (dit aussi "opaque"), auquel cas tu peux mettre la définition de la liste dans le .c et l'enlever du .h, donc l'utilisateur ne saura pas à quoi ressemblent les entrailles de la liste et devra passer par des pointeurs, ou alors tu laisse la définition visible dans le header, et dans ce cas tu peux te passer de l'allocation dynamique dans create_list.

Et comme le dit PierrotLeFou, tu ne libère jamais la mémoire utilisée par la liste (la liste elle même, pas son contenu), chose qu'on aurait pas à faire si la liste était stockée côté utilisateur

ChristianAlbertLamy a écrit:

Je n'avais encore jamais entendu parlé du macro assert mais après quelque recherches, je comprends à présent son utilité. Cependant j'ai une question (même si elle peut sembler un peu bête) : Etant donné que l'assert interrompt le programme si la condition est fausse, cela ne revient-il pas au même? La principale différence étant bien sûr le message renvoyé. J'ai encore quelques doutes (surtout corrige moi si je me trompe).

Oui ça revient complètement au même, la différence est plutôt "conceptuelle", l'idée de l'assert c'est de vérifier les erreurs qui ne sont pas censées se produire, autrement dit les erreurs de programmation. Si le programmeur est censé passer une liste existante, il est de sa responsabilité de s'en assurer, et donc le code de la liste peut simplement "assert" que la liste existe et sinon ça fait tout planter. Par contre ce n'est pas le cas de d'autres types d'erreur, par exemple une erreur d'allocation en cas de manque de mémoire. Là c'est une vraie erreur qui peut complètement se produire, même si tout est codé parfaitement, il faut donc le vérifier "explicitement", et idéalement ne pas planter misérablement (par exemple si on veut charger une image mais qu'on a plus de mémoire, on peut la remplacer temporairement par un carré plutôt que de faire planter tout le jeu)

ChristianAlbertLamy a écrit:

 Justement à ce propos, j'aimerais savoir: est-ce judicieux d'inclure une fonction statique dans le header ? Il semblerait d'ailleurs que @rouloude soit du même avis.

Ce qu'il faut mettre dans le header, c'est l'interface publique, c'est ce qu'on veut que l'utilisateur puisse voir, en gros ce qui est "public". Est ce que l'utilisateur a besoin de savoir qu'une liste est composée de noeuds pour pouvoir la manipuler ? Alors en théorie non puisque comme je l'ai dit, si on utilise que des pointeurs, l'utilisateur n'a pas besoin de connaitre la définition de la struct, mais en plus dans ce cas présent, aucune des fonctions qui manipulent la liste ne parlent de "Node", c'est donc un concept qui n'a pas besoin d'être connu par l'utilisateur. Du coup il n'a pas besoin non plus de connaitre la fonction "create_node", donc ça a du sens de la mettre dans le .c, et éventuellement en static pour indiquer qu'elle n'est pas censée être utilisée à l'extérieur du fichier .c

ChristianAlbertLamy a écrit:

Je vais peut-être passer pour le dernier des idiots mais à vrai dire, je ne sais pas comment m'y prendre. J'ai essayé en mettant un free(list) dans delete_list, suivi d'un list = NULL, mais ça n'a pas marché. En effet, lorsque je le fait et que j'appelle la fonction display_list après le delete_list dans la fonction main, au lieu d'un <<The passed list does not exist>>, c'est une boucle infinie qui m'accueille . Ou devrais-je plutôt le faire directement dans le main ?

-
Edité par LucieNottin1 17 juin 2022 à 12:23:00

Il y a une autre différence entre un assert() et un code en dur qui teste une condition et termine le programme si la condition est fausse.

Les assertions évaluées dans la macro assert() le sont tant que l'include de assert.h n'est pas précédé de la définition de la macro NDEBUG. Tout compilateur C standard doit respecter cela depuis C89.

Du coup, je peux effectivement utiliser assert() pour tester mon programme ou vérifier de façon générale que certaines conditions à l'exécution sont vérifiées, tant que je suis en cours de développement, et une fois que le programme est testé et peut aller en production, je peux le compiler en définissant la macro NDEBUG pour retirer les assertions du code compilé, optimiser le code, etc.

Cela montre bien l'esprit dans lequel assert() a été inséré dans la bibliothèque standard. C'est plus approprié de l'utiliser pour vérifier l'absence d'erreurs de programmation mettant le programme dans un état "impossible" ou non prévu et donc dans les phases de mise au point ou de maintenance du programme; plutôt que pour vérifier si une allocation mémoire a réussit, laquelle, comme le dit LucieNottin1, est une situation dépendant de la quantité de mémoire disponible susceptible éventuellement d'un traitement en mettant en oeuvre une stratégie de secours.

Certains sont partisans de conserver les assert() dans le code en production. La question fait débat :-)

Dans une discussion récente, on a aussi évoqué la possibilité d'utiliser assert() pour l'écriture de tests unitaires avec cet outil simplifié disponible en standard. C'est un autre type d'utilisation de assert() sur du code en amont du code en production.

LucieNottin1 a écrit:

Ce qu'il faut mettre dans le header, c'est l'interface publique, c'est ce qu'on veut que l'utilisateur puisse voir, en gros ce qui est "public". Est ce que l'utilisateur a besoin de savoir qu'une liste est composée de noeuds pour pouvoir la manipuler ? Alors en théorie non puisque comme je l'ai dit, si on utilise que des pointeurs, l'utilisateur n'a pas besoin de connaitre la définition de la struct, mais en plus dans ce cas présent, aucune des fonctions qui manipulent la liste ne parlent de "Node", c'est donc un concept qui n'a pas besoin d'être connu par l'utilisateur. (...)

Dans d'autres langages des années 70-80 (Ada,...), on va séparer clairement (dans des fichiers sources différents), ce qui est interface de programmation du type (la liste des fonctionnalités qu'il fournit) et ce qui est son implémentation (le code qui le fait).

Bon, en C (et en C++), les headers ce n'est pas fait pour définir des types opaques. Si on définit un type pour une liste doublement chainée, par exemple, on met

typedef struct list {
   int size;
   struct cell *first, *last;
} list_t;
   

dans une entête que l'on fait inclure là où on en a besoin, et du coup tout le monde à accès aux 3 champs qui normalement personne n'a besoin de voir, côté utilisation du type. 

Le langage C ne possède pas les mécanismes qui permettent de cacher les informations non nécessaires. On fait avec cette réalité en

• considérant que ce n'est pas très grave
• se reposant sur la discipline du programmeur pour faire ce qui est écrit dans la doc (quand on distribue son code), qui est du genre : ne touchez pas directement ces trucs, ça peut changer dans une prochaine version, et passez pas les fonctions x y et z)

struct list;

typedef struct list *p_list_t;

mais ça veut dire que le "code client" qui utilise le type ne manipule que des pointeurs. (*)  C'est pas forcément un gain, vu qu'en général si on programme en C, c'est pour accéder plus directement aux ressources, et que là on s'oblige à avoir des données allouéess dynamiquement, les manipuler en s'ajoutant des indirections.

(*) C'est un peu ce qu'on fait quand on apprend à manipuler les fichiers par des FILE*.  On sait pas ce qu'il y a dans un FILE, sauf qu'on sait que ça existe et que ça fait ce qu'on lui demande.

-
Edité par michelbillaud 17 juin 2022 à 14:42:48

ChristianAlbertLamy a écrit:

LucieNottin1 a écrit:

Et sinon que fait la fonction "create_list" à part ça ? Elle met simplement les champs à 0... Sans aller jusqu'à dire qu'il faut virer cette fonction qui ne sert à rien, on pourrait directement créer la liste l'initialisant à 0 :

Si tu as suivi le lien que j'ai posté au début, tu verras que justement @Whitecrow avait souligné le fait que ce genre d'initialisation ne permettait pas d'obtenir une liste vide si on le souhaitait. Je n'ais pas d'exemple sous la main mais tu conviendras avec moi qu'avoir une liste initialement vide peut parfois s'avérer utile.

[...]-

Edité par ChristianAlbertLamy il y a environ 3 heures

Attention, ce que je disais dans le message est que si tu n'as qu'un constructeur qui prend en paramètre une valeur de la liste, alors tu ne peux pas créer une liste vide … C'est un problème de design d'API.

michelbillaud a écrit:

LucieNottin1 a écrit:

Ce qu'il faut mettre dans le header, c'est l'interface publique, c'est ce qu'on veut que l'utilisateur puisse voir, en gros ce qui est "public". Est ce que l'utilisateur a besoin de savoir qu'une liste est composée de noeuds pour pouvoir la manipuler ? Alors en théorie non puisque comme je l'ai dit, si on utilise que des pointeurs, l'utilisateur n'a pas besoin de connaitre la définition de la struct, mais en plus dans ce cas présent, aucune des fonctions qui manipulent la liste ne parlent de "Node", c'est donc un concept qui n'a pas besoin d'être connu par l'utilisateur. (...)

Dans d'autres langages des années 70-80 (Ada,...), on va séparer clairement (dans des fichiers sources différents), ce qui est interface de programmation du type (la liste des fonctionnalités qu'il fournit) et ce qui est son implémentation (le code qui le fait).

Bon, en C (et en C++), les headers ce n'est pas fait pour définir des types opaques.[...]
-

Edité par michelbillaud il y a 22 minutes

Si si, il y a plusieurs idiomes pour cela.

Par exemple, on sépare la partie publique qui définit l'interface accessible par tous et la partie privée accessible uniquement à ceux qui en ont besoin, principalement les sources qui implémentent l'interface.

On peut également simplement utiliser un void * comme type, ce qui n'est pas  forcément recommandé … ou on peut également utiliser un simple handle de type scalaire ; tout n'est pas forcément pointeur en C

Mais on peut aussi utiliser l'idiome PIMPL (pointer to implementation) que je citais dans le message donné en référence au-dessus.

On peut également faire confiance à l'utilisateur de ne pas foutre le bordel si on laisse accès aux détails d'implémentation.

Cacher les détails d'implémentations a l'immense avantage de ne pas injecter trop de dépendances. Si on est simplement dépendant d'une interface publique, rien ne change à l'utilisation tant que l'interface ne change pas (et encore). On peut imaginer utiliser une liste d'entiers, et pouvoir choisir au runtime l'implémentation à utiliser que ce soit le sacro-saint classique «je mets des pointeurs partout» à j'utilise un simple tableau, ou un BTree ou …
Un exemple intéressant est le module list de la GNULIB (une bibliothèque de sources).

Mais mis à part tout cela, l'important est de comprendre que dans ce cas précis, on implémente une sda (structure de donnée abstraite) qui a une interface publique connue, et des comportements attendus connus. Indépendamment de l'implémentation, on sait que :

• une liste nouvellement créée doit être vide ;
• une liste vide a une longueur nulle ;
• ajouter une valeur à la liste augmente sa longueur de 1 ;
• supprimer une valeur de la liste diminue sa longueur de 1 ;
• si on supprime un élément d'une liste de longueur 1 alors le résultat doit être la liste vide ;
• si on ajoute une valeur en tête alors si on demande la valeur de la tête elle doit être celle qu'on vient d'ajouter ;
• …

Tous ces comportements sont testables. Si on a une interface publique on peut directement implémenter les tests.

Tout à fait. Dans l'exemple que tu donnes

void delete_list(List *list) {
    Node *current = list->first;
    ...
}

tester si list est NULL, ça relèverait de la programmation défensive contre les erreurs du programmeur qui emploie delete_list() n'importe comment - par opposition aux cas qui se posent légitimement dans le déroulement normal du programme.

(Tout ça par faute d'analyse statique vérifiant que par construction, la valeur reçue n'est pas NULL. Billion dollar mistake).

Dans un programme en test, si on écrit au début

if (list == NULL) {
    printf("....");
    exit(1);
}

ok, on va détecter et signaler que le programmeur a fait un truc chelou. Mais ça se limite à ça, ça n'apporte pas un comportement correct en production, parce qu'on ne déclenche pas d'actions correctives.  Ca ne fait pas mieux le boulot, tout en pénalisant systématiquement le code qui marche très bien quand il est employé correctement, par l'immense majorité (*) de ceux qui l'utilisent.

La moins pire des solutions est de compiler conditionnellement ce test

void delete_list(List *list) {

#ifdef CHECK_GOOD_USE_OF_LIST_API
    if (list == NULL) {
        // badaboum
    }
#endif
    Node *current = list->first;
    ...
}

(*) j'te jure, crois-moi frère

-
Edité par michelbillaud 17 juin 2022 à 18:13:50

Pas contre la génération conditionnelle. Je l'ai déjà fait.

LucieNottin1 a écrit:

Pour avoir une liste vide il suffit de ne pas créer un élément lors de l'initialisation, c'est ce que tu fais dans la fonction "create_list", et qu'on pourrait faire tout aussi bien en créant une liste sur la pile et initialisée à 0 : [...] Ou alors en gardant la fonction d'initialisation mais en ne faisant pas d'allocation dynamique [...]

Désolé, j'avais mal compris le contexte. En effet, cette méthode me permet d'éviter l'allocation dynamique. Seulement, je serais obligé de faire des trucs du genre:

add_first(&myList, 4);

Mais bon, l'essentiel est que ça fonctionne correctement.

#Problème avec l'assert

Je ne sais pas pourquoi mais quand je remplace le 

if(list == NULL)
{
   puts("The passed list does not exist");
   exit(EXIT_FAILURE);
}

par

assert(list != NULL)

le message d'erreur s'affiche mais ensuite le programme plante. Je n'arrive pas à comprendre quel est le problème.

# Petite question toute bête

Si dans ma fonction main je fais :

int main(int argc, char *argv[])
{
    List *myList = create_list();
 
    /* Adding nodes */
    add_first(myList, 4);
    add_first(myList, 8);
    add_first(myList, 15);
    insert_in_list(myList, 12, 10);
    display_list(myList);
 
    delete_list(myList);
 
    return EXIT_SUCCESS;
}

A la ligne numéro 9, le programme sera interrompu et un message d'erreur s'affichera. Seulement ayant déja alloué de la mémoire pour les trois premières nodes, le fait que je ne détruise pas la liste en cas d'erreur ne cause t-il pas une fuite de mémoire ?

Si insert_in_list déclenche un exit() - c'était dans ton code plus haut - le programme s'arrête et le problème de fuite mémoire ne tire absolument pas à conséquence, puisque toute la mémoire du programme est restituée au système d'exploitation : il n'en utilisera jamais plus, repose en paix petit processus décédé trop tôt.

# Petit problème

J'ai remarqué que mes fonctions insert_in_list et delete_in_list devenaient bancales si l'on passe un index négatif. Du coup j'aimerais savoir la quelle des solutions suivante serait la plus appropriée.

• Utiliser la fonction abs() de stdlib pour m'assurer que la variable index soit toujours positive.
• Vérifier la valeur de la variable index à l'aide d'un if et interrompre le programme en affichant un message si celle-ci est négative.

ChristianAlbertLamy a écrit:

# Petit problème

J'ai remarqué que mes fonctions insert_in_list et delete_in_list devenaient bancales si l'on passe un index négatif. Du coup j'aimerais savoir la quelle des solutions suivante serait la plus appropriée.

• Utiliser la fonction abs() de stdlib pour m'assurer que la variable index soit toujours positive.
• Vérifier la valeur de la variable index à l'aide d'un if et interrompre le programme en affichant un message si celle-ci est négative.

La première solution est mauvaise … La seconde un peu meilleure …

L'idéal est d'interdire le passage d'un argument scalaire négatif, soit d'utiliser un type non signé. Le type size_t est idéal dans ce cas. Si par inattention tu passes un argument scalaire négatif, tu auras un avertissement lors de la compilation.

Si tu tiens absolument à utiliser des entiers signés alors tu devrais utiliser un assert qui pendant la phase de test déclenchera une erreur.

Passer un argument négatif n'est pas une erreur à détecter  au runtime mais avant car c'est signe d'une mauvaise utilisation.

Remarque que le type liste n'est pas le plus approprié pour un accès par indice. Le type plus appropriés pour posséder ce genre d'API est un vecteur/array.

Solution : Ne pas les appeler avec un index négatif ! C'est au codeur qui se sert de la liste d'y prêter attention !

Remarque, tu peux également décider que par design un index négatif indique une position à partir de la fin … l'indice -1 est le dernier élément de la liste, -2 celui qui le précède, etc …

Mais il faut décider ça avant de commencer à coder.

On peut aussi prévoir une fonction avec index positif à partir de la fin.

int list_get_at         (list_t *list, unsigned index);    // normal
int list_get_at_from_end(list_t *list, unsigned index);    // depuis la fin

Je suspecte que le code qui utiliserait une seule fonction avec des index positifs dans un sens et négatifs dans l'autre se retrouverait en fait truffé par ailleurs de tests pour regarder le signe. A vérifier sur un corpus de programmes python, où les indices des listes font ça. Ça sent l' astuce"  bien intentionnée qui va vite mal tourner en pratique, cette idée.

En tout ca, il faut DECIDER avant de programmer comment la fonction doit se comporter quand les paramètres sont invalides. Il y a le choix

• ne rien faire
• afficher un message d'erreur
• afficher un message d'erreur et planter le programme
• planter le programme
• lever une exception (ah mince y en a pas en C)
• avoir un comportement indéfini.

-
Edité par michelbillaud 18 juin 2022 à 17:12:07

J'ai suggéré une fonction qui retourne la longueur de la liste.

Disons qu'elle s'appelle list_length()

Je peux faire:

    insert_in_list(list, 42, list_length(list) - 3);  // Insérer avant le troisième à partir de la fin.

     delete_in_list(list, list_length(list) - 1);   // supprimer le dernier
Pourquoi ce serait toujours au programme à tenir compte des conneries de l'utilisateur?Le code serait d'autant simplifié.
De plus, si index == length pour l'insertion, on peut insérer à la fin.
Mais si c'est pour supprimer, index ne peut pas être égal à length.
(Si les positions sont numérotées à partir de 0)

-
Edité par PierrotLeFou 18 juin 2022 à 18:33:37

White Crow a écrit:

[...] L'idéal est d'interdire le passage d'un argument scalaire négatif, soit d'utiliser un type non signé. Le type size_t est idéal dans ce cas. Si par inattention tu passes un argument scalaire négatif, tu auras un avertissement lors de la compilation. [...]

En effet, le type size_t semble être idéal. Seulement, ma version de gcc ne supportant pas le %zu, j'ai donc opté pour un unsigned. Cependant cette méthode me renverra un out of bounds suivi d'un plantage du programme en cas mauvaise utilisation. Ce qui m'amène à penser que le mieux serait d'afficher un message d'erreur (ou plutôt un warning) et ensuite ne rien faire. Cela en utilisant bien sûr un type signé.

#Illustration

void insert_in_list(List *list, int newNumber, int index)
{
    if(list == NULL)
    {
        puts("The passed list does not exist");
        exit(EXIT_FAILURE);
    }

    // Verify that the passed index is not out of range
    if(!(index < list->length))
    {
        printf("Error: list index %d is out of bounds, unable to insert the node\n", index);
        exit(EXIT_FAILURE);
    }

    if(!(index < 0)) // We verify that the passed index is not negative
    {
        if(index == 0)
        {
            add_first(list, newNumber);
        }
        else
        {
            Node *newNode = create_node(newNumber);
            Node *previousNode = list->first;

            while(index > 1)
            {
                previousNode = previousNode->next;
                index--;
            }

            // Insert the node at the passed index
            newNode->next = previousNode->next;
            previousNode->next = newNode;

            list->length++; // Increment the length
        }
    }
    else
    {
        puts("WARNING: Cannot insert a node at a negative index");
    }
}

Quels sont vos avis ? 

Quant à ce qui concerne les index négatifs, on entre déjà dans les listes doublement chainées et j'en suis encore à résoudre les problèmes de ma liste simplement chainée.

PS: Dans le cas d'une liste doublement chainée, je crois que la méthode proposée par @michelbillaud me conviendrait mieux.

rouIoude a écrit:

Solution : Ne pas les appeler avec un index négatif ! C'est au codeur qui se sert de la liste d'y prêter attention !

Je suis d'accord avec toi, mais il y en a toujours qui iront faire le contraire de ce qu'on leur demande et c'est ce que je cherche à éviter.

PierrotLeFou a écrit:

J'ai suggéré une fonction qui retourne la longueur de la liste.

Disons qu'elle s'appelle list_length()

Je peux faire:

    insert_in_list(list, 42, list_length(list) - 3);  // Insérer avant le troisième à partir de la fin.

     delete_in_list(list, list_length(list) - 1);   // supprimer le dernier
Pourquoi ce serait toujours au programme à tenir compte des conneries de l'utilisateur? Le code serait d'autant simplifié.
De plus, si index == length pour l'insertion, on peut insérer à la fin.
Mais si c'est pour supprimer, index ne peut pas être égal à length.
(Si les positions sont numérotées à partir de 0)

 insert_in_list(list, 42, list_length(list) - 3); 

-
Edité par ChristianAlbertLamy 18 juin 2022 à 19:36:29

rouIoude a écrit:

Solution : Ne pas les appeler avec un index négatif ! C'est au codeur qui se sert de la liste d'y prêter attention !

Je suis d'accord avec toi, mais il y en a toujours qui iront faire le contraire de ce qu'on leur demande et c'est ce que je cherche à éviter.

Si on regarde la libc, ne lui passe JAMAIS de mauvais paramètres. Soit tu auras un ub, soit ton programme plantera. Je suis de l'avis de michelbillaud: une lib n'a pas à prévoir les conneries de celui qui l'emploie.

ChristianAlbertLamy a écrit:

il y en a toujours qui iront faire le contraire de ce qu'on leur demande et c'est ce que je cherche à éviter.

Il y a certes des gens qui font n'importe quoi, mais aucune mesure technique ne permet de l'éviter vraiment.

Et comme ça arrive souvent (même à des gens bien de temps en temps), la solution n'est pas de mettre en place des mesures qui peuvent s'avérer bancales.

PS: pour un index dans une liste chainée, un unsigned int doit largement suffire concrètement.  Parce qu'accéder par indexation dans une liste chainée de plus de 4 M élements, ça me parait mal parti comme affaire.

(size_t : entiers suffisants pour représenter la taille d'un objet - nombre d'octets - en mémoire)

-
Edité par michelbillaud 18 juin 2022 à 20:51:18

ChristianAlbertLamy a écrit:

En effet, le type size_t semble être idéal. Seulement, ma version de gcc ne supportant pas le %zu, 

Si tu es sous MinGW Pour le %zu mets :

#define __USE_MINGW_ANSI_STDIO 1

avant les includes.

edit : Corrigé après la remarque de @rouloude

# Aller plus loin

Salut tout le monde !

Pour corser un peu les choses, j'ai décidé de créer quelques fonctions supplémentaires (en m'inspirant du langage python) pour:

• Ajouter un élément à la fin de la liste (list_append)
• Supprimer un élément à la fin de la liste (list_delete_last)
• Ajouter les éléments d'une liste à la suite d'une autre (list_extend)
• Supprimer le premier élément avec la valeur spécifiée (list_remove)
• Compter le nombre d'éléments avec la valeur spécifiée (list_count)
• Classer les éléments d'une liste par ordre croissant (list_sort)
• Inverser l'ordre d'une liste (list_reverse)
• Copier une liste (list_copy)
• Renvoyer l'indice du premier élément avec la valeur spécifiée (list_index)

Et encore une fois, j'aimerais avoir vos avis. J'ai modifié les noms de mes fonctions afin que l'on puisse avoir une vue claire de l'API. Du coup, voici ce à quoi ressemblent mes fichiers à présent :

NB: Pour éviter de reposter ce que j'avais déjà présenté plus haut, ceci inclut uniquement les nouvelles fonctions.

# Mon fichier .h

#ifndef LINKED_LIST_H_INCLUDED
#define LINKED_LIST_H_INCLUDED

    typedef struct Node Node;
    struct Node
    {
        int number;
        Node *next;
    };

    typedef struct List List;
    struct List
    {
        int length;
        Node *first;
    };

    List *create_list();

    int list_isEmpty(const List *list); // new
    int is_in_list(const List *list, const int number); // new
    int list_length(const List *list); // new

    void list_prepend(List *list, int newNumber);
    void list_append(List *list, int newNumber); // new
    void list_insert(List *list, int newNumber, unsigned index);
    void list_extend(List *list, const List *listToMerge); // new

    void list_delete_first(List *list);
    void list_delete_last(List *list); // new
    void list_pop(List *list, unsigned index);
    void list_clear(List *list); // new
    void list_free(List *list);
    void list_remove(List *list, int number); // new

    void list_print(const List *list);

    int list_count(const List *list, int number); // new
    void list_sort(List *list); // new
    void list_reverse(List *list); // new
    void list_copy(List *list, const List *listToCopy); // new
    int list_index(const List *list, int number); // new

#endif // LINKED_LIST_H_INCLUDED

# Mon fichier .c

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
 
#include "linked_list.h"


static Node *create_node(int number)
{
    Node *node = malloc(sizeof(*node));

    if(node == NULL)
    {
        puts("Unable to create the node due to memory allocation failure");
        exit(EXIT_FAILURE);
    }

    node->number = number;
    node->next = NULL;

    return node;
}


List *create_list()
{
    List *list = malloc(sizeof(*list));

    if(list == NULL)
    {
        puts("Failed to allocate the memory for the creation of the list");
        exit(EXIT_FAILURE);
    }

    list->first = NULL;
    list->length = 0; // Initialize the length of the list

    return list;
}


 
/* Basic functions */
 
int list_isEmpty(const List *list)
{
    assert(list != NULL);
    return list->first == NULL;
}
 
 
int is_in_list(const List *list, const int number)
{
    if(list_isEmpty(list))
        return 0;
 
    Node *currentNode = list->first;
 
    while(currentNode != NULL)
    {
        if(currentNode->number == number)
            return 1;
 
        currentNode = currentNode->next;
    }
 
    return 0;
}
 
 
int list_length(const List *list)
{
    assert(list != NULL);
 
    int length = 0;
    Node *currentNode = list->first;
 
    while(currentNode != NULL)
    {
        length++;
        currentNode = currentNode->next;
    }
 
    return length;
}



/* Functions to add nodes in the list */

void list_prepend(List *list, int newNumber)
{
    assert(list != NULL);

    // Create the new node
    Node *newNode = create_node(newNumber);

    // Insert the node at the beginning of the list
    newNode->next = list->first;
    list->first = newNode;

    list->length++; // Increment the length
}


void list_append(List *list, int newNumber)
{
 
    if(list_isEmpty(list))
    {
        list_prepend(list, newNumber);
    }
    else
    {
        int lastIndex = list->length - 1; // As we start from index 0
        Node *lastNode = list->first;
 
        // Find the last node in the list
        while(lastIndex > 0)
        {
            lastNode = lastNode->next;
            lastIndex--;
        }
 
        // Create the new node
        Node *newNode = create_node(newNumber);
 
        // Insert the new node at the end of the list
        newNode->next = lastNode->next; // Better put NULL
        lastNode->next = newNode;
 
        list->length++; // Increment the length
    }
}


void list_insert(List *list, int newNumber, unsigned index)
{
    assert(list != NULL);

    // Verify that the passed index is not out of range
    if(!(index <= list->length))
    {
        printf("Error: Attempt to insert a node at index %u in list of size %d.\n", index, list->length);
        exit(EXIT_FAILURE);
    }

    if(index == 0)
    {
        list_prepend(list, newNumber);
    }
    else
    {
        Node *newNode = create_node(newNumber);
        Node *previousNode = list->first;

        while(index > 1)
        {
            previousNode = previousNode->next;
            index--;
        }

        // Insert the node at the passed index
        newNode->next = previousNode->next;
        previousNode->next = newNode;

        list->length++; // Increment the length
    }
}
 
 
void list_extend(List *list, const List *listToMerge)
{
    assert(list != NULL);
 
    // Add the elements of listToMerge to the end of list
    if(!list_isEmpty(listToMerge))
    {
        Node *currentNode = listToMerge->first;
 
        while(currentNode != NULL)
        {
            list_append(list, currentNode->number);
            currentNode = currentNode->next;
        }
    }
}
 
 
 
/* Functions to delete nodes from the list */

void list_delete_first(List *list)
{
    if(!list_isEmpty(list))
    {
        Node *toDelete = list->first;
        list->first = list->first->next; // Same as list->first = toDelete->next
        free(toDelete);

        list->length--; // Decrement the length
    }
    else
    {
        puts("WARNING: Cannot delete a node from an empty list... skipping");
    }
}


void list_delete_last(List *list)
{
    assert(list != NULL);
 
    if(list->length == 1)
    {
        list_delete_first(list);
    }
    else
    {
        if(!list_isEmpty(list))
        {
            int lastIndex = list->length - 1; // As we start from index 0
            Node *previousNode = list->first;
 
            // Find the second last node
            while(lastIndex > 1)
            {
                previousNode = previousNode->next;
                lastIndex--;
            }
 
            // Delete the last node
            Node *toDelete = previousNode->next;
            previousNode->next = previousNode->next->next; // Better put NULL
            free(toDelete);
 
            list->length--; // Decrement the length
        }
        else
        {
            puts("WARNING: Cannot delete a node from an empty list... skipping");
        }
    }
}


void list_pop(List *list, unsigned index)
{
    assert(list != NULL);

    // Verify that the passed index is not out of range
    if(!(index < list->length))
    {
        printf("Error: list index %u is out of bounds, passed list is of size %d.\n", index, list->length);
        exit(EXIT_FAILURE);
    }

    if(index == 0)
    {
        list_delete_first(list);
    }
    else
    {
        if(!list_isEmpty(list))
        {
          Node *previousNode = list->first;

          while(index > 1)
          {
              previousNode = previousNode->next;
              index--;
          }

          Node *toDelete = previousNode->next;
          previousNode->next = previousNode->next->next; // Same as previousNode->next = toDelete->next
          free(toDelete);

          list->length--; // Decrement the length
        }
        else
        {
            puts("WARNING: Cannot delete a node from an empty list... skipping");
        }
    }
}
 
 
void list_remove(List *list, int number)
{
    int position = list_index(list, number);
 
    if(position == 0)
    {
        list_delete_first(list);
    }
    else
    {
        Node *previousNode = list->first;
 
        while(position > 1)
        {
            previousNode = previousNode->next;
            position--;
        }
 
        Node *toDelete = previousNode->next;
        previousNode->next = previousNode->next->next; // Same as previousNode->next = toDelete->next
        free(toDelete);
 
        list->length--;
    }
}


void list_clear(List *list)
{
    assert(list != NULL);

    while(list->first != NULL)
    {
        list_delete_first(list);
    }
}


void list_free(List *list)
{
    list_clear(list);
    free(list);
}
 
 
/* Other functions */

void list_print(const List *list)
{
    assert(list != NULL);

    Node *currentNode = list->first;

    while(currentNode != NULL)
    {
        printf("%d -> ", currentNode->number);
        currentNode = currentNode->next;
    }
    puts("NULL");
}

 
int list_count(const List *list, int number)
{
    int count = 0;
 
    if(is_in_list(list, number))
    {
      Node *currentNode = list->first;
 
      // Count number of elements with the specified value
      while(currentNode != NULL)
      {
          if(currentNode->number == number)
              count++;
 
          currentNode = currentNode->next;
      }
    }
 
    return count;
}
 
 
void list_sort(List *list)
{
    if(!list_isEmpty(list))
    {
        Node *currentNode = NULL;
        Node *nextNode = NULL;
 
        for(currentNode = list->first; currentNode != NULL; currentNode = currentNode->next)
        {
            for(nextNode = currentNode->next; nextNode != NULL; nextNode = nextNode->next)
            {
                if(currentNode->number > nextNode->number)
                {
                    int temp = currentNode->number;
                    currentNode->number = nextNode->number;
                    nextNode->number = temp;
                }
            }
        }
    }
}
 
 
void list_reverse(List *list)
{
    if(!list_isEmpty(list))
    {
        int *array = NULL;
        int len = list_length(list), i = 0;
 
        array = malloc(len * sizeof(int));
        if(array == NULL)
        {
            puts("Unable to allocate the memory for the array");
            exit(EXIT_FAILURE);
        }
 
        Node *currentNode = list->first;
 
        // Copy the numbers from the list into the array
        for(currentNode = list->first; currentNode != NULL; currentNode = currentNode->next)
        {
            array[i] = currentNode->number;
            i++;
        }
 
        // Remove all nodes from the list
        list_clear(list);
 
        // Copy the numbers from the array into the list backwards
        for(i = len - 1; i >= 0; i--)
        {
            list_append(list, array[i]);
        }
 
        free(array);
    }
}
 
 
void list_copy(List *list, const List *listToCopy)
{
    if(!list_isEmpty(list))
        list_clear(list);
 
    if(!list_isEmpty(listToCopy))
        list_extend(list, listToCopy);
}
 
 
int list_index(const List *list, int number)
{
    if(!is_in_list(list, number))
    {
        printf("Error: Value %d is not in list\n", number);
        exit(EXIT_FAILURE);
    }
 
    int index = 0;
    Node *currentNode = list->first;
 
    while(currentNode != NULL)
    {
        if(currentNode->number == number)
            break;
 
        currentNode = currentNode->next;
        index++;
    }
 
    return index;
}

# Mon fichier main

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#include "linked_list.h"


int main(int argc, char *argv[])
{
    List *myList = create_list();
    List *otherList = create_list();

    /* Adding nodes */
    list_prepend(myList, 4);
    list_prepend(myList, 8);
    list_prepend(myList, 15);
    list_insert(myList, 12, 0);
    list_append(myList, 27);

    fputs("\nBase list (myList) : ", stdout);
    list_print(myList);

    list_append(otherList, 15);
    fputs("\nBase list (otherList) : ", stdout);
    list_print(otherList);

    list_extend(otherList, myList);
    fputs("\nExtended list (otherList) : ", stdout);
    list_print(otherList);

    list_reverse(otherList);
    fputs("\nReversed list (otherList) : ", stdout);
    list_print(otherList);

    list_sort(otherList);
    fputs("\nSorted list (otherList) : ", stdout);
    list_print(otherList);

    printf("\nThe number 15 appears %d time(s) in otherList.\n", list_count(otherList, 15));
    printf("\nThe number 12 is at index %d in otherList.\n", list_index(otherList, 12));

    list_remove(otherList, 15);
    fputs("\nRemoving first occ of 15 (otherList) : ", stdout);
    list_print(otherList);

    list_clear(otherList);
    fputs("\nCleared list (otherList) : ", stdout);
    list_print(otherList);

    list_copy(otherList, myList);
    fputs("\nCopying myList into otherList (otherList) : ", stdout);
    list_print(otherList);

    list_free(myList);
    list_free(otherList);

    return EXIT_SUCCESS;
}

# Output (Je l'ai un peu agrandi)

-
Edité par ChristianAlbertLamy 20 juin 2022 à 18:30:50

ChristianAlbertLamy a écrit:

NB: Pour éviter de reposter ce que j'avais déjà présenté plus haut, ceci inclut uniquement les nouvelles fonctions.

Tu devrais tirer plus avantage du fait que tu connais la longueur de ta liste pour certaines fonctions.
Ex. le append se fait avec insert_in_list

Pour le tri, tu fais un tri par sélection qui n'est normalement pas efficace.

Mais tu n'échanges que les valeurs sans toucher au chaînage. Je dirais que ça peut être efficace dans les circonstances.
Pour la fonction reverse, tu recopies dans un vecteur et tu les remets dans une autre liste si j'ai bien compris?
Voici ma variante:
 
void reverse(List *list) {
    Node *backward = NULL;
    Node *current = list->first;
    while(current) {
        Node *forward = current->next;
        current->next = backward;
        backward = current;
        current = forward;
    }
    list->first = backward;
}

Dans is_in_list, pas besoin de tester si la liste est vide, tu passeras rapidement à la fin.

D'autres commentaires suivront ...

-
Edité par PierrotLeFou 20 juin 2022 à 19:26:27

ChristianAlbertLamy a écrit:

edit : Corrigé après la remarque de @rouloude

# Aller plus loin

Salut tout le monde !

Pour corser un peu les choses, j'ai décidé de créer quelques fonctions supplémentaires (en m'inspirant du langage python) pour:

• Ajouter un élément à la fin de la liste (list_append)
• Supprimer un élément à la fin de la liste (list_delete_last)

si c'est en s'inspirant de python ça serait peut être bien de tenter de modifier l'implémentation pour qu'elle soit plus efficace sur ces opérations, en ajoutant

• dans la structure "liste", un pointeur vers le dernier noeud. Ce qui permet d'ajouter à la fin sans avoir à parcourir.
• dans la structure "noeud", un pointeur vers le noeud précédent, pour enlever le dernier sans douleur.

Bienvenue chez les listes à double chainage.

PS: les listes de python ne sont pas des listes chaînées, mais des tableaux "extensibles" de taille variable. Ce qui permet l'accès par indice en temps constant.

-
Edité par michelbillaud 20 juin 2022 à 19:26:37